車(chē)輛路徑問(wèn)題

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

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

2023/2/6高開(kāi)周5車(chē)輛路徑問(wèn)題的概念

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

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

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

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

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

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

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

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

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

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

（next）2023/2/6高開(kāi)周272023/2/6高開(kāi)周28

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

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

2023/2/6高開(kāi)周29成本比較法

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

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

將所有運(yùn)輸路線首尾相連順序排列，使車(chē)輛的空閑時(shí)間最短，就此決定車(chē)輛數(shù)，并排出配車(chē)計(jì)劃。2023/2/6高開(kāi)周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高開(kāi)周36單一路線選擇運(yùn)輸線路的選擇影響到運(yùn)輸設(shè)備和人員的利用，正確地確定合理的運(yùn)輸線路可以縮短運(yùn)輸時(shí)間，降低運(yùn)輸成本，因此運(yùn)輸線路的的選擇是運(yùn)輸決策的一個(gè)重要領(lǐng)域。運(yùn)輸線路選擇問(wèn)題盡管種類繁多，但我們可以簡(jiǎn)單劃分為單一路線選擇和多起訖點(diǎn)路線選擇兩種類型。2023/2/6高開(kāi)周37（一）起訖點(diǎn)不同的單一路線選擇問(wèn)題對(duì)分離的、單個(gè)始發(fā)點(diǎn)和終點(diǎn)的網(wǎng)絡(luò)運(yùn)輸路線選擇問(wèn)題，最簡(jiǎ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)開(kāi)始。2023/2/6高開(kāi)周38（二）多起訖點(diǎn)路線選擇問(wèn)題如果有多個(gè)貨源地可以服務(wù)多個(gè)目的地，那么我們面臨的問(wèn)題是：要指定各目的地的供貨地、目的地之間的最佳路徑。該問(wèn)題經(jīng)常發(fā)生在多個(gè)供應(yīng)商、工廠或倉(cāng)庫(kù)服務(wù)于多個(gè)客戶的情況下。如果各供貨地能夠滿足的需求數(shù)據(jù)有限，則問(wèn)題會(huì)更復(fù)雜。解決這類問(wèn)題常?？梢赃\(yùn)輸一類特殊的線性規(guī)劃算法，即運(yùn)輸方法求解。利用計(jì)算機(jī)軟件TRANLP（這是LOGWARE軟件包內(nèi)的程序),任何運(yùn)輸方法的軟件都能解決該問(wèn)題.2023/2/6高開(kāi)周39供應(yīng)商B

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

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

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

123A121214B11118C1510132023/2/6高開(kāi)周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高開(kāi)周41（三）起訖點(diǎn)重合的問(wèn)題物流管理人員經(jīng)常會(huì)遇到起訖點(diǎn)相同的路徑規(guī)劃問(wèn)題。在企業(yè)自己擁有運(yùn)輸工具時(shí)，該問(wèn)題是相當(dāng)普遍的。我們熟悉的例子有：從某倉(cāng)庫(kù)送貨到零售點(diǎn)然后返回的路線（從中央配送中心送貨到食品店或藥店）；從零售店到客戶本地配送的路線設(shè)計(jì)（商店送貨上門(mén)）；校車(chē)、送報(bào)車(chē)、垃圾收集車(chē)和送餐車(chē)等的路線設(shè)計(jì)。這類路徑問(wèn)題是起訖點(diǎn)不同的問(wèn)題的擴(kuò)展形式，但是由于要求車(chē)輛必須返回起點(diǎn)行程才能結(jié)束，這樣問(wèn)題的難度就提高了。我們的目標(biāo)是找出途徑點(diǎn)的順序，使其滿足必須經(jīng)過(guò)所有點(diǎn)且總出行時(shí)間或總距離最短的要求。2023/2/6高開(kāi)周42不好的路線規(guī)劃—線路交叉

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

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

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

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

Step1：取原點(diǎn)0作為線路的起點(diǎn)；

Step2