運(yùn)輸線路決策ppt課件

1、選擇運(yùn)輸線路,起止點(diǎn)不同的單一問題：最短路徑法 多起點(diǎn)問題： 表上作業(yè)法 圖上作業(yè)法 節(jié)約里程法,最短路徑法,練習(xí),A,F,E,D,C,B,50,40,90,80,40,50,30,表上作業(yè)法是單純形法在求解運(yùn)輸問題的一種簡化方法，尋求運(yùn)費(fèi)最少的調(diào)運(yùn)方案。 解題思路是： 首先依據(jù)已知問題列出貨物的供需平衡表及運(yùn)價表；然后使用左上角法或者最小元素法或伏格爾法確定初始的調(diào)運(yùn)方案；最后根據(jù)一個判定法則判斷初始方案是不是最優(yōu)方案，如果不是最優(yōu)方案，要借助調(diào)出變量調(diào)整調(diào)配方案，再判斷，直到判定為最優(yōu)方案為止,初始方案容易找 利用左上角法尋找初始方案，基本思路 從運(yùn)價表元素中左上角的元素開始，集中供應(yīng)，依

2、次安排調(diào)運(yùn)量，直到得到一個可行方案。 利用最小元素法尋找初始方案，基本思路 就近運(yùn)輸，也就是從運(yùn)價表中找到最小的運(yùn)價，優(yōu)先滿足運(yùn)價最小的調(diào)運(yùn)，然后在剩下的供需狀態(tài)中，尋找次小的運(yùn)價，滿足此供需路徑，再重復(fù)尋找剩下的最小的運(yùn)價給與滿足，直到給出初始方案為止。這種方法找到的方案，雖然每次都找的是運(yùn)價最低的路徑優(yōu)先調(diào)運(yùn)，但為了節(jié)省一個節(jié)點(diǎn)的費(fèi)用，有時會造成其他節(jié)點(diǎn)費(fèi)用的大幅增加，所以進(jìn)行判定最優(yōu)解時，會比較麻煩,伏格爾法，一個調(diào)運(yùn)地如果不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有了一個差額，差額越大，說明不按最小運(yùn)費(fèi)供應(yīng)，越不合理，運(yùn)費(fèi)增加越多，所以應(yīng)優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn),例3-1 某公司有3個倉

3、庫，分別是A、B、C，供應(yīng)量分別是7噸、4噸、9噸，每天向4個配送中心送貨，分別是甲、乙、丙、丁，需求量分別是10噸，3噸、2噸和5噸。單位運(yùn)價表如圖7-2所示，請確定初始可行方案,單位運(yùn)價表 單位：元/噸,解： 第一步建立貨物的供需平衡表及運(yùn)價表如表所示。 平衡表,第二步，利用最小元素法尋找初始方案,最小元素法確定的初始方案表,第三步判定最優(yōu)方案,位勢法 首先在初始方案中找到運(yùn)量分配最多的行或列，確定其所在行或列的位勢為零， 然后根據(jù)有調(diào)運(yùn)量的格所對應(yīng)的運(yùn)價等于行位勢加上列位勢之和，依次求出各行和列的位勢， 再根據(jù)下列公式求空格所對應(yīng)的檢驗數(shù),Aij Cij （Ui + Vj） 公式中的Ai

4、j表示空格所對應(yīng)的檢驗數(shù)，Cij表示空格所對應(yīng)的運(yùn)價，Ui表示行位勢，Vj表示列位勢，i表示運(yùn)價表的行數(shù)，j表示運(yùn)價表的列數(shù),最小元素法確定的初始方案表,最小元素法確定的初始方案的檢驗數(shù),最后判斷，如果所有的檢驗數(shù)均大于等于零，則判斷的方案最優(yōu)。當(dāng)檢驗數(shù)有至少一個負(fù)數(shù)時，說明該方案不是最優(yōu)的方案，運(yùn)輸成本還有調(diào)整的空間，對負(fù)數(shù)檢驗數(shù)絕對值最大的所在的閉回路進(jìn)行調(diào)整 。 Aij=0，初始方案最優(yōu)；有一個Aij0，則不是最優(yōu)，需要調(diào)整負(fù)數(shù)中|Aij |值最大的所在閉合回路,閉合回路 基本思路是從任意一個空格（沒有安排調(diào)運(yùn)量的格）出發(fā)，沿著行或列尋找的一條除此空格之外其余頂點(diǎn)均為有數(shù)字格（安排有調(diào)運(yùn)

5、量的格）的閉合回路。 找出某一空格的閉合回路；從該空格開始在閉合回路上給各個頂點(diǎn)進(jìn)行 “+” 、“- ”間隔標(biāo)號； 對負(fù)數(shù)檢驗數(shù)絕對值最大的所在的閉回路進(jìn)行調(diào)整:標(biāo)有負(fù)號頂點(diǎn)中對應(yīng)的最小運(yùn)量作為調(diào)入運(yùn)量，標(biāo)有“+”的頂點(diǎn)所對應(yīng)的運(yùn)量加上調(diào)入運(yùn)量，標(biāo)有“”的頂點(diǎn)所對應(yīng)的運(yùn)量減去調(diào)入運(yùn)量； 形成新的調(diào)運(yùn)方案，再判斷和調(diào)整直到得到最優(yōu)方案為止,例7-2 某公司有3個倉庫，分別是A、B、C，供應(yīng)量分別是7噸、4噸、9噸，每天向4個配送中心送貨，分別是甲、乙、丙、丁，需求量分別是10噸，3噸、2噸和5噸。單位運(yùn)價表如圖所示，請確定最優(yōu)方案,單位運(yùn)價表 單位：元/噸,Aij 0，得到最優(yōu)解 x13 = 5

6、, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3, 其余 xij = 0 ; 最優(yōu)值： f* = 35+102+13+81+46+53 = 85,例,某地區(qū)有3個煤礦，所產(chǎn)煤炭全部銷往兩座火力發(fā)電廠。各礦產(chǎn)量、電廠需求量及單位運(yùn)價表如表所示，問如何安排運(yùn)輸可使總運(yùn)費(fèi)最省,練習(xí)題:某商品產(chǎn)地：A、B、C、D銷地：a、b、c、d、e供應(yīng)量分別為：100、300、600、800，需求量分別為：250、300、350、400、500 ，請確定最優(yōu)方案。 單位運(yùn)價表 a b c d e A B C D,練習(xí),供需不平衡的物資調(diào)運(yùn)問題,1、供應(yīng)量大于需求量 2、需

7、求量大于供應(yīng)量,處理：引入一個虛設(shè)的需求點(diǎn)，令其的需求量等于實(shí)際問題中供應(yīng)量與需求量之差。實(shí)際中，相當(dāng)于在某個供應(yīng)點(diǎn)的倉庫里將多余部分儲存起來了。因此，可視其相應(yīng)運(yùn)價為,零,處理：引入一個虛設(shè)的供應(yīng)點(diǎn)，令其的供應(yīng)量等于實(shí)際問題中需求量與供應(yīng)量之差。實(shí)際中，相當(dāng)于在某個需求點(diǎn)內(nèi)設(shè)立一個倉庫，將不足部分另找出路供應(yīng)好，預(yù)先儲存起來了。相應(yīng)運(yùn)價為零,例:某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小,解：增加一個虛設(shè)的銷地運(yùn)輸費(fèi)用為0,例:某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地

8、B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小,解：增加一個虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0,圖上作業(yè)法,圖上作業(yè)法： 利用商品產(chǎn)地和銷地的地理分布和交通路線示意圖，采用科學(xué)規(guī)劃的方法，制定出商品合理的運(yùn)輸方案，來求得商品運(yùn)輸最小噸公里的方法。 它適用于交通線路為線狀、圈狀，而且對產(chǎn)銷地點(diǎn)的數(shù)量沒有嚴(yán)格限制的情況。 如果沒有對流和迂回，就是一個運(yùn)輸力最省的最優(yōu)方案,圖上作業(yè)法,交通圖畫法 1、交通圖的符號： 發(fā)點(diǎn)用“ ”表示，并將發(fā)貨量記在里面，收點(diǎn)用“ ”表示，并將收貨量記在里面。兩點(diǎn)間交通線的長度記在交通線旁邊。 2、調(diào)運(yùn)物資

9、的流向圖： 物資調(diào)運(yùn)的方向（流向）用“ ”表示，并把“ ” 按調(diào)運(yùn)方向畫在交通線的右邊，把調(diào)運(yùn)物資的數(shù)量記在“ ”的右邊并加上括號,例1：調(diào)運(yùn)線路呈線狀。 依據(jù)“就近調(diào)空”原則，只要不出現(xiàn)對流情況，即是最優(yōu)方案。 設(shè)產(chǎn)地A、D、F，產(chǎn)量為10、3、9，銷地B、C、E、G，需求為2、5、11、4，試求合理的運(yùn)輸方案,第一步，編制商品產(chǎn)銷平衡表,第二步，繪制交通線路示意圖,A 10,B -2,5 C,3 D,E -11,F 9,G -4,第三步，按交通路線示意圖進(jìn)行圖上作業(yè)。就近調(diào)空，首先從各端開始就近調(diào)運(yùn)，在進(jìn)行調(diào)整,A 10,B -2,5 C,3 D,E -11,F 9,G -4,第四步，將結(jié)

10、果填入商品調(diào)運(yùn)平衡表,例,有某物資17萬噸，由A1，A2，A3，A4發(fā)出，發(fā)量分別為5，2，3，7（單位：萬噸），運(yùn)往B1，B2，B3，B4，收量分別為8，1，3，5，收發(fā)量是平衡的，它的交通路線如圖所示，問應(yīng)如何調(diào)運(yùn)，才能使運(yùn)輸噸千米最小,例2：調(diào)運(yùn)線路呈圈狀。設(shè)有產(chǎn)地，銷地,其距離及供需量見書，求最優(yōu)運(yùn)輸線路。 它的原則可歸納為：流向劃右方，對流不應(yīng)當(dāng)；里圈、外圈分別算，要求不過半圈長；如若超過半圈長，應(yīng)甩運(yùn)量最小段；反復(fù)求算最優(yōu)方案,第一步，在每個圈中，去掉一段距離最長的線路，用虛線表示，變成線狀，再根據(jù)線路不含圈的情況作出初始調(diào)運(yùn)方案。 第二步，檢查有無迂回現(xiàn)象。 第三步，調(diào)整流向。

11、第四步將結(jié)果填入平衡表,例調(diào)運(yùn)線路成圈狀例。設(shè)有某商品發(fā)運(yùn)點(diǎn)A、B、C、D等四處，接收點(diǎn)a、b、c、d位于圈狀，其距離及供需量如表所示，試求最優(yōu)運(yùn)輸路線,解：具體作業(yè)步驟如下： A首先假定里程最長的一段沒有貨流通過，使圈狀線路變成非圈線狀，其B 應(yīng)甩去。 B進(jìn)行合理運(yùn)輸，即從B運(yùn)150噸到a，再從a運(yùn)20噸到A，A運(yùn)100噸到d。另一方面，從D運(yùn)10噸到d。此外，從D運(yùn)90噸到e，C地運(yùn)70噸到e，同時運(yùn)100噸到b地,C根據(jù)圖中虛線簡示將內(nèi)外圈貨流里程匯總檢查是否超過全圈長的一半,一般來說，利用圖上作業(yè)法尋求商品最優(yōu)運(yùn)輸方案，可以按運(yùn)輸噸公里最小原則，也可以從運(yùn)送時間最短或運(yùn)費(fèi)最省等角度來分

12、別計算，只要商品在圖上沒有對流，內(nèi)外圈長都不大于半圈長，該運(yùn)輸方案就是最優(yōu)運(yùn)輸方案,練習(xí),在實(shí)際運(yùn)輸活動中，各流向上的物資是不平衡的，如進(jìn)多出少或進(jìn)少出多，就會出現(xiàn)有時車輛卸貨后空載，如何調(diào)運(yùn)才能使空車行駛里程最少,練習(xí),節(jié)約法確定路徑的基本原理,車輛運(yùn)行計劃法(VSP，Vehicles Scheduling Program)又稱里程節(jié)約法（VSP方法）。適用于實(shí)際工作中為求得較優(yōu)解或最優(yōu)的近似解時采用。它的基本原理是三角形的一邊之長必定小于另外兩邊之和。如圖所示,為實(shí)現(xiàn)所節(jié)約里程?？筛鶕?jù)用戶要求、道路條件等設(shè)計幾種巡回方案，再計算節(jié)約里程，以其中節(jié)約里程最大者為優(yōu)選的方案。VSP方法可對所有

13、需求地點(diǎn)計算其節(jié)約里程，按節(jié)約量的大小順序，優(yōu)選確定路線,如圖所示交通網(wǎng)絡(luò)圖。由起始點(diǎn)P向A、B、C、D、E等五個用戶送物品。圖中連線上的數(shù)字表示公路里程（km）。圖中靠近各用戶括號里的數(shù)字，表示對貨物的需求量（t）。起始點(diǎn)備有2t和4t載質(zhì)量的汽車，且汽車一次巡回行駛里程不能超過30km。求解滿意的送貨方案,節(jié)約里程數(shù)額排序表,節(jié)約里程表,最短距離表,從圖中可以看出，依次確定的3條路徑均符合約束條件。最后選擇的方案是：使用2輛4t車，1輛2t車，行駛里程共52km。其中： 路徑1：4t車，載貨量3.5t，行駛里程30km； 路徑2：2t車，載貨量1.5t，行駛里程16km； 路徑3：4t車，

14、載貨量3t，行駛里程6km。 在環(huán)形的線路起點(diǎn)，可以通過計算實(shí)載率的思路確定?？傊?，這一方法用計算機(jī)計算將變得非常簡單,練習(xí)：有一配送中心（Q）要向10個用戶配送，配送距離（公里）和需用量（噸）。采用最大載重量2t、4t、8t三種汽車，并限定車輛一次運(yùn)行距離 50 km,第一步，從配送網(wǎng)絡(luò)圖中列出配送中心至用戶及用戶相互間的最短距離。 第二步：從最短距離中，計算用戶相互間的節(jié)約里程。 第三步：將節(jié)約里程按大小順序排列分類。 第四步：按節(jié)約里程大小順序，組成配送路線,第一步：做出最短距離,例如：C-d之間的節(jié)約里程為： S= s1s2-s3=785=10 km,第二步：從最短矩陣中，計算用戶相互

15、間的節(jié)約里程如圖所示,第三步：將節(jié)約里程按大小順序排列分類見表,第四步：按節(jié)約里程大小順序，組成配送路線。此方案總路線7條，總行程為109公里，用6輛2噸載重汽車和1輛4噸汽車。 按上述方法，逐次取代，優(yōu)化配送路線，得出方案共有兩條路線，線路A和B，總行程70公里，用8噸的載重車1輛（實(shí)際載重6.9噸），最大行程46公里；2噸的載重車1輛（實(shí)際載重1.9噸），最大行程24公里,節(jié)約里程法應(yīng)用原則 節(jié)約里程法的原則是在約束條件下追求利潤最大化。為了使利潤最大，可以通過使路程最短，運(yùn)力最優(yōu)，運(yùn)送準(zhǔn)確性最高來實(shí)現(xiàn)。約束條件也就是應(yīng)該注意的事項，例如： 客戶的需要。即客戶對配送數(shù)量、質(zhì)量、時間的要求。

16、 應(yīng)充分考慮交通和道路情況。 充分考慮收貨站的停留時間。 應(yīng)充分考慮運(yùn)載工具的載重量和容積要求及配送中心的配送能力等,起訖點(diǎn)重合的問題 起訖點(diǎn)重合的路徑問題一般被稱為推銷員問題。直覺方法和啟發(fā)式方法是求解這類問題的有效方法。 例如，好的路線規(guī)劃中應(yīng)沒有線路交叉，呈凸形或水滴形,行車路線和時刻表的制訂 原則 劃分站點(diǎn)群以分派車輛時，將距離靠近的站點(diǎn)劃在一起； 在安排每天各車的運(yùn)輸線路時，同樣要使它們的站點(diǎn)群不重疊； 從距離倉庫最遠(yuǎn)的站點(diǎn)開始劃分站點(diǎn)群，分派車輛； 各卡車的行車路線應(yīng)呈水滴狀，避免交叉； 對于孤立于站點(diǎn)群之外的站點(diǎn)，可采用其它配送方式，如第三方服務(wù)； 各站點(diǎn)規(guī)定的取貨/送貨時間要與

17、行車路線之間協(xié)調(diào),啟發(fā)式方法 啟發(fā)式方法中很多是貪婪方法 ，例如最近鄰點(diǎn)法，最近插入法等。 最近鄰點(diǎn)法就是從某點(diǎn)開始，總是找離目前位置最近的、還未到過的節(jié)點(diǎn)作為下一點(diǎn)，直到所有節(jié)點(diǎn)走完，再回到起點(diǎn)。得到的結(jié)果常常是不理想的。 最近插入法要更進(jìn)一步，在選擇下一點(diǎn)時，不僅僅只考慮當(dāng)前的一點(diǎn)，而是考慮所有已走過的點(diǎn)。另外，它每一步是整個回路的擴(kuò)張，即從一開始它就考慮回到起點(diǎn)的成本。方法描述如下： （1） 找出離起點(diǎn)最近的節(jié)點(diǎn)，構(gòu)成子回路T。 （2） 重復(fù)（3）直到T包含所有節(jié)點(diǎn)： （3）從子回路T以外的節(jié)點(diǎn)中找出離回路T中節(jié)點(diǎn)最近的節(jié)點(diǎn)v，在T中找到一條邊(a,b)，使av+vb-ab最小，將v插在

18、a,b之間，用av+vb代替(a,b)，構(gòu)成新的回路T,例如一家面包房每天要向五家零售店送貨，各點(diǎn)之間的行車時間如下,自 到,掃描法 方法簡單，在較快時間內(nèi)得到一個合理解。 在地圖或方格圖上確定所有站點(diǎn)的位置； 劃分站點(diǎn)群：自倉庫向任意方向劃一直線，沿一個方向（順時針或逆時針）旋轉(zhuǎn)，依次根據(jù)一輛車能裝載的站點(diǎn)劃分出所有的站點(diǎn)群； 用“水滴法”或其它方法確定每個站點(diǎn)群的路線計劃。 缺點(diǎn)： 在劃分站點(diǎn)群時，沒有考慮在途總運(yùn)行時間、各站點(diǎn)的取貨/送貨時間等。 可以對結(jié)果調(diào)整（如：與P.158圖7-8是自相矛盾的,貨郎擔(dān)問題,有一個串村走戶賣貨郎，他從某個村莊出發(fā)，通過若干個村莊一次且僅一次，最后仍回

19、到原出發(fā)的村莊，問應(yīng)如何選擇行走路線，能使總的行程最短,例：求解四個城市旅行推銷員問題，其距離矩陣如表。當(dāng)推銷員從1城出發(fā)，經(jīng)過每個城市一次且僅一次，最后回到1城，問按怎樣的路線走，能使總的行程距離最短？最短距離為多少,中國郵路問題,郵遞員的工作是每天在郵局里選出郵件，然后送到他所管轄的客戶中，再返回郵局。自然地，若他要完成當(dāng)天的投遞任務(wù)，則他必須要走過他所投遞郵件的每一條街道至少一次。問怎樣的走法使他的投遞總行程為最短？這個問題就稱為中國郵路問題,1、提出問題,返回 結(jié)束,上圖表示從R1-R15個街道交叉點(diǎn)，街道上的數(shù)字表示該街道的長度，單位為米,首先把這個實(shí)際問題轉(zhuǎn)換成一個非負(fù)賦權(quán)圖G，G的頂點(diǎn)代表街與街之間的交叉路口和終端，兩個頂點(diǎn)相鄰當(dāng)且僅當(dāng)這兩點(diǎn)所對應(yīng)的路口有直通街道而中間不通過其他路口，每條邊的權(quán)是這條邊所對應(yīng)街道的長度。G的通過每條邊至少一次的閉途徑稱為G的環(huán)游。具有最小權(quán)的環(huán)游稱為G的最優(yōu)環(huán)游，則中國郵路問題就是要在賦權(quán)圖G中找一條最優(yōu)環(huán)游,2、分析問題,街道結(jié)構(gòu)圖,由上構(gòu)造右圖,3、解決問題,返回 結(jié)束,尋找Euler圖的最優(yōu)環(huán)游的基本思路： （1）用雙倍邊方法求 的一個Euler賦權(quán)母圖 ，使 達(dá)到最小。 （2）用Fleury算法求得 的Euler環(huán)游 ,就是 圖 的環(huán)游,定理4