車輛路徑問題

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

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

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

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

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

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

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

最佳解法又稱“精確解法”、數(shù)學(xué)解析法，就是標(biāo)準(zhǔn)的”最佳化法”，將車輛配送問題，通過嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型或計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)規(guī)劃，利用數(shù)學(xué)法則或數(shù)據(jù)結(jié)構(gòu)搜尋的方式，求得問題的解1。

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

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

人機(jī)互動(dòng)法是利用人的經(jīng)驗(yàn)和計(jì)算機(jī)的運(yùn)算所合成的方法，而根據(jù)Bodin(1983)等人的描述，人機(jī)互動(dòng)法是一種將人的反應(yīng)能力，納入問題求解過程的一般性解法。其具備人的實(shí)際情況和計(jì)算機(jī)強(qiáng)力的計(jì)算能力等綜合優(yōu)勢(shì)，這種方法是先將使用者或是規(guī)劃者的規(guī)劃直覺、經(jīng)驗(yàn)、及能力納入求解的重要因子，并數(shù)據(jù)話統(tǒng)整后交由計(jì)算機(jī)依一定的公式來運(yùn)算其派車路線的最佳解，并在獲得路線的解只后再重新由使用者依據(jù)現(xiàn)實(shí)層面的考慮因素進(jì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.線路內(nèi)路線交換或節(jié)點(diǎn)交換2.路線間部分線路交換3.路線間節(jié)點(diǎn)交換改善或交換法2023/2/6高開周19車輛路線問題研究現(xiàn)狀

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

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

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

他們?cè)賹⒚吭碌倪\(yùn)輸總支出，根據(jù)運(yùn)送的次數(shù)進(jìn)行了計(jì)算，并對(duì)單程與往返、自營與外包進(jìn)行了比較，見表2。

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

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

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

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

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

供給≤700供應(yīng)商A

供給≤500供應(yīng)商c

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

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

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

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

節(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：取原點(diǎn)0作為線路的起點(diǎn)；

Step2