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

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

2、所走的路線不能重復(fù)，目的是找到最小成本的配送方案。,根據(jù)實(shí)際約束條件的差異，車輛路徑問題種類千變?nèi)f化，并各具特色。,經(jīng)典車輛路徑問題，其實(shí)就是在車輛路徑的調(diào)度中，僅僅考慮最基本的貨車載重量約束(或容量約束)的最一般化的運(yùn)輸問題，即有容量約束的車輛路徑問題(Capacitated Vehicle Routing Problem）。 經(jīng)典VRP要求滿足的條件及假設(shè)：,經(jīng)典車輛路徑問題CVRP,CVRP的數(shù)學(xué)模型,k：第k輛車 ：運(yùn)輸車輛的數(shù)量 ：車輛k所走的路徑的集合,帶時間窗的車輛路徑問題VRPTW,在很多時候，會要求在一定時間范圍內(nèi)到達(dá)顧客點(diǎn)(當(dāng)然有時配送中心也有時間范圍限制)，否則將因停車等

3、待或配送延遲而產(chǎn)生損失。比較而言，時間窗VRP除了必須實(shí)現(xiàn)經(jīng)典 VRP 的要求，還要考慮訪問時間的限制，這樣才能找到合理方案。,VRPTW 的數(shù)學(xué)模型,2,VRP問題的相關(guān)研究,對VRP問題的相關(guān)研究,3,蟻群算法簡介,蟻群算法簡史,2001年至今,1996年-2001年,意大利學(xué)者 Dorigo1991年,啟發(fā),蟻群算法簡史,蟻群算法（Ant Algorithm)是一種由自然界真實(shí)螞蟻覓食行為提煉而成的優(yōu)化算法，于1991年，由意大利學(xué)者M(jìn)acro Dorigo在其博士論文中提出，并成功的解決了旅行商（TSP）問題。 1996年,Macro Dorigo等人在IEEE系統(tǒng)、人、控制論匯刊上發(fā)

4、表了”Ant system:optimization by a colony of cooperating agents”一文，系統(tǒng)地闡述了蟻群算法的基本原理和數(shù)學(xué)模型，蟻群算法逐漸引起了世界許多國家研究者的關(guān)注，其應(yīng)用領(lǐng)域也得到了迅速拓寬。,1998年10月在比利時布魯塞爾召開了第一屆蟻群算法國際研討會（ANTS），標(biāo)志著蟻群算法的正式國際化。 2000年，Marco Dorigo和Bonabeau E等人在國際頂級學(xué)術(shù)刊物Nature上發(fā)表了蟻群算法的研究綜述，從而把這一領(lǐng)域的研究推向了國際數(shù)學(xué)的最前沿。 在我國，最早關(guān)于蟻群算法的研究見于1997年10月張紀(jì)會與徐心和發(fā)表的論文“一種新的

5、進(jìn)化算法蟻群算法”中。,蟻群算法簡史,蟻群算法的研究現(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ā)展

6、 前景的優(yōu)化算法,蟻群算法原理,蟻群算法原理,螞蟻能快速找到最佳覓食路徑是因?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)較短路徑通過的螞蟻要多于較長路徑，而某一路徑上走過的螞蟻越多，則后來的螞蟻選擇該路徑的概率就越大。,下圖是一個形象化的圖示，用以說明蟻群的路徑搜索過程,螞蟻覓食協(xié)作本質(zhì)可概括成如下三點(diǎn)： 路徑概率選擇機(jī)制：信息素蹤跡越濃的路徑，被選中的概率越大；

7、 信息素更新機(jī)制：路徑越短，路徑上的信息素蹤跡增長得越快； 協(xié)同工作機(jī)制：螞蟻個體通過信息素進(jìn)行信息交流。,螞蟻算法采用人工螞蟻模擬自然界螞蟻的尋徑方式，每個人工螞蟻的行為符合下列規(guī)律,基于TSP的基本蟻群算法的數(shù)學(xué)模型,以TSP為例說明 Dorigo等人提出的螞蟻系統(tǒng)(Ant System)模型,其目標(biāo)函數(shù)是：,模型中會用到的變量:,在 t 時刻螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j的狀態(tài)轉(zhuǎn)移概率,為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪λ衝個城市的遍歷（也即一個循環(huán)結(jié)束）后，要對殘留信息進(jìn)行更新處理。t+n時刻在路徑(i, j)上的信息量可按照如下規(guī)則進(jìn)

8、行調(diào)整。, 表示信息素?fù)]發(fā)系數(shù)，則1-表示信息素殘留因子，為了防止信息的無限積累， 的取值范圍為： 含于0,1),根據(jù)信息素更新策略的不同，Dorigo M 提出了三種不同的基本蟻群算法模型，分別稱之為Ant-Cycle 模型、Ant-Quantity 模型及Ant-Density模型, 值的大小表明留在每個結(jié)點(diǎn)上的信息量受重視的程度， 值越大，螞蟻選擇以前選過的點(diǎn)的可能性越大，但過大會使搜索過早陷入局部最小點(diǎn), 的大小表明啟發(fā)式信息受重視的程度， 越大，表明選擇路徑時越依賴啟發(fā)式信息,表示揮發(fā)程度的 對收斂結(jié)果有很大的影響，實(shí)驗(yàn)表明，取值太大或太小，運(yùn)行結(jié)果都不理想，一般取0.5左右,Q值會

9、影響算法的收斂速度，Q過大會使算法收斂于局部最小值，過小又會影響算法的收斂速度，隨著問題規(guī)模的增大Q的值也需隨之變化,螞蟻算法中 Q 、 、 、 等參數(shù)對算法性能有很大影響,基本蟻群算法的程序結(jié)構(gòu)流程,4,改進(jìn)ACO及TSP求解,蟻群算法的基本步驟：,基本蟻群算法的改進(jìn),一系列研究結(jié)果發(fā)現(xiàn)，用基本螞蟻算法求解時容易如下出現(xiàn)兩個問題：,改進(jìn)算法中位于第i個結(jié)點(diǎn)的螞蟻k，按以下選擇策略移動到結(jié)點(diǎn) j：,改進(jìn)算法的轉(zhuǎn)移規(guī)則,改進(jìn)的蟻群算法采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略，并且在搜索過程中動態(tài)調(diào)整確定性選擇的概率。,改進(jìn)算法的信息素局部更新規(guī)則,其中， 稱為學(xué)習(xí)率， 稱為揮發(fā)因子。通過引入蒸發(fā)

10、因子，可以做到對過去信息的慢慢遺忘，因而能夠強(qiáng)化后來學(xué)習(xí)得到的知識，這樣可以使較少的路徑得到更多的訪問機(jī)會，搜索的范圍會更加廣，增加螞蟻選擇其它邊的概率，防止算法收斂到局部最優(yōu)解，有利于發(fā)現(xiàn)更好解，不致過早出現(xiàn)停滯現(xiàn)象。,局部更新是為了避免所有螞蟻都選擇同一條路徑。,改進(jìn)算法的信息素全局更新規(guī)則,在改進(jìn)的蟻群算法的迭代過程中，全局更新原則只對獲得最短路徑的螞蟻實(shí)施。當(dāng)所有螞蟻均完成一次循環(huán)時，信息素更新采用如下規(guī)則：,蟻群算法應(yīng)用實(shí)例,以30個城市TSP問題為例，說明蟻群算法的應(yīng)用。城市的位置信息如表所示：,計算結(jié)果,22- 2123- 25- 30- 29- 9-24- 27 26- 1-

11、28- 6 - 2 - 3-5- 7 - 8 - 4- 10- 12- 11- 14- 18- 19- 20- 16- 17- 15- 13- 22,每次迭代的最短距離與平均距離對比圖,結(jié)果對比,原文,算法實(shí)現(xiàn),5,CVRP問題及求解,CVRP 問題的蟻群算法實(shí)現(xiàn),在VRP 問題中，每只螞蟻所構(gòu)造的回路僅是可行解的一個組成部分，各螞蟻所構(gòu)造的回路可能能夠組成一些可行解，但也可能一個可行解都得不到。避免無可行解 可采取以下策略：,大螞蟻數(shù)策略：增加算法的螞蟻數(shù)量M ，擴(kuò)大組合范圍，從而增加可行解產(chǎn)生的可能性。 螞蟻初始分布均勻策略：在每次迭代前，將螞蟻隨機(jī)均勻分布于各個結(jié)點(diǎn)，從而增加發(fā)現(xiàn)可行解的機(jī)會。 近似解可行化策略：前兩種策略的目的都是為了提高各螞蟻所構(gòu)造的子回路組合成可行解的可能性，是一些針對無可行解的“事前”預(yù)防性措施。,避免無可行解的策略,CVRP實(shí)例仿真,下面通過一個實(shí)例，進(jìn)行仿真試驗(yàn)，檢驗(yàn)上述算法的有效性及具體性能。 結(jié)點(diǎn)數(shù)據(jù)如下：假設(shè)共有19個客戶隨機(jī)分布，配送中心位于坐標(biāo)點(diǎn)(0,0)，每個客戶的需求量由計算機(jī)隨機(jī)產(chǎn)生，車輛限載9t，試驗(yàn)數(shù)據(jù)如下表所示。,運(yùn)行過程界面,一次仿真運(yùn)行的結(jié)果,原文結(jié)果,多配送中心的車輛路徑