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

1、線路優(yōu)化線路優(yōu)化-圖上作業(yè)法圖上作業(yè)法第四章第四章 運(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)化方法-圖上作業(yè)法能力目標(biāo)養(yǎng)成嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)，培養(yǎng)團(tuán)隊(duì)協(xié)作能力。能夠利用物流運(yùn)輸線路優(yōu)化方法解決實(shí)際工作中存在問題。任務(wù)描述任務(wù)描述 任務(wù)五 運(yùn)輸線路優(yōu)化 案例放送案例放送任務(wù)五 運(yùn)輸線路優(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è)集團(tuán)公司特效藥品交通線路圖康鑫全藥業(yè)集團(tuán)公司特效藥品交通線路圖 相關(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)形線路包還有形成閉合回路的環(huán)形線路，環(huán)形線路包括有一個(gè)圈和多個(gè)圈的。案例中涉及的路線括有一個(gè)圈和多個(gè)圈的。案例中涉及的路線類型為類型為多起點(diǎn)、多終點(diǎn)問題的物流運(yùn)輸線路多起點(diǎn)、多終點(diǎn)問題的物流運(yùn)輸線路問題問題一、物流運(yùn)輸線路的類型一、物流運(yùn)輸線路的類型v 多起點(diǎn)、多終點(diǎn)問題的物流運(yùn)輸線路

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

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

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

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

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

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

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

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

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

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

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

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