基于蟻群算法的物流車(chē)輛路徑優(yōu)化問(wèn)題的研究

作者：

于芹作者單位：上海交通大學(xué)文獻(xiàn)類(lèi)型：碩士論文基于蟻群算法的物流車(chē)輛路徑優(yōu)化問(wèn)題的研究現(xiàn)在是1頁(yè)\一共有46頁(yè)\編輯于星期一01車(chē)輛路徑規(guī)劃概述03蟻群算法簡(jiǎn)介02VRP問(wèn)題的相關(guān)研究04改進(jìn)的ACO及TSP求解05CVRP問(wèn)題及求解Contents目錄現(xiàn)在是2頁(yè)\一共有46頁(yè)\編輯于星期一1車(chē)輛路徑問(wèn)題概述現(xiàn)在是3頁(yè)\一共有46頁(yè)\編輯于星期一車(chē)輛路徑規(guī)劃概述車(chē)輛路徑調(diào)度問(wèn)題是由GDantzig首先提出的,NChristofides在后來(lái)總結(jié)深化。車(chē)輛路徑問(wèn)題（VRP），主要解決的是派多少輛車(chē)走什么樣的路線進(jìn)行運(yùn)輸?shù)膯?wèn)題。具體來(lái)講，就是給定了相互連通的若干有貨物需求的顧客點(diǎn)，若干車(chē)輛從配送中心出發(fā)，完成對(duì)所有顧客點(diǎn)的配送任務(wù)后回到配送中心，要求所走的路線不能重復(fù)，目的是找到最小成本的配送方案。

現(xiàn)在是4頁(yè)\一共有46頁(yè)\編輯于星期一根據(jù)實(shí)際約束條件的差異，車(chē)輛路徑問(wèn)題種類(lèi)千變?nèi)f化，并各具特色?，F(xiàn)在是5頁(yè)\一共有46頁(yè)\編輯于星期一經(jīng)典車(chē)輛路徑問(wèn)題，其實(shí)就是在車(chē)輛路徑的調(diào)度中，僅僅考慮最基本的貨車(chē)載重量約束(或容量約束)的最一般化的運(yùn)輸問(wèn)題，即有容量約束的車(chē)輛路徑問(wèn)題(CapacitatedVehicleRoutingProblem）。經(jīng)典VRP要求滿足的條件及假設(shè)：

經(jīng)典車(chē)輛路徑問(wèn)題CVRP所有的配送車(chē)輛以配送中心為起點(diǎn)并最終回到配送中心1每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)車(chē)輛的載重量。2每個(gè)需求點(diǎn)的需求由且僅由一輛車(chē)一次送貨滿足3現(xiàn)在是6頁(yè)\一共有46頁(yè)\編輯于星期一CVRP的數(shù)學(xué)模型(1)(2)(3)(4)(5)(6)k：第k輛車(chē)

：運(yùn)輸車(chē)輛的數(shù)量

：車(chē)輛k所走的路徑的集合現(xiàn)在是7頁(yè)\一共有46頁(yè)\編輯于星期一帶時(shí)間窗的車(chē)輛路徑問(wèn)題VRPTW

在很多時(shí)候，會(huì)要求在一定時(shí)間范圍內(nèi)到達(dá)顧客點(diǎn)(當(dāng)然有時(shí)配送中心也有時(shí)間范圍限制)，否則將因停車(chē)等待或配送延遲而產(chǎn)生損失。比較而言，時(shí)間窗VRP除了必須實(shí)現(xiàn)經(jīng)典VRP的要求，還要考慮訪問(wèn)時(shí)間的限制，這樣才能找到合理方案。

軟時(shí)間窗VRP：要求竟可能在時(shí)間窗內(nèi)到達(dá)訪問(wèn)硬時(shí)間窗VRP：必須在時(shí)間窗內(nèi)到達(dá)訪問(wèn)現(xiàn)在是8頁(yè)\一共有46頁(yè)\編輯于星期一VRPTW的數(shù)學(xué)模型現(xiàn)在是9頁(yè)\一共有46頁(yè)\編輯于星期一2VRP問(wèn)題的相關(guān)研究現(xiàn)在是10頁(yè)\一共有46頁(yè)\編輯于星期一對(duì)VRP問(wèn)題的相關(guān)研究求解問(wèn)題的精確算法分支定界法Laporte等人利用VRP和其松弛形式T-VRP之間的關(guān)系,把T-VRP轉(zhuǎn)化成了TSP的分枝定界算法求解了一般問(wèn)題動(dòng)態(tài)規(guī)劃算法將VRP問(wèn)題視為一個(gè)n階段的決策問(wèn)題,進(jìn)而將其轉(zhuǎn)化為依次求解n個(gè)具有遞推關(guān)系的單階段決策問(wèn)題.Eilon通過(guò)遞歸的形式利用動(dòng)態(tài)規(guī)劃法求解具有固定車(chē)輛數(shù)的VRP問(wèn)題三下標(biāo)車(chē)輛流方程由Fisher等人提出,用以求解帶能力約束、時(shí)間窗口以及無(wú)停留時(shí)間的VRP問(wèn)題。在該方程中,兩個(gè)下標(biāo)表示弧或邊,另一個(gè)下標(biāo)表示車(chē)輛的序號(hào)。二下標(biāo)車(chē)輛流方程Laporte提出了用以求解對(duì)稱(chēng)的一般VRP問(wèn)題,結(jié)合了爬山法的思想,核心依然是線性規(guī)劃?，F(xiàn)在是11頁(yè)\一共有46頁(yè)\編輯于星期一求解問(wèn)題的元啟發(fā)式算法禁忌搜索算法由Glover在1986年提出，是一種全局逐步尋優(yōu)算法,此算法采用禁忌搜索表紀(jì)錄已達(dá)到過(guò)的局部最優(yōu)點(diǎn),在下一次搜索中對(duì)于禁忌表中的節(jié)點(diǎn)有選擇或是不再選擇，以此來(lái)避免陷入局部最優(yōu)解。Gendrean最先用此法解決VRP問(wèn)題模擬退火算法解決VRP問(wèn)題時(shí)，將物理退火中原子獲得的能量相當(dāng)于分配最優(yōu)節(jié)點(diǎn)，將原子震動(dòng)模擬為線路尋優(yōu)空間的隨機(jī)搜索。（Laporte和Teodorovic）遺傳算法Berger和Barkaoui（2004）利用并行混合遺傳算法求解帶時(shí)間窗的車(chē)輛路徑問(wèn)題。郎茂祥通過(guò)構(gòu)建單親遺傳算法,有效改進(jìn)了傳統(tǒng)遺傳算法對(duì)復(fù)雜問(wèn)題搜索效率低,易陷入過(guò)早收斂的缺陷。蟻群算法BullnheimerB.等人首先將蟻群算法的思想用于VRP問(wèn)題。BellJohn.E等提出一種改進(jìn)的蟻群算法用來(lái)求解VRP。AlberboV等人改進(jìn)蟻群算法求解TDVRP。劉志碩等人構(gòu)造了求解的自適應(yīng)蟻群算法?，F(xiàn)在是12頁(yè)\一共有46頁(yè)\編輯于星期一3蟻群算法簡(jiǎn)介現(xiàn)在是13頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法簡(jiǎn)史2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改進(jìn)算法的提出，應(yīng)用領(lǐng)域更廣引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為現(xiàn)在是14頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法簡(jiǎn)史蟻群算法（AntAlgorithm)是一種由自然界真實(shí)螞蟻覓食行為提煉而成的優(yōu)化算法，于1991年，由意大利學(xué)者M(jìn)acroDorigo在其博士論文中提出，并成功的解決了旅行商（TSP）問(wèn)題。1996年,MacroDorigo等人在《IEEE系統(tǒng)、人、控制論匯刊》上發(fā)表了”Antsystem:optimizationbyacolonyofcooperatingagents”一文，系統(tǒng)地闡述了蟻群算法的基本原理和數(shù)學(xué)模型，蟻群算法逐漸引起了世界許多國(guó)家研究者的關(guān)注，其應(yīng)用領(lǐng)域也得到了迅速拓寬?，F(xiàn)在是15頁(yè)\一共有46頁(yè)\編輯于星期一1998年10月在比利時(shí)布魯塞爾召開(kāi)了第一屆蟻群算法國(guó)際研討會(huì)（ANTS），標(biāo)志著蟻群算法的正式國(guó)際化。2000年，MarcoDorigo和BonabeauE等人在國(guó)際頂級(jí)學(xué)術(shù)刊物《Nature》上發(fā)表了蟻群算法的研究綜述，從而把這一領(lǐng)域的研究推向了國(guó)際數(shù)學(xué)的最前沿。在我國(guó)，最早關(guān)于蟻群算法的研究見(jiàn)于1997年10月張紀(jì)會(huì)與徐心和發(fā)表的論文“一種新的進(jìn)化算法——蟻群算法”中。蟻群算法簡(jiǎn)史現(xiàn)在是16頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法的研究現(xiàn)狀

目前，人們對(duì)蟻群算法的研究已經(jīng)由當(dāng)初的TSP領(lǐng)域滲透到多個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問(wèn)題發(fā)展到解決多維動(dòng)態(tài)優(yōu)化組合問(wèn)題，由離散域范圍內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究。同時(shí)在蟻群算法的模型改進(jìn)以及其他仿生優(yōu)化算法的融合方面也取得了相當(dāng)豐富的研究成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的生機(jī)。有學(xué)者通過(guò)對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問(wèn)題中，蟻群算法的優(yōu)化性能要好于遺傳算法等算法。蟻群算法是一種基于種群的啟發(fā)式搜索算法。蟻群算法廣泛應(yīng)用于求解TSP問(wèn)題，Job-Shop調(diào)度問(wèn)題，二次指派問(wèn)題，背包問(wèn)題等。

蟻群算法是一種很有發(fā)展前景的優(yōu)化算法現(xiàn)在是17頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法原理現(xiàn)在是18頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法原理螞蟻能快速找到最佳覓食路徑是因?yàn)樵谖浵亗€(gè)體之間是通過(guò)一種稱(chēng)為信息素的物質(zhì)進(jìn)行信息傳遞的。螞蟻在運(yùn)動(dòng)過(guò)程中，不但能夠在它所經(jīng)過(guò)的路徑上留下該物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強(qiáng)度，并朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，以此指導(dǎo)自己的運(yùn)動(dòng)方向。

因此，由大量螞蟻組成的蟻群集體行為表現(xiàn)出一種信息正反饋現(xiàn)象。在一定時(shí)間內(nèi)較短路徑通過(guò)的螞蟻要多于較長(zhǎng)路徑，而某一路徑上走過(guò)的螞蟻越多，則后來(lái)的螞蟻選擇該路徑的概率就越大?，F(xiàn)在是19頁(yè)\一共有46頁(yè)\編輯于星期一下圖是一個(gè)形象化的圖示，用以說(shuō)明蟻群的路徑搜索過(guò)程螞蟻覓食協(xié)作本質(zhì)可概括成如下三點(diǎn)：①路徑概率選擇機(jī)制：信息素蹤跡越濃的路徑，被選中的概率越大；②信息素更新機(jī)制：路徑越短，路徑上的信息素蹤跡增長(zhǎng)得越快；③協(xié)同工作機(jī)制：螞蟻個(gè)體通過(guò)信息素進(jìn)行信息交流。現(xiàn)在是20頁(yè)\一共有46頁(yè)\編輯于星期一螞蟻算法采用人工螞蟻模擬自然界螞蟻的尋徑方式，每個(gè)人工螞蟻的行為符合下列規(guī)律人工螞蟻的尋徑規(guī)律根據(jù)路徑上的信息素濃度，以相應(yīng)的概率來(lái)選取下一步路徑；01不再選取自己本次循環(huán)已經(jīng)走過(guò)的路徑為下一步路徑，用一個(gè)數(shù)據(jù)結(jié)構(gòu)(tabulist)來(lái)控制這一點(diǎn)；02當(dāng)完成了一次循環(huán)后，根據(jù)整個(gè)路徑長(zhǎng)度來(lái)釋放相應(yīng)濃度的信息素，并更新走過(guò)的路徑上的信息素濃度03現(xiàn)在是21頁(yè)\一共有46頁(yè)\編輯于星期一基于TSP的基本蟻群算法的數(shù)學(xué)模型以TSP為例說(shuō)明Dorigo等人提出的螞蟻系統(tǒng)(AntSystem)模型,其目標(biāo)函數(shù)是：模型中會(huì)用到的變量:現(xiàn)在是22頁(yè)\一共有46頁(yè)\編輯于星期一在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率現(xiàn)在是23頁(yè)\一共有46頁(yè)\編輯于星期一為了避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有n個(gè)城市的遍歷（也即一個(gè)循環(huán)結(jié)束）后，要對(duì)殘留信息進(jìn)行更新處理。t+n時(shí)刻在路徑(i,j)上的信息量可按照如下規(guī)則進(jìn)行調(diào)整。ρ表示信息素?fù)]發(fā)系數(shù)，則1-ρ表示信息素殘留因子，為了防止信息的無(wú)限積累，ρ的取值范圍為：ρ含于[0,1)現(xiàn)在是24頁(yè)\一共有46頁(yè)\編輯于星期一根據(jù)信息素更新策略的不同，DorigoM提出了三種不同的基本蟻群算法模型，分別稱(chēng)之為Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型Ant-Cycle模型Ant-Quantity模型Ant-Density模型現(xiàn)在是25頁(yè)\一共有46頁(yè)\編輯于星期一α值的大小表明留在每個(gè)結(jié)點(diǎn)上的信息量受重視的程度，α值越大，螞蟻選擇以前選過(guò)的點(diǎn)的可能性越大，但過(guò)大會(huì)使搜索過(guò)早陷入局部最小點(diǎn)β的大小表明啟發(fā)式信息受重視的程度，β越大，表明選擇路徑時(shí)越依賴(lài)啟發(fā)式信息表示揮發(fā)程度的ρ對(duì)收斂結(jié)果有很大的影響，實(shí)驗(yàn)表明，取值太大或太小，運(yùn)行結(jié)果都不理想，一般取0.5左右Q值會(huì)影響算法的收斂速度，Q過(guò)大會(huì)使算法收斂于局部最小值，過(guò)小又會(huì)影響算法的收斂速度，隨著問(wèn)題規(guī)模的增大Q的值也需隨之變化螞蟻算法中Q、α、β、ρ等參數(shù)對(duì)算法性能有很大影響現(xiàn)在是26頁(yè)\一共有46頁(yè)\編輯于星期一基本蟻群算法的程序結(jié)構(gòu)流程現(xiàn)在是27頁(yè)\一共有46頁(yè)\編輯于星期一4改進(jìn)ACO及TSP求解現(xiàn)在是28頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法的基本步驟：

初始化路徑構(gòu)造信息更新輸出結(jié)果現(xiàn)在是29頁(yè)\一共有46頁(yè)\編輯于星期一基本蟻群算法的改進(jìn)一系列研究結(jié)果發(fā)現(xiàn)，用基本螞蟻算法求解時(shí)容易如下出現(xiàn)兩個(gè)問(wèn)題：

搜索進(jìn)行到一定程度后，所有的個(gè)體發(fā)現(xiàn)的解基木完全一致，出現(xiàn)停滯現(xiàn)象，不能再對(duì)解空間進(jìn)一步搜索，導(dǎo)致可能無(wú)法找到全局最優(yōu)解搜索陷入局部最優(yōu)解收斂到全局最優(yōu)解的時(shí)間長(zhǎng)，求解結(jié)果反復(fù)在局部最優(yōu)解和全局最優(yōu)解之間震蕩。時(shí)間長(zhǎng)現(xiàn)在是30頁(yè)\一共有46頁(yè)\編輯于星期一改進(jìn)算法中位于第i個(gè)結(jié)點(diǎn)的螞蟻k，按以下選擇策略移動(dòng)到結(jié)點(diǎn)j：改進(jìn)算法的轉(zhuǎn)移規(guī)則改進(jìn)的蟻群算法采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并且在搜索過(guò)程中動(dòng)態(tài)調(diào)整確定性選擇的概率?，F(xiàn)在是31頁(yè)\一共有46頁(yè)\編輯于星期一改進(jìn)算法的信息素局部更新規(guī)則其中，γ稱(chēng)為學(xué)習(xí)率，δ稱(chēng)為揮發(fā)因子。通過(guò)引入蒸發(fā)因子，可以做到對(duì)過(guò)去信息的慢慢遺忘，因而能夠強(qiáng)化后來(lái)學(xué)習(xí)得到的知識(shí)，這樣可以使較少的路徑得到更多的訪問(wèn)機(jī)會(huì)，搜索的范圍會(huì)更加廣，增加螞蟻選擇其它邊的概率，防止算法收斂到局部最優(yōu)解，有利于發(fā)現(xiàn)更好解，不致過(guò)早出現(xiàn)停滯現(xiàn)象。局部更新是為了避免所有螞蟻都選擇同一條路徑?，F(xiàn)在是32頁(yè)\一共有46頁(yè)\編輯于星期一改進(jìn)算法的信息素全局更新規(guī)則在改進(jìn)的蟻群算法的迭代過(guò)程中，全局更新原則只對(duì)獲得最短路徑的螞蟻實(shí)施。當(dāng)所有螞蟻均完成一次循環(huán)時(shí)，信息素更新采用如下規(guī)則：現(xiàn)在是33頁(yè)\一共有46頁(yè)\編輯于星期一蟻群算法應(yīng)用實(shí)例以30個(gè)城市TSP問(wèn)題為例，說(shuō)明蟻群算法的應(yīng)用。城市的位置信息如表所示：現(xiàn)在是34頁(yè)\一共有46頁(yè)\編輯于星期一計(jì)算結(jié)果22--21–23--25--30--29--9--24--27–26--1--28--

6--2--3--5--7--8--4--10--12--11--14--18--19--20--16--17--15--13--22現(xiàn)在是35頁(yè)\一共有46頁(yè)\編輯于星期一每次迭代的最短距離與平均距離對(duì)比圖現(xiàn)在是36頁(yè)\一共有46頁(yè)\編輯于星期一結(jié)果對(duì)比原文算法實(shí)現(xiàn)現(xiàn)在是37頁(yè)\一共有46頁(yè)\編輯于星期一5CVRP問(wèn)題及求解現(xiàn)在是38頁(yè)\一共有46頁(yè)\編輯于星期一CVRP問(wèn)題的蟻群算法實(shí)現(xiàn)VRP與TSP蟻群算法的區(qū)別子路徑構(gòu)造過(guò)程的區(qū)別在TSP中，每只螞蟻均要經(jīng)過(guò)所有結(jié)點(diǎn)，而在VRP中，每只螞蟻并不需要遍歷所有結(jié)點(diǎn)。2allowedk的區(qū)別在TSP中，螞蟻轉(zhuǎn)移時(shí)只需考慮路徑的距離和信息濃度即可，但在VRP中，螞蟻轉(zhuǎn)移時(shí)不但要考慮上述因素，還需要考慮車(chē)輛容量的限制。這一差異在算法中的具體體現(xiàn)就是allowedk的確定問(wèn)題。1可行解結(jié)構(gòu)的區(qū)別在求解TSP問(wèn)題中，每只螞蟻所構(gòu)造出來(lái)的路徑均是一個(gè)可行解，但在VRP問(wèn)題中，每只螞蟻所構(gòu)造的回路僅是可行解的“零部件”3現(xiàn)在是39頁(yè)\一共有46頁(yè)\編輯于星期一在VRP問(wèn)題中，每只螞蟻所構(gòu)造的回路僅是可行解的一個(gè)組成部分，各螞蟻所構(gòu)造的回路可能能夠組成一些可行解，但也可能一個(gè)可行解都得不到。避免無(wú)可行解可采取以下策略：大螞蟻數(shù)策略：增加算法的