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

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

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

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

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

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

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

8、運行線路。是合理的運行線路。 （二）（二）規(guī)模比較小規(guī)模比較小 對于規(guī)模相對比較小的情況，也可以應用對于規(guī)模相對比較小的情況，也可以應用節(jié)約里節(jié)約里程法程法 (1)(1)節(jié)約里程法假設條件節(jié)約里程法假設條件v(2)(2)節(jié)約里程法原理節(jié)約里程法原理 已知已知P P點為配送中心，它分別向用戶點為配送中心，它分別向用戶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é)約里程法工作過程第一步：計算各點之間的最短距離第一步：計算各點之間的最短距離第二步：計算分店之間的節(jié)約里程第二步：計算分店之間的節(jié)約里程第三步：按節(jié)約里程從大到小排序第三步：按節(jié)約里程從大到小排序第四步：確定配送線路（優(yōu)化過程）第四步：確定配送線路（優(yōu)化過程）第一步：計算各點之間的最短距離第一步：計算各點之間的最短距離( (圖圖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）初始方案：對每個客戶分別單獨派車送貨）初始方案：對每個客戶分別單獨派車送貨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點并入線路點并入線路BFEPGDCAIJH7834710576446配送線路：4條配送距離：85km配送車輛：2t2+ 4t2（6 6）最終方案：將）最終方案：將H H和和I I連接形成新的線路連接形成新的線路BFEPGDCAIJH7834710576446配送線路：3條配送距離：80km配送車輛：2t1+ 4t2 任務實施任務實施好而惠連鎖超市配送中心除了為以上十家分店送貨外，還未其他地區(qū)的6個門店送貨，計劃調(diào)度員找到了配送中心到每個門店是成本最低路線，但是配送中心送貨資源有限，不能為每個門店單獨送貨，只能一輛車為幾個門店循環(huán)送貨。這樣從一個門店到另一個門店到另一個門店也要找到成本最低的線路?，F(xiàn)在，調(diào)度員要規(guī)劃從配送中心出發(fā)為各個門店循環(huán)