資源描述：
《基于蟻群算法的物流車輛路徑優(yōu)化問題的研究.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、作者：于芹作者單位：上海交通大學(xué)文獻類型：碩士論文基于蟻群算法的物流車輛路徑優(yōu)化問題的研究01車輛路徑規(guī)劃概述03蟻群算法簡介02VRP問題的相關(guān)研究04改進的ACO及TSP求解05CVRP問題及求解Contents目錄1車輛路徑問題概述車輛路徑規(guī)劃概述車輛路徑調(diào)度問題是由GDantzig首先提出的,NChristofides在后來總結(jié)深化。車輛路徑問題（VRP），主要解決的是派多少輛車走什么樣的路線進行運輸?shù)膯栴}。具體來講，就是給定了相互連通的若干有貨物需求的顧客點，若干車輛從配送中心出發(fā)，完成對所有顧客
2、點的配送任務(wù)后回到配送中心，要求所走的路線不能重復(fù)，目的是找到最小成本的配送方案。根據(jù)實際約束條件的差異，車輛路徑問題種類千變?nèi)f化，并各具特色。經(jīng)典車輛路徑問題，其實就是在車輛路徑的調(diào)度中，僅僅考慮最基本的貨車載重量約束(或容量約束)的最一般化的運輸問題，即有容量約束的車輛路徑問題(CapacitatedVehicleRoutingProblem）。經(jīng)典VRP要求滿足的條件及假設(shè)：經(jīng)典車輛路徑問題CVRP所有的配送車輛以配送中心為起點并最終回到配送中心1每條配送路徑上各需求點的需求量之和不超過車輛的載重量。
3、2每個需求點的需求由且僅由一輛車一次送貨滿足3CVRP的數(shù)學(xué)模型(1)(2)(3)(4)(5)(6)k：第k輛車：運輸車輛的數(shù)量：車輛k所走的路徑的集合帶時間窗的車輛路徑問題VRPTW在很多時候，會要求在一定時間范圍內(nèi)到達顧客點(當(dāng)然有時配送中心也有時間范圍限制)，否則將因停車等待或配送延遲而產(chǎn)生損失。比較而言，時間窗VRP除了必須實現(xiàn)經(jīng)典VRP的要求，還要考慮訪問時間的限制，這樣才能找到合理方案。軟時間窗VRP：要求竟可能在時間窗內(nèi)到達訪問硬時間窗VRP：必須在時間窗內(nèi)到達訪問VRPTW的數(shù)學(xué)模型2VRP
4、問題的相關(guān)研究對VRP問題的相關(guān)研究求解問題的精確算法分支定界法Laporte等人利用VRP和其松弛形式T-VRP之間的關(guān)系,把T-VRP轉(zhuǎn)化成了TSP的分枝定界算法求解了一般問題動態(tài)規(guī)劃算法將VRP問題視為一個n階段的決策問題,進而將其轉(zhuǎn)化為依次求解n個具有遞推關(guān)系的單階段決策問題.Eilon通過遞歸的形式利用動態(tài)規(guī)劃法求解具有固定車輛數(shù)的VRP問題三下標車輛流方程由Fisher等人提出,用以求解帶能力約束、時間窗口以及無停留時間的VRP問題。在該方程中,兩個下標表示弧或邊,另一個下標表示車輛的序號。二下
5、標車輛流方程Laporte提出了用以求解對稱的一般VRP問題,結(jié)合了爬山法的思想,核心依然是線性規(guī)劃。求解問題的元啟發(fā)式算法禁忌搜索算法由Glover在1986年提出，是一種全局逐步尋優(yōu)算法,此算法采用禁忌搜索表紀錄已達到過的局部最優(yōu)點,在下一次搜索中對于禁忌表中的節(jié)點有選擇或是不再選擇，以此來避免陷入局部最優(yōu)解。Gendrean最先用此法解決VRP問題模擬退火算法解決VRP問題時，將物理退火中原子獲得的能量相當(dāng)于分配最優(yōu)節(jié)點，將原子震動模擬為線路尋優(yōu)空間的隨機搜索。（Laporte和Teodorovic）
6、遺傳算法Berger和Barkaoui（2004）利用并行混合遺傳算法求解帶時間窗的車輛路徑問題。郎茂祥通過構(gòu)建單親遺傳算法,有效改進了傳統(tǒng)遺傳算法對復(fù)雜問題搜索效率低,易陷入過早收斂的缺陷。蟻群算法BullnheimerB.等人首先將蟻群算法的思想用于VRP問題。BellJohn.E等提出一種改進的蟻群算法用來求解VRP。AlberboV等人改進蟻群算法求解TDVRP。劉志碩等人構(gòu)造了求解的自適應(yīng)蟻群算法。3蟻群算法簡介蟻群算法簡史2001年至今1996年-2001年意大利學(xué)者Dorigo1991年啟發(fā)各
7、種改進算法的提出，應(yīng)用領(lǐng)域更廣引起學(xué)者關(guān)注，在應(yīng)用領(lǐng)域得到拓寬ACO首次被系統(tǒng)的提出自然界中真實蟻群集體行為蟻群算法簡史蟻群算法（AntAlgorithm)是一種由自然界真實螞蟻覓食行為提煉而成的優(yōu)化算法，于1991年，由意大利學(xué)者MacroDorigo在其博士論文中提出，并成功的解決了旅行商（TSP）問題。1996年,MacroDorigo等人在《IEEE系統(tǒng)、人、控制論匯刊》上發(fā)表了”Antsystem:optimizationbyacolonyofcooperatingagents”一文，系統(tǒng)地闡述了
8、蟻群算法的基本原理和數(shù)學(xué)模型，蟻群算法逐漸引起了世界許多國家研究者的關(guān)注，其應(yīng)用領(lǐng)域也得到了迅速拓寬。1998年10月在比利時布魯塞爾召開了第一屆蟻群算法國際研討會（ANTS），標志著蟻群算法的正式國際化。2000年，MarcoDorigo和BonabeauE等人在國際頂級學(xué)術(shù)刊物《Nature》上發(fā)表了蟻群算法的研究綜述，從而把這一領(lǐng)域的研究推向了國際數(shù)學(xué)的最前沿。在我國，最早關(guān)于蟻群算法的研究見于1997年1
