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

1、1,第六章 配送路線選擇與車(chē)輛調(diào)度,主要內(nèi)容： 配送路線安排與車(chē)輛調(diào)度問(wèn)題及節(jié)約法原理； 單中心配送路線選擇與車(chē)輛調(diào)度； 多中心配送路線選擇與車(chē)輛調(diào)度； 貨車(chē)配載 。,2,第一節(jié) 配送路線安排與車(chē)輛調(diào)度問(wèn)題及節(jié)約法原理,一、配送路線安排與車(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)度，后者則要考慮時(shí)間要求。顯然VSP問(wèn)題比VRP 問(wèn)題討論的范圍寬，或者說(shuō)，VSP問(wèn)題是有時(shí)間約束的VRP

2、 問(wèn)題。本書(shū)主要討論VRP問(wèn)題。,3,VRP問(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問(wèn)題的分類,VRP問(wèn)題又根據(jù)不同標(biāo)準(zhǔn)分為：車(chē)輛滿載問(wèn)題（一個(gè)用戶的貨運(yùn)量大于一輛車(chē)的容量，完成任務(wù)需要多輛車(chē)）與非滿載問(wèn)題（一個(gè)用戶的貨運(yùn)量不大于一輛車(chē)的容量，完成任務(wù)只需要一輛車(chē)）、單車(chē)場(chǎng)問(wèn)題（一個(gè)貨場(chǎng)或一個(gè)配送中心）與多車(chē)場(chǎng)問(wèn)題（多個(gè)貨場(chǎng)或多個(gè)配送中心）、單車(chē)型（所有車(chē)輛容量相

3、同）與多車(chē)型問(wèn)題（車(chē)輛容量不全相同），以及優(yōu)化目標(biāo)的單目標(biāo)與多目標(biāo)問(wèn)題。,5,二、VRP問(wèn)題精確求解方法的局限性,1. VRP問(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.精確算法的局限性,VRP問(wèn)題的求解方法可分為兩大類，即精確算法和啟發(fā)式算法。精確算法主要有分枝定界法、割平面法、網(wǎng)絡(luò)流算法、動(dòng)態(tài)規(guī)劃方法等。精確算法隨著配送系統(tǒng)規(guī)模的增大，其計(jì)算量呈指數(shù)遞增，使得獲取系統(tǒng)最優(yōu)解越來(lái)

4、越困難。因此，精確算法在實(shí)際應(yīng)用中受到很大的局限。,7,三、節(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é)約法的基本原理：,9,10,11,第二節(jié) 單中心配送路線選擇與車(chē)輛調(diào)度,12,如果將配送中心也作為一個(gè)用戶點(diǎn)，貨車(chē)從配送中心出發(fā)，對(duì)所有用戶巡回送貨后回到配送中心，這樣就把單車(chē)非滿載車(chē)輛的配送路線安排問(wèn)題轉(zhuǎn)化為個(gè)點(diǎn)的旅行商問(wèn)題（Trave

5、ling Salesman Problem，簡(jiǎn)記TSP）。它的解是：從配送中心出發(fā)，對(duì)所有用戶巡回一次回到配送中心的距離最短的路線。,13,14,15,16,17,18,19,20,t06+t16+t26+t36+t46+t56+t76=2;因此如果t67=t76=1,則t06=1 含義就是配送第6個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。 t07+t17+t27+t37+t47+t57+t67=2;因此如果t67=t76=1,則t07=1 含義就是配送第7個(gè)客戶的車(chē)輛不是完成任務(wù)直接返回中心了。,21,22,23,二、多車(chē)非滿載配送路線安排與車(chē)輛調(diào)度,24,25,26,此模型用精確算法求解更加

6、困難，下面仍用節(jié)約法求解此類問(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 各點(diǎn)之間里程表（單位：公里） 表6-2 可供調(diào)度的汽車(chē),28,解：由表6-1中的數(shù)據(jù)，按節(jié)約量公式（6.5）計(jì)算每?jī)捎脩糁g的節(jié)約量Si,j 列于表6-3，稱節(jié)約量表。,表6-3 節(jié)約量表（單位：公里）,如:S1,2d0

7、,1+d0,2d1,2 9145 18,S2,4d0,2+d0,4d2,4 142317 20,29,設(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ú)送貨。 根據(jù)以上定義，對(duì)任一用戶j,有以下等式成立：,j=1, , n （6.7）,30,迭代求解：,第一步，求初始解 每用戶各派一臺(tái)車(chē)單獨(dú)送貨，得初始方案如表64。表中B0列中的數(shù)字為ti,j的取值。

8、此方案的總行程為728公里。 按表64的初始方案，所用汽車(chē)臺(tái)數(shù)如表65所列。,31,表6-4 初始方案 表65 初始方案所用汽車(chē)臺(tái)數(shù),32,第二步，按下述條件在初始方案表中尋找具有最大節(jié)約量的用戶i、j,（1）t0,i、t0,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,第三步，按ti,j的定義和公

9、式67修正ti,j的值。,B11與B12連接，即令t11,12=1，由公式（6.7）得： t0,11=1 t0,12=1 其他不變。,34,第四步，按以下原則修正bi、bj,（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-7 該方案所用汽車(chē)臺(tái)數(shù),36,重復(fù)第二步，按下述條件在第一次迭代方案表66中尋

10、找具有最大節(jié)約量的用戶i、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ù)第三步，按ti,j的定義和公式（6.7）修正ti,j的值。,B10與B11連接，則t10,11=1，由公式（6.7）得： t0,11=0 t0,10=1 其他不變。,38,重復(fù)第四步，按以下原則修正bi、bj,（1）t

11、0,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ù),40,表6-10 第三次迭代方案 表6-11 該方案所用汽車(chē)臺(tái)數(shù),為什么不選B10B9、B10B8？,可否將B11與B7連接？,41,得到第一條配送路線：B0B7B10

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

13、0，行程112公里，用6噸車(chē)配送，載重5.6噸； B0B6B8B9B0，行程80公里，用6噸車(chē)配送，載重5.1噸； B0B5B0，行程44公里，用4噸車(chē)配送，載重1.7噸； B0B1B2B3B4B0，行程54公里，用6噸車(chē)配送，載重5.8噸； 滿意方案共用四臺(tái)車(chē)配送，總行程290公里。,47,第三節(jié) 多中心配送路線選擇與車(chē)輛調(diào)度,一、制定多中心配送方案的基本思想 多中心配送與單中心配送不同的是，制定配送計(jì)劃時(shí)，不僅要選擇配送路線和調(diào)度車(chē)輛，還要確定各配送中心所服務(wù)的用戶對(duì)象。 所以，制定多中心配送的配送計(jì)劃，首先將所有用戶按一定的方法分派給各配送中心，形成每個(gè)配送中心的服務(wù)區(qū)，然后用上一節(jié)討論

14、的節(jié)約法在各配送中心的服務(wù)區(qū)選擇配送路線和調(diào)度車(chē)輛。,48,二、制定多中心配送方案的邊界點(diǎn)方法,1.邊界點(diǎn)與非邊界點(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ù)。,49,2.非邊界點(diǎn)的分派,對(duì)非邊界點(diǎn)，按最近分派原則，將它們分別分派給離它們最近的配送中心。,50,3.邊界點(diǎn)的分派,對(duì)邊界點(diǎn)的分派，按r(i)1 和r(i)=1 兩種情況分別處理。 （1）當(dāng)r(i)1

15、時(shí)，用節(jié)約法進(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。,j點(diǎn)還未給一永久分派，挪到非最近配送中心 否則,i點(diǎn)還未給一永久分派，挪到非最近配送中心 否則,52,（2）當(dāng)r(i)=1時(shí)，按如下方法分派。 將i分別試分派給各配送中心t（t1，p)，若j和k是已分派給配送中心t的用戶，將點(diǎn)i插入用戶j與k之間；若t中心只有

16、一個(gè)用戶j，則將i插入j與t之間。對(duì)配送中心t產(chǎn)生的運(yùn)輸距離增加量按（6.9）式計(jì)算。 按增加量最小原則，將用戶i分派給使djik(t)或dij(t)最小的配送中心。,（6.9）,53,對(duì)所有用戶分派完畢后，分別在每個(gè)配送中心的服務(wù)區(qū)域內(nèi)，用節(jié)約法確定配送路線和進(jìn)行車(chē)輛調(diào)度，得到各配送中心的配送計(jì)劃。,54,例：假設(shè)有三個(gè)配送中心（編號(hào)是1,2,3）給10個(gè)用戶（編號(hào)是4,13）配送貨物。配送中心與用戶以及用戶與用戶之間的運(yùn)輸距離如表6-18。,表6-18配送中心及用戶之間的距離（單位：公里）,55,計(jì)算r(i)，得表6-19。 表6-19 r(i)數(shù)值表,56,取=0.7,所有r(i)的用戶分派給最近的配送中心，如表6-20。 表6-20非邊界點(diǎn)用戶分派表,57,對(duì)r(i)且r(i)1的點(diǎn)8，10和12，根據(jù)式（6.8）計(jì)算 (i,j=8,10,12;t=1,2,3)，并按從大到小的順序排列，列于表6-21。 表6-21 r(i)1的邊界點(diǎn)用