任務五_優(yōu)化運輸路線

1、配貨管理配貨管理本課程教學的組織本課程教學的組織任務五 配送運輸?shù)木€路優(yōu)化任務描述任務描述 任務五 優(yōu)化物流運輸?shù)木€路 案例放送案例放送A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29）（127）（13）+60+100+20-30-30-50-70-20圖圖4-1 4-1 康鑫全藥業(yè)集團公司特效藥品交通線路圖康鑫全藥業(yè)集團公司特效藥品交通線路圖案例研討案例研討 優(yōu)化物流運輸線路與運輸線路開發(fā)有區(qū)別，它是優(yōu)化物流運輸線路與運輸線路開發(fā)有區(qū)別，它是在已知貨物名稱及數(shù)量、貨源地和目的地的情況下，在已知貨物名稱及數(shù)量、貨源地和目的地的情況下，根據(jù)運輸合理

2、化原則對運輸線路的選擇與優(yōu)化。根據(jù)運輸合理化原則對運輸線路的選擇與優(yōu)化。 物流運輸合理化要求以最佳的運輸線路、最快的物流運輸合理化要求以最佳的運輸線路、最快的運輸速度和最低的運輸費用等將物品從原產地運送到運輸速度和最低的運輸費用等將物品從原產地運送到目的地，案例中康鑫全集團的目的地，案例中康鑫全集團的4 4個生產供應點，個生產供應點，5 5個批個批發(fā)配送點，線路圖中有成圈的，有不成圈的，屬于相發(fā)配送點，線路圖中有成圈的，有不成圈的，屬于相對復雜的情況。應該如何安排，才能達到路程最近和對復雜的情況。應該如何安排，才能達到路程最近和時間及費用最??？經過本單元以下內容的學習，可以時間及費用最??？經過

3、本單元以下內容的學習，可以找到解決問題的辦法找到解決問題的辦法。任務五 優(yōu)化物流運輸?shù)木€路 相關知識相關知識任務五 優(yōu)化物流運輸?shù)木€路v 物流運輸線路，從起點到終點，常見的有物流運輸線路，從起點到終點，常見的有不成圈的直線、丁字線、交叉線和分支線，不成圈的直線、丁字線、交叉線和分支線，還有形成閉合回路的環(huán)形線路，環(huán)形線路包還有形成閉合回路的環(huán)形線路，環(huán)形線路包括有一個圈和多個圈的。盡管線路的類型頗括有一個圈和多個圈的。盡管線路的類型頗多，但是可以將其歸納為以下多，但是可以將其歸納為以下三個基本類型三個基本類型一、物流運輸線路的類型一、物流運輸線路的類型（一）單一裝貨地和單一卸貨地的物流運輸線（

4、一）單一裝貨地和單一卸貨地的物流運輸線路路v 如圖如圖4-2是路路通運輸公司簽訂了的一項運是路路通運輸公司簽訂了的一項運輸合同，要把輸合同，要把A城的一批化肥運送到城的一批化肥運送到J城，路城，路路通公司根據(jù)這兩個城市之間可選擇的行車路通公司根據(jù)這兩個城市之間可選擇的行車線路繪制的公路網(wǎng)絡。其中線路繪制的公路網(wǎng)絡。其中A點表示裝貨地點表示裝貨地，J點是卸貨地。此類運輸線路的特點是點是卸貨地。此類運輸線路的特點是A點點和和J點是兩個點，不重合。這是運輸活動中的點是兩個點，不重合。這是運輸活動中的一種情況。一種情況。 B CA DG E H J I8012874741161161405011238

5、122110381463388056 F圖圖4-24-2公路網(wǎng)絡示意圖公路網(wǎng)絡示意圖（二）起點與終點為同一地點的物流運輸線路（二）起點與終點為同一地點的物流運輸線路v 在運輸生產實踐中，自有車輛運輸時，車輛往往在運輸生產實踐中，自有車輛運輸時，車輛往往要回到起點?；蛘呤悄澄锪髦行乃拓浀脚渌椭行娜灰氐狡瘘c。或者是某物流中心送貨到配送中心然后返回物流中心的線路；或某配送中心送貨上門后后返回物流中心的線路；或某配送中心送貨上門后返回，這就是屬于起點與終點為同一地點的情況。返回，這就是屬于起點與終點為同一地點的情況。如圖如圖4-3（a）中，從）中，從V1經過經過V2、V3、V4、V5和和V6回到回到

6、V1，V1既是起點，也是終點。始發(fā)點和終點既是起點，也是終點。始發(fā)點和終點相重合的線路選擇問題通常被稱為相重合的線路選擇問題通常被稱為“旅行推銷員旅行推銷員”問題、貨郎擔問題或者中國郵遞員郵路問題問題、貨郎擔問題或者中國郵遞員郵路問題。（a a）不合理的運輸路線）不合理的運輸路線（b b）合理的運輸路線）合理的運輸路線V3V2V1V6V4V5V2V4V5V6V1V3圖圖4-34-3運輸線路示意圖運輸線路示意圖（三）多起點、多終點問題的物流運輸線路（三）多起點、多終點問題的物流運輸線路v 多起點、多終點問題的物流運輸線路，在物多起點、多終點問題的物流運輸線路，在物流運輸實踐中，經常存在。如多個供

7、應商供應流運輸實踐中，經常存在。如多個供應商供應給多個工廠的情況，或者把不同工廠生產的同給多個工廠的情況，或者把不同工廠生產的同一產品分配到不同用戶的問題。在這些問題中一產品分配到不同用戶的問題。在這些問題中，起點和終點都不是單一的。在這類問題中，起點和終點都不是單一的。在這類問題中，各供應點的供應量往往也有限制。各供應點的供應量往往也有限制。v 在多個貨源地服務于多個目的地時，物流運在多個貨源地服務于多個目的地時，物流運輸線路存在兩種情況：運輸線路成圈的和不成輸線路存在兩種情況：運輸線路成圈的和不成圈的。圈的。v 案例廣西康鑫全藥業(yè)集團公司案例廣西康鑫全藥業(yè)集團公司“護肝王護肝王”特效藥的生

8、產和銷售的交通線路（特效藥的生產和銷售的交通線路（圖圖4-14-1），），從公路運輸線路看，從公路運輸線路看，A1-B2-B3-B4-A2-B1A1-B2-B3-B4-A2-B1構成構成一個圈，其余的不成圈。一個圈，其余的不成圈。二、物流運輸線路的選擇優(yōu)化二、物流運輸線路的選擇優(yōu)化v（一）單一裝貨地和單一卸貨地的物流運輸線（一）單一裝貨地和單一卸貨地的物流運輸線路的選擇優(yōu)化路的選擇優(yōu)化最短路徑法最短路徑法 在圖在圖4-2中，路路通運輸公司要在裝貨地中，路路通運輸公司要在裝貨地A點，滿載點，滿載貨物到貨物到J點卸貨。點卸貨。B、C、D、E、F、G、H、和、和I是是網(wǎng)絡中的站點，站點之間以線路連接

9、，線路上標明網(wǎng)絡中的站點，站點之間以線路連接，線路上標明了兩個站點之間的距離。從圖了兩個站點之間的距離。從圖2-可以看出，從可以看出，從A地地到到J地，有很多條線路可以選擇，然而，運輸線路地，有很多條線路可以選擇，然而，運輸線路選擇優(yōu)化的任務就是要找出使總路程的長度最短的選擇優(yōu)化的任務就是要找出使總路程的長度最短的線路。這就是運輸規(guī)劃中的最短線路問題，通常稱線路。這就是運輸規(guī)劃中的最短線路問題，通常稱為最短路徑法，或者稱最短路線方法。即是列出最為最短路徑法，或者稱最短路線方法。即是列出最短運輸線路計算表（如表短運輸線路計算表（如表1-1），分步驟地計算。），分步驟地計算。通過比較，選擇走近路。

10、通過比較，選擇走近路。表表1-1 最短運輸線路計算表最短運輸線路計算表表表1-1最短運輸線路計算表（續(xù)）最短運輸線路計算表（續(xù)）v步驟步驟1：在圖：在圖4-1可以看出，裝貨地可以看出，裝貨地A即是起點，即是起點，是第一個已解的節(jié)點。與是第一個已解的節(jié)點。與A點直接連接的未解的點直接連接的未解的節(jié)點有節(jié)點有B、C和和D點。點。B到到A的距離最短，所以是的距離最短，所以是唯一的選擇，成為已解的節(jié)點。唯一的選擇，成為已解的節(jié)點。v步驟步驟2 2：是找出距離已解：是找出距離已解A A點和點和B B點最近的未解節(jié)點最近的未解節(jié)點。只要列出距各個已解節(jié)點最近的連接點，點。只要列出距各個已解節(jié)點最近的連接點

11、，則有則有A-CA-C，B-CB-C。注意從起點通過已解節(jié)點到某注意從起點通過已解節(jié)點到某一節(jié)點所需的路程應該等于到達這個已解節(jié)點一節(jié)點所需的路程應該等于到達這個已解節(jié)點的最短路程加上已解節(jié)點與未解節(jié)點之間的路的最短路程加上已解節(jié)點與未解節(jié)點之間的路程。程。即從即從A A經過經過B B到達到達C C的距離為的距離為80+56=13680+56=136公里，公里，而從而從A A直達直達C C的距離為的距離為128128公里?，F(xiàn)在公里?，F(xiàn)在C C點也成為點也成為已解節(jié)點。已解節(jié)點。v步驟步驟3：要找出與各已解節(jié)點直接連接的最近的未：要找出與各已解節(jié)點直接連接的最近的未解節(jié)點。在圖解節(jié)點。在圖4-1

12、5上可見，在與已解節(jié)點上可見，在與已解節(jié)點A、B、C直接連接的有直接連接的有D、E、F三個點，自起點到三個候三個點，自起點到三個候選點的路程分別是選點的路程分別是338、154、208公里，其中連公里，其中連接接BE的路程最短，為的路程最短，為154公里。因此，公里。因此，E點為所選點為所選。v重復上述過程，直至到達終點重復上述過程，直至到達終點J J，即步驟，即步驟8 8。由此。由此得到最優(yōu)線路為得到最優(yōu)線路為A-B-E-I-JA-B-E-I-J，最短的路程的，最短的路程的344344公公里。里。v 最短路徑法可以利用計算機進行求解。把最短路徑法可以利用計算機進行求解。把運輸網(wǎng)絡中的線路（有

13、的稱為鏈）和節(jié)點的資運輸網(wǎng)絡中的線路（有的稱為鏈）和節(jié)點的資料都存入數(shù)據(jù)庫中，選好起點和終點后，計算料都存入數(shù)據(jù)庫中，選好起點和終點后，計算機可以很快就算出最短路徑。機可以很快就算出最短路徑。v 此計算的結果，稱為單純的最短距離路徑，此計算的結果，稱為單純的最短距離路徑，并未考慮各條線路的運行質量。不能說明穿越并未考慮各條線路的運行質量。不能說明穿越網(wǎng)絡的最短時間。因此，對運行時間和距離都網(wǎng)絡的最短時間。因此，對運行時間和距離都設定權數(shù)就可以得出比較具有實際意義的線路。設定權數(shù)就可以得出比較具有實際意義的線路。案例案例 單一裝貨地和單一卸貨地的物流運輸線路的選擇優(yōu)單一裝貨地和單一卸貨地的物流運

14、輸線路的選擇優(yōu)化化 某連鎖超市的配送中心位于城市邊緣的郊區(qū)，但超市某連鎖超市的配送中心位于城市邊緣的郊區(qū)，但超市的一家門店位于繁華的城市中心區(qū)，因此負責送貨路線規(guī)的一家門店位于繁華的城市中心區(qū)，因此負責送貨路線規(guī)劃的計劃調度員要規(guī)劃出配送中心到這個門店的送貨成本劃的計劃調度員要規(guī)劃出配送中心到這個門店的送貨成本最低的路線。最初按交通圖所示里程最短的線路進行送貨最低的路線。最初按交通圖所示里程最短的線路進行送貨，見下圖，見下圖4-4： 任務實施任務實施1 1OAV4V2V3V1235223396圖圖4-4中中O代表配送中心，代表配送中心，A代表門店，代表門店，V1V4代代表要經過的關鍵節(jié)點（如主

15、要道路的交叉路口、表要經過的關鍵節(jié)點（如主要道路的交叉路口、立體交叉互通樞紐等），連線邊上的數(shù)值代表每立體交叉互通樞紐等），連線邊上的數(shù)值代表每一路段的里程，圖中綠線連接的一路段的里程，圖中綠線連接的O-V1-V4-A為里為里程最短線路。程最短線路。但但很快發(fā)現(xiàn)里程最短并不意味著成本最低，因為里程最短很快發(fā)現(xiàn)里程最短并不意味著成本最低，因為里程最短這條路有一條新建的大橋（圖中這條路有一條新建的大橋（圖中V4點與點與A點之間黑色加粗點之間黑色加粗部分）來回都要收取通行費，這條路是城區(qū)主干道且建成部分）來回都要收取通行費，這條路是城區(qū)主干道且建成時間較長通行條件較差，越往城中心走道路擁堵越嚴重，時

16、間較長通行條件較差，越往城中心走道路擁堵越嚴重，每趟送貨產生的油耗、車輛送貨時間占用、送貨人員工作每趟送貨產生的油耗、車輛送貨時間占用、送貨人員工作時間等綜合成本超出了正常水平，并且多次發(fā)生沒按門店時間等綜合成本超出了正常水平，并且多次發(fā)生沒按門店的要求時間送達的情況。因此計劃調度員對每一條能從的要求時間送達的情況。因此計劃調度員對每一條能從O到到A的線路都進行了實地勘察記錄，并綜合考慮每條送貨的線路都進行了實地勘察記錄，并綜合考慮每條送貨線路的里程、時間、車輛耗損，得出了每條線路每一個路線路的里程、時間、車輛耗損，得出了每條線路每一個路段的送貨運行成本，匯總出了一張從配送中心到此門店的段的送

17、貨運行成本，匯總出了一張從配送中心到此門店的送貨路徑數(shù)據(jù)圖?，F(xiàn)在計劃調度員要依據(jù)此圖，找出配送送貨路徑數(shù)據(jù)圖?，F(xiàn)在計劃調度員要依據(jù)此圖，找出配送中心與該門店之間送貨成本最低路徑。中心與該門店之間送貨成本最低路徑。OAV4V2V3送中心與位于城中心門店之間的網(wǎng)絡路線圖，圖配送中心與位于城中心門店之間的網(wǎng)絡路線圖，圖4-5中中O代表配送中心，代表配送中心，A代表門店，代表門店，V1V4代表要經過的關鍵節(jié)代表要經過的關鍵節(jié)點（如主要道路的交叉路口、立體交叉互通樞紐等），連點（如主要道路的交叉路口、立體交叉互通樞紐等），連線邊上的數(shù)值代表每一路段送貨運行的最低成本值。線邊上的

18、數(shù)值代表每一路段送貨運行的最低成本值。v一、小組搶答（一、小組搶答（1個個/公司）公司）v二、參考答案（教師總結）二、參考答案（教師總結）v三、評價及獎勵結果公布三、評價及獎勵結果公布v四、學習收獲一句話及下次課預告四、學習收獲一句話及下次課預告教師總結教師總結第一步：第一步：O點是原始已解節(jié)點，從配送中心O點出發(fā)，可以走V1、V2兩個節(jié)點，由于OV13、OV211，因此選擇走OV1線路，V1成為已解節(jié)點，見下圖。OAV4V2V3二步：第二步： 與O、V1兩個已解節(jié)點相連的未解節(jié)點有V2、V3、V4，可選擇的送貨路線為：O-V1-V4、O-V1-V3、O-V2，相應的

19、送貨成本值為： O-V1-V43+14O-V1-V33+710O-V211O-V1-V4線路的成本最少，因此V4成為已解節(jié)點，見下圖。OAV4V2V3三步：第三步： 與O、V1、V4三個已解節(jié)點相連的未解節(jié)點有V2、V3、A，可選擇的送貨路線為：O-V1-V4-A、O-V1-V4-V3、O-V1-V3、O-V2，相應的送貨成本值為：O-V1-V4-A3+1+812O-V1-V4-V33+1+37O-V1-V33+710O-V211O-V1-V4-V3線路的成本最少，因此V3成為已解節(jié)點，見下圖。OAV4V2V3四步：第四步：與O、V1、V4、

20、V3四個已解節(jié)點相連的未解節(jié)點有V2、 A，可選擇的送貨路線為：O-V1-V4-V3-A、O-V1-V4-V3-V2、O-V1-V3-A、O-V1-V3-V2、O-V2，相應的送貨成本值為：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V23+1+3+18O-V1-V3-A3+7+414O-V1-V3-V23+7+111O-V211O-V1-V4-V3-V2線路的成本最少，因此V2成為已解節(jié)點，見下圖。OAV4V2V3五步：第五步：與O、V1、V4、V3、V2五個已解節(jié)點相連的未解節(jié)點只有A，可選擇的送貨路線為：O-V1-V4-V3-A、O-V1-V

21、4-V3-V2-A、O-V1-V3-A、O-V1-V3-V2-A、O-V2-A、O-V1-V4-A，相應的送貨成本值為：O-V1-V4-V3-A3+1+3+411O-V1-V4-V3-V2-A3+1+3+1+210O-V1-V3-A3+7+414O-V1-V3-V2-A3+7+1+213O-V2-A11+213O-V1-V4-A3+1+812O-V1-V4-V3-V2-A線路的成本最少，因此這條線路是配送中心與該門店之間成本最低的送貨線路，線路的送貨成本數(shù)值為10，見下圖。OAV4V2V3論：結論：最后通過與實訓情境中里程最短路線O-V1-V4-A的成本比較一下，里程

22、最短路線的成本為12，成本最小路線O-V1-V4-V3-V2-A的成本為10。（二）起點與終點為同一地點的物流運輸線（二）起點與終點為同一地點的物流運輸線路的選擇優(yōu)化路的選擇優(yōu)化v 起點與終點為同一地點（起迄點重合）的物流運起點與終點為同一地點（起迄點重合）的物流運輸線路的選擇優(yōu)化，目標是找到一個可以走遍所有輸線路的選擇優(yōu)化，目標是找到一個可以走遍所有地點的最佳順序，使運輸車輛必須經過所有站點并地點的最佳順序，使運輸車輛必須經過所有站點并且總距離或運輸時間最短?？梢苑譃閮煞N情況：且總距離或運輸時間最短?？梢苑譃閮煞N情況：v1.1.規(guī)模很大規(guī)模很大 規(guī)模很大，即是包含站點很多。某次運輸在很多規(guī)模

23、很大，即是包含站點很多。某次運輸在很多個站點的規(guī)模中找到最優(yōu)路徑，是不切合實際的。個站點的規(guī)模中找到最優(yōu)路徑，是不切合實際的。此情況不是我們討論的范圍。此情況不是我們討論的范圍。 2.2.規(guī)模比較小規(guī)模比較小 對于規(guī)模相對比較小的情況，可以應用經驗試探對于規(guī)模相對比較小的情況，可以應用經驗試探法加以解決。其步驟是：法加以解決。其步驟是： （1）掌握來自實踐的經驗。）掌握來自實踐的經驗。經驗經驗是：合理的經停是：合理的經停線路中各條線路之間是不交叉的，并且只要有可線路中各條線路之間是不交叉的，并且只要有可能路徑就會呈凸形或水滴狀。能路徑就會呈凸形或水滴狀。 （2）根據(jù)經驗作出判斷。按照）根據(jù)經驗

24、作出判斷。按照“線路不交叉線路不交叉”和和“凸形或水滴狀凸形或水滴狀”的兩條原則，畫出線路規(guī)劃圖的兩條原則，畫出線路規(guī)劃圖，如圖，如圖4-3所示。圖所示。圖4-3所示的是通過各點的運行線所示的是通過各點的運行線路示意圖，都是經過所有站點，但是先后次序不路示意圖，都是經過所有站點，但是先后次序不同，即線路不同。其中同，即線路不同。其中A是不合理的運行線路，是不合理的運行線路，B是合理的運行線路。是合理的運行線路。(1)(1)節(jié)約里程法假設條件節(jié)約里程法假設條件節(jié)約里程法節(jié)約里程法(2)(2)節(jié)約里程法原理節(jié)約里程法原理 已知已知P P點為配送中心，它分別向用戶點為配送中心，它分別向用戶A A和和

25、B B送貨，送貨，P P到到A A和和B B的距離分別為的距離分別為a a、b b，A A和和B B之間的距離為之間的距離為c c，送貨方案只有以，送貨方案只有以下兩種：下兩種：ABPABP方案方案從上圖可以得知：方案從上圖可以得知：方案的配送距離為：的配送距離為：2a+2b2a+2b 方案方案的配送距離為：的配送距離為：a+b+ca+b+c 顯然：顯然： 2a+2b2a+2ba+b+c a+b+c （為什么？）（為什么？） 例：某連鎖零售店，下設有一個配送中心例：某連鎖零售店，下設有一個配送中心P P和和1010個連鎖個連鎖分店分店A AJ J，配送中心和各連鎖分店及各連鎖分店之間的位，配送

26、中心和各連鎖分店及各連鎖分店之間的位置關系如下圖所示，兩點間連線上的數(shù)字為兩點間的路置關系如下圖所示，兩點間連線上的數(shù)字為兩點間的路線長度（單位：公里），括號內的數(shù)字為各連鎖分店對線長度（單位：公里），括號內的數(shù)字為各連鎖分店對某種商品的需求量（單位：某種商品的需求量（單位：t t）。該商品由配送中心統(tǒng)一）。該商品由配送中心統(tǒng)一采購并進行配送。配送中心備用采購并進行配送。配送中心備用2t2t和和4t4t的貨車，限定送的貨車，限定送貨車輛一次巡回距離不超過貨車輛一次巡回距離不超過3030公里，設送到時間均符合公里，設送到時間均符合用戶要求，求配送中心的最優(yōu)送貨方案。用戶要求，求配送中心的最優(yōu)送貨

27、方案。BFEPGDCAIJH第一步：計算各點之間的最短距離第一步：計算各點之間的最短距離IJGHEFCDAPAPBCDEIGHFJB第二步：計算分店之間的節(jié)約里程第二步：計算分店之間的節(jié)約里程CGHIJEFDABACBEDGFIHJ第三步：將上述所得的節(jié)約里程按從大到小排序第三步：將上述所得的節(jié)約里程按從大到小排序EF69121196BJCEBDACIJAB146423DEAICDBCAJ順序排位連接線BE9319867892222222119CJFIEGGIDF11123順序排位15131091013111616161313節(jié)約里程FG5BIFHADHIGH44455連接線節(jié)約里程第四步：確

28、定配送線路第四步：確定配送線路（1 1）初始方案：對每個客戶分別單獨派車送貨）初始方案：對每個客戶分別單獨派車送貨BFEPGDCAIJH883410710978配送距離：148km配送車輛：2t10(2)(2)修正方案修正方案1 1：按節(jié)約里程大小順序，連接：按節(jié)約里程大小順序，連接A A和和B B，A A和和J J，B B和和C C配送線路：7條配送距離：109km配送車輛：2t6+ 4t1BFEPGDCAIJH883471057844（3 3）修正方案）修正方案2 2：連接：連接D D和和E E形成一個新的線路形成一個新的線路BFEPGDCAIJH8834710578446配送線路：6條配

29、送距離：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 任務實施任務實施2 2

30、212066991212241019v一、團隊搶答（一、團隊搶答（1個個/公司）公司）v二、參考答案（教師總結）二、參考答案（教師總結）v三、評價及獎勵結果公布三、評價及獎勵結果公布v四、學習收獲一句話及下次課預告四、學習收獲一句話及下次課預告教師總結教師總結第一步：第一步：根據(jù)根據(jù)“配送中心到各門店及兩兩門店之間成本最低線路的數(shù)配送中心到各門店及兩兩門店之間成本最低線路的數(shù)值表（見上表）值表（見上表）”和節(jié)約法的基本原理，計算出兩兩門店之和節(jié)約法的基本原理，計算出兩兩門店之間的最小成本值及節(jié)約成本。計算方法是：間的最小成本值及節(jié)約成本。計算方法是：i,j是任意相鄰兩是任意相鄰兩門店節(jié)點門店節(jié)

31、點Oi=a，OJ=b，ij=c，則，則 ij節(jié)約的成本為：節(jié)約的成本為：a+b-c 。計算結果填入下表中。計算結果填入下表中。第二步：第二步：根據(jù)上表中的出兩兩門店之間的節(jié)約成本計算結果，按節(jié)約成本大小順序排列到下表中。第三步：方案調整第三步：方案調整EG節(jié)約里程最大，從表3-2中得知，它們的配送貨物量是：175 + 115 =29 t，在貨車載重限度內，可以入選。FG的配送貨物量11 t，正好可以與29 t拼裝為一輛4 t貨車的載運量，它們相互銜接成為一條路線AEGFA。全程為20 + 1 + 6 + 24 = 51 km。因4 t貨車已裝滿，所以應考慮第二條配送路線。C，D配送貨物量是10

32、 + 07 = 17 t，在貨車載重限度內，可以將B點的08 t貨物集中在一起，拼裝為一輛25 t貨車的載運量，形成第二條配送路線ABCDA或ADCBA，全程為9 + 9 + 10 + 12 = 40 km。 此案例的配送路線優(yōu)化后確定為二條，即AEGFA和ABCDA（ADCBA），總行程為51 + 40 = 91 km，使用4 t和25 t的貨車各一輛。結論 使用4 t和25 t的貨車各一輛 總節(jié)約里程: (9+12+12+24+20+21)*2-91=105B=2.5tA=4t 案例放送案例放送A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29

33、）（127）（13）+60+100+20-30-30-50-70-20圖圖4-1 4-1 康鑫全藥業(yè)集團公司特效藥品交通線路圖康鑫全藥業(yè)集團公司特效藥品交通線路圖（三）多起點、多終點的物流運輸線路的選（三）多起點、多終點的物流運輸線路的選擇優(yōu)化擇優(yōu)化v 有多個貨源地服務于多個目的地時，物流運輸線路選擇優(yōu)化有多個貨源地服務于多個目的地時，物流運輸線路選擇優(yōu)化的任務是要指定為各目的地服務的供貨地，同時要找到供貨的任務是要指定為各目的地服務的供貨地，同時要找到供貨地、目的地之間的最佳路徑。解決這類問題可以運用一類特地、目的地之間的最佳路徑。解決這類問題可以運用一類特殊的線性規(guī)劃方法即物資調運問題殊的

34、線性規(guī)劃方法即物資調運問題圖上作業(yè)法圖上作業(yè)法進行求解。進行求解。v 圖上作業(yè)法圖上作業(yè)法是在運輸圖上求解線性規(guī)劃運輸模型的方法。交是在運輸圖上求解線性規(guī)劃運輸模型的方法。交通運輸以及類似的線性規(guī)劃問題，都可以通運輸以及類似的線性規(guī)劃問題，都可以首先畫出流向圖，首先畫出流向圖，然后根據(jù)有關規(guī)則進行必要調整，直至求出最小運輸費用或然后根據(jù)有關規(guī)則進行必要調整，直至求出最小運輸費用或最大運輸效率的解最大運輸效率的解。這種求解方法，就是圖上作業(yè)法。這種求解方法，就是圖上作業(yè)法。v 適用適用于交通線路呈樹狀、圈狀，而且對產銷地點的數(shù)量沒有于交通線路呈樹狀、圈狀，而且對產銷地點的數(shù)量沒有嚴格限制的情況。

35、嚴格限制的情況。v圖上作業(yè)法的求解規(guī)則可以歸納為：圖上作業(yè)法的求解規(guī)則可以歸納為：流向劃右流向劃右方，對流不應當；里圈、外圈分別算，要求不方，對流不應當；里圈、外圈分別算，要求不能過半圈長；若超過半圈長，應去運量最小段；能過半圈長；若超過半圈長，應去運量最小段；反復運算可得最優(yōu)方案。反復運算可得最優(yōu)方案。v圖上作業(yè)法包括運輸線路不成圈的圖上作業(yè)法圖上作業(yè)法包括運輸線路不成圈的圖上作業(yè)法和運輸線路成圈的圖上作業(yè)法。和運輸線路成圈的圖上作業(yè)法。1.1.運輸線路不成圈的圖上作業(yè)法運輸線路不成圈的圖上作業(yè)法v 對于線路不成圈的貨物運輸，即是不構成回路的運輸對于線路不成圈的貨物運輸，即是不構成回路的運輸

36、線路，包括直線、丁字線、交叉線和分支線等。只要線路，包括直線、丁字線、交叉線和分支線等。只要不出現(xiàn)對流和迂回現(xiàn)象，就是最優(yōu)調運方案。不出現(xiàn)對流和迂回現(xiàn)象，就是最優(yōu)調運方案。v 運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端點開始，按點開始，按“各站供需就近調撥各站供需就近調撥”的原則進行調配。的原則進行調配。v 如圖如圖3-13-1是某地區(qū)的物資供應網(wǎng)絡，有是某地區(qū)的物資供應網(wǎng)絡，有4 4個起運站個起運站、，供應量分別為，供應量分別為+7+7、+8+8、+6+6、+4+4單位（為單位（為了便于識別，供應量記了便于識別，供應量記“+ +”，需求量記，需求

37、量記“- -”）；另）；另有有4 4個目的地個目的地、，需求量分別為，需求量分別為-2-2、-8-8、-7-7、-8-8。為了便于檢查對流現(xiàn)象，把流向箭頭統(tǒng)一畫。為了便于檢查對流現(xiàn)象，把流向箭頭統(tǒng)一畫在右側。箭頭旁標注的數(shù)字表示調運量。在右側。箭頭旁標注的數(shù)字表示調運量。圖圖3-1 3-1 運輸線路不成圈的調運方案運輸線路不成圈的調運方案58-85-77248-8+8+7-2+4+6v具體調運方案是：具體調運方案是：v 從站點從站點開始，把開始，把7 7個單位的物資供應給個單位的物資供應給，剩余剩余5 5個單位，供應給個單位，供應給；站點；站點的的8 8個單位由個單位由供應；供應；剩余的剩余的

38、5 5個單位供應給個單位供應給，尚缺少尚缺少2 2單位由單位由提供。提供。的的4 4個單位經過個單位經過，連，連原有原有的的4 4單位合計單位合計8 8單位供給單位供給。這樣就得出一個最優(yōu)。這樣就得出一個最優(yōu)調運方案。調運方案。2.2.運輸線路成圈的圖上作業(yè)法運輸線路成圈的圖上作業(yè)法v 運輸線路成圈，就是形成閉合回路的環(huán)形線路，包括一個運輸線路成圈，就是形成閉合回路的環(huán)形線路，包括一個圈和多個圈。在圖圈和多個圈。在圖3-2中，包含有兩個圈，一是由中，包含有兩個圈，一是由、組成的圈；另一是由組成的圈；另一是由、組組成的圈。圈可以是三角形、四邊形和多邊形。圖成的圈。圈可以是三角形、四邊形和多邊形。

39、圖3-6中的兩中的兩個圈都是多邊形。起運站（目的地）之間線路旁括號內標注個圈都是多邊形。起運站（目的地）之間線路旁括號內標注的數(shù)字表示兩點之間的距離。的數(shù)字表示兩點之間的距離。v 對于成圈運輸線路的圖上作業(yè)法，可以按照如下三個步對于成圈運輸線路的圖上作業(yè)法，可以按照如下三個步驟求解，直到尋求到最優(yōu)方案。成圈的線路流向圖要同時達驟求解，直到尋求到最優(yōu)方案。成圈的線路流向圖要同時達到既無對流現(xiàn)象，又無迂回現(xiàn)象的要求才是最優(yōu)流向圖，所到既無對流現(xiàn)象，又無迂回現(xiàn)象的要求才是最優(yōu)流向圖，所對應的方案為最優(yōu)運輸方案。對應的方案為最優(yōu)運輸方案。 圖圖3-23-2運輸線路成圈的調運方案運輸線路成圈的調運方案v

40、 第第1步步 去段破圈，確定初始運輸方案。在成圈的線路去段破圈，確定初始運輸方案。在成圈的線路中，先假設某兩點間的線路中，先假設某兩點間的線路“不通不通”，去掉這段線路，去掉這段線路，把成圈線路轉化為不成圈的線路，即破圈；然后按照運把成圈線路轉化為不成圈的線路，即破圈；然后按照運輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。v 第第2 2步步 檢查有無迂回現(xiàn)象。因為流向箭頭都統(tǒng)一畫檢查有無迂回現(xiàn)象。因為流向箭頭都統(tǒng)一畫在線路右邊，所以圈內圈外都畫有一些流向。分別檢查在線路右邊，所以圈內圈外都畫有一些流向。分別檢查每個小圈，如果內圈和外圈流向的總

41、長度都不超過全圈每個小圈，如果內圈和外圈流向的總長度都不超過全圈總長度的總長度的1/21/2，那么，全圈就沒有迂回現(xiàn)象，這個線路流，那么，全圈就沒有迂回現(xiàn)象，這個線路流向圖就是最優(yōu)的，對應的方案就是最優(yōu)運輸方案。否則，向圖就是最優(yōu)的，對應的方案就是最優(yōu)運輸方案。否則，轉向第三步。轉向第三步。v 第第3 3步步 重新去段破圈，調整流向。在超過全圈總長重新去段破圈，調整流向。在超過全圈總長1/21/2的里（外）圈各段流向線上減去最小運量，然后在相的里（外）圈各段流向線上減去最小運量，然后在相反方向的外（里）圈流向線上和原來沒有流向線的各段上，反方向的外（里）圈流向線上和原來沒有流向線的各段上，加上

42、所減去的最小運量，這樣可以得到一個新的線路流向加上所減去的最小運量，這樣可以得到一個新的線路流向圖，然后轉到第二步檢查有無迂回現(xiàn)象。如此反復，直至圖，然后轉到第二步檢查有無迂回現(xiàn)象。如此反復，直至得到最優(yōu)線路流向圖為止。得到最優(yōu)線路流向圖為止。v 如果線路圖存在兩個及兩個以上的圈，則需分別對各如果線路圖存在兩個及兩個以上的圈，則需分別對各圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過全圈總線長的不超過全圈總線長的1/21/2，則不存在迂回現(xiàn)象，此方案為，則不存在迂回現(xiàn)象，此方案為最優(yōu)運輸方案。最優(yōu)運輸方案。 現(xiàn)在，解決【案例現(xiàn)在，解決

43、【案例4.34.3】所涉及問題?！克婕皢栴}。v （1）去段破圈，確定初始運輸方案。在圖）去段破圈，確定初始運輸方案。在圖4-1中，中，A1（南寧）（南寧）-B2（合山）（合山）-B3（宜州）（宜州）-B4（河池）（河池）-A2（巴馬）（巴馬）-B1（平果）組成的圈，去掉（平果）組成的圈，去掉A1至至B2的線路，然后根據(jù)的線路，然后根據(jù)“各站供需就近調撥各站供需就近調撥”的原則進的原則進行調運，即可得到初始運輸流向線路圖，如圖行調運，即可得到初始運輸流向線路圖，如圖1.4-6所示。所示。v（2）檢查有無迂回現(xiàn)象。由圖）檢查有無迂回現(xiàn)象。由圖1.4-6看出，不存看出，不存在對流現(xiàn)象，但是要檢查里

44、、外圈流向線長，看在對流現(xiàn)象，但是要檢查里、外圈流向線長，看是否超過全圈總長的是否超過全圈總長的1/2。 全圈總長全圈總長=（45+23+25+18+23+36）km=170km 半圈總長半圈總長=170/2km=85km 外圈流向線長外圈流向線長=（45+25+18+23）km=111km 里圈流向線長里圈流向線長= 23km，v 從計算結果看出，里圈流向線長從計算結果看出，里圈流向線長=23km，小于全圈總長，小于全圈總長的的1/2（85km），沒有迂回現(xiàn)象。而外圈流向線長），沒有迂回現(xiàn)象。而外圈流向線長111km，超過了全圈總長，超過了全圈總長1/2的的85km，可以斷定，初始運輸流向，

45、可以斷定，初始運輸流向線路存在迂回現(xiàn)象，所對應的運輸方案不是最優(yōu)方案，線路存在迂回現(xiàn)象，所對應的運輸方案不是最優(yōu)方案，必須進行優(yōu)化調整。必須進行優(yōu)化調整。v （3 3）重新去段破圈，調整流向。）重新去段破圈，調整流向。v 初始運輸中，外圈流向線路中運量最小的是初始運輸中，外圈流向線路中運量最小的是A1A1至至B1B1的的“20”20”，所以，去掉，所以，去掉A1A1到到B1B1的線路，并在外圈各段流的線路，并在外圈各段流向線路上減去最小運量向線路上減去最小運量“20”20”，同時在里圈各段流向線，同時在里圈各段流向線上和原來沒有流向線的上和原來沒有流向線的A1A1到到B2B2上，各加上最小運量

46、上，各加上最小運量“20”20”，這樣可以得到一個新的線路流向圖，如圖，這樣可以得到一個新的線路流向圖，如圖1.3-71.3-7所示。所示。v檢查新運輸線路圖的里、外圈流向線長，看是檢查新運輸線路圖的里、外圈流向線長，看是否超過全圈（封閉回路線）總長的否超過全圈（封閉回路線）總長的1/2。新的。新的流向線路圖相關情況是：流向線路圖相關情況是：v外圈流向總長外圈流向總長=（25+18+23）km=66kmv里圈流向總長里圈流向總長=（23+36）km=59kmv兩者均沒有超過全圈總的兩者均沒有超過全圈總的1/2，即，即85km，所以，所以調整后的新線路流向圖所對應的方案為最優(yōu)運調整后的新線路流向

47、圖所對應的方案為最優(yōu)運輸方案。輸方案。v之所以說調整后的新線路流向圖所對應的方案為最優(yōu)之所以說調整后的新線路流向圖所對應的方案為最優(yōu)運輸方案，可以將它與初始運輸方案進行對比：運輸方案，可以將它與初始運輸方案進行對比： 按調整后的新方案組織運輸，運力消耗為按調整后的新方案組織運輸，運力消耗為（2036+1023+2013+3023+3025+4018+8029+20127）tkm=8230tkm 按初始方案組織運輸?shù)倪\力消耗為按初始方案組織運輸?shù)倪\力消耗為（2045+1023+5025+8029+20127+2013+3023+6018）tkm =9270tkmv可見，調整后的運輸方案比初始運輸

48、方案節(jié)約運可見，調整后的運輸方案比初始運輸方案節(jié)約運力力1040tkm，當然是最優(yōu)運輸方案。，當然是最優(yōu)運輸方案。v多起點、多終點的物流運輸線路的選擇優(yōu)化方法多起點、多終點的物流運輸線路的選擇優(yōu)化方法，還有表上作業(yè)法等，限于篇幅，此處暫時不加，還有表上作業(yè)法等，限于篇幅，此處暫時不加以介紹。以介紹。項目項目 尋求最優(yōu)運輸方案尋求最優(yōu)運輸方案 圖圖3-2是一個單位的運輸是一個單位的運輸線路圖。圖中，線路圖。圖中，、 、 、 是產地，是產地， 、 、 、是銷地。起運站是銷地。起運站（目的地）之間線路旁括（目的地）之間線路旁括號內標注的數(shù)字表示兩點號內標注的數(shù)字表示兩點之間的距離。之間的距離。如何找

49、到最如何找到最優(yōu)運輸方案？優(yōu)運輸方案？ 技能訓練技能訓練圖圖1-71-7成圈的運輸線路成圈的運輸線路v一、各公司提供答案（一、各公司提供答案（1個個/公司）公司）v二、參考答案（見給你提個醒）二、參考答案（見給你提個醒）v三、評價及獎勵結果公布三、評價及獎勵結果公布v四、學習收獲一句話及下次課預告四、學習收獲一句話及下次課預告給你提個醒給你提個醒v 如果運輸線路全圖存在兩個及兩個以上的圈，則需分別如果運輸線路全圖存在兩個及兩個以上的圈，則需分別對各圈進行是否存在迂回線路的檢查，如果各圈的里、對各圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過全圈總線長的外圈都不超過全圈總線長的1/2，

50、則不存在迂回現(xiàn)象，則，則不存在迂回現(xiàn)象，則此方案為最優(yōu)運輸方案。此方案為最優(yōu)運輸方案。 v 1.1.分別破圈。對于由分別破圈。對于由、組成的圈，組成的圈，去掉去掉至至的線路；在由的線路；在由、組成的圈組成的圈中，去掉中，去掉到到的線路，便得到不成圈的線路，從各端的線路，便得到不成圈的線路，從各端點開始，按點開始，按“各站供需就近調撥各站供需就近調撥”的原則進行調配，得的原則進行調配，得出調運方案，如圖出調運方案，如圖1-81-8。圖中線路旁括號內的數(shù)字表示兩。圖中線路旁括號內的數(shù)字表示兩點之間的距離，箭頭線旁不帶括號的數(shù)字表示調運量。點之間的距離，箭頭線旁不帶括號的數(shù)字表示調運量。v 1 去段

51、破圈，確定初始運輸方案。在成圈的線路中，去段破圈，確定初始運輸方案。在成圈的線路中，先假設某兩點間的線路先假設某兩點間的線路“不通不通”，去掉這段線路，把成，去掉這段線路，把成圈線路轉化為不成圈的線路，即破圈；然后按照運輸線圈線路轉化為不成圈的線路，即破圈；然后按照運輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。路不成圈的圖上作業(yè)法，即可得到初始運輸方案。+8-7-8(50)(90)55246(50)+71238457-2+4+6-8(50)(200)(90)(30)(50)(100)788v 2.檢查。在圖檢查。在圖1-8上部的圈中，總長度為上部的圈中，總長度為580，調運方案，調運方案外

52、圈總長度為外圈總長度為50+50+90+100=290，內圈總長度為，內圈總長度為90，均不超過圈總長度的一半。而在圖下部的圈中，總長度均不超過圈總長度的一半。而在圖下部的圈中，總長度為為310，外圈總長度為，外圈總長度為50+90+50=190，大于圈總長度的，大于圈總長度的一半。所以，此方案不是最優(yōu)方案，應當進行調整。一半。所以，此方案不是最優(yōu)方案，應當進行調整。v 3.3.調整。辦法是：去掉調整。辦法是：去掉至至、至至的線路（因為的線路（因為至至是是、組成的圈中外圈各段流向線組成的圈中外圈各段流向線上的最小運量），運輸線路就不成圈了。按照前述辦法，上的最小運量），運輸線路就不成圈了。按照

53、前述辦法，做出調運方案如圖做出調運方案如圖1-91-9。圖圖1-91-9運輸線路成圈的初始調運方案運輸線路成圈的初始調運方案v 4.再檢查。在圖再檢查。在圖1-9上部的圈中，總長度的上部的圈中，總長度的1/2為為290，調，調運方案外圈總長度為運方案外圈總長度為50+50+90+100=290，內圈總長度，內圈總長度為為0，均不超過圈總長度的一半。在圖，均不超過圈總長度的一半。在圖1-9下部的圈中，下部的圈中，總長度的總長度的1/2為為155，外圈總長度為，外圈總長度為50+50=100，內圈總，內圈總長度為長度為30+90=120，外、內圈總長度均不超過全圈總長，外、內圈總長度均不超過全圈總

54、長度的一半（度的一半（155）。所以，圖）。所以，圖1-9方案是最優(yōu)方案。方案是最優(yōu)方案。課后自我檢測課后自我檢測v在給定的運輸線路圖在給定的運輸線路圖( (圖圖1-101-10) )上，運用圖上作上，運用圖上作業(yè)法，求出最優(yōu)運輸線路圖。業(yè)法，求出最優(yōu)運輸線路圖。A2A1A3A3圖圖1-101-10某集團公司物資供應交通線路圖某集團公司物資供應交通線路圖B1B5B7B3（78）-1500（75）（32）（109）（132）（74）（57）（13）+2000+2900-1000+3200-1300-600B8-900（55）B6B2B4-900-900（74）（45）（41）-1000v問題：優(yōu)

55、化物流運輸線路與運輸線路開發(fā)問題：優(yōu)化物流運輸線路與運輸線路開發(fā)“不是一碼事不是一碼事”主要區(qū)別是：優(yōu)化物流運輸線路是在已知貨物主要區(qū)別是：優(yōu)化物流運輸線路是在已知貨物名稱及數(shù)量、貨源地和目的地的情況下，根據(jù)名稱及數(shù)量、貨源地和目的地的情況下，根據(jù)運輸合理化原則對運輸線路的選擇與優(yōu)化，而運輸合理化原則對運輸線路的選擇與優(yōu)化，而運輸線路的開發(fā)主要是根據(jù)當前物流市場環(huán)境運輸線路的開發(fā)主要是根據(jù)當前物流市場環(huán)境、貨源數(shù)量情況、政府規(guī)定等對運輸線路的選、貨源數(shù)量情況、政府規(guī)定等對運輸線路的選擇確定，兩者在目的、市場環(huán)境等多方面不同擇確定，兩者在目的、市場環(huán)境等多方面不同，因此不是一碼事。，因此不是一碼

56、事。配送運輸配送運輸表上作業(yè)法表上作業(yè)法 例例1 1：有四個用戶：有四個用戶B1B1、B2B2、B3B3、B4B4所需的某種物品可由所需的某種物品可由三個配送中心三個配送中心A1A1、A2A2、A3A3供應，各配送中心的可供給量供應，各配送中心的可供給量和各用戶的需求量以及各配送中心運送單位物品到各用和各用戶的需求量以及各配送中心運送單位物品到各用戶的運價（單位：百元戶的運價（單位：百元/ /噸）見下表，求使總運費最小的噸）見下表，求使總運費最小的調運方案。調運方案。 9192第一步：確定初始方案第一步：確定初始方案最小元素法最小元素法 基本思想是按照運價的大小決定供應的先后，優(yōu)先滿足單位運價最小基本思想是按照運價的大小決定供應的先后，優(yōu)先滿足單位運價最小者的供需要求者的供需要求 40 1 5 3 6 3 7 2 3 5 4 4 2 70 50 301093 從上圖可知，初始方案對應的總運費為：從上圖可知，初始方案對應的總運費為： 70 702+302+303+503+504+404+401+101+102=4902=490（元）（元）94 第二步：用位勢法（第二步：用位勢法（霍撒克方法