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

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