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

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

2、方案。 根據(jù)實(shí)踐約束條件的差別，車輛途徑問題種類千變?nèi)f化，并各具特征。經(jīng)典車輛途徑問題，其實(shí)就是在車輛途徑的調(diào)度中，僅僅思索最根本的貨車載分量約束(或容量約束)的最普通化的運(yùn)輸問題，即有容量約束的車輛途徑問題(Capacitated Vehicle Routing Problem。經(jīng)典VRP要求滿足的條件及假設(shè)： 經(jīng)典車輛途徑問題CVRP一切的配送車輛以配送中心為起點(diǎn)并最終回到配送中心1每條配送途徑上各需求點(diǎn)的需求量之和不超越車輛的載分量。2每個需求點(diǎn)的需求由且僅由一輛車一次送貨滿足3CVRP的數(shù)學(xué)模型(1)(2)(3)(4)(5)(6)k：第k輛車 ：運(yùn)輸車輛的數(shù)量 ：車輛k所走的途徑的集合

3、帶時間窗的車輛途徑問題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á)訪問VRPTW 的數(shù)學(xué)模型2VRP問題的相關(guān)研討對VRP問題的相關(guān)研討求解問題的精確算法分支定界法Laporte等人利用VRP和其松弛形式T-VRP之間的關(guān)系,把T-VRP轉(zhuǎn)化成了TSP的分枝定界算法求解了一般問題動態(tài)規(guī)劃算法將VRP問題視為一個n階段的決策問題

4、,進(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ī)劃。求解問題的元啟發(fā)式算法禁忌搜索算法由Glover在1986年提出，是一種全局逐步尋優(yōu)算法,此算法采用禁忌搜索表紀(jì)錄已達(dá)到過的局部最優(yōu)點(diǎn),在下一次搜索中對于禁忌表中的節(jié)點(diǎn)有選擇或是不再選擇，以此來避免陷入局部最優(yōu)解。

5、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ù)雜問題搜索效率低,易陷入過早收斂的缺陷。蟻群算法Bullnheimer B.等人首先將蟻群算法的思想用于VRP問題。Bell John.E等提出一種改進(jìn)的蟻群算法用來求解VRP。Alberbo V等人改進(jìn)蟻群算法求解TDVRP。劉志碩等人構(gòu)造了求解的自

6、適應(yīng)蟻群算法。3蟻群算法簡介蟻群算法簡史2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各種改良算法的提出，運(yùn)用領(lǐng)域更廣 引起學(xué)者關(guān)注，在運(yùn)用領(lǐng)域得到拓寬ACO初次被系統(tǒng)的提出自然界中真實(shí)蟻群集體行為蟻群算法簡史蟻群算法Ant Algorithm)是一種由自然界真實(shí)螞蟻尋食行為提煉而成的優(yōu)化算法，于1991年，由意大利學(xué)者M(jìn)acro Dorigo在其博士論文中提出，并勝利的處理了游覽商TSP問題。1996年,Macro Dorigo等人在上發(fā)表了Ant system:optimization by a colony of cooperating agents一文，系統(tǒng)地

7、論述了蟻群算法的根本原理和數(shù)學(xué)模型，蟻群算法逐漸引起了世界許多國家研討者的關(guān)注，其運(yùn)用領(lǐng)域也得到了迅速拓寬。1998年10月在比利時布魯塞爾召開了第一屆蟻群算法國際研討會ANTS，標(biāo)志著蟻群算法的正式國際化。2000年，Marco Dorigo和Bonabeau E等人在國際頂級學(xué)術(shù)刊物上發(fā)表了蟻群算法的研討綜述，從而把這一領(lǐng)域的研討推向了國際數(shù)學(xué)的最前沿。在我國，最早關(guān)于蟻群算法的研討見于1997年10月張紀(jì)會與徐心和發(fā)表的論文“一種新的進(jìn)化算法蟻群算法中。蟻群算法簡史蟻群算法的研討現(xiàn)狀 目前，人們對蟻群算法的研討曾經(jīng)由當(dāng)初的TSP領(lǐng)域浸透到多個運(yùn)用領(lǐng)域，由處理一維靜態(tài)優(yōu)化問題開展到處理多維

8、動態(tài)優(yōu)化組合問題，由離散域范圍內(nèi)研討逐漸拓展到了延續(xù)域范圍內(nèi)研討。同時在蟻群算法的模型改良以及其他仿生優(yōu)化算法的交融方面也獲得了相當(dāng)豐富的研討成果，從而使這種新興的仿生優(yōu)化算法展現(xiàn)出前所未有的活力。有學(xué)者經(jīng)過對比實(shí)驗(yàn)發(fā)現(xiàn)，在組合優(yōu)化問題中，蟻群算法的優(yōu)化性能要好于遺傳算法等算法。蟻群算法是一種基于種群的啟發(fā)式搜索算法 。蟻群算法廣泛運(yùn)用于求解TSP問題，Job-Shop調(diào)度問題，二次指派問題，背包問題等。 蟻群算法 是一種很有開展前景的優(yōu)化算法 蟻群算法原理蟻群算法原理 螞蟻能快速找到最正確尋食途徑是由于在螞蟻個體之間是經(jīng)過一種稱為信息素的物質(zhì)進(jìn)展信息傳送的。螞蟻在運(yùn)動過程中，不但可以在它所經(jīng)

9、過的途徑上留下該物質(zhì)，而且可以感知這種物質(zhì)的存在及其強(qiáng)度，并朝著該物質(zhì)強(qiáng)度高的方向挪動，以此指點(diǎn)本人的運(yùn)動方向。 因此，由大量螞蟻組成的蟻群集體行為表現(xiàn)出一種信息正反響景象。在一定時間內(nèi)較短途徑經(jīng)過的螞蟻要多于較長途徑，而某一途徑上走過的螞蟻越多，那么后來的螞蟻選擇該途徑的概率就越大。以下圖是一個籠統(tǒng)化的圖示，用以闡明蟻群的途徑搜索過程螞蟻尋食協(xié)作本質(zhì)可概括成如下三點(diǎn)： 途徑概率選擇機(jī)制：信息素蹤跡越濃的途徑，被選中的概率越大； 信息素更新機(jī)制：途徑越短，途徑上的信息素蹤跡增長得越快； 協(xié)同任務(wù)機(jī)制：螞蟻個體經(jīng)過信息素進(jìn)展信息交流。螞蟻算法采用人工螞蟻模擬自然界螞蟻的尋徑方式，每個人工螞蟻的行

10、為符合以下規(guī)律人工螞蟻的尋徑規(guī)律根據(jù)途徑上的信息素濃度，以相應(yīng)的概率來選取下一步途徑； 01不再選取本人本次循環(huán)曾經(jīng)走過的途徑為下一步途徑，用一個數(shù)據(jù)構(gòu)造( tabu list )來控制這一點(diǎn)；02當(dāng)完成了一次循環(huán)后，根據(jù)整個途徑長度來釋放相應(yīng)濃度的信息素，并更新走過的途徑上的信息素濃度03基于TSP的根本蟻群算法的數(shù)學(xué)模型以TSP為例闡明 Dorigo等人提出的螞蟻系統(tǒng)(Ant System)模型,其目的函數(shù)是：模型中會用到的變量:在 t 時辰螞蟻 k 由城市 i 轉(zhuǎn)移到城市 j的形狀轉(zhuǎn)移概率 為了防止殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪σ磺衝個城市的遍歷也即

11、一個循環(huán)終了后，要對殘留信息進(jìn)展更新處置。t+n時辰在途徑(i, j)上的信息量可按照如下規(guī)那么進(jìn)展調(diào)整。 表示信息素?fù)]發(fā)系數(shù)，那么1-表示信息素殘留因子，為了防止信息的無限積累， 的取值范圍為： 含于0,1) 根據(jù)信息素更新戰(zhàn)略的不同，Dorigo M 提出了三種不同的根本蟻群算法模型，分別稱之為Ant-Cycle 模型、Ant-Quantity 模型及Ant-Density模型Ant-Cycle 模型Ant-Quantity模型Ant-Density模型 值的大小闡明留在每個結(jié)點(diǎn)上的信息量受注重的程度， 值越大，螞蟻選擇以前選過的點(diǎn)的能夠性越大，但過大會使搜索過早墮入部分最小點(diǎn) 的大小闡明

12、啟發(fā)式信息受注重的程度， 越大，闡明選擇途徑時越依賴啟發(fā)式信息表示揮發(fā)程度的 對收斂結(jié)果有很大的影響，實(shí)驗(yàn)闡明，取值太大或太小，運(yùn)轉(zhuǎn)結(jié)果都不理想，普通取0.5左右Q值會影響算法的收斂速度，Q過大會使算法收斂于部分最小值，過小又會影響算法的收斂速度，隨著問題規(guī)模的增大Q的值也需隨之變化螞蟻算法中 Q 、 、 、 等參數(shù)對算法性能有很大影響根本蟻群算法的程序構(gòu)造流程4改良ACO及TSP求解蟻群算法的根本步驟： 根本蟻群算法的改良 一系列研討結(jié)果發(fā)現(xiàn)，用根本螞蟻算法求解時容易如下出現(xiàn)兩個問題： 搜索進(jìn)展到一定程度后，一切的個體發(fā)現(xiàn)的解基木完全一致，出現(xiàn)停滯景象，不能再對解空間進(jìn)一步搜索，導(dǎo)致能夠無法

13、找到全局最優(yōu)解搜索墮入部分最優(yōu)解收斂到全局最優(yōu)解的時間長，求解結(jié)果反復(fù)在部分最優(yōu)解和全局最優(yōu)解之間震蕩。時間長 改良算法中位于第i個結(jié)點(diǎn)的螞蟻k，按以下選擇戰(zhàn)略挪動到結(jié)點(diǎn) j：改良算法的轉(zhuǎn)移規(guī)那么 改良的蟻群算法采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇戰(zhàn)略，并且在搜索過程中動態(tài)調(diào)整確定性選擇的概率。改良算法的信息素部分更新規(guī)那么 其中， 稱為學(xué)習(xí)率， 稱為揮發(fā)因子。經(jīng)過引入蒸發(fā)因子，可以做到對過去信息的漸漸遺忘，因此可以強(qiáng)化后來學(xué)習(xí)得到的知識，這樣可以使較少的途徑得到更多的訪問時機(jī)，搜索的范圍會更加廣，添加螞蟻選擇其它邊的概率，防止算法收斂到部分最優(yōu)解，有利于發(fā)現(xiàn)更好解，不致過早出現(xiàn)停滯景象。部分

14、更新是為了防止一切螞蟻都選擇同一條途徑。改良算法的信息素全局更新規(guī)那么 在改良的蟻群算法的迭代過程中，全局更新原那么只對獲得最短途徑的螞蟻實(shí)施。當(dāng)一切螞蟻均完成一次循環(huán)時，信息素更新采用如下規(guī)那么：蟻群算法運(yùn)用實(shí)例 以30個城市TSP問題為例，闡明蟻群算法的運(yùn)用。城市的位置信息如表所示： 計(jì)算結(jié)果22- 2123- 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每次迭代的最短間隔與平均間隔對比圖結(jié)果對比原文算法實(shí)現(xiàn)5CVRP問題及求解CV

15、RP 問題的蟻群算法實(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)移時不但要思索上述要素，還需求思索車輛容量的限制。 這一差別在算法中的詳細(xì)表達(dá)就是allowedk 確實(shí)定問題。1可行解構(gòu)造的區(qū)別 在求解TSP問題中，每只螞蟻所構(gòu)造出來的途徑均是一個可行解，但在VRP問題中，每只螞蟻所構(gòu)造的回路僅是可行解的“零部件3 在VRP 問題中，每只螞蟻所構(gòu)造的回路僅是可行解的一個組成部分，各螞蟻所構(gòu)造的回路能夠可以組成一些可行解，但也能夠一個可行解都得不到。防止無可行解 可采取以下戰(zhàn)略：大螞蟻數(shù)戰(zhàn)略：添加算法的螞蟻數(shù)量M ，擴(kuò)展組合范圍，從而添加可行解產(chǎn)生的能夠性。 螞蟻初始分布均勻戰(zhàn)略：在每次迭代前，將螞蟻隨機(jī)均勻分布于各個結(jié)點(diǎn)，從而添加發(fā)現(xiàn)可行解的時機(jī)。近似解可行化戰(zhàn)略：前兩種戰(zhàn)略的目的都是為了提高各螞蟻所構(gòu)造的子回路組合成可行解的能夠性，是一些針對無可行解的“事前預(yù)防性措施。防止無可行解的戰(zhàn)略CVRP實(shí)例仿真 下面經(jīng)過一個實(shí)例，進(jìn)展仿真實(shí)驗(yàn)，檢驗(yàn)上述算法的有效性及詳細(xì)性能。 結(jié)點(diǎn)數(shù)據(jù)如下：假設(shè)共有19個客戶隨機(jī)分布，配送中心位