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

作者：

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

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

經(jīng)典車輛路徑問題CVRP所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心1每條配送路徑上各需求點(diǎn)的需求量之和不超過車輛的載重量。2每個需求點(diǎn)的需求由且僅由一輛車一次送貨滿足3當(dāng)前6頁，總共46頁。CVRP的數(shù)學(xué)模型(1)(2)(3)(4)(5)(6)k：第k輛車

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

：車輛k所走的路徑的集合當(dāng)前7頁，總共46頁。帶時間窗的車輛路徑問題VRPTW

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

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

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

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

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

初始化路徑構(gòu)造信息更新輸出結(jié)果當(dāng)前29頁，總共46頁?；鞠伻核惴ǖ母倪M(jìn)一系列研究結(jié)果發(fā)現(xiàn)，用基本螞蟻算法求解時容易如下出現(xiàn)兩個問題：

搜索進(jìn)行到一定程度后，所有的個體發(fā)現(xiàn)的解基木完全一致，出現(xiàn)停滯現(xiàn)象，不能再對解空間進(jìn)一步搜索，導(dǎo)致可能無法找到全局最優(yōu)解搜索陷入局部最優(yōu)解收斂到全局最優(yōu)解的時間長，求解結(jié)果反復(fù)在局部最優(yōu)解和全局最優(yōu)解之間震蕩。時間長當(dāng)前30頁，總共46頁。改進(jìn)算法中位于第i個結(jié)點(diǎn)的螞蟻k，按以下選擇策略移動到結(jié)點(diǎn)j：改進(jìn)算法的轉(zhuǎn)移規(guī)則改進(jìn)的蟻群算法采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并且在搜索過程中動態(tài)調(diào)整確定性選擇的概率。當(dāng)前31頁，總共46頁。改進(jìn)算法的信息素局部更新規(guī)則其中，γ稱為學(xué)習(xí)率，δ稱為揮發(fā)因子。通過引入蒸發(fā)因子，可以做到對過去信息的慢慢遺忘，因而能夠強(qiáng)化后來學(xué)習(xí)得到的知識，這樣可以使較少的路徑得到更多的訪問機(jī)會，搜索的范圍會更加廣，增加螞蟻選擇其它邊的概率，防止算法收斂到局部最優(yōu)解，有利于發(fā)現(xiàn)更好解，不致過早出現(xiàn)停滯現(xiàn)象。局部更新是為了避免所有螞蟻都選擇同一條路徑。當(dāng)前32頁，總共46頁。改進(jìn)算法的信息素全局更新規(guī)則在改進(jìn)的蟻群算法的迭代過程中，全局更新原則只對獲得最短路徑的螞蟻實(shí)施。當(dāng)所有螞蟻均完成一次循環(huán)時，信息素更新采用如下規(guī)則：當(dāng)前33頁，總共46頁。蟻群算法應(yīng)用實(shí)例以30個城市TSP問題為例，說明蟻群算法的應(yīng)用。城市的位置信息如表所示：當(dāng)前34頁，總共46頁。計(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當(dāng)前35頁，總共46頁。每次迭代的最短距離與平均距離對比圖當(dāng)前36頁，總共46頁。結(jié)果對比原文算法實(shí)現(xiàn)當(dāng)前37頁，總共46頁。5CVRP問題及求解當(dāng)前38頁，總共46頁。CVRP問題的蟻群算法實(shí)現(xiàn)VRP與TSP蟻群算法的區(qū)別子路徑構(gòu)造過程的區(qū)別在TSP中，每只螞蟻均要經(jīng)過所有結(jié)點(diǎn)，而在VRP中，每只螞蟻并不需要遍歷所有結(jié)點(diǎn)。2allowedk的區(qū)別在TSP中，螞蟻轉(zhuǎn)移時只需考慮路徑的距離和信息濃度即可，但在VRP中，螞蟻轉(zhuǎn)移時不但要考慮上述因素，還需要考慮車輛容量的限制。這一差異在算法中的具體體現(xiàn)就是allowedk的確定問題。1可行解結(jié)構(gòu)的區(qū)別在求解TSP問題中，每只螞蟻所構(gòu)造出來的路徑均是一個可行解，但在VRP問題中，每只螞蟻所構(gòu)造的回路僅是可行解的“零部件”3當(dāng)前39頁，總共46頁。在VRP問題中，每只螞蟻所構(gòu)造的回路僅是可行解的一個組成部分，各螞蟻所構(gòu)造的回路可能能夠組成一些可行解，但也可能一個可行解都得不到。避免無可行解可