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

作者：

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

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

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

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

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

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

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

目前，人們對蟻群算法的研究已經(jīng)由當(dāng)初的TSP領(lǐng)域滲透到多個(gè)應(yīng)用領(lǐng)域，由解決一維靜態(tài)優(yōu)化問題發(fā)展到解決多維動(dòng)態(tài)優(yōu)化組合問題，由離散域范圍內(nèi)研究逐漸拓展到了連續(xù)域范圍內(nèi)研究。同時(shí)在蟻群算法的模型改進(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)化算法現(xiàn)在是17頁\一共有46頁\編輯于星期一蟻群算法原理現(xiàn)在是18頁\一共有46頁\編輯于星期一蟻群算法原理螞蟻能快速找到最佳覓食路徑是因?yàn)樵谖浵亗€(gè)體之間是通過一種稱為信息素的物質(zhì)進(jìn)行信息傳遞的。螞蟻在運(yùn)動(dòng)過程中，不但能夠在它所經(jīng)過的路徑上留下該物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強(qiáng)度，并朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)，以此指導(dǎo)自己的運(yùn)動(dòng)方向。

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

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

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