物流工程——節(jié)約里程法

1、物流配送節(jié)約里程法(saving algorithm) 車輛調(diào)度程序法(vehicle scheduling program:vsp) 又稱節(jié)約算法，是指用來解決運(yùn)輸車輛數(shù)目不確定的問題的最有名的啟發(fā)式算法。 核心思想: 節(jié)約里程法核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。節(jié)約里程法 利用節(jié)約法制定出的配送方案除了使配送總噸公里數(shù)最小外，還應(yīng)滿足以下條件： 滿足所有用戶的需求不使任何一輛車超載每輛車每天的總運(yùn)行時(shí)間或行駛里程不超過規(guī)定的上限；用戶到貨時(shí)間要求。

2、不得超過規(guī)定時(shí)間。節(jié)約里程法pa（客戶）b（客戶）ab(配送中心)p a（客戶）b（客戶）(配送中心)bac運(yùn)行距離為：2a+2b運(yùn)行距離為：a+b+c節(jié)約行程：節(jié)約行程：a + bc節(jié)約里程法例題：已知配送中心p0向5個(gè)用戶pj配送貨物，其配送路線網(wǎng)絡(luò)、配送中心與用戶的距離以及用戶之間的距離如下圖所示，配送中心有3臺(tái)2t卡車和2臺(tái)4t兩種車輛可供使用。利用節(jié)約里程法制定最優(yōu)的配送方案。(1.4)p0p2p3p4p5p1( 2.4 )( 0.9 )(1.7）(1.5 )101275124136812168節(jié)約里程法 第第1 1 步：作運(yùn)輸里程表，列出配送中心到用戶步：作運(yùn)輸里程表，列出配送中心

3、到用戶及用戶間的最短距離。及用戶間的最短距離。需求量p0p11.58p1p21.7812p2p30.96134p3p41.471595p4p52.41016181612p5節(jié)約里程法第第2 2步：按節(jié)約里程公式求得相應(yīng)的節(jié)約里程數(shù)步：按節(jié)約里程公式求得相應(yīng)的節(jié)約里程數(shù)需求量p01.58p11.7812p240.96134p31101.471595p40682.41016181612p52005如：p0 p1+ p0p2 -p1p2 =8+8 -12 =4節(jié)約里程法第第 3 步：將節(jié)約里程按從大到小順序排列步：將節(jié)約里程按從大到小順序排列序號(hào)路線節(jié)約里程1p2p3102p3p483p2p464p

4、4p555p1p246p1p527p1p318p2p509p3p5010p1p40節(jié)約里程法第第4 4步：根據(jù)載重量約束與節(jié)約里程大小，順序連接各客戶步：根據(jù)載重量約束與節(jié)約里程大小，順序連接各客戶結(jié)點(diǎn)結(jié)點(diǎn), ,形成二個(gè)配送路線形成二個(gè)配送路線 . .（1.4）p0p2p3p4p5p1（2.4）（0.9）（1.7）(1.5)10768845優(yōu)先考慮節(jié)約里程最大的路線，以此類推，如果前面涉及了某些路線，往后就考慮未涉及的路線p2p3-p3p4-p1p5節(jié)約里程法（1.4）p0p2p3p4p5p1（2.4）（0.9）（1.7）(1.5)1078845配送線路1節(jié)約里程法（1.4）p0p2p3p4p

5、5p1（2.4）（0.9）（1.7）(1.5)1078845配送線路1配送線路1： 運(yùn)量 = 1.7+0.9+1.4= 4t 運(yùn)行距離845724km 用一輛 4t車運(yùn)送節(jié)約距離 =18km（即2*21-24） 配送線路2: 運(yùn)量=2.4+1.5=3.9t4t 運(yùn)行距離8101634km 用一輛 4t車運(yùn)送 節(jié)約距離=2km（即2*18-34）節(jié)約里程法（1.4）p0p2p3p4p5p1（2.4）（0.9）（1.7）(1.5)107688初始方案：配送線路5條， 需要車5輛 配送距離=392=78km 節(jié)約里程法 初始方案：初始方案： 配送線路配送線路5 5條，條， 需要車需要車5 5輛輛 配

6、送距離：配送距離：39392=78km2=78km 優(yōu)化后的方案：優(yōu)化后的方案： 2 2條配送線路，條配送線路，2 2輛輛4t4t車車 配送距離：配送距離：2424343458km58km節(jié)約里程法案例：寶潔公司是廣州配送中心最大的服務(wù)商,為其配送的客戶和貨量見下表,我們以廣州配送中心為例來說明有裝載限制的車輛調(diào)度的優(yōu)化方法。公司客戶分布在全國各地,這里主要以廣東省內(nèi)7家客戶及省外一家特殊客戶的一次配送為例?？蛻艨蛻?i)東莞東莞江門江門惠州惠州陽江陽江汕尾汕尾揭陽揭陽汕頭汕頭漳州漳州貨運(yùn)量(qi)4.31.80.72.23.63.61.62節(jié)約里程法 廣州配送中心為這次配送提供了三種車型,載

7、重量分別為2噸、5噸和8噸,不同車型的運(yùn)輸單價(jià)不一樣,具體見運(yùn)輸單價(jià)表。配送中心的配送是由外協(xié)商提供車輛,因此汽車的數(shù)量沒有限制 車輛載重 2t5t 8t 運(yùn)價(jià)(元/公里)2.42.73.65節(jié)約里程法2.步驟第一步:各城市之間的距離：節(jié)約里程法第二步:計(jì)算連接城市到同一線路上的距離節(jié)約值節(jié)約里程法第三步:確定初始方案的運(yùn)輸線路及運(yùn)輸費(fèi)用,現(xiàn)安排4輛2噸、4輛5噸的車給每個(gè)客戶送貨。運(yùn)輸線路及運(yùn)輸費(fèi)用見下表所示。節(jié)約里程法第四步:進(jìn)行線路第一次優(yōu)化。節(jié)約里程法第一次修改后的車輛調(diào)度結(jié)果：節(jié)約里程法第五步:繼續(xù)進(jìn)行線路優(yōu)化。節(jié)約里程法第二次修改后的車輛調(diào)度結(jié)果：節(jié)約里程法節(jié)約里程法 從表中可以看

8、出,廣州-惠州-揭陽-汕頭-漳州路線上的總貨運(yùn)量達(dá)到7.9噸,再連接任何一個(gè)城市都將使貨運(yùn)量超過最高限制(8噸),則不能繼續(xù)配載,所以可以首先確定的是這一條線路。然后在剩下的東莞、江門、陽江和汕尾重復(fù)以上的優(yōu)化步驟。得到最終配送計(jì)劃。節(jié)約里程法第六步:最終方案的確定。節(jié)約里程法 最終修改后的車輛調(diào)度結(jié)果：節(jié)約里程法 通過對(duì)比初始方案與最終方案可知,通過優(yōu)化可節(jié)約里程(1768-1047)=721(公里),節(jié)約成本(4476.3-3384.55)=1091.75(元),僅8家客戶的一次配送就節(jié)約了物流配送成本1091.75。練習(xí)題練習(xí)題 某連鎖零售店，下設(shè)有一個(gè)配送中心某連鎖零售店，下設(shè)有一個(gè)配送中心p p和和1010個(gè)連個(gè)連鎖分店鎖分店a aj j，配送中心和各連鎖分店及各連鎖分店，配送中心和各連鎖分店及各連鎖分店之間的位置關(guān)系如下圖之間的位置關(guān)系如下圖1 1所示，兩點(diǎn)間連線上的數(shù)字所示，兩點(diǎn)間連線上的數(shù)字為兩點(diǎn)間的路線長度（單位：公里）。各連鎖分店對(duì)為兩點(diǎn)間的路線長度（單位：公里）。各連鎖分店對(duì)某種商品的需求量見表某種商品的需求量見表1 1，該商品由配送中心統(tǒng)一采，該商品由配送中心統(tǒng)一采購并進(jìn)行配送。配送中心備用購并進(jìn)行配送。配送中心備用2t2t和和4t4t的貨車，限定的貨車，限定送貨車輛一次巡回距離不超過送貨車