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

作者：

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

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

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

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

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

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

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

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

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

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

初始化路徑構造信息更新輸出結果當前29頁，總共46頁。基本蟻群算法的改進一系列研究結果發(fā)現(xiàn)，用基本螞蟻算法求解時容易如下出現(xiàn)兩個問題：

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