車輛路徑問題

車輛路徑問題（VRP）作者：高開周2023/2/6高開周12023/2/6高開周2鐵路公路航空水路管道成本中中高低很低速度快快很快慢很慢頻率高很高高有限連續(xù)可靠性很好好好有限很好可用性廣泛有限有限很有限專業(yè)化距離長中，短很長很長長規(guī)模大小小大大能力強強弱最強最弱不同運輸方式的技術和經濟運作特征對比2023/2/6高開周3車輛路徑問題車輛路徑問題概念車輛路徑問題的類型車輛路徑問題的方法車輛路線問題研究現(xiàn)狀2023/2/6高開周4車輛路徑問題的概念

車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當?shù)男熊嚶肪€，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。

2023/2/6高開周5車輛路徑問題的概念

由此定義不難看出，旅行商問題（TravelingSalemanProblem,TSP）是VRP的特例，由于Gaery已證明TSP問題是NP難題，因此，VRP也屬于NP難題。

車輛路線問題自1959年提出以來，一直是網絡優(yōu)化問題中最基本的問題之一，由于其應用的廣泛性和經濟上的重大價值，一直受到國內外學者的廣泛關注。車輛路線問題可以描述如下（如圖1）：2023/2/6高開周6車輛路徑問題的概念2023/2/6高開周7車輛路徑問題的概念

設有一場站（depot），共有M輛貨車，車輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進行配送服務最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實際問題包括配送中心配送、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。2023/2/6高開周8車輛路徑問題的類型

一般而言車輛路線問題大致可以分為以下三種類型（Ballou，1992）：1、相異的單一起點和單一終點。2、相同的單一起點和終點。3、多個起點和終點。2023/2/6高開周9車輛路徑問題的方法數(shù)學解析法（ExactProcedure）；人機互動法（InteractiveOptimization）；先分群再排路線（ClusterFirst–RouteSecond）；先排路線再分群（RouteFirst–ClusterSecond）；節(jié)省法或插入法（SavingorInsertion）；改善或交換法（ImprovementorExchanges）；數(shù)學規(guī)劃近似法（Mathematicalprogramming）。2023/2/6高開周10數(shù)學解析法

最佳解法又稱“精確解法”、數(shù)學解析法，就是標準的”最佳化法”，將車輛配送問題，通過嚴謹?shù)臄?shù)學模型或計算機數(shù)據(jù)結構規(guī)劃，利用數(shù)學法則或數(shù)據(jù)結構搜尋的方式，求得問題的解1。

2023/2/6高開周11數(shù)學解析法常見的有:分枝界限法（BranchandBound）、整數(shù)規(guī)劃法（IntegerProgramming）、動態(tài)規(guī)劃法（DynamicProgramming）。

2023/2/6高開周12數(shù)學解析法1、分枝界限法把問題的可行解展開如樹的分枝，再經由各個分枝中尋找最佳解。2、整數(shù)規(guī)劃法在數(shù)學模式中加入變量必須為整數(shù)的限制式，將問題列出目標方程序以及限制式來求解，能夠將實際情形化做限制條件加入模式中，讓一般人較容易理解及方便使用。這個解法會隨限制式的增加而趨于復雜，使得演算復雜度大為提高。2023/2/6高開周13數(shù)學解析法3、動態(tài)規(guī)劃法主要是將一個大問題分解成幾個小問題來求解，以反向工作的方式，求解路徑中連接兩點的最短距離，但是動態(tài)規(guī)劃法缺乏效率，比較適合小問題和批次問題。Bodin（1983）等人同時也指出，此類方法雖然可以求得最佳解，但其求解范圍太小，當需求點數(shù)目大于25時便無法使用。2023/2/6高開周14人機互動法

人機互動法是利用人的經驗和計算機的運算所合成的方法，而根據(jù)Bodin(1983)等人的描述，人機互動法是一種將人的反應能力，納入問題求解過程的一般性解法。其具備人的實際情況和計算機強力的計算能力等綜合優(yōu)勢，這種方法是先將使用者或是規(guī)劃者的規(guī)劃直覺、經驗、及能力納入求解的重要因子，并數(shù)據(jù)話統(tǒng)整后交由計算機依一定的公式來運算其派車路線的最佳解，并在獲得路線的解只后再重新由使用者依據(jù)現(xiàn)實層面的考慮因素進行修改更正。

2023/2/6高開周15先分群再排路線2465713802023/2/6高開周16先排路線再分群2465713802023/2/6高開周17節(jié)省法213055664445+6-4=786+4-8=25+4-10=-1102023/2/6高開周181.線路內路線交換或節(jié)點交換2.路線間部分線路交換3.路線間節(jié)點交換改善或交換法2023/2/6高開周19車輛路線問題研究現(xiàn)狀

經過幾十年的研究發(fā)展，車輛路線問題研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。2023/2/6高開周20車輛路線問題研究現(xiàn)狀車輛路線問題型態(tài)在基本車輛路線問題（VRP）的基礎上，車輛路線問題在學術研究和實際應用上產生了許多不同的延伸和變化型態(tài)，包括時窗限制車輛路線問題（vehicleroutingproblemswithtimewindows，VRPTW）、追求最佳服務時間的車輛路線問題（VRPDT）、多車種車輛路線問題（fleetsizeandmixvehicleroutingproblems，F(xiàn)SVRP）、2023/2/6高開周21車輛路線問題研究現(xiàn)狀車輛多次使用的車輛路線問題（vehicleroutingproblemswithmultipleuseofvehicle，VRPM）、考慮收集的車輛路線問題（vehicleroutingproblemswithbackhauls，VRPB）、隨機需求車輛路線問題（vehicleroutingproblemwithstochasticdemand，VRPSD）等。2023/2/6高開周22車輛路線問題研究現(xiàn)狀求解方法綜合過去有關車輛路線問題的求解方法，可以分為精確算法（exactalgorithm）與啟發(fā)式解法（heuristics），其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經網絡、螞蟻算法等。2023/2/6高開周23車輛路線問題研究現(xiàn)狀1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，屬于較新的方法，包括利用嚴謹啟發(fā)式方法、人工智能方法等。2023/2/6高開周24【例】有一條公路A－D，全長400km，其中B、D為煤炭供應點，以三角形表示；A、C為煤炭的銷售點，以矩形表示，各站點煤炭供應數(shù)量及站點距離如下圖所示。試問如何組織更為合理？100km100km200kmAD-3000t-500t500t3000t物流實例2023/2/6高開周25ADBC3000t500t甲方案ADBC2500t乙方案500t500t2023/2/6高開周26物流實例

假設某公司在甲地至乙地之間具有比較穩(wěn)定的貨流量。該企業(yè)的物流管理人員面臨這樣兩種抉擇：一方面，第三方物流服務公司按平均的市場價格進行了報價：噸公里0.45元。甲地至乙地距離計為1500公里，每趟運載能力為10噸，因此，每趟（10噸）報價為6750元（0.45%×1500×1O，含所有的裝卸費用）。同時，對于往返運輸?shù)幕爻?，則按單程報價的50％計算。而另一方面，該公司的管理人員也在考慮自己投資買車、配備司機、建自己的車隊。他們進行了測算，投資購買一輛普通加長（10噸）卡車，并改裝成廂式貨車，一次性投資為人民幣20萬元。每輛車配備兩名司機（按正式員工錄用，并享受所有人事方面的福利），運營中的固定和可變成本見表1

（next）2023/2/6高開周272023/2/6高開周28

他們再將每月的運輸總支出，根據(jù)運送的次數(shù)進行了計算，并對單程與往返、自營與外包進行了比較，見表2。

結果發(fā)現(xiàn)，不論是以單程還是以往返計算，如果貨流量足以使運送次數(shù)保持在3趟或以上，自營將比“外包”更經濟。由于自營車輛每輛每月的最大往返次數(shù)為5趟，所以只有在貨流量在6～7趟時，對于自營車輛無力運送的部分才可能采取外包。

2023/2/6高開周29成本比較法

某公司欲將產品從座落位置A的工廠運往座落位置B的公司自有倉庫，年運量D為700,000件，每件產品的價格C為30元，每年的存貨成本I為產品價格的30％。公司希望選擇使總成本最小的運輸方式。據(jù)估計，運輸時間每減少一天，平均庫存可以減少1％。各種運輸服務的參數(shù)如圖。在途運輸?shù)哪甏尕洺杀緸镮CDT/365，兩端儲存點的存貨成本各為，但其中C值有差別，工廠的儲存點C為產品的價格，購買者儲存點的C為產品價格加上運費之和。問題：選擇哪種運輸方式的方案最優(yōu)？2023/2/6高開周302023/2/6高開周31制定車輛運行路線采用掃描法制定行車路線，由兩個階段組成：

將停留點的貨運量分配給送貨車；安排停留點在路線上的順序。掃描法的步驟：在地圖上或者方格圖中確定所有站點（含倉庫）的位置；2023/2/6高開周32自倉庫開始沿任一方向向外劃一直線，沿著順時針或者逆時針方向旋轉該直線與某點相交。同時要考慮如果在某線路上再增加該站點，是否會超過車輛的載貨能力？如沒有，繼續(xù)旋轉該直線直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力（先使用最大的車輛）。如超過，就去掉最后的站點，并確定路線。最后，從不包括在上一條路線中的站點開始，繼續(xù)旋轉以尋找新路線。直到所有點被安排在路線中；排定各路線上每個站點的順序，使行車路線最短。2023/2/6高開周33汽車站100040002000300020002000200010002000200030003000停留點提貨量數(shù)據(jù)汽車站100040002000300020002000200010002000200030003000掃描法解決方案2023/2/6高開周34安排車輛運行時間

將所有運輸路線首尾相連順序排列，使車輛的空閑時間最短，就此決定車輛數(shù)，并排出配車計劃。2023/2/6高開周35最優(yōu)運輸計劃安排表1號線10號線6號線9號線4號線5號線8號線2號線7號線3號線2023/2/6高開周36單一路線選擇運輸線路的選擇影響到運輸設備和人員的利用，正確地確定合理的運輸線路可以縮短運輸時間，降低運輸成本，因此運輸線路的的選擇是運輸決策的一個重要領域。運輸線路選擇問題盡管種類繁多，但我們可以簡單劃分為單一路線選擇和多起訖點路線選擇兩種類型。2023/2/6高開周37（一）起訖點不同的單一路線選擇問題對分離的、單個始發(fā)點和終點的網絡運輸路線選擇問題，最簡單和直觀的方法是最短路線法。網絡由節(jié)點和線組成，點與點之間由線連接，線代表點與點之間運行的成本（距離、時間或時間和距離加權的組合）。初始，除始發(fā)點外，所有節(jié)點都被認為是未解的，即均未確定是否在選定的運輸路線上，始發(fā)點作為已解的點，計算從原點開始。2023/2/6高開周38（二）多起訖點路線選擇問題如果有多個貨源地可以服務多個目的地，那么我們面臨的問題是：要指定各目的地的供貨地、目的地之間的最佳路徑。該問題經常發(fā)生在多個供應商、工廠或倉庫服務于多個客戶的情況下。如果各供貨地能夠滿足的需求數(shù)據(jù)有限，則問題會更復雜。解決這類問題常?？梢赃\輸一類特殊的線性規(guī)劃算法，即運輸方法求解。利用計算機軟件TRANLP（這是LOGWARE軟件包內的程序),任何運輸方法的軟件都能解決該問題.2023/2/6高開周39供應商B

供給≤700供應商A

供給≤500供應商c

供給≤300工廠1需求量＝600工廠2需求量＝500工廠3需求量＝300

123A121214B11118C1510132023/2/6高開周40最佳供貨計劃至：123自：A40000B200200300C03000運送單位總量＝1400最低總成本＝14600美元對該結果的解釋如下：貨運計劃：從供應商A運輸400噸到工廠1。從供應商B運輸200噸到工廠1。從供應商B運輸200噸到工廠2。從供應商B運輸300噸到工廠3。從供應商C運輸300噸到工廠2。該運行線路計劃的成本最低，為14600美元。2023/2/6高開周41（三）起訖點重合的問題物流管理人員經常會遇到起訖點相同的路徑規(guī)劃問題。在企業(yè)自己擁有運輸工具時，該問題是相當普遍的。我們熟悉的例子有：從某倉庫送貨到零售點然后返回的路線（從中央配送中心送貨到食品店或藥店）；從零售店到客戶本地配送的路線設計（商店送貨上門）；校車、送報車、垃圾收集車和送餐車等的路線設計。這類路徑問題是起訖點不同的問題的擴展形式，但是由于要求車輛必須返回起點行程才能結束，這樣問題的難度就提高了。我們的目標是找出途徑點的順序，使其滿足必須經過所有點且總出行時間或總距離最短的要求。2023/2/6高開周42不好的路線規(guī)劃—線路交叉

好的路線規(guī)劃—線路不交叉

2023/2/6高開周43TSP的啟發(fā)式算法線路構造法線路改進法綜合法2023/2/6高開周44TSP的啟發(fā)式算法線路構造法

節(jié)約算法最臨近法幾何啟發(fā)式算法最小生成樹算法最近插入算法2023/2/6高開周45TSP的啟發(fā)式算法節(jié)約算法

213055664445+6-4=786+4-8=25+4-10=-1102023/2/6高開周46TSP的啟發(fā)式算法12345678185912131217288517711143587910712491573171116512179318111561371017188871211711118581714121615852023/2/6高開周47TSP的啟發(fā)式算法1-3-4-5-7-8-6-2-1542023/2/6高開周48TSP的啟發(fā)式算法最臨近算法

Step1：取原點0作為線路的起點；

Step2