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

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