運(yùn)輸路線優(yōu)化PPT課件

,節(jié)約里程法,最短路徑法,圖表作業(yè)法,圖上作業(yè)法,（2）運(yùn)輸線路的選擇,運(yùn)輸線路的優(yōu)化,在車輛路線設(shè)計(jì)方案中，“節(jié)約法”是最廣為人知的方法，它也形成了人工和計(jì)算機(jī)載荷計(jì)劃系統(tǒng)的基礎(chǔ)。,從倉庫O要運(yùn)送貨物給客戶A和B,第一條路線是從O到A，再返回，然后再從O到B，再返回O，總距離為aabb2a2b,外一種路線，從O到A到B，再到O?？偩嚯x為：abx。將客戶結(jié)合考慮，在第二種方案下走行路線的節(jié)約里程數(shù)是：（2a2b）（abx）即：abx,1節(jié)約里程法,它從不為負(fù)。因?yàn)槿切蔚牡谌龡l邊總是小于其他兩條邊之和，因此，它最小為零。將客戶連接起來，增加了節(jié)約。客戶之間的距離越近，而且它們距離倉庫越遠(yuǎn)，那么節(jié)約就會越大。這個(gè)方法也可以用時(shí)間來代替距離計(jì)算。,2,3,1,4,關(guān)于這個(gè)公式，有許多事情要注意：,為了描述這個(gè)方法的使用，考慮下例。,例：如圖所示，需要安排從倉庫O送貨給四個(gè)客戶A、B、C、D。任何路程不得超過75千米。,配送路線圖,解：第一步：計(jì)算任一對客戶的節(jié)約里程值，見下表：,節(jié)約值計(jì)算表,解：第一步：計(jì)算任一對客戶的節(jié)約里程值，見下表：,節(jié)約值計(jì)算表,第二步：從最大的節(jié)約值開始，將客戶連接在一起，直到達(dá)到一個(gè)限制。,第三步：因此選擇第一條路線OCDO。,從最大節(jié)約值27開始，連接客戶C和D。距離OCDO，和為63千米，沒有超過限制。選擇下一個(gè)最大的節(jié)約值，為20，將A、B、C和D連在一起，距離OABCDO，超過了75千米，不予采納。選擇另一個(gè)最大的節(jié)約值10，將B、C和D連接在一起，距離OBCDO，超過了75千米，仍然不采納。選擇另一個(gè)最大的節(jié)約值5，將A、C和D連接在一起，距離OADCO，大于75千米，不采納。,計(jì)算結(jié)果,第五步：重新進(jìn)行剛才的程序，從最大的20開始，將A和B連接在一起，距離OABO是50千米，是第二條路線。,第四步：劃掉C和D之間的行和列。,如左圖所示，要從P點(diǎn)出發(fā)，把貨物運(yùn)到AJ共10個(gè)目的地，括號內(nèi)的數(shù)字表示需要運(yùn)送貨物的噸數(shù)，線路上的數(shù)字表示運(yùn)輸距離（單位：km）。另外，假設(shè)現(xiàn)在只有額定載重量分別為2t和4t的貨車，每車每次運(yùn)行距離不超過30km。請為該次運(yùn)輸任務(wù)選擇最優(yōu)運(yùn)輸線路。,用節(jié)約里程法選擇運(yùn)輸線路,圖表分析法是在分區(qū)產(chǎn)銷平衡所確定的供銷區(qū)域內(nèi)，按照生產(chǎn)地與消費(fèi)地的地理分布，根據(jù)有利于生產(chǎn)、有利于市場供給、近產(chǎn)近銷的原則，應(yīng)用交通路線示意圖和商品產(chǎn)銷平衡表找出產(chǎn)銷之間經(jīng)濟(jì)合理的商品運(yùn)輸路線。,2、圖表分析法,步驟2,步驟1,步驟3,步驟4,編制產(chǎn)銷平衡表,繪制交通示意圖,制定商品運(yùn)輸方案(就近原則),填入商品平衡表,圖表分析法(操作步驟),例：有一種商品從A地運(yùn)出400單位，從B地運(yùn)出700單位，從C地運(yùn)出300單位，從D地運(yùn)出600單位，供給abc三地分別為700、800、500單位，各地間的里程(km)圖如下，采用圖表分析法進(jìn)行運(yùn)輸路線的優(yōu)化。,小飛守角制作,步驟1：編制產(chǎn)銷平衡表,小飛守角制作,a,B,D,步驟2：繪制交通示意圖,表示接受點(diǎn)，其中數(shù)字表示運(yùn)量,表示發(fā)運(yùn)點(diǎn)，其中數(shù)字表示發(fā)出量,表示兩地的距離,小飛守角制作,a,B,D,步驟3：制定商品運(yùn)輸方案,300,200,C,步驟4：填入商品平衡表,圖表分析法簡單易行，不必計(jì)算運(yùn)輸里程，適用于產(chǎn)銷地區(qū)域較小，產(chǎn)銷點(diǎn)少，產(chǎn)銷關(guān)系比較簡單的情況。,最短路徑法要求在一個(gè)無向圖中從出發(fā)點(diǎn)開始，用最短的距離（或最少的費(fèi)用）到達(dá)目的地。,從出發(fā)點(diǎn)開始，將其運(yùn)輸距離標(biāo)號為“0”,找出與出發(fā)點(diǎn)相鄰但未標(biāo)號點(diǎn)的最小距離值并在相應(yīng)點(diǎn)標(biāo)號。,找出與已標(biāo)號點(diǎn)相鄰但未標(biāo)號點(diǎn)的最小距離值并在相應(yīng)點(diǎn)標(biāo)號。,重復(fù)步驟3，直到最后一個(gè)未標(biāo)號點(diǎn)也標(biāo)號.,3最短路徑法,用最短路徑法選擇運(yùn)輸線路,如上圖所示，假設(shè)要從V1點(diǎn)出發(fā)到V7，請用標(biāo)號法找出V1到V7的最短路徑。圖中線路上的數(shù)字表示運(yùn)輸距離（KM）。,【分析】從V1點(diǎn)出發(fā)到V7點(diǎn)，可以經(jīng)過V1V2V5V7，也可以經(jīng)過V1V3V6V7等。要找出最短路徑，只需按步驟逐步計(jì)算即可。【操作】步驟1在V1點(diǎn)標(biāo)為L1=0。步驟2求與V1相鄰但未標(biāo)號點(diǎn)的最小距離值并標(biāo)號。V2：0+5=5V3：0+2=2則標(biāo)號L3=2，并標(biāo)記V1V3。,步驟3求與V1、V3相鄰但未標(biāo)號點(diǎn)的最小距離值并標(biāo)號。V2：0+5=5V4：2+7=9V6：2+4=6則標(biāo)號L2=5，并標(biāo)記V1V2。步驟4求與V1、V2、V3相鄰但未標(biāo)號點(diǎn)的最小距離值并標(biāo)號。V4：5+2=7V5：5+7=12V6：2+4=6則標(biāo)號L6=6，并標(biāo)記V3V6。,2最短路徑法,步驟5求與V1、V2、V3、V6相鄰但未標(biāo)號點(diǎn)的最小距離值并標(biāo)號。,則標(biāo)號L4=7，L5=7，并標(biāo)記V2V4，V6V5。,步驟6求與V1、V2、V3、V4、V5、V6相鄰未標(biāo)號點(diǎn)的最小值。,則標(biāo)號L7=10，并標(biāo)記V5V7。,綜上所述，可知V1到V7最短路徑為V1V3V6V5V7（如圖中雙線所示），距離為2+4+1+3=10。,如圖所示是某地區(qū)交通運(yùn)輸?shù)氖疽鈭D.試問：從V1出發(fā)，經(jīng)哪條路線到達(dá)V8才能使總行程最短？,圖上作業(yè)法是指利用產(chǎn)地和銷地的地理分布和運(yùn)輸線路示意圖制定產(chǎn)品運(yùn)輸最小噸公里的方法。圖上作業(yè)法可以避免對流運(yùn)輸和迂回運(yùn)輸?shù)默F(xiàn)象，找出運(yùn)輸線路最短、運(yùn)力最省的運(yùn)輸方案。其原理可歸納為：流向畫右方，對流不應(yīng)當(dāng)；里圈、外圈分別算，要求不能過半圈長；如若超過半圈長，應(yīng)去運(yùn)量最小段；反復(fù)運(yùn)算可得最優(yōu)方案。,4圖上作業(yè)法,運(yùn)輸線路不成圈是指不構(gòu)成回路的“樹”形線路，包括直線、丁字線、交叉線、分支線等，其中，直線為圖上作業(yè)法的基本線路。無論哪種線路，都要將此轉(zhuǎn)化為直線運(yùn)輸形式，以便做出流向線。運(yùn)輸線路不成圈的圖書作業(yè)法較為簡單，就是從各端點(diǎn)開始，按“各站供需就近調(diào)撥”的原則進(jìn)行調(diào)配，只要不出現(xiàn)對流現(xiàn)象就是最優(yōu)方案。,（1）運(yùn)輸線路不成圈的圖上作業(yè)法,某地區(qū)物資供應(yīng)情況如下圖所示，其中“”表示起運(yùn)站，“”表示目的站?，F(xiàn)要求通過圖上作業(yè)法得到物資調(diào)運(yùn)的最優(yōu)方案。,運(yùn)輸線路不成圈的圖上作業(yè)法,【分析】該題中有4個(gè)起運(yùn)站：A1、A2、A3、A4，供應(yīng)量分別為+7、+8、+6、+4；另有4個(gè)目的站B1、B2、B3、B4，需求量分別為-2、-8、-7、-8。為了便于檢查對流現(xiàn)象，把流向箭頭統(tǒng)一畫在線路右邊，調(diào)運(yùn)量用數(shù)字表示，標(biāo)注在箭頭旁邊。【操作】步驟1從起運(yùn)站A1開始，把7個(gè)單位的物資供應(yīng)給B1，剩余5個(gè)單位的物資再調(diào)運(yùn)給A2。步驟2起運(yùn)站A2的8個(gè)單位的物資供應(yīng)給B2，從A1調(diào)運(yùn)過來的5個(gè)單位的物資供應(yīng)給B3，這時(shí)，B3缺2個(gè)單位的物資。,步驟3將起運(yùn)站A4的4個(gè)單位的物資調(diào)運(yùn)給A3，連同A3原有的6個(gè)單位的物資共10個(gè)單位，供應(yīng)8個(gè)單位給B4，另外2個(gè)單位供應(yīng)給B3，填補(bǔ)B3所缺的2個(gè)單位的物資。步驟4此時(shí)，沒有出現(xiàn)對流現(xiàn)象，故此方案為最優(yōu)方案，如下圖所示。,運(yùn)輸線路成圈，就是形成閉合回路的“環(huán)”形線路，包括一個(gè)圈（有三角形、四邊形、多邊形）和多個(gè)圈。對于成圈運(yùn)輸線路的圖上作業(yè)法，可按下述三個(gè)步驟尋求最優(yōu)方案。去段破圈，確定初始運(yùn)輸方案就是在成圈的線路中，先假設(shè)某兩點(diǎn)間的線路“不通”，去掉這段線路，把成圈線路轉(zhuǎn)化為不成圈的線路，即破圈；按照運(yùn)輸線路不成圈的圖上作業(yè)法，即可得到初始運(yùn)輸方案。,（2）運(yùn)輸線路成圈的圖上作業(yè)法,檢查有無迂回現(xiàn)象因?yàn)榱飨蚣^統(tǒng)一畫在線路右邊，所以圈內(nèi)外都畫有一些流向，分別檢查每個(gè)小圈，如果圈內(nèi)和圈外流向的總長度都不超過全圈總長度的1/2，則可斷定全圈不存在迂回現(xiàn)象，這個(gè)線路流向圖就是最優(yōu)的，否則繼續(xù)第三步。重新去段破圈，調(diào)整流向在超過全圈總長1/2的里（外）圈各段流向線上減去最小運(yùn)量，然后在相反方向的外（里）圈流向線上和原來沒有流向線的各段上加上或減去最小運(yùn)量，這樣可以得到一個(gè)新的線路流向圖，然后轉(zhuǎn)到第二步檢查有無迂回現(xiàn)象。如此反復(fù)，直到得到最優(yōu)線路流向圖為止。,某地區(qū)的物資供應(yīng)情況如下圖所示，其中“”表示起運(yùn)站，“”表示目的站，線路間括號中的數(shù)字表示起運(yùn)站與目的站之間的距離（單位：km），現(xiàn)要求用圖上作業(yè)法找出物資調(diào)運(yùn)的最優(yōu)方案。,運(yùn)輸線路成圈的圖上作業(yè)法,【分析】該題中有4個(gè)起運(yùn)站：A1、A2、A3、A4，供應(yīng)量分別為+20、+60、+100、+20；另有5個(gè)目的站B1、B2、B3、B4、B5，需求量分別為-30、-30、-50、-70、-20。圖中有一個(gè)圈，由A1、B1、A2、B4、B3、B2構(gòu)成?！静僮鳌坎襟E1去段破圈，確定初始運(yùn)輸方案。去掉A1到B2的線路，然后按照“各站供需就近調(diào)撥”的原則進(jìn)行調(diào)運(yùn)，即可得到初始運(yùn)輸流向線路圖，如下圖所示。,步驟2檢查有無迂回現(xiàn)象。由上圖可看出不存在對流現(xiàn)象，但要檢查里、外圈流向線長，看是否超過全圈（閉合線路）總長的1/2。在本例中，全圈總長為45+23+25+18+23+36=170（km）半圈長為170/2=85（km）外圈流向總長為45+25+18+23=111（km）里圈流向總長為23（km）因?yàn)橥馊α飨蚩傞L超過了全圈總長的1/2（111km85km），則可斷定初始運(yùn)輸線路存在迂回現(xiàn)象，所對應(yīng)的方案不是最優(yōu)方案。因此，必須進(jìn)行優(yōu)化調(diào)整。,步驟3重新去段破圈，調(diào)整流向。初始方案中里圈符合要求，外圈流向總長超過全圈的1/2，故需縮小外圈。因?yàn)橥馊α飨蚓€中運(yùn)量最小的是A1到B1的“20”，所以去掉A1到B1的線路，并在外圈各段流向線上減去“20”的運(yùn)量，同時(shí)在里圈個(gè)流向線上以及原來沒有流向線的A1到B2線上各加上“20”的運(yùn)量，這樣可得到新的運(yùn)輸線路流向圖，如下圖所示。,步驟4檢查新的流向線路圖的里、外圈流向線長，看是否超過全圈（閉合線路）總長的1/2，在本例中，外圈流向總長為25+18+23=66（km）里圈流向總長為23+36=59（km）兩者均沒有超過全圈總長的1/2（即85km)，所以調(diào)整后的新流向線路