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

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

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

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

4、性精確算法的局限性 VRP問題的求解方法可分為兩大類，即精確算法和啟發(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)法則，并通過模仿人的跟蹤校正過程來(lái)求得系統(tǒng)的滿意解。 啟發(fā)式算法中最具有代表性的是由Clarke和Wright提出的節(jié)約法（Saving Method）。 8節(jié)約法的基本原

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

7、仍用節(jié)約法求解此類問題的滿意解。求解的過程與例6-1基本相同，只是在方案改進(jìn)的過程中，尋找具有最大節(jié)約量的用戶i、j時(shí)，增加了考慮車輛載重量和可調(diào)度車輛數(shù)的約束，而且，車輛調(diào)度時(shí)優(yōu)先使用載重量大的車輛。 27 例：由配送中心B0向12個(gè)用戶Bj (j=1,2,12)送貨，各點(diǎn)之間的運(yùn)輸里程和各用戶的需求量見表6-1。表6-2為可供調(diào)度的車輛數(shù)目及其載重量。 表表6-1 6-1 各點(diǎn)之間里程表（單位：公里）各點(diǎn)之間里程表（單位：公里） 表表6-2 6-2 可供調(diào)度的汽車可供調(diào)度的汽車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)車單獨(dú)送貨。

10、 根據(jù)以上定義，對(duì)任一用戶j,有以下等式成立：j=1, , n （6.7）30迭代求解：迭代求解： 第一步，求初始解第一步，求初始解 每用戶各派一臺(tái)車單獨(dú)送貨，得初始方案如表64。表中B0列中的數(shù)字為ti,j的取值。此方案的總行程為728公里。 按表64的初始方案，所用汽車臺(tái)數(shù)如表65所列。31 表表6-4 6-4 初始方案初始方案 表表65 65 初始方案所用汽車臺(tái)數(shù)初始方案所用汽車臺(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）考慮車輛臺(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ā)送車，總發(fā)送距離減少92公里。 35 表表6-6 6-6 第一次迭代方案第一次迭代方案 表表6-7 6-7 該方案所用汽車臺(tái)數(shù)該方案所用汽車臺(tái)數(shù)36 重復(fù)第二步，按下述條件在第一次迭代方案表重復(fù)第二步，按下述條件在第一次迭代方案表6 66 6中中尋找具有最大節(jié)約量的用戶尋找具有最大節(jié)約量的

14、用戶i i、j j（1）t0i、t0j0ij；（2）Bi、Bj尚未連接在一條巡回路線上；（3）考慮車輛臺(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)配送車，只需10臺(tái)，其中一臺(tái)為5噸車；總發(fā)送距離比前一方案減少84公里。 39 表6-8 第二次迭代方案 表6-9 該方案所用汽車臺(tái)數(shù)該方案所用汽車臺(tái)數(shù)40 表表6-10 6-10 第三次迭代方案第三次迭代方案 表表6-1

16、1 6-11 該方案所用汽車臺(tái)數(shù)該方案所用汽車臺(tái)數(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 該方案所用汽車臺(tái)數(shù)該方案所用汽車臺(tái)數(shù)43 表表6-14 6-14 第五次迭代方案第五次迭代方案 表表6-15 6-15 該方案所用汽車臺(tái)數(shù)該方案所用汽車臺(tái)數(shù)44得到二條配送路線：B0B6B8B9B

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

18、，載重5.8噸；滿意方案共用四臺(tái)車配送，總行程290公里。47第三節(jié)第三節(jié) 多中心配送路線選擇與車輛調(diào)度多中心配送路線選擇與車輛調(diào)度 一、制定多中心配送方案的基本思想一、制定多中心配送方案的基本思想 多中心配送與單中心配送不同的是，制定配送計(jì)劃時(shí)，不僅要選擇配送路線和調(diào)度車輛，還要確定各配送中心所服務(wù)的用戶對(duì)象。 所以，制定多中心配送的配送計(jì)劃，首先將所有用戶按一定的方法分派給各配送中心，形成每個(gè)配送中心的服務(wù)區(qū)，然后用上一節(jié)討論的節(jié)約法在各配送中心的服務(wù)區(qū)選擇配送路線和調(diào)度車輛。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)。 顯然，通過改變值的大小可以控制邊界點(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ú)派車配送，構(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