運輸線路優(yōu)化3---圖上作業(yè)法

1、線路優(yōu)化線路優(yōu)化-圖上作業(yè)法圖上作業(yè)法第四章第四章 運輸管理運輸管理本課程教學的組織本課程教學的組織任務五 運輸線路優(yōu)化知識目標明確優(yōu)化物流運輸線路與運輸線路開發(fā)是不同的。掌握多起點多終點的物流運輸線路類型及其特點。掌握運輸線路選擇的優(yōu)化方法-圖上作業(yè)法能力目標養(yǎng)成嚴謹的工作作風，培養(yǎng)團隊協作能力。能夠利用物流運輸線路優(yōu)化方法解決實際工作中存在問題。任務描述任務描述 任務五 運輸線路優(yōu)化 案例放送案例放送任務五 運輸線路優(yōu)化A1A2A4A3B2B3B5B4B1（36）+20（45）（23）（18）（25）（23）（29）（127）（13）+60+100+20-30-30-50-70-20圖圖4

2、-1 4-1 康鑫全藥業(yè)集團公司特效藥品交通線路圖康鑫全藥業(yè)集團公司特效藥品交通線路圖 相關理論知識相關理論知識任務五 運輸線路優(yōu)化v 物流運輸線路，從起點到終點，常見的有物流運輸線路，從起點到終點，常見的有不成圈的直線、丁字線、交叉線和分支線，不成圈的直線、丁字線、交叉線和分支線，還有形成閉合回路的環(huán)形線路，環(huán)形線路包還有形成閉合回路的環(huán)形線路，環(huán)形線路包括有一個圈和多個圈的。案例中涉及的路線括有一個圈和多個圈的。案例中涉及的路線類型為類型為多起點、多終點問題的物流運輸線路多起點、多終點問題的物流運輸線路問題問題一、物流運輸線路的類型一、物流運輸線路的類型v 多起點、多終點問題的物流運輸線路

3、，在物流多起點、多終點問題的物流運輸線路，在物流運輸實踐中，經常存在。如多個供應商供應給多個運輸實踐中，經常存在。如多個供應商供應給多個工廠的情況，或者把不同工廠生產的同一產品分配工廠的情況，或者把不同工廠生產的同一產品分配到不同用戶的問題。在這些問題中，起點和終點都到不同用戶的問題。在這些問題中，起點和終點都不是單一的。在這類問題中，各供應點的供應量往不是單一的。在這類問題中，各供應點的供應量往往也有限制。往也有限制。v 在多個貨源地服務于多個目的地時，物流運輸線在多個貨源地服務于多個目的地時，物流運輸線路存在兩種情況：運輸線路成圈的和不成圈的。路存在兩種情況：運輸線路成圈的和不成圈的。一、

4、物流運輸線路的類型一、物流運輸線路的類型二、物流運輸線路的選擇優(yōu)化二、物流運輸線路的選擇優(yōu)化 有多個貨源地服務于多個目的地時，物流運輸有多個貨源地服務于多個目的地時，物流運輸線路選擇優(yōu)化的任務是要指定為各目的地服務線路選擇優(yōu)化的任務是要指定為各目的地服務的供貨地，同時要找到供貨地、目的地之間的的供貨地，同時要找到供貨地、目的地之間的最佳路徑。解決這類問題可以運用一類特殊的最佳路徑。解決這類問題可以運用一類特殊的線性規(guī)劃方法即物資調運問題線性規(guī)劃方法即物資調運問題圖上作業(yè)法圖上作業(yè)法進行進行求解。求解。二、物流運輸線路的選擇優(yōu)化二、物流運輸線路的選擇優(yōu)化v圖上作業(yè)法圖上作業(yè)法是在運輸圖上求解線性

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

6、圈、外圈分別算，劃右方，對流不應當；里圈、外圈分別算，要求不能過半圈長；若超過半圈長，應去要求不能過半圈長；若超過半圈長，應去運量最小段；運量最小段；反復運算可得最優(yōu)方案。反復運算可得最優(yōu)方案。v圖上作業(yè)法包括運輸線路不成圈的圖上作圖上作業(yè)法包括運輸線路不成圈的圖上作業(yè)法和運輸線路成圈的圖上作業(yè)法。業(yè)法和運輸線路成圈的圖上作業(yè)法。二、物流運輸線路的選擇優(yōu)化二、物流運輸線路的選擇優(yōu)化1.1.運輸線路不成圈的圖上作業(yè)法運輸線路不成圈的圖上作業(yè)法v對于線路不成圈的貨物運輸，即是不構成回路的運對于線路不成圈的貨物運輸，即是不構成回路的運輸線路，包括直線、丁字線、交叉線和分支線等。輸線路，包括直線、丁字

7、線、交叉線和分支線等。只要不出現對流和迂回現象，就是最優(yōu)調運方案。只要不出現對流和迂回現象，就是最優(yōu)調運方案。v運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端點運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端點開始，按開始，按“各站供需就近調撥各站供需就近調撥”的原則進行調配。的原則進行調配。二、物流運輸線路的選擇優(yōu)化二、物流運輸線路的選擇優(yōu)化圖圖3-1 3-1 運輸線路不成圈的調運方案運輸線路不成圈的調運方案585-8-77248-8+8+7-2+4+62.2.運輸線路成圈的圖上作業(yè)法運輸線路成圈的圖上作業(yè)法v 對于成圈運輸線路的圖上作業(yè)法，可以按照如對于成圈運輸線路的圖上作業(yè)法，可以按照如下三個

8、步驟求解，直到尋求到最優(yōu)方案。成圈的線下三個步驟求解，直到尋求到最優(yōu)方案。成圈的線路流向圖要同時達到既無對流現象，又無迂回現象路流向圖要同時達到既無對流現象，又無迂回現象的要求才是最優(yōu)流向圖，所對應的方案為最優(yōu)運輸的要求才是最優(yōu)流向圖，所對應的方案為最優(yōu)運輸方案。方案。 v 第第1 1步步 去段破圈，確定初始運輸方案。在去段破圈，確定初始運輸方案。在成圈的線路中，先假設某兩點間的線路成圈的線路中，先假設某兩點間的線路“不通不通”，去掉這段線路，把成圈線路轉化為不成圈，去掉這段線路，把成圈線路轉化為不成圈的線路，即破圈；然后按照運輸線路不成圈的的線路，即破圈；然后按照運輸線路不成圈的圖上作業(yè)法，

9、即可得到初始運輸方案。圖上作業(yè)法，即可得到初始運輸方案。（1 1）工作過程）工作過程v 第第2 2步步 檢查有無迂回現象。因為流向箭頭都統一畫檢查有無迂回現象。因為流向箭頭都統一畫在線路右邊，所以圈內圈外都畫有一些流向。分別檢在線路右邊，所以圈內圈外都畫有一些流向。分別檢查每個小圈，如果內圈和外圈流向的總長度都不超過查每個小圈，如果內圈和外圈流向的總長度都不超過全圈總長度的全圈總長度的1/21/2，那么，全圈就沒有迂回現象，這，那么，全圈就沒有迂回現象，這個線路流向圖就是最優(yōu)的，對應的方案就是最優(yōu)運輸個線路流向圖就是最優(yōu)的，對應的方案就是最優(yōu)運輸方案。否則，轉向第三步。方案。否則，轉向第三步。

10、v 第第3 3步步 重新去段破圈，調整流向。在超過全圈總長重新去段破圈，調整流向。在超過全圈總長1/21/2的里（外）圈各段流向線上減去最小運量，然后在的里（外）圈各段流向線上減去最小運量，然后在相反方向的外（里）圈流向線上和原來沒有流向線的相反方向的外（里）圈流向線上和原來沒有流向線的各段上，加上所減去的最小運量，這樣可以得到一個各段上，加上所減去的最小運量，這樣可以得到一個新的線路流向圖，然后轉到第二步檢查有無迂回現象。新的線路流向圖，然后轉到第二步檢查有無迂回現象。如此反復，直至得到最優(yōu)線路流向圖為止。如此反復，直至得到最優(yōu)線路流向圖為止。v 注：注： 如果線路圖存在兩個及兩個以上的圈，

11、如果線路圖存在兩個及兩個以上的圈，則需分別對各圈進行是否存在迂回線路的檢查，則需分別對各圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過全圈總線長的如果各圈的里、外圈都不超過全圈總線長的1/21/2，則不存在迂回現象，此方案為最優(yōu)運輸方案。則不存在迂回現象，此方案為最優(yōu)運輸方案。 （2 2）解決【案例解決【案例4.54.5】所涉及問題】所涉及問題第一步：去段破圈，形成初始方案v第二步：檢查有無迂回現象。由圖看出，不存在對流第二步：檢查有無迂回現象。由圖看出，不存在對流現象，但是要檢查里、外圈流向線長，看是否超過全現象，但是要檢查里、外圈流向線長，看是否超過全圈總長的圈總長的1/2。 全

12、圈總長全圈總長=（45+23+25+18+23+36）km=170km 半圈總長半圈總長=170/2km=85km 外圈流向線長外圈流向線長=（45+25+18+23）km=111km 里圈流向線長里圈流向線長= 23km，v 從計算結果看出，里圈流向線長從計算結果看出，里圈流向線長=23km，小于全圈總長，小于全圈總長的的1/2（85km），沒有迂回現象。而外圈流向線長），沒有迂回現象。而外圈流向線長111km，超過了全圈總長，超過了全圈總長1/2的的85km，可以斷定，初始運輸流向，可以斷定，初始運輸流向線路存在迂回現象，所對應的運輸方案不是最優(yōu)方案，線路存在迂回現象，所對應的運輸方案不是

13、最優(yōu)方案，必須進行優(yōu)化調整。必須進行優(yōu)化調整。v 第三步第三步 調整初始方案調整初始方案v 初始運輸中，外圈流向線路中運量最小的是初始運輸中，外圈流向線路中運量最小的是A1A1至至B1B1的的“20”20”，所以，去掉，所以，去掉A1A1到到B1B1的線路，并在外圈各段流的線路，并在外圈各段流向線路上減去最小運量向線路上減去最小運量“20”20”，同時在里圈各段流向線，同時在里圈各段流向線上和原來沒有流向線的上和原來沒有流向線的A1A1到到B2B2上，各加上最小運量上，各加上最小運量“20”20”，這樣可以得到一個新的線路流向圖，這樣可以得到一個新的線路流向圖v檢查新運輸線路圖的里、外圈流向線

14、長，看是檢查新運輸線路圖的里、外圈流向線長，看是否超過全圈（封閉回路線）總長的否超過全圈（封閉回路線）總長的1/2。新的。新的流向線路圖相關情況是：流向線路圖相關情況是：v外圈流向總長外圈流向總長=（25+18+23）km=66kmv里圈流向總長里圈流向總長=（23+36）km=59kmv兩者均沒有超過全圈總的兩者均沒有超過全圈總的1/2，即，即85km，所以，所以調整后的新線路流向圖所對應的方案為最優(yōu)運調整后的新線路流向圖所對應的方案為最優(yōu)運輸方案。輸方案。v之所以說調整后的新線路流向圖所對應的方案為最優(yōu)之所以說調整后的新線路流向圖所對應的方案為最優(yōu)運輸方案，可以將它與初始運輸方案進行對比：運輸方案，可以將它與初始運輸方案進行對比： 按調整后的新方案組織運輸，運力消耗為按調整后的新方案組織運輸，運力消耗為（2036+1023+2013+3023+3025+4018+8029+20127）tkm=8230tkm 按初始方案組織運輸的運力消耗為按初始方案組織運輸的運力消耗為（2045+1023+5025+8029+20127+2013+3023+6018）tkm =9270tkm任務實施任務實施 尋求最優(yōu)運輸方案尋求最優(yōu)運輸方案 圖圖3-2是一個單位的運輸是一個單位的運輸線路圖。圖中，線路圖。圖中，、 、 、 是產地，是產