第六章配送路線選擇與車(chē)輛調(diào)度-徐天亮

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

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

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

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

5、理：節(jié)約法的基本原理： 91011第二節(jié)第二節(jié) 單中心配送路線選擇與車(chē)輛調(diào)度單中心配送路線選擇與車(chē)輛調(diào)度12 如果將配送中心也作為一個(gè)用戶點(diǎn)，貨車(chē)從配送中心出發(fā)，對(duì)所有用戶巡回送貨后回到配送中心，這樣就把單車(chē)非滿載車(chē)輛的配送路線安排問(wèn)題轉(zhuǎn)化為個(gè)點(diǎn)的旅行商問(wèn)題（Traveling Salesman Problem，簡(jiǎn)記TSP）。它的解是：從配送中心出發(fā)，對(duì)所有用戶巡回一次回到配送中心的距離最短的路線。 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個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。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個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。212223二、多車(chē)非滿載配送路線安排與車(chē)輛調(diào)度二、多車(chē)非滿載配送路線安排與車(chē)輛調(diào)度242526 此模型用精確算法求解更加困難，下面

7、仍用節(jié)約法求解此類(lèi)問(wèn)題的滿意解。求解的過(guò)程與例6-1基本相同，只是在方案改進(jìn)的過(guò)程中，尋找具有最大節(jié)約量的用戶i、j時(shí)，增加了考慮車(chē)輛載重量和可調(diào)度車(chē)輛數(shù)的約束，而且，車(chē)輛調(diào)度時(shí)優(yōu)先使用載重量大的車(chē)輛。 27 例：由配送中心B0向12個(gè)用戶Bj (j=1,2,12)送貨，各點(diǎn)之間的運(yùn)輸里程和各用戶的需求量見(jiàn)表6-1。表6-2為可供調(diào)度的車(chē)輛數(shù)目及其載重量。 表表6-1 6-1 各點(diǎn)之間里程表（單位：公里）各點(diǎn)之間里程表（單位：公里） 表表6-2 6-2 可供調(diào)度的汽車(chē)可供調(diào)度的汽車(chē)28 解：由表6-1中的數(shù)據(jù)，按節(jié)約量公式（6.5）計(jì)算每?jī)捎脩糁g的節(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 設(shè)ti,j(i=0,1,12; j=1,2,12；ij )表示i、j兩點(diǎn)是否連接在一起的決策變量，并對(duì)其取值作如下定義： ti,j=1 表示i、j用戶連接，即在同一巡回路線中； ti,j=0 表示i、j用戶不連接，即不在同一巡回路線中； t0,j=2 表示j用戶只與配送中心B。連接，由一臺(tái)車(chē)單獨(dú)送貨。

10、 根據(jù)以上定義，對(duì)任一用戶j,有以下等式成立：j=1, , n （6.7）30迭代求解：迭代求解： 第一步，求初始解第一步，求初始解 每用戶各派一臺(tái)車(chē)單獨(dú)送貨，得初始方案如表64。表中B0列中的數(shù)字為ti,j的取值。此方案的總行程為728公里。 按表64的初始方案，所用汽車(chē)臺(tái)數(shù)如表65所列。31 表表6-4 6-4 初始方案初始方案 表表65 65 初始方案所用汽車(chē)臺(tái)數(shù)初始方案所用汽車(chē)臺(tái)數(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）考慮車(chē)輛臺(tái)數(shù)和載重量的約束。 如果最大節(jié)約量有兩個(gè)或兩個(gè)以上相同時(shí)，可隨機(jī)取一個(gè)。 按此條件，在初始方案表64中尋到具有最大節(jié)約量的一對(duì)用戶為：i=11,j=12，其節(jié)約量為92公里。將11和12兩用戶連接到一個(gè)運(yùn)輸回路中，并在對(duì)應(yīng)的格中記上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時(shí)，令bi或bj等于0； （2）t0,i或t0,j等于1時(shí)，令bi或bj等于所在巡回路線中所有用戶需求量之和，以此代替原bi或bj,因此 b11=b12=1.1+1.7=2.8（噸） 得改進(jìn)方案（表6-6、表6-7）。 改進(jìn)后的方案比原方案少一臺(tái)發(fā)送車(chē)，總發(fā)送距離減少92公里。 35 表表6-6 6-6 第一次迭代方案第一次迭代方案 表表6-7 6-7 該方案所用汽車(chē)臺(tái)數(shù)該方案所用汽車(chē)臺(tái)數(shù)36 重復(fù)第二步，按下述條件在第一次迭代方案表重復(fù)第二步，按下述條件在第一次迭代方案表6 66 6中中尋找具有最大節(jié)約量的用戶尋找具有最大節(jié)約量的

14、用戶i i、j j（1）t0i、t0j0ij；（2）Bi、Bj尚未連接在一條巡回路線上；（3）考慮車(chē)輛臺(tái)數(shù)和載重量的約束。 如果最大節(jié)約量有兩個(gè)或兩個(gè)以上相同時(shí)，可隨機(jī)取一個(gè)。 按此條件，在表66中尋得具有最大節(jié)約量的用戶有兩對(duì)，分別為：i=10,j=11和i=10,j=12 ，其節(jié)約量均為84公里，任取一對(duì)i=10, j=11，將其連接到一個(gè)回路中。37 重復(fù)第三步，按第三步，按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重復(fù)第

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

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

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

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

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

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