第六章配送路線選擇與車輛調度-徐天亮

1、1第六章第六章 配送路線選擇與車輛調度配送路線選擇與車輛調度主要內容：主要內容：u配送路線安排與車輛調度問題及節(jié)約法原理； u單中心配送路線選擇與車輛調度；u多中心配送路線選擇與車輛調度；u貨車配載 。2第一節(jié)第一節(jié) 配送路線安排與車輛調度問題配送路線安排與車輛調度問題及節(jié)約法原理及節(jié)約法原理 一、配送路線安排與車輛調度問題一、配送路線安排與車輛調度問題 配送路線安排與車輛優(yōu)化調度問題常被分為車輛路線安排問題（Vehicle Routing Problem，簡記VRP）和車輛調度問題（Vehicle Scheduling Problem，簡記VSP），前者僅從空間位置考慮車輛路線的安排和車輛調

2、度，后者則要考慮時間要求。顯然VSP問題比VRP 問題討論的范圍寬，或者說，VSP問題是有時間約束的VRP 問題。本書主要討論VRP問題。3 VRP VRP問題的描述問題的描述 VRP問題一般可描述為：對一系列裝貨點或（和）卸貨點，組織適當合理的行車路線，使車輛有序地通過它們，在滿足一定的約束（如貨物需求量、發(fā)送量，車輛容量、數(shù)目限制、車輛行駛里程限制等）條件下，達到一定的目標（如最短路程、最小費用、最短時間、最少車輛等）。 4 VRP VRP問題的分類問題的分類 VRP問題又根據(jù)不同標準分為：車輛滿載問題（一個用戶的貨運量大于一輛車的容量，完成任務需要多輛車）與非滿載問題（一個用戶的貨運量不

3、大于一輛車的容量，完成任務只需要一輛車）、單車場問題（一個貨場或一個配送中心）與多車場問題（多個貨場或多個配送中心）、單車型（所有車輛容量相同）與多車型問題（車輛容量不全相同），以及優(yōu)化目標的單目標與多目標問題。 5 二、二、VRPVRP問題精確求解方法的局限性問題精確求解方法的局限性 1. VRP1. VRP問題求解思路問題求解思路 VRP問題的求解方法一般相當復雜，通常的做法是應用相關技術將問題分解或者轉化為一個或多個已經研究過的基本問題（如旅行商問題、指派問題、運輸問題、最短路問題、最小費用流問題、中國郵遞員問題等），再使用相對比較成熟的基本理論和方法進行求解。6 2.2.精確算法的局限

4、性精確算法的局限性 VRP問題的求解方法可分為兩大類，即精確算法和啟發(fā)式算法。精確算法主要有分枝定界法、割平面法、網絡流算法、動態(tài)規(guī)劃方法等。精確算法隨著配送系統(tǒng)規(guī)模的增大，其計算量呈指數(shù)遞增，使得獲取系統(tǒng)最優(yōu)解越來越困難。因此，精確算法在實際應用中受到很大的局限。7 三、節(jié)約法原理三、節(jié)約法原理 為了克服精確優(yōu)化方法的不足，人們提出了許多能獲得“滿意”解的啟發(fā)式算法。啟發(fā)式算法是一種基于直觀或經驗構造的算法，它運用一些經驗法則，并通過模仿人的跟蹤校正過程來求得系統(tǒng)的滿意解。 啟發(fā)式算法中最具有代表性的是由Clarke和Wright提出的節(jié)約法（Saving Method）。 8節(jié)約法的基本原

5、理：節(jié)約法的基本原理： 91011第二節(jié)第二節(jié) 單中心配送路線選擇與車輛調度單中心配送路線選擇與車輛調度12 如果將配送中心也作為一個用戶點，貨車從配送中心出發(fā)，對所有用戶巡回送貨后回到配送中心，這樣就把單車非滿載車輛的配送路線安排問題轉化為個點的旅行商問題（Traveling Salesman Problem，簡記TSP）。它的解是：從配送中心出發(fā)，對所有用戶巡回一次回到配送中心的距離最短的路線。 1314151617181920t t0606+t+t1616+t+t2626+t+t3636+t+t4646+t+t5656+t+t7676=2;=2;因此如果因此如果t67=t76=1,t67

6、=t76=1,則則t06=1t06=1含義就是配送第含義就是配送第6 6個客戶的車輛不是完成任務直接返回中心了。個客戶的車輛不是完成任務直接返回中心了。t t0707+t+t1717+t+t2727+t+t3737+t+t4747+t+t5757+t+t6767=2;=2;因此如果因此如果t67=t76=1,t67=t76=1,則則t07=1t07=1含義就是配送第含義就是配送第7 7個客戶的車輛不是完成任務直接返回中心了。個客戶的車輛不是完成任務直接返回中心了。212223二、多車非滿載配送路線安排與車輛調度二、多車非滿載配送路線安排與車輛調度242526 此模型用精確算法求解更加困難，下面

7、仍用節(jié)約法求解此類問題的滿意解。求解的過程與例6-1基本相同，只是在方案改進的過程中，尋找具有最大節(jié)約量的用戶i、j時，增加了考慮車輛載重量和可調度車輛數(shù)的約束，而且，車輛調度時優(yōu)先使用載重量大的車輛。 27 例：由配送中心B0向12個用戶Bj (j=1,2,12)送貨，各點之間的運輸里程和各用戶的需求量見表6-1。表6-2為可供調度的車輛數(shù)目及其載重量。 表表6-1 6-1 各點之間里程表（單位：公里）各點之間里程表（單位：公里） 表表6-2 6-2 可供調度的汽車可供調度的汽車28 解：由表6-1中的數(shù)據(jù)，按節(jié)約量公式（6.5）計算每兩用戶之間的節(jié)約量Si,ji,j 列于表6-3，稱節(jié)約量

8、表。 表表6-3 6-3 節(jié)約量表（單位：公里）節(jié)約量表（單位：公里）bj B0 1.2 B1 1.7 18 B2 1.5 18 28 B3 1.4 10 20 34 B4 1.7 10 20 22 26 B5 1.4 10 16 16 20 38 B6 1.2 10 20 26 30 44 50 B7 1.9 10 20 20 24 42 50 58 B8 1.8 10 16 16 20 38 50 54 68 B9 1.6 10 20 32 36 44 50 64 72 68 B10 1.7 10 20 34 42 44 50 64 72 76 84 B11 1.1 10 20 34 46

9、 44 50 64 72 70 84 92 B12 如如: :S S1,21,2d d0,10,1+ +d d0,20,2d d1,2 1,2 9 914145 5 1818 S S2,42,4d d0,20,2+ +d d0,40,4d d2,4 2,4 141423231717 202029 設ti,j(i=0,1,12; j=1,2,12；ij )表示i、j兩點是否連接在一起的決策變量，并對其取值作如下定義： ti,j=1 表示i、j用戶連接，即在同一巡回路線中； ti,j=0 表示i、j用戶不連接，即不在同一巡回路線中； t0,j=2 表示j用戶只與配送中心B。連接，由一臺車單獨送貨。

10、 根據(jù)以上定義，對任一用戶j,有以下等式成立：j=1, , n （6.7）30迭代求解：迭代求解： 第一步，求初始解第一步，求初始解 每用戶各派一臺車單獨送貨，得初始方案如表64。表中B0列中的數(shù)字為ti,j的取值。此方案的總行程為728公里。 按表64的初始方案，所用汽車臺數(shù)如表65所列。31 表表6-4 6-4 初始方案初始方案 表表65 65 初始方案所用汽車臺數(shù)初始方案所用汽車臺數(shù)bj B0 1.2 2) B1 1.7 2) 18 B2 1.5 2) 18 28 B3 1.4 2) 10 20 34 B4 1.7 2) 10 20 22 26 B5 1.4 2) 10 16 16 20

11、 38 B6 1.2 2) 10 20 26 30 44 50 B7 1.9 2) 10 20 20 24 42 50 58 B8 1.8 2) 10 16 16 20 38 50 54 68 B9 1.6 2) 10 20 32 36 44 50 64 72 68 B10 1.7 2) 10 20 34 42 44 50 64 72 76 84 B11 1.1 2) 10 20 34 46 44 50 64 72 70 84 92 B12 32 第二步，按下述條件在初始方案表中尋找具有第二步，按下述條件在初始方案表中尋找具有最大節(jié)約量的用戶最大節(jié)約量的用戶i i、j j（1）t0,i、t0,

12、j0ij；（2）Bi、Bj尚未連接在一條巡回路線中；（3）考慮車輛臺數(shù)和載重量的約束。 如果最大節(jié)約量有兩個或兩個以上相同時，可隨機取一個。 按此條件，在初始方案表64中尋到具有最大節(jié)約量的一對用戶為：i=11,j=12，其節(jié)約量為92公里。將11和12兩用戶連接到一個運輸回路中，并在對應的格中記上t11,12的值，用“1）”表示。33 第三步，按第三步，按t ti,ji,j的定義和公式的定義和公式6767修正修正t ti,ji,j的值。的值。 B11與B12連接，即令t11,12=1，由公式（6.7）得： t0,11=1 t0,12=1 其他不變。34第四步，按以下原則修正第四步，按以下原則

13、修正b bi i、b bj j （1）t0,i或t0,j等于0時，令bi或bj等于0； （2）t0,i或t0,j等于1時，令bi或bj等于所在巡回路線中所有用戶需求量之和，以此代替原bi或bj,因此 b11=b12=1.1+1.7=2.8（噸） 得改進方案（表6-6、表6-7）。 改進后的方案比原方案少一臺發(fā)送車，總發(fā)送距離減少92公里。 35 表表6-6 6-6 第一次迭代方案第一次迭代方案 表表6-7 6-7 該方案所用汽車臺數(shù)該方案所用汽車臺數(shù)36 重復第二步，按下述條件在第一次迭代方案表重復第二步，按下述條件在第一次迭代方案表6 66 6中中尋找具有最大節(jié)約量的用戶尋找具有最大節(jié)約量的

14、用戶i i、j j（1）t0i、t0j0ij；（2）Bi、Bj尚未連接在一條巡回路線上；（3）考慮車輛臺數(shù)和載重量的約束。 如果最大節(jié)約量有兩個或兩個以上相同時，可隨機取一個。 按此條件，在表66中尋得具有最大節(jié)約量的用戶有兩對，分別為：i=10,j=11和i=10,j=12 ，其節(jié)約量均為84公里，任取一對i=10, j=11，將其連接到一個回路中。37 重復第三步，按第三步，按t ti,ji,j的定義和公式（的定義和公式（6.76.7）修正）修正t ti,ji,j的值。的值。 B10與B11連接，則t10,11=1，由公式（6.7）得： t0,11=0 t0,10=1 其他不變。38重復第

15、四步，按以下原則修正重復第四步，按以下原則修正b bi i、b bj j （1）t0,i或t0,j等于0時，令bi或bj等于0； （2）t0,i或t0,j等于1時，令bi或bj等于所在巡回路線中所有用戶需求量之和，以此代替原bi或bj,因此 b10=b12=2.81.6=4.4（噸） b11=0 得第二次迭代方案（表6-8、表6-9）。 第二次迭代方案比第一次迭代方案又少一臺配送車，只需10臺，其中一臺為5噸車；總發(fā)送距離比前一方案減少84公里。 39 表6-8 第二次迭代方案 表6-9 該方案所用汽車臺數(shù)該方案所用汽車臺數(shù)40 表表6-10 6-10 第三次迭代方案第三次迭代方案 表表6-1

16、1 6-11 該方案所用汽車臺數(shù)該方案所用汽車臺數(shù) 為什么不選為什么不選B B1010B B9 9、B B1010B B8 8？ 可否將可否將B B1111與與B B7 7連連接？接？41得到第一條配送路線：B0B7B10B11B12B0，行程112公里，用6噸車配送，載重5.6噸；開始下一條配送路線的選擇，過程如何？42 表表6-12 6-12 第四次迭代方案第四次迭代方案 表表6-13 6-13 該方案所用汽車臺數(shù)該方案所用汽車臺數(shù)43 表表6-14 6-14 第五次迭代方案第五次迭代方案 表表6-15 6-15 該方案所用汽車臺數(shù)該方案所用汽車臺數(shù)44得到二條配送路線：B0B6B8B9B

17、0，行程80公里，用6噸車配送，載重5.1噸；再開始下一條配送路線的選擇，過程與前相同。45 反復進行第二第四步，直至沒有可連接的用戶時為止，得最終滿意配送方案如表6-16，表6-17。 表表6-16 6-16 滿意配送方案滿意配送方案 表表6-17 6-17 最終方案所用汽車臺數(shù)最終方案所用汽車臺數(shù)46 滿意配送方案有四條配送路線，它們是： B0B7B10B11B12B0，行程112公里，用6噸車配送，載重5.6噸； B0B6B8B9B0，行程80公里，用6噸車配送，載重5.1噸； B0B5B0，行程44公里，用4噸車配送，載重1.7噸； B0B1B2B3B4B0，行程54公里，用6噸車配送

18、，載重5.8噸；滿意方案共用四臺車配送，總行程290公里。47第三節(jié)第三節(jié) 多中心配送路線選擇與車輛調度多中心配送路線選擇與車輛調度 一、制定多中心配送方案的基本思想一、制定多中心配送方案的基本思想 多中心配送與單中心配送不同的是，制定配送計劃時，不僅要選擇配送路線和調度車輛，還要確定各配送中心所服務的用戶對象。 所以，制定多中心配送的配送計劃，首先將所有用戶按一定的方法分派給各配送中心，形成每個配送中心的服務區(qū)，然后用上一節(jié)討論的節(jié)約法在各配送中心的服務區(qū)選擇配送路線和調度車輛。48 二、制定多中心配送方案的邊界點方法二、制定多中心配送方案的邊界點方法 1.1.邊界點與非邊界點邊界點與非邊界

19、點 設di(t)表示用戶i與配送中心t之間的距離，記集合 ，p是配送中心的個數(shù)。計算 ，minDi和subminDi分別表示集合Di中的最小值和次小值；取適當?shù)模? 1），比較r(i)與的大小，當r(i)，稱i為非邊界點，否則為邊界點。 顯然，通過改變值的大小可以控制邊界點的個數(shù)。 iiDsubDirmin/min)( ),.,1),(pttdDii 49 2.2.非邊界點的分派非邊界點的分派 對非邊界點，按最近分派原則，將它們分別分派給離它們最近的配送中心。50 3. 3.邊界點的分派邊界點的分派 對邊界點的分派，按r(i)1 和r(i)=1 兩種情況分別處理。 （1）當r(i)1時，用節(jié)約

20、法進行分派。 首先考慮由最近的配送中心對每個點單獨派車配送，構成初始解。一旦兩個點或多個點已被分派給同一個配送中心時，這些點為永久分派，不能再分派給其他配送中心；如果i，j不在同一配送中心，按一般節(jié)約法將其連接并分別試分配給某一配送中心，連接產生的節(jié)約量按下式（6.8）計算。 51式中： 選 最大者，將i,j分派給對應的t。 iiitiDtdDdminmin2)(/ jjjtjDtdDdminmin2)(/j點還未給一永久分派，挪到非最近配點還未給一永久分派，挪到非最近配送中心送中心否則否則 i點還未給一永久分派，挪到非最近配送點還未給一永久分派，挪到非最近配送中心中心否則否則 52 （2）當r(i)=1時，按如下方法分派。 將i分別試分派給各配送中心t（t1，p)，若j和k是已分派給配送中心t的用戶，將點i插入用戶j與k之間；若t中心只有一個用戶j，則將i插入j與t之間。對配送中心t產生的運輸距離增加量按（6.9）式計算。 按增加量最小原則，將用戶i分派給使djik(t)或dij(t)最小的配送中心。（6.9）用戶時）中心只有（用戶時）用戶和中心已有（jtdddtdkjtdddtdjtitji