資源描述：
《求解車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、ComputerEngineeringandApplications計(jì)算機(jī)工程與應(yīng)用2010，46（36）219?工程與應(yīng)用?求解車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法程林輝，王江晴CHENGLin-hui，WANGJiang-qing中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074CollegeofComputerScience，South-CentralUniversityforNationalities，Wuhan430074，ChinaE-mail：clh333@163.comCHENGLin-hui，WANGJi
2、ang-qing.Improvedgeneticalgorithmforvehicleroutingproblem.ComputerEngineeringandApplications，2010，46（36）：219-221.Abstract：Vehicleroutingproblemisatypicalcombinationaloptimizationproblem.GeneticalgorithmisoneofthemethodsusedtosolveVRP.Aimingatthedefectsofpr
3、ematureconvergenceintheevolutionprocessofgeneticalgorithm，thisthesisdesignsanimprovedgeneticalgorithm，referringtheadvantagesofimmunealgorithmwhichusesantibodyconcentrationre-strictiontokeeppopulationdiversityandtheindividualchoiceapproachofsimulatedanneali
4、ngalgorithm.Theimprovedge-neticalgorithmisusedtosolveVRPinthethesis.Someexperimentdataprovetheeffectivenessofthealgorithmandauthen-ticatethesearchefficiencyandsolutionqualityofthealgorithm.Keywords：geneticalgorithm；vehicleroutingproblem；combinationaloptimi
5、zation摘要：車(chē)輛路徑問(wèn)題是一個(gè)典型的組合優(yōu)化類問(wèn)題，遺傳算法是求解此類問(wèn)題的方法之一。針對(duì)遺傳算法容易出現(xiàn)“早熟”現(xiàn)象的問(wèn)題，借鑒免疫算法通過(guò)抗體濃度抑制以保持種群多樣性的優(yōu)勢(shì)以及模擬退火算法的個(gè)體選擇策略，提出了一種改進(jìn)的遺傳算法，并將其用于解決車(chē)輛路徑問(wèn)題。實(shí)驗(yàn)驗(yàn)證了算法的有效性以及求解的效率和解的質(zhì)量。關(guān)鍵詞：遺傳算法；車(chē)輛路徑問(wèn)題；組合優(yōu)化DOI：10.3778/j.issn.1002-8331.2010.36.061文章編號(hào)：1002-8331（2010）36-0219-03文獻(xiàn)標(biāo)識(shí)碼：Ａ中
6、圖分類號(hào)：TP3011引言習(xí)性等智能特性，可用于解決組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控車(chē)輛路徑問(wèn)題（VehicleRoutingProblem，VRP）[1]是一個(gè)制等智能問(wèn)題。經(jīng)典的組合優(yōu)化問(wèn)題，最早由著名學(xué)者Dantzig和Ramser于在研究遺傳算法的基本思想和優(yōu)化原理的基礎(chǔ)上，為更1959年提出。由于該問(wèn)題將理論研究和實(shí)際應(yīng)用緊密地聯(lián)系好地求出滿足問(wèn)題各個(gè)約束條件的解、提高解的質(zhì)量和算法在一起，自提出以來(lái)就引起了包括計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、組合的收斂速度，借鑒免疫算法中抗體濃度抑制的思想以及模擬數(shù)學(xué)等多個(gè)學(xué)科
7、專家學(xué)者的高度重視。到目前為止，用于求退火算法的個(gè)體選擇策略，針對(duì)VRP問(wèn)題提出了一種改進(jìn)的解車(chē)輛路徑問(wèn)題的方法已可劃分為三類，即精確優(yōu)化方法、傳遺傳算法，并進(jìn)行了相關(guān)的程序設(shè)計(jì)和實(shí)驗(yàn)驗(yàn)證。統(tǒng)啟發(fā)式方法、智能優(yōu)化算法。目前，國(guó)內(nèi)外的研究者基本都集中在對(duì)智能優(yōu)化算法的研究上[2-6]。隨著國(guó)內(nèi)外研究人員的2VRP問(wèn)題建模共同努力，求解VRP問(wèn)題的智能優(yōu)化算法在理論研究方面逐VRP問(wèn)題一般定義為：對(duì)于一系列的客戶點(diǎn)，組織合理的漸取得了一定的進(jìn)展，但這些智能算法在求解時(shí)間和解的質(zhì)車(chē)輛行駛路線，使車(chē)輛在滿足一定的約
8、束條件（如貨物的需求量上都還需要做進(jìn)一步的改進(jìn)和完善。量、車(chē)輛的容量限制、貨物的送達(dá)時(shí)間、車(chē)輛的行駛時(shí)間等）遺傳算法（GeneticAlgorithm，GA）是智能優(yōu)化算法的一下，能夠有序地通過(guò)它們，并達(dá)到一定的目標(biāo)（如里程最短、費(fèi)種，它是基于自然選擇和遺傳變異等生物進(jìn)化機(jī)制而發(fā)展起用最少、使用車(chē)輛盡量少等）。來(lái)的高度并行、隨機(jī)、自適應(yīng)的全局性概率搜索算法。作為一主要研究的是容量受限的VRP問(wèn)題（Capacita
