專題2車輛路徑問題課件

1、2006.12.8張軍車輛路徑問題第1頁，共37頁。主要內(nèi)容什么是VRPVRP背景及應(yīng)用VRP問題定義VRP問題的分類VRP問題數(shù)學(xué)模型VRP算法類型及簡要介紹近年來關(guān)于VRP的研究第2頁，共37頁。一、什么是VRP VRP（Vehicle Routing Problem） 車輛路徑問題 當(dāng)不考慮時間要求，僅根據(jù)空間位置安排線路時，稱為車輛路徑問題。第3頁，共37頁。二、VRP的背景及應(yīng)用 車輛路徑問題是由G.Dantzig和J.Ramser于1959年首先提出來的,很快引起運籌學(xué)、管理學(xué)、計算機應(yīng)用、組合數(shù)學(xué)、圖論等學(xué)科的專家學(xué)者的高度重視。 其研究結(jié)果在運輸系統(tǒng)、物流配送系統(tǒng)、快遞收發(fā)系統(tǒng)

2、中都已得到廣泛應(yīng)用。第4頁，共37頁。三、VRP問題定義 對一系列發(fā)貨點或收貨點，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等) 下，達到一定的目標(biāo)(如路程最短、費用最小、時間盡量少、使用車輛盡量少等)。第5頁，共37頁。四、VRP問題的分類按任務(wù)特征分類 裝貨問題(Pure Pick Up )、卸貨問題(Pure Delivery)及裝卸混合問題(Combined Pick Up and Delivery)按任務(wù)性質(zhì)分類 有對弧服務(wù)問題(如中國郵遞員問題) 和對點服務(wù)問題(如旅行商問題) 以及混合服務(wù)

3、問題(如交通車路線安排問題)按車輛載貨狀況分類 有滿載問題和非滿載問題第6頁，共37頁。按車場數(shù)目分類 有單車場問題和多車場問題按車輛類型分類 有單車型問題和多車型問題按車輛對車場的所屬關(guān)系分類 有車輛開放問題(車輛可不返回車場)和車輛封閉問題(車輛必須返回車場)按已知信息的特征分類 有確定性VRP和不確定性VRP,其中不確定性VRP 可進一步分為隨機VRP(SVRP)和模糊VRP(FVRP)第7頁，共37頁。按優(yōu)化目標(biāo)數(shù)來分類 有單目標(biāo)問題和多目標(biāo)問題按約束條件分類有距離約束的VRP問題(Distance Constrained Vehicle Routing Problem)有能力約束的V

4、RP問題(Vehicle Routing Problem with Capacity Restriction )對稱問題和非對稱問題三角不等式問題第8頁，共37頁。按約束條件分類有等需求問題(Equal Demand)和非等需求問題(Unequal Demand)有時間窗的VRP問題(Vehicle Routing Problem with Time Window) 該問題中還包括柔性時間窗約束和剛性時間窗約束 第9頁，共37頁。五、VRP問題的數(shù)學(xué)模型(1)問題 從一個配送中心出發(fā)，向多個客戶點送貨，然后在同一天內(nèi)返回到該配送中心，要安排一個滿意的運行路線。(2)已知條件配送中心擁有的車輛臺

5、數(shù)m及每輛車的載重量（噸位）為需求點 數(shù)為n及每個點的需貨量為配送中心到各需求點的費用及各需求點之間的費用為第10頁，共37頁。五、VRP問題的數(shù)學(xué)模型(3)目標(biāo) 各車輛行走的路徑使總運輸費用最小。(4)模型中符號定義所有收貨點的貨物量需求為車輛的容量限制決策變量第k輛車從點i到點j0 否則 需求點i由車輛k送貨0 否則 第11頁，共37頁。五、VRP問題的數(shù)學(xué)模型數(shù)學(xué)模型為：每輛車所運送的貨物量不超過其載重量每個需求點由且僅由一輛車送貨若客戶點j由車輛k送貨，則車輛k必由某點i到達點j若客戶點i由車輛k送貨，則車輛k送完該點的貨后必到達另一點j第12頁，共37頁。六、VRP算法類型及簡要介紹

6、VRP算法類型精確解法啟發(fā)式算法分枝定界法(Branch and Bound Approach)割平面法(Cutting Planes Approach)網(wǎng)絡(luò)流算法(Network Flow Approach)動態(tài)規(guī)劃算法(Dynamic Programming Approach)構(gòu)造算法(Constructive Algorithm )兩階段算法(Two Phase Algorithm)亞啟發(fā)式算法(Metaheuristics Algorithm)第13頁，共37頁。C-W節(jié)約算法算法的思想假定有n個訪問地，把每個訪問地看成一個點，并取其中的一個點作為基點。首先將每個點與基點相聯(lián)接，構(gòu)成線

7、路1j1(j2，3,n)這樣就得到一個具有n-1條線路的圖。旅行者按照此路線訪問的n個點所走的路程總為 z=2c1j ,其中c1j 為點1到點j(j2，3,n)的路段長度，這里假定c1j cj1（對所有點j）。若聯(lián)接點i和j,即使旅行者走弧(i,j),所節(jié)約的路程值(i,j)可計算如下：s(i,j)=2 c1i+2 c1j (c1i + c1j + cij )。對不同的點對s(i,j)越大，所節(jié)約的路程越多，因此應(yīng)優(yōu)先將這段弧插入到旅行線路中。第14頁，共37頁。算法的步驟(1)選取基點，將基點與其他各點聯(lián)接，得到n-1條線路1-j-1(j2，3,n)(2)對不違背條件的所有可聯(lián)接點對(i,j

8、)計算節(jié)約值s(i,j)=c1i + c1j cij(3)將所有的s(i,j)按其值由大到小排列。(4)按s(i,j)值的上述順序，逐個考察其端點i和j，若滿足以下條件，就將弧(i,j)插入到線路中。其條件是：點i和點j不在一條線路上點i和點j均與基點相鄰。(5)返回步驟(4),直至考察完所有的弧為止。 通過上面的步驟，使問題的解逐步得到改善，最后達到滿意解。 C-W節(jié)約算法第15頁，共37頁。y2520151050510152025xABCDEFG各點坐標(biāo)：A(10,23)B(0,13)C(1,0)D(21,2)E(13,4)F(11,6)G(10,10)例：用C-W節(jié)約算法求解下述TSP問

9、題，已知訪問點的位置如下所示第16頁，共37頁。各點坐標(biāo)：A(10,23)B(0,13)C(1,0)D(21,2)E(13,4)F(11,6)G(10,10)2520151050510152025xABCDEFGy第17頁，共37頁。到 從ABCDEFGA014.1424.723.7119.2417.0313.00B013.0423.7115.8113.0410.44C020.1012.6511.6613.45D08.2510.7713.60E02.836.71F04.12G0各點對之間的距離，cij=cji第18頁，共37頁。序號弧節(jié)約值序號弧節(jié)約值1(D,E)34.709(E,G)25.5

10、32(E,F)33.4410(C,G)24.253(C,E)31.2911(D,G)23.114(C,F)30.0712(B,F)18.135(D,F)29.9713(B,E)17.576(C,D)28.3114(B,G)16.707(F,G)25.9115(B,D)14.148(B,C)25.80按各段弧節(jié)約值由大到小的順序進行排列第19頁，共37頁。序號弧線路及說明插入該弧的節(jié)約值0A-B-A,A-C-A,A-D-A,A-E-A,A-F-A,A-G-A1(D,E)A-B-A,A-C-A,A-D-E-A,A-F-A,A-G-A34.702(E,F)A-B-A,A-C-A,A-D-E-F-A,

11、A-G-A33.443(C,E)E點與基點A不相鄰，不插入04(C,F)A-B-A,A-D-E-F-C-A,A-G-A30.075，6(D,F)(C,D)這些點已在同一條線路上07(F,G)F點與基點A不相鄰，不插入08(B,C)A-D-E-F-C-B-A,A-G-A25.89，10(E,G)(C,G)E點、C點與基點A不相鄰，不插入011(D,G)A-G-D-E-F-C-B-A23.11第20頁，共37頁。2520151050510152025xABCDEFGy最后得到的線路為A-G-D-E-F-C-B-A，線路總長度為76.52第21頁，共37頁。插入法算法思想 在已有的路徑中插入別的需求

12、點，從而不斷擴大配送路徑，在插入其他需求點時，需檢驗是否滿足最大運距約束、最大載重量約束和作業(yè)時間約束等條件。算法步驟分別對于每臺配送車輛適當(dāng)選擇客戶群。在配送中心與客戶群之間構(gòu)筑路徑，以此作為初始路徑。對于客戶群之外的客戶k按照適當(dāng)順序，在具有實施可能性而且使總的費用增加最小。 第22頁，共37頁。PiPjP0PkPiPjP0PkCikCkiCij由此帶來的費用：其中 為插入客戶k時，客戶j的等待時間增量第23頁，共37頁。Sweep算法算法思想 顧客點的位置以極坐標(biāo)給出。倉庫假設(shè)在原點的位置，客戶點按照角度的逐步增加被排序，如果兩個點有同樣的角度，那么半徑小的先訪問。然后在滿足可行性條件的

13、前提下,按角度大小歸并到不同的子路徑中,最后再根據(jù)TSP的優(yōu)化算法對所得到的子路徑進行優(yōu)化。算法步驟從倉庫出發(fā)。在目前的車輛路徑中加入目前序號最小的顧客點，如果車輛超載了，選擇一個新的車輛，回到步驟1重復(fù)步驟2直到所有的客戶點都被訪問。構(gòu)造完初始路徑后，通過交換路徑中的節(jié)點來改善調(diào)度。第24頁，共37頁。132456780度第25頁，共37頁。先路徑后分組算法算法思想 先松弛模型中關(guān)于車輛載重和距離等的約束，構(gòu)造一個或幾個很長的路徑，然后把這些很長的線路分解成一些短而可行的線路。算法步驟尋求對于每個節(jié)點通過一次且只通過一次的巡回路徑。在滿足步驟1上的路徑中節(jié)點的連續(xù)性和給定的條件（最大裝載量或

14、最大距離）下進行分組。確定各組需求點的最優(yōu)訪問順序。第26頁，共37頁。 常用的分組方法有集合劃分算法(Set Partitioning Approach)、集合覆蓋算法(Set Covering Approach)、最優(yōu)劃分法(Optimal Partitioning Method)和填充曲線法(Spacefilling Curve Method)第27頁，共37頁。先分組后路徑算法算法思路 這種方法先按節(jié)點和/或弧的要求進行分組或劃群,然后對每一組設(shè)計一條經(jīng)濟的路線。算法步驟先將客戶按其地理位置和需求量合理地分成若干組，每組客戶的需求總量不超過配送車輛的裝載限量。對各組加上倉庫求巡回路徑。

15、第28頁，共37頁。 領(lǐng)域分派法Gillett&Miller的扇形分派法Marchetti&Spaccamela的極線分派法第29頁，共37頁。 領(lǐng)域分派法Karp的矩形分派法Haimovitch&Rinnooy Kan的圓形分派法第30頁，共37頁。近年來關(guān)于VRP的研究國內(nèi)關(guān)于VRP研究的特點是：(1)所研究的問題類型確定性占大多數(shù)。(2)開始使用蟻群算法、粒子群、免疫算法等新的啟發(fā)式算法解決VRP問題。(3)研究具有時間窗約束的VRP。(4)我國開始研究關(guān)于開路式VRP，但是文獻非常少，僅1篇。第31頁，共37頁。近年來關(guān)于VRP的研究國外關(guān)于VRP研究的特點是： 國外對VRP問題研究比國內(nèi)早大約30余年，因此國外關(guān)于VRP問題的文獻相當(dāng)豐富，而且對該問題的研究還有逐年增加的趨勢。國外的VRP研究主要集中在新的約束條件或新的問題實例下VRP的建模及快速求解方法上，來更好的適用于不同的實際情況。 第32頁，共37頁。The EndThank You第33頁，共37頁。depotcustomer第34頁，共37頁。中國郵遞員問題 一名郵遞員帶著要分發(fā)的郵件從郵局出發(fā)，經(jīng)過要分發(fā)的每個街道，送完郵件后又返回郵局如果他必須至少一次走過他管轄范圍內(nèi)的每一條街道，如何選擇投遞路