運(yùn)輸線路優(yōu)化2---節(jié)約里程法

1、線路優(yōu)化線路優(yōu)化-節(jié)約里程法節(jié)約里程法第四章第四章 運(yùn)輸管理運(yùn)輸管理本課程教學(xué)的組織本課程教學(xué)的組織任務(wù)五 運(yùn)輸線路優(yōu)化知識目標(biāo)明確優(yōu)化物流運(yùn)輸線路與運(yùn)輸線路開發(fā)是不同的。掌握起點(diǎn)終點(diǎn)重合的物流運(yùn)輸線路類型及其特點(diǎn)。掌握運(yùn)輸線路選擇的優(yōu)化方法-節(jié)約里程法能力目標(biāo)養(yǎng)成嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)，培養(yǎng)團(tuán)隊協(xié)作能力。能夠利用物流運(yùn)輸線路優(yōu)化方法解決實(shí)際工作中存在問題。任務(wù)描述任務(wù)描述 任務(wù)五 運(yùn)輸線路優(yōu)化面對市場競爭的日益激烈，物流運(yùn)輸企業(yè)的成本劇增，如何應(yīng)對挑戰(zhàn)？物流公司普遍的做法是：強(qiáng)化經(jīng)營管理，在降本減耗上下功夫，抵御高物流成本經(jīng)營風(fēng)險。其中重要的一條就是不斷優(yōu)化運(yùn)輸（配送）線路，減少人為的加大運(yùn)距，節(jié)約

2、油耗，避免油資源浪費(fèi)，提高運(yùn)輸效率。案例4-1就是好而惠連鎖超市配送中心成功的為十家分店配送的經(jīng)驗。 案例放送案例放送任務(wù)五 運(yùn)輸線路優(yōu)化好而惠連鎖零售店，下設(shè)有一個配送中心好而惠連鎖零售店，下設(shè)有一個配送中心P P和和1010個連鎖分店個連鎖分店A AJ J，配送中心和各連鎖分店及各連，配送中心和各連鎖分店及各連鎖分店之間的位置關(guān)系如下圖所示，兩點(diǎn)間連線鎖分店之間的位置關(guān)系如下圖所示，兩點(diǎn)間連線上的數(shù)字為兩點(diǎn)間的路線長度（單位：公里），上的數(shù)字為兩點(diǎn)間的路線長度（單位：公里），括號內(nèi)的數(shù)字為各連鎖分店對某種商品的需求量括號內(nèi)的數(shù)字為各連鎖分店對某種商品的需求量（單位：（單位：t t）。該商品

3、由配送中心統(tǒng)一采購并進(jìn)）。該商品由配送中心統(tǒng)一采購并進(jìn)行配送。配送中心備用行配送。配送中心備用2t2t和和4t4t的貨車，限定送貨的貨車，限定送貨車輛一次巡回距離不超過車輛一次巡回距離不超過3030公里，設(shè)送到時間均公里，設(shè)送到時間均符合用戶要求，請問配送中心的最優(yōu)送貨方案怎符合用戶要求，請問配送中心的最優(yōu)送貨方案怎樣安排。樣安排。BFEPGDCAIJH 相關(guān)理論知識相關(guān)理論知識任務(wù)五 運(yùn)輸線路優(yōu)化v 物流運(yùn)輸線路，從起點(diǎn)到終點(diǎn)，常見的有物流運(yùn)輸線路，從起點(diǎn)到終點(diǎn)，常見的有不成圈的直線、丁字線、交叉線和分支線，不成圈的直線、丁字線、交叉線和分支線，還有形成閉合回路的環(huán)形線路，環(huán)形線路包還有形成

4、閉合回路的環(huán)形線路，環(huán)形線路包括有一個圈和多個圈的。案例中涉及的路線括有一個圈和多個圈的。案例中涉及的路線類型為類型為起點(diǎn)與終點(diǎn)為同一地點(diǎn)的物流運(yùn)輸線起點(diǎn)與終點(diǎn)為同一地點(diǎn)的物流運(yùn)輸線路的選擇優(yōu)化路的選擇優(yōu)化問題問題一、物流運(yùn)輸線路的類型一、物流運(yùn)輸線路的類型v 在運(yùn)輸生產(chǎn)實(shí)踐中，自有車輛運(yùn)輸時，車在運(yùn)輸生產(chǎn)實(shí)踐中，自有車輛運(yùn)輸時，車輛往往要回到起點(diǎn)?；蛘呤悄澄锪髦行乃拓浀捷v往往要回到起點(diǎn)?；蛘呤悄澄锪髦行乃拓浀脚渌椭行娜缓蠓祷匚锪髦行牡木€路；或某配送配送中心然后返回物流中心的線路；或某配送中心送貨上門后返回，這就是屬于起點(diǎn)與終點(diǎn)中心送貨上門后返回，這就是屬于起點(diǎn)與終點(diǎn)為同一地點(diǎn)的情況。為同一地

5、點(diǎn)的情況。v始發(fā)點(diǎn)和終點(diǎn)相重合的線路選擇問題通常被稱始發(fā)點(diǎn)和終點(diǎn)相重合的線路選擇問題通常被稱為為“旅行推銷員旅行推銷員”問題、貨郎擔(dān)問題或者中國問題、貨郎擔(dān)問題或者中國郵遞員郵路問題郵遞員郵路問題。一、物流運(yùn)輸線路的類型一、物流運(yùn)輸線路的類型二、物流運(yùn)輸線路的選擇優(yōu)化二、物流運(yùn)輸線路的選擇優(yōu)化v起點(diǎn)與終點(diǎn)為同一地點(diǎn)的物流運(yùn)輸線路的選擇優(yōu)起點(diǎn)與終點(diǎn)為同一地點(diǎn)的物流運(yùn)輸線路的選擇優(yōu)化化v 起點(diǎn)與終點(diǎn)為同一地點(diǎn)（起迄點(diǎn)重合）的物流運(yùn)輸線路起點(diǎn)與終點(diǎn)為同一地點(diǎn)（起迄點(diǎn)重合）的物流運(yùn)輸線路的選擇優(yōu)化，目標(biāo)是找到一個可以走遍所有地點(diǎn)的最佳的選擇優(yōu)化，目標(biāo)是找到一個可以走遍所有地點(diǎn)的最佳順序，使運(yùn)輸車輛必須

6、經(jīng)過所有站點(diǎn)并且總距離或運(yùn)輸順序，使運(yùn)輸車輛必須經(jīng)過所有站點(diǎn)并且總距離或運(yùn)輸時間最短。可以分為兩種情況：時間最短?？梢苑譃閮煞N情況：v（一）規(guī)模很大（一）規(guī)模很大 規(guī)模很大，即是包含站點(diǎn)很多。某次運(yùn)輸在很多個站規(guī)模很大，即是包含站點(diǎn)很多。某次運(yùn)輸在很多個站點(diǎn)的規(guī)模中找到最優(yōu)路徑，是不切合實(shí)際的。此情況點(diǎn)的規(guī)模中找到最優(yōu)路徑，是不切合實(shí)際的。此情況不是我們討論的范圍。不是我們討論的范圍。 （二）（二）規(guī)模比較小規(guī)模比較小 對于規(guī)模相對比較小的情況，可以應(yīng)用對于規(guī)模相對比較小的情況，可以應(yīng)用經(jīng)驗試探經(jīng)驗試探法法加以解決。其步驟是：加以解決。其步驟是： （1）掌握來自實(shí)踐的經(jīng)驗。）掌握來自實(shí)踐的經(jīng)驗

7、。經(jīng)驗經(jīng)驗是：合理的經(jīng)停是：合理的經(jīng)停線路中各條線路之間是不交叉的，并且只要有可線路中各條線路之間是不交叉的，并且只要有可能路徑就會呈凸形或水滴狀。能路徑就會呈凸形或水滴狀。 （2）根據(jù)經(jīng)驗作出判斷。按照）根據(jù)經(jīng)驗作出判斷。按照“線路不交叉線路不交叉”和和“凸形或水滴狀凸形或水滴狀”的兩條原則，畫出線路規(guī)劃圖的兩條原則，畫出線路規(guī)劃圖，如圖，如圖4-3所示。圖所示。圖4-3所示的是通過各點(diǎn)的運(yùn)行線所示的是通過各點(diǎn)的運(yùn)行線路示意圖，都是經(jīng)過所有站點(diǎn)，但是先后次序不路示意圖，都是經(jīng)過所有站點(diǎn)，但是先后次序不同，即線路不同。其中同，即線路不同。其中A是不合理的運(yùn)行線路，是不合理的運(yùn)行線路，B是合理的

8、運(yùn)行線路。是合理的運(yùn)行線路。 （二）（二）規(guī)模比較小規(guī)模比較小 對于規(guī)模相對比較小的情況，也可以應(yīng)用對于規(guī)模相對比較小的情況，也可以應(yīng)用節(jié)約里節(jié)約里程法程法 (1)(1)節(jié)約里程法假設(shè)條件節(jié)約里程法假設(shè)條件v(2)(2)節(jié)約里程法原理節(jié)約里程法原理 已知已知P P點(diǎn)為配送中心，它分別向用戶點(diǎn)為配送中心，它分別向用戶A A和和B B送貨送貨，P P到到A A和和B B的距離分別為的距離分別為a a、b b，A A和和B B之間的距離為之間的距離為c c，送貨方，送貨方案只有以案只有以下兩種：下兩種：ABPABP方案方案從上圖可以得知：方案從上圖可以得知：方案的配送距離為：的配送距離為：2a+2b

9、2a+2b 方案方案的配送距離為：的配送距離為：a+b+ca+b+c 顯然：顯然： 2a+2b2a+2ba+b+c a+b+c （為什么？）（為什么？） (3)(3)節(jié)約里程法工作過程節(jié)約里程法工作過程第一步：計算各點(diǎn)之間的最短距離第一步：計算各點(diǎn)之間的最短距離第二步：計算分店之間的節(jié)約里程第二步：計算分店之間的節(jié)約里程第三步：按節(jié)約里程從大到小排序第三步：按節(jié)約里程從大到小排序第四步：確定配送線路（優(yōu)化過程）第四步：確定配送線路（優(yōu)化過程）第一步：計算各點(diǎn)之間的最短距離第一步：計算各點(diǎn)之間的最短距離( (圖圖4-44-4) )IJGHEFCDAPAPBCDEIGHFJB (4)(4)以好而惠

10、配送中心為以好而惠配送中心為1010家分店配送為例家分店配送為例第二步：計算分店之間的節(jié)約里程第二步：計算分店之間的節(jié)約里程CGHIJEFDABACBEDGFIHJ (4)(4)以好而惠配送中心為以好而惠配送中心為1010家分店配送為例家分店配送為例第三步：將上述所得的節(jié)約里程按從大到小排序第三步：將上述所得的節(jié)約里程按從大到小排序EF69121196BJCEBDACIJAB146423DEAICDBCAJ順序排位連接線BE9319867892222222119CJFIEGGIDF11123順序排位15131091013111616161313節(jié)約里程FG5BIFHADHIGH44455連接線

11、節(jié)約里程 (4)(4)以好而惠配送中心為以好而惠配送中心為1010家分店配送為例家分店配送為例第四步：確定配送線路第四步：確定配送線路（1 1）初始方案：對每個客戶分別單獨(dú)派車送貨）初始方案：對每個客戶分別單獨(dú)派車送貨BFEPGDCAIJH883410710978配送距離：148km配送車輛：2t10 (4)(4)以好而惠配送中心為以好而惠配送中心為1010家分店配送為例家分店配送為例(2)(2)修正方案修正方案1 1：按節(jié)約里程大小順序，連接：按節(jié)約里程大小順序，連接A A和和B B，A A和和J J，B B和和C C配送線路：7條配送距離：109km配送車輛：2t6+ 4t1BFEPGDC

12、AIJH883471057844（3 3）修正方案）修正方案2 2：連接：連接D D和和E E形成一個新的線路形成一個新的線路BFEPGDCAIJH8834710578446配送線路：6條配送距離：99km配送車輛：2t5+ 4t1（4 4）修正方案）修正方案3 3：將：將F F并入線路并入線路BFEPGDCAIJH7834710578446配送線路：5條配送距離：90km配送車輛：2t3+ 4t2（5 5）修正方案）修正方案4 4：將：將G G點(diǎn)并入線路點(diǎn)并入線路BFEPGDCAIJH7834710576446配送線路：4條配送距離：85km配送車輛：2t2+ 4t2（6 6）最終方案：將）最終方案：將H H和和I I連接形成新的線路連接形成新的線路BFEPGDCAIJH7834710576446配送線路：3條配送距離：80km配送車輛：2t1+ 4t2 任務(wù)實(shí)施任務(wù)實(shí)施好而惠連鎖超市配送中心除了為以上十家分店送貨外，還未其他地區(qū)的6個門店送貨，計劃調(diào)度員找到了配送中心到每個門店是成本最低路線，但是配送中心送貨資源有限，不能為每個門店單獨(dú)送貨，只能一輛車為幾個門店循環(huán)送貨。這樣從一個門店到另一個門店到另一個門店也要找到成本最低的線路?，F(xiàn)在，調(diào)度員要規(guī)劃從配送中心出發(fā)為各個門店循環(huán)