資源描述：
《基于免疫遺傳算法的車(chē)輛路徑優(yōu)化問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、第29卷第3期2010年9月中南民族大學(xué)學(xué)報(bào)（自然科學(xué)版）JournalofSouth-(^entralLniversityforNationalities(Nat.Sci.Edition)Vol.29No.3Sep.2010基于免疫遺傳算法的車(chē)輛路徑優(yōu)化問(wèn)題程林輝，吳立鋒，張瀟(中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)摘要在研宄免疫遺傳算法基本理論的基礎(chǔ)上，設(shè)計(jì)了一種用于求解車(chē)輛路徑優(yōu)化問(wèn)題的免疫遺傳算法，并進(jìn)行了實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果表明算法具有良好的全局搜索能力，并且能夠有效地克服遺傳算法在進(jìn)化過(guò)程中由于種群多樣性降低而出現(xiàn)早熟收斂現(xiàn)象的缺點(diǎn).關(guān)鍵詞遺傳算法；免疫遺傳算
2、法;車(chē)輛路徑問(wèn)題中圖分類(lèi)號(hào)TP301文獻(xiàn)標(biāo)識(shí)碼A文章編號(hào)1672-4321(2010)03~0089-4VehicleRoutingOptimizationProblemBasedonImmuneGeneticAlgorithmChengLinhui，WuLifeng，ZhangXiao(CollegeofComputerScience，South-CentralUniversityforNationalities，Wuhan430074，China)AbstractThispaperproposedanImmuneGeneticAlgorithmtoVehicleRoutin
3、gProblembystudyingtheoptimizationtheoriesofIGA.ExperimentalresultsverifythegoodglobalsearchcapabilityofIGA.Theyalsoshowthatn;Acaneffectivelyover(mmethedefectsofprematureconvergencecausedbythedecreaseofpopulationdiversityintheprocessofevolutionofgeneticalgorithm.Keywordsgeneticalgorithm；immun
4、egeneticalgorithim；vehideroutingproblem收稿日期2010-)6-30作者簡(jiǎn)介程林輝（1980-，女，碩士，講師，研宄方向：演化計(jì)算，E-mail:clh333@163.com基金項(xiàng)目中南民族大學(xué)自然科學(xué)基金資助項(xiàng)目（YZQ07?6).11問(wèn)題背景及常用算法車(chē)輛路徑問(wèn)題（VehicleRoutingProblem，簡(jiǎn)稱VRP)最早是由著名學(xué)者Dantzig和Ramser于1959年提出的⑴，它一般可描述為:對(duì)于一系列的送貨點(diǎn)和（或)卸貨點(diǎn)，配貨中心組織合理的車(chē)輛行駛路線，使車(chē)輛在滿足一定的約束條件(如貨物的需求量、車(chē)輛的容量限制、貨物的送達(dá)時(shí)
5、間、車(chē)輛的行駛時(shí)間等)下，能夠有序地通過(guò)它們，并達(dá)到一定的目標(biāo)(如費(fèi)用最少、里程最短、使用車(chē)輛盡量少等).目前，VRP問(wèn)題在人們生活的很多方面都己經(jīng)有了廣泛的應(yīng)用，如超級(jí)市場(chǎng)的商品供應(yīng)、工業(yè)產(chǎn)品運(yùn)輸、交通運(yùn)輸路線安排等，并取得了極大的效益.VRP問(wèn)題是一個(gè)典型的組合優(yōu)化類(lèi)問(wèn)題，具有很高的計(jì)算復(fù)雜性，己被證明屬于NP難問(wèn)題，因此自提出以來(lái)就引起了多個(gè)領(lǐng)域的專家學(xué)者們的關(guān)注，并先后涌現(xiàn)出一批用于求解該問(wèn)題的方法，如精確算法、傳統(tǒng)啟發(fā)式算法、智能優(yōu)化算法等.顯然，精確算法與傳統(tǒng)啟發(fā)式算法并不太適合解決復(fù)雜的VRP問(wèn)題，目前，絕大多數(shù)研宄者采用智能優(yōu)化算法，比如遺傳算法⑵、免疫算法1
6、31、免疫遺傳算法[4,5]、蟻群算法[6]、模擬退火算法171等.本文在分析了遺傳算法及免疫算法各自優(yōu)缺點(diǎn)的基礎(chǔ)上，設(shè)計(jì)了求解VRP問(wèn)題的免疫遺傳算法，并進(jìn)行了相關(guān)的程序設(shè)計(jì)，通過(guò)與其它算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較和分析，驗(yàn)證算法的有效性及優(yōu)勢(shì).2VRP問(wèn)題建模VRP問(wèn)題要求任何一輛車(chē)在行駛路徑上所裝載的貨物總量不能超出車(chē)輛的最大負(fù)載限制.假定第3期程林輝，等：基于免疫遺傳算法的車(chē)輛路徑優(yōu)化問(wèn)題93^Drk(i-1)rki+Drknkrk〇)，(5)的免疫遺傳算法的基本步驟如圖1所示.更新抗體群新型智能優(yōu)化算法，它具有良好記憶功能、自我調(diào)lis3i2:1初始抗1體群產(chǎn)生served
7、-所有車(chē)輛都相同，并且載貨能力也相等，求解過(guò)程還必須同時(shí)滿足:所有車(chē)輛均由單一配貨中心出發(fā)，最后再回到原處，且每個(gè)客戶點(diǎn)只被一輛車(chē)訪問(wèn)一次且需求量能被滿足.假設(shè)己知一個(gè)配貨中心(用0表示)和n個(gè)客戶點(diǎn)（1，2,…，n)，每個(gè)客戶點(diǎn)需求量設(shè)為q,(i=1，2,…，n)，客戶點(diǎn)i到j(luò)的距離是Dj(i，j=1，2,…，n)，配貨中心每輛車(chē)的負(fù)載能力均限制為Q，假設(shè)M為實(shí)際所使用的車(chē)輛數(shù)，設(shè)nk為第k(k=1，2,…，M)輛車(chē)所經(jīng)過(guò)的客戶點(diǎn)總數(shù)，用集合{vk.
8、0彡i彡rn}來(lái)表示第k輛車(chē)所經(jīng)過(guò)的各
