車輛路徑問題

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

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

3、線制定、信件和報紙投遞、航空和鐵路時間表安排、工業(yè)廢品收集等。 2022-3-96車輛路徑問題的方法 數(shù)學(xué)解析法（Exact Procedure）； 人機(jī)互動法（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é)解析法，就是標(biāo)準(zhǔn)的”最佳化法”，將車輛配送問題，通過嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)模型或計算機(jī)數(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ù)的限制式，將問題列出目標(biāo)方程序以及限制式來求解，能夠?qū)?shí)際情形化做限制條件加入模式中，讓一般人較容

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

6、計算能力等綜合優(yōu)勢，這種方法是先將使用者或是規(guī)劃者的規(guī)劃直覺、經(jīng)驗(yàn)、及能力納入求解的重要因子，并數(shù)據(jù)話統(tǒng)整后交由計算機(jī)依一定的公式來運(yùn)算其派車路線的最佳解，并在獲得路線的解只后再重新由使用者依據(jù)現(xiàn)實(shí)層面的考慮因素進(jì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é)點(diǎn)交換2.路線間部分線路交換3.路線間節(jié)點(diǎn)交換改善或交換法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ù)研究和實(shí)際應(yīng)用上產(chǎn)生了許多不同的延伸和變化型態(tài)，包括時窗限制車輛路線問題、追求最佳服務(wù)時間的車輛路線問題、多車種車輛路線問題、2022-3-918車輛路線問題研究現(xiàn)狀車輛多次使用的車輛路線問題、考慮收集的車輛路線問題、隨機(jī)需求車輛路線問題等。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開始至今，屬于較新的方法，包括利用嚴(yán)謹(jǐn)啟發(fā)式方法、人工智能

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

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

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

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

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

14、線選擇兩種類型。2022-3-932（一）起訖點(diǎn)不同的單一路線選擇問題（一）起訖點(diǎn)不同的單一路線選擇問題 對分離的、單個始發(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)行的成本（距離、時間或時間和距離加權(quán)的組合）。 初始，除始發(fā)點(diǎn)外，所有節(jié)點(diǎn)都被認(rèn)為是未解的，即均未確定是否在選定的運(yùn)輸路線上，始發(fā)點(diǎn)作為已解的點(diǎn)，計算從原點(diǎn)開始。 2022-3-933（二）多起訖點(diǎn)路線選擇問題 如果有多個貨源地可以服務(wù)多個目的地，那么我們面臨的問題是： 要指定各目的地的供貨地、目的地之間的最佳路徑要指定各目的地的供貨地、目的地之間的

15、最佳路徑。 該問題經(jīng)常發(fā)生在多個供應(yīng)商、工廠或倉庫服務(wù)于多個客戶的情況下。如果各供貨地能夠滿足的需求數(shù)據(jù)有限，則問題會更復(fù)雜。解決這類問題常常可以運(yùn)輸一類特殊的線性規(guī)劃算法，即運(yùn)輸方法求解。 利用計算機(jī)軟件TRANLP（這是LOGWARE軟件包內(nèi)的程序),任何運(yùn)輸方法的軟件都能解決該問題.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運(yùn)送單位總量1400最低總成本14600美元對該結(jié)果的解釋如下：貨運(yùn)計劃：從供應(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)行線路計劃的成本最低，為14600美元。2022-3-936（三）起訖點(diǎn)重合的問題 物流管理人員經(jīng)常會遇到起訖點(diǎn)相同的路徑規(guī)劃問題。 在企業(yè)自己擁有運(yùn)輸工具時，該問題是相當(dāng)普遍的。我們熟悉的例子有：從某倉庫送貨到零售點(diǎn)然后返回的路線（從中央配送中心送貨到食品店或藥店）；從零售店到客戶本

17、地配送的路線設(shè)計（商店送貨上門）；校車、送報車、垃圾收集車和送餐車等的路線設(shè)計。 這類路徑問題是起訖點(diǎn)不同的問題的擴(kuò)展形式，但是由于要求車輛必須返回起點(diǎn)行程才能結(jié)束，這樣問題的難度就提高了。 我們的目標(biāo)是找出途徑點(diǎn)的順序，使其滿足必須經(jīng)過所有我們的目標(biāo)是找出途徑點(diǎn)的順序，使其滿足必須經(jīng)過所有點(diǎn)且總出行時間或總距離最短的要求。點(diǎn)且總出行時間或總距離最短的要求。2022-3-937不好的路線規(guī)劃線路交叉 好的路線規(guī)劃線路不交叉 2022-3-938TSP的啟發(fā)式算法 線路構(gòu)造法 線路改進(jìn)法 綜合法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：取原點(diǎn)0作為線路的起點(diǎn)； Step2：尋找與上一次加入線路的點(diǎn)距離 最近的點(diǎn)， 把此點(diǎn)加入到線路中； Step3：重復(fù)S