車輛路徑問題

1、2022-3-91車輛路徑問題 車輛路徑問題概念 車輛路徑問題的方法 車輛路線問題研究現(xiàn)狀 2022-3-92車輛路徑問題的概念 車輛路線問題（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當?shù)男熊嚶肪€，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。 2022-3-93車輛路徑問題的概念 由此定義不難看出，旅行商問題（Traveling Saleman Problem,TSP）是VRP的特例，由于Gaery已證明TSP問題

2、是NP難題，因此，VRP也屬于NP難題。 車輛路線問題自1959年提出以來，一直是網(wǎng)絡(luò)優(yōu)化問題中最基本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟上的重大價值，一直受到國內(nèi)外學(xué)者的廣泛關(guān)注。車輛路線問題可以描述如下（如圖1）： 2022-3-94車輛路徑問題的概念2022-3-95車輛路徑問題的概念 設(shè)有一場站（depot），共有M 輛貨車，車輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場站出發(fā)對客戶進行配送服務(wù)最后返回場站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。 車輛路線的實際問題包括配送中心配送、公共汽車路

3、線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。 2022-3-96車輛路徑問題的方法 數(shù)學(xué)解析法（Exact Procedure）； 人機互動法（Interactive Optimization）； 先分群再排路線（Cluster FirstRoute Second）； 先排路線再分群（Route FirstCluster Second）； 節(jié)省法或插入法（Saving or Insertion）； 改善或交換法（Improvement or Exchanges）； 數(shù)學(xué)規(guī)劃近似法（Mathematical programming）。 2022-3-97數(shù)學(xué)解析法 最佳解法最佳

4、解法又稱“精確解法”、數(shù)學(xué)解析法，就是標準的”最佳化法”，將車輛配送問題，通過嚴謹?shù)臄?shù)學(xué)模型或計算機數(shù)據(jù)結(jié)構(gòu)規(guī)劃，利用數(shù)學(xué)法則或數(shù)據(jù)結(jié)構(gòu)搜尋的方式，求得問題的解1。2022-3-98數(shù)學(xué)解析法常見的有:分枝界限法（Branch and Bound）、整數(shù)規(guī)劃法（Integer Programming）、動態(tài)規(guī)劃法（Dynamic Programming）。2022-3-99數(shù)學(xué)解析法1、分枝界限法把問題的可行解展開如樹的分枝，再經(jīng)由各個分枝中尋找最佳解。2、整數(shù)規(guī)劃法在數(shù)學(xué)模式中加入變量必須為整數(shù)的限制式，將問題列出目標方程序以及限制式來求解，能夠?qū)嶋H情形化做限制條件加入模式中，讓一般人較容

5、易理解及方便使用。這個解法會隨限制式的增加而趨于復(fù)雜，使得演算復(fù)雜度大為提高。2022-3-910數(shù)學(xué)解析法3、動態(tài)規(guī)劃法主要是將一個大問題分解成幾個小問題來求解，以反向工作的方式，求解路徑中連接兩點的最短距離，但是動態(tài)規(guī)劃法缺乏效率，比較適合小問題和批次問題。Bodin（1983）等人同時也指出，此類方法雖然可以求得最佳解，但其求解范圍太小，當需求點數(shù)目大于25時便無法使用。 2022-3-911人機互動法 人機互動法是利用人的經(jīng)驗和計算機的運算所合成的方法，而根據(jù)Bodin(1983)等人的描述，人機互動法是一種將人的反應(yīng)能力，納入問題求解過程的一般性解法。其具備人的實際情況和計算機強力的

6、計算能力等綜合優(yōu)勢，這種方法是先將使用者或是規(guī)劃者的規(guī)劃直覺、經(jīng)驗、及能力納入求解的重要因子，并數(shù)據(jù)話統(tǒng)整后交由計算機依一定的公式來運算其派車路線的最佳解，并在獲得路線的解只后再重新由使用者依據(jù)現(xiàn)實層面的考慮因素進行修改更正。 2022-3-912先分群再排路線2465713802022-3-913先排路線再分群2465713802022-3-914節(jié)省法213055664445+6-4=786+4-8=25+4-10=-1102022-3-9151.線路內(nèi)路線交換或節(jié)點交換2.路線間部分線路交換3.路線間節(jié)點交換改善或交換法2022-3-916車輛路線問題研究現(xiàn)狀 經(jīng)過幾十年的研究發(fā)展，車輛

7、路線問題研究取得了大量成果。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。 2022-3-917車輛路線問題研究現(xiàn)狀車輛路線問題型態(tài)車輛路線問題型態(tài) 在基本車輛路線問題（VRP）的基礎(chǔ)上，車輛路線問題在學(xué)術(shù)研究和實際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括時窗限制車輛路線問題、追求最佳服務(wù)時間的車輛路線問題、多車種車輛路線問題、2022-3-918車輛路線問題研究現(xiàn)狀車輛多次使用的車輛路線問題、考慮收集的車輛路線問題、隨機需求車輛路線問題等。2022-3-919車輛路線問題研究現(xiàn)狀求解方法 綜合過去有關(guān)車輛路線問題的求解方法，可以分為精確算法（exact al

8、gorithm）與啟發(fā)式解法（heuristics），其中精確算法有分支界限法、分支切割法、集合涵蓋法等；啟發(fā)式解法有節(jié)約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經(jīng)網(wǎng)絡(luò)、螞蟻算法等。2022-3-920車輛路線問題研究現(xiàn)狀 1995年，F(xiàn)isher曾將求解車輛路線問題的算法分成三個階段。第一階段是從1960年到1970年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（Greedy）等；第二階段是從1970年到1980年，屬于一種以數(shù)學(xué)規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從1990開始至今，屬于較新的方法，包括利用嚴謹啟發(fā)式方法、人工智能

9、方法等。 2022-3-921 【例例】有一條公路AD，全長400km，其中B、D為煤炭供應(yīng)點，以三角形表示；A、C為煤炭的銷售點，以矩形表示，各站點煤炭供應(yīng)數(shù)量及站點距離如下圖所示。 試問如何組織更為合理？100km100km200kmAD-3000t-500t500t3000t物流實例2022-3-922ADBC3000t500t甲方案甲方案ADBC2500t乙方案乙方案500t500t2022-3-923物流實例 假設(shè)某公司在甲地至乙地之間具有比較穩(wěn)定的貨流量。該企業(yè)的物流管理人員面臨這樣兩種抉擇：一方面，第三方物流服務(wù)公司按平均的市場價格進行了報價：噸公里0.45元。甲地至乙地距離計為

10、1500公里，每趟運載能力為10噸，因此，每趟（10噸）報價為6750元（0.451500 1O，含所有的裝卸費用）。同時，對于往返運輸?shù)幕爻?，則按單程報價的50計算。而另一方面，該公司的管理人員也在考慮自己投資買車、配備司機、建自己的車隊。他們進行了測算，投資購買一輛普通加長（10噸）卡車，并改裝成廂式貨車，一次性投資為人民幣20萬元。每輛車配備兩名司機（按正式員工錄用，并享受所有人事方面的福利），運營中的固定和可變成本見表1 （next）2022-3-9242022-3-925 他們再將每月的運輸總支出，根據(jù)運送的次數(shù)進行了計算，并對單程與往返、自營與外包進行了比較，見表2。 結(jié)果發(fā)現(xiàn)，不

11、論是以單程還是以往返計算，如果貨流量足以使運送次數(shù)保持在3趟或以上，自營將比“外包”更經(jīng)濟。由于自營車輛每輛每月的最大往返次數(shù)為5趟，所以只有在貨流量在67趟時，對于自營車輛無力運送的部分才可能采取外包。 2022-3-926制定車輛運行路線采用掃描法制定行車路線，由兩個階段組成：采用掃描法制定行車路線，由兩個階段組成： 將停留點的貨運量分配給送貨車； 安排停留點在路線上的順序。掃描法的步驟： 在地圖上或者方格圖中確定所有站點（含倉庫）的位置；2022-3-927自倉庫開始沿任一方向向外劃一直線，沿著順時針或者逆時針方向旋轉(zhuǎn)該直線與某點相交。同時要考慮如果在某線路上再增加該站點，是否會超過車輛

12、的載貨能力？如沒有，繼續(xù)旋轉(zhuǎn)該直線直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力（先使用最大的車輛）。如超過，就去掉最后的站點，并確定路線。最后，從不包括在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)以尋找新路線。直到所有點被安排在路線中；排定各路線上每個站點的順序，使行車路線最短。2022-3-928汽車站汽車站100040002000300020002000200010002000200030003000停留點提貨量數(shù)據(jù)停留點提貨量數(shù)據(jù)汽車站汽車站100040002000300020002000200010002000200030003000掃描法解決方案掃描法解決方案2022-3-9

13、29安排車輛運行時間 將所有運輸路線首尾相連順序排列，使車輛的空閑時間最短，就此決定車輛數(shù)，并排出配車計劃。2022-3-930最優(yōu)運輸計劃安排表最優(yōu)運輸計劃安排表1 1號線號線1010號線號線6 6號線號線9 9號線號線4 4號線號線5 5號線號線8 8號線號線2 2號線號線7 7號線號線3 3號線號線2022-3-931單一路線選擇單一路線選擇 運輸線路的選擇影響到運輸設(shè)備和人員的利用，正確地確定合理的運輸線路可以縮短運輸時間，降低運輸成本，因此運輸線路的的選擇是運輸決策的一個重要領(lǐng)域。 運輸線路選擇問題盡管種類繁多，但我們可以簡單劃分為單一路線選擇單一路線選擇和多起訖點多起訖點路線選擇路

14、線選擇兩種類型。2022-3-932（一）起訖點不同的單一路線選擇問題（一）起訖點不同的單一路線選擇問題 對分離的、單個始發(fā)點和終點的網(wǎng)絡(luò)運輸路線選擇問題，最簡單和直觀的方法是最短路線法。 網(wǎng)絡(luò)由節(jié)點和線組成，點與點之間由線連接，線代表點與點之間運行的成本（距離、時間或時間和距離加權(quán)的組合）。 初始，除始發(fā)點外，所有節(jié)點都被認為是未解的，即均未確定是否在選定的運輸路線上，始發(fā)點作為已解的點，計算從原點開始。 2022-3-933（二）多起訖點路線選擇問題 如果有多個貨源地可以服務(wù)多個目的地，那么我們面臨的問題是： 要指定各目的地的供貨地、目的地之間的最佳路徑要指定各目的地的供貨地、目的地之間的

15、最佳路徑。 該問題經(jīng)常發(fā)生在多個供應(yīng)商、工廠或倉庫服務(wù)于多個客戶的情況下。如果各供貨地能夠滿足的需求數(shù)據(jù)有限，則問題會更復(fù)雜。解決這類問題常?？梢赃\輸一類特殊的線性規(guī)劃算法，即運輸方法求解。 利用計算機軟件TRANLP（這是LOGWARE軟件包內(nèi)的程序),任何運輸方法的軟件都能解決該問題.2022-3-934供應(yīng)商供應(yīng)商B 供給供給700供應(yīng)商供應(yīng)商A 供給供給500供應(yīng)商供應(yīng)商c 供給供給300工廠工廠1需求量需求量600工廠工廠2需求量需求量500工廠工廠3需求量需求量300 1 2 3A 12 12 14B 11 11 8 C 15 10 132022-3-935最佳供貨計劃至： 1 2

16、 3自： A 400 0 0 B 200 200 300 C 0 300 0運送單位總量1400最低總成本14600美元對該結(jié)果的解釋如下：貨運計劃：從供應(yīng)商A運輸400噸到工廠1。從供應(yīng)商B運輸200噸到工廠1。從供應(yīng)商B運輸200噸到工廠2。從供應(yīng)商B運輸300噸到工廠3。從供應(yīng)商C運輸300噸到工廠2。該運行線路計劃的成本最低，為14600美元。2022-3-936（三）起訖點重合的問題 物流管理人員經(jīng)常會遇到起訖點相同的路徑規(guī)劃問題。 在企業(yè)自己擁有運輸工具時，該問題是相當普遍的。我們熟悉的例子有：從某倉庫送貨到零售點然后返回的路線（從中央配送中心送貨到食品店或藥店）；從零售店到客戶本

17、地配送的路線設(shè)計（商店送貨上門）；校車、送報車、垃圾收集車和送餐車等的路線設(shè)計。 這類路徑問題是起訖點不同的問題的擴展形式，但是由于要求車輛必須返回起點行程才能結(jié)束，這樣問題的難度就提高了。 我們的目標是找出途徑點的順序，使其滿足必須經(jīng)過所有我們的目標是找出途徑點的順序，使其滿足必須經(jīng)過所有點且總出行時間或總距離最短的要求。點且總出行時間或總距離最短的要求。2022-3-937不好的路線規(guī)劃線路交叉 好的路線規(guī)劃線路不交叉 2022-3-938TSP的啟發(fā)式算法 線路構(gòu)造法 線路改進法 綜合法2022-3-939TSP的啟發(fā)式算法 線路構(gòu)造法 節(jié)約算法 最臨近法 幾何啟發(fā)式算法 最小生成樹算法

18、 最近插入算法2022-3-940TSP的啟發(fā)式算法 節(jié)約算法 213055664445+6-4=786+4-8=25+4-10=-1102022-3-941TSP的啟發(fā)式算法12345678185912131217288517711143587910712491573171116512179318111561371017188871211711118581714121615852022-3-942TSP的啟發(fā)式算法 1-3-4-5-7-8-6-2-1 542022-3-943TSP的啟發(fā)式算法最臨近算法 Step1：取原點0作為線路的起點； Step2：尋找與上一次加入線路的點距離 最近的點， 把此點加入到線路中； Step3：重復(fù)S