車輛路徑問題指的是什么意思（什么是車輛路徑問題)
你真的知道車輛路徑問題嗎？你知道多少？以下是愛68為您整理車輛路徑問題的相關知識，讓您更深入地了解什么是車輛路徑問題。那么，車輛路徑問題在公路運輸行業代表什么呢？讓我們一起看看。
車輛路徑問題（Vehicle Routing Problem,VRP）
目錄
|
車輛路徑問題是什么？
車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。
這個定義不難看出旅行者的問題（Traveling Saleman Problem,TSP）是VRP因為Gaery已證明TSP問題是NP所以，VRP也屬于NP難題。
自1959年提出以來，車輛路線問題一直是網絡優化中最基本的問題之一。由于其廣泛的應用和重大的經濟價值，它一直受到國內外學者的廣泛關注。車輛路線問題可描述如下（如圖1所示）：
設有一場站（depot），共有M 卡車，車輛容量為Q，有N位顧客（customer），每個客戶都有自己的需求D。車輛從車站出發，為客戶提供配送服務，最后返回車站，要求所有客戶配送，每位客戶一次完成配送，不得違反車輛容量限制。目的是盡量減少所有車輛路線的總距離。車輛路線的實際問題包括配送中心配送、公交路線制定、信件報紙配送、航空鐵路時間表安排、工業廢物收集等。
車輛路徑問題類型
一般來說，車輛路線問題可分為以下三種類型（Ballou，1992）：
1.不同的單一起點和單一終點。
2.單個起點和終點相同。
3.多個起點和終點。
車輛路徑問題的方法
有許多關于車輛路線問題的學術研究文獻，也提出了相當多的求解策略和方法，Bodin and Golden(1981)將多種求解方法歸納為以下七種:
- 數學解析法（Exact Procedure）；
- 人機互動法（Interactive Optimization）；
- 先分組再排路線（Cluster First–Route Second）；
- 先排路線再分組（Route First–Cluster Second）；
- 節約法或插入法（Saving or Insertion）；
- 改進或交換法（Improvement or Exchanges）；
- 近似法的數學規劃（Mathematical programming）。
車輛路線問題研究現狀
經過幾十年的研究和發展，車輛路線問題的研究取得了很大的成果。以下從車輛路線問題的現有研究模式和解決方案兩個方面介紹了車輛路線問題的研究現狀。
車輛路線問題型態
基本車輛路線問題（VRP）在此基礎上，車輛路線問題在學術研究和實際應用中產生了許多不同的延伸和變化，包括時窗限制車輛路線問題（vehicle routing problems with time windows，VRPTW）、追求最佳服務時間的車輛路線問題（VRPDT）、多車種車輛路線問題（fleet size and mix vehicle routing problems，FSVRP）、多次使用車輛的車輛路線問題（vehicle routingproblems with multiple use of vehicle，VRPM）、考慮收集的車輛路線（vehicle routingproblems with backhauls，VRPB）、隨機車輛路線問題（vehicle routing problem with stochastic demand，VRPSD）等。
求解方法
1.解決方法的演進
結合過去對車輛路線問題的解決方法，可分為精確算法（exact algorithm）和啟發式解法（heuristics），精密算法包括分支邊界法、分支切割法、***覆蓋法等。啟發式解決方案包括節約法、模擬退火法、確定性退火法、禁忌搜索法、基因算法、神經網絡、螞蟻殖民算法等。1995年，Fisher將解決車輛路線問題的算法分為三個階段。第一階段是從1960年到1970年，它是一種簡單的啟發方式，包括各種局部改進啟發算法和貪婪法（Greedy）等等；第二階段是從1970年到1980年，它是一種基于數學規劃的啟發性解決方案，包括分配法、***分割法和***涵蓋法；第三階段是自1990年以來的一種新方法，包括使用嚴格的啟發法、人工智能法等。
2.啟發算法
由于VRP是NP-hard問題很難用精確的計算來解決。啟發算法是解決車輛運輸問題的主要方法。多年來，許多學者研究了車輛運輸問題，并提出了各種啟發方法。車輛運輸問題的啟發方法可分為簡單啟發算法、兩階段啟發算法和人工智能方法。
簡單的啟發方法包括節省法或插入法、路線/間節點交換法、貪婪法和局部搜索法。節省法或插入法（savings or insertion）在求解過程中，采用節約成本的最可行方式構建路線，直至無法節約。交換規則是依靠其他方法生成起始路線，然后通過迭代減少路線距離，直到無法改善。1960年，Clarke和Wright首先，提出啟發性節約法（savings methods）建立團隊配送路線。簡單的啟發方法簡單易懂，求解速度快，但只適合求解小而簡單VRP問題。
兩階段的方法包括先分組后定路線（clusterfirst-route second）先定路線后分組（routefirst-cluster second）兩種啟發式策略。前者是先將所有需求點大略分為幾個組，然后再對各個組分別進行路線排序；后者則是先將所有的需求點建構成一條路線，再根據車輛的容量將這一路線分割成許多適合的單獨路線。
自1990年以來，人工智能方法在解決組合優化問題方面發揮了強大的作用，并在各個領域得到了充分的應用。許多學者還將人工智能引入了車輛路線問題的解決方案，并構建了大量基于人工智能的啟發性算法。禁止搜索方法（TS）基本屬于人工智能型（AI）局部搜索方法，Willard首先，該算法用于解釋VRP ，隨后，許多學者也發表了求解VRP的TS 算法。西南交通大學的袁慶達設計了考慮時間窗口和不同車輛類型的禁忌算法，該算法主要采用GENIUS該方法產生初始解，然后禁忌算法優化初始解。模擬退火方法具有收斂速度快、全局搜索的特點，Osman對VRP研究了模擬退火算法，他提出的模擬退火方法主要適用于解決路線分組。遺傳算法具有解決組合優化問題的良好特點，Holland首先采用遺傳算法（GA）編碼解決VRPTW 問題。現在大多數學者采用混合策略，路線分組和路線優化分別采用兩種人工智能方法。Ombuki提出了用遺傳算法分組路線，然后用禁忌搜索方法優化路線的混合算法。Bent和Van Hentenryck先用模擬退火算法將車輛路線數量最小化，再用大鄰域搜索法（largneighborhood search）盡量減少運輸成本。
總結幾種人工智能方法，TS算法獲得的解最接近最優解，但其計算時間也最長GA算法的2~3倍，SA算法的近20倍；因為GA算法也能更好地接近最優解，大大縮短操作時間，因此GA算法可以兼顧計算時間和效率，是一種發展前景良好的方法；SA算法求解速度非常快，也能在一定程度上提供優化方案，求解小規模問題上有很好的效果。
參考文獻
- ↑ Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM。Society for Industrial and Applied Mathematics philadephia.2002
- ↑ 朱崇軍，劉民，吳澄.供應鏈中車輛路徑問題的研究進展和前景.計算機集成制造系統-CMS.2001,7(11):1-6
- ↑ 邱志鴻.物流配送中心貨車路線問題研究
- ↑ 張強、荊剛、陳建嶺.研究車輛路線的現狀和發展方向.2004年(1)交通技術:60-62
- ↑ Fisher M L，Vehicle Routing．Handbooks in Operations Research ＆ Management Science Vol 8，1995.1～33
- ↑ Clarke G，Wright J．Sche***ng of vehicles from central depot to a number of delivery points.Operations Research,1964,12:568～581
- ↑ 袁慶達、閆昱、周再玲Tabu Search算法在優化配送路線中的應用.2001(11)計算機工程:86~89
- ↑ Osman I H.Meta-strategy simulatedannealing an Tabu search algorithms for the vehicle routin problem.Annu Oper Res,1993,41:77～86
- ↑ Ombuki.B M，Nakamura M，Osamu M．Ahybri search based on genetic algorithm s and tabu search for vehicle routing.Brock University T echnica Report:#CS-02-07,2002,5:1～7
- ↑ R .Bent and P.Van Hentenryck.A two-stage hybri local search for the vehicle routing problem with tim windows.Technical Report,CS-01-06,Brown University,2001,9:1～30
車輛路徑問題指的是什么意思（什么是車輛路徑問題)
車輛路徑問題指的是什么意思（什么是車輛路徑問題)發表于2022-06-29，由周林編輯，文章《車輛路徑問題指的是什么意思（什么是車輛路徑問題)》由admin于2022年06月29日發布于本網，共4253個字，共5106人圍觀，目錄為公路運輸，如果您還要了解相關內容敬請點擊下方標簽，便可快捷查找與文章《車輛路徑問題指的是什么意思（什么是車輛路徑問題)》相關的內容。
版權聲明：
文章:(車輛路徑問題指的是什么意思（什么是車輛路徑問題))，來源：，閱讀原文。
車輛路徑問題指的是什么意思（什么是車輛路徑問題)若有[原創]標注，均為本站原創文章，任何內容僅供學習參考，未經允許不得轉載，任何內容不得引用，文章若為轉載文章，請注明作者來源，本站僅為分享知識，不參與商業活動，若有侵權請聯系管理刪除
微信掃一掃打賞
支付寶掃一掃打賞
