運(yùn)輸決策與配送路線規(guī)劃

1、第四章運(yùn)輸決策與配送路線規(guī)劃本章主要內(nèi)容運(yùn)輸模式選擇運(yùn)輸線路優(yōu)化模型配送線路設(shè)計(jì)第一節(jié)運(yùn)輸模式的選擇運(yùn)輸模式的特點(diǎn)常用的運(yùn)輸方式有鐵路公路(整車發(fā)運(yùn)、零擔(dān)貨運(yùn))包裹運(yùn)輸空運(yùn)水運(yùn)運(yùn)輸模式的特點(diǎn)鐵路運(yùn)輸：高額的固定成本及低廉的運(yùn)營(yíng)成本。運(yùn)輸價(jià)格主要取決于運(yùn)量與運(yùn)輸距離。缺點(diǎn)是時(shí)間較長(zhǎng)，所以一般適合于大規(guī)模、低價(jià)值、對(duì)時(shí)間要求不敏感的產(chǎn)品。鐵路運(yùn)輸?shù)闹饕繕?biāo)是充分提高機(jī)車、車組人員的利用率。公路運(yùn)輸：包括整車發(fā)運(yùn)(TL)與零擔(dān)貨運(yùn)(LTL)兩種。整車發(fā)運(yùn)按照整車收費(fèi)，不考慮貨運(yùn)量，費(fèi)率隨運(yùn)輸距離的不同而改變。零擔(dān)貨運(yùn)則按照運(yùn)輸量與運(yùn)輸距離來收費(fèi)。運(yùn)輸模式的特點(diǎn)包裹運(yùn)輸利用空運(yùn)、鐵路或公路運(yùn)輸方式為顧

2、客提供時(shí)間敏感的小件貨物的運(yùn)輸。主要運(yùn)輸對(duì)象是小件、對(duì)時(shí)間非常敏感的貨品，其收費(fèi)標(biāo)準(zhǔn)較昂貴?？者\(yùn)基礎(chǔ)設(shè)施及裝備方面的固定成本很高，勞動(dòng)力與燃料耗費(fèi)主要取決于航線，與一次飛行運(yùn)載 的乘客量與貨物重量無關(guān)。運(yùn)輸模式的特點(diǎn)就貨物量的大小而言，鐵路、水路的批量最大、空運(yùn)的批量最?。痪瓦\(yùn)輸速度而言，空運(yùn)速度最快、水路運(yùn)輸速度最慢；就運(yùn)輸成本而言，一般來說，水路運(yùn)輸?shù)某杀咀畹汀⒖者\(yùn)最高；就服務(wù)響應(yīng)時(shí)間而言，水路最慢、空運(yùn)最快；就運(yùn)輸引起的庫存成本而言，鐵路、水路最高，空運(yùn)最低。進(jìn)行運(yùn)輸決策時(shí)，要綜合考慮上述因素，進(jìn)行成本分析，確定最佳方案。庫存與運(yùn)輸決策就不同的運(yùn)輸模式而言，其對(duì)庫存的影響有以下幾點(diǎn)：較慢

3、的運(yùn)輸模式會(huì)引起較大的中轉(zhuǎn)或運(yùn)輸庫存。較大運(yùn)量單位的運(yùn)輸方式會(huì)出現(xiàn)訂單批量超過當(dāng)前需求量的情況，出現(xiàn)不需要的庫存。較慢的運(yùn)輸模式會(huì)引起安全庫存的提高。例：某銷售公司的商品需求互相獨(dú)立，每周的平均需求為1000件，每件成本為200美元， 存儲(chǔ)成本率為25%，每件重量為3公斤。運(yùn)輸方式初步選擇采用鐵路或整車、零擔(dān)，其中零擔(dān) 有2個(gè)批量1000或2000，如表所示。請(qǐng)根據(jù)上述信息確定優(yōu)化的運(yùn)輸方式。解：根據(jù)上述信息，可首先計(jì)算運(yùn)輸費(fèi)用如表所示。從中可以看出鐵路運(yùn)輸?shù)某杀咀畹停?000 件零擔(dān)貨運(yùn)的運(yùn)輸成本最高。計(jì)算周期庫存成本以及由于運(yùn)輸時(shí)間引起的中轉(zhuǎn)庫存成本，并累加計(jì)算其總庫存成本。從中 可以看出

4、，鐵路運(yùn)輸引起的總庫存成本最高，1000件起運(yùn)的零擔(dān)方式總庫存成本最低。庫存成本的計(jì)算(單位：美元)累積運(yùn)輸成本以及總庫存成本(單位：美元)第二節(jié)線路優(yōu)化模型點(diǎn)點(diǎn)間運(yùn)輸一一最短路線問題多點(diǎn)間運(yùn)輸一一運(yùn)輸問題(直達(dá)與中轉(zhuǎn))多回路運(yùn)輸一一配送問題最短路線問題例如圖所示為一交通線路網(wǎng)絡(luò)，現(xiàn)在一批貨物要從A點(diǎn)運(yùn)至E點(diǎn)，中間要經(jīng)過3個(gè)地區(qū)B、 C、D。圖中各點(diǎn)之間的連線表示兩點(diǎn)間通行路線，連線上的數(shù)字表示兩點(diǎn)間的距離。要求選擇 一條A點(diǎn)至E點(diǎn)的最短路線。一.最短路線問題求解最短路線問題重要性質(zhì)若已經(jīng)給定從始點(diǎn)S到終點(diǎn)T的最短路線，如圖2-3中的實(shí)線所示，則從其上任一中間點(diǎn)P 到終點(diǎn)T的部分路線也必然是P

5、點(diǎn)到終點(diǎn)T的所有可選擇的路線中的最短路線。最短路線問題求解逆序遞推法根據(jù)最短路線問題的性質(zhì)，我們可以從最后一個(gè)階段開始，由終點(diǎn)向始點(diǎn)方向逐階段遞推， 尋找各點(diǎn)到終點(diǎn)的最短路線，當(dāng)遞推到始點(diǎn)時(shí)，就找到了始點(diǎn)到終點(diǎn)的最短路線。最短路線問題求解逆序遞推法求解例題中的最短路線問題首先把從A到E的全過程分成4個(gè)階段，用k表示階段變量，第1階段，有一個(gè)初始狀態(tài)A,3條可供選擇的支路AB.、AB,、AB.；第2階段，有3個(gè)初始狀態(tài)B.B,、B,它們各有3條可供123l 23選擇的支路。我們用1 (sk, Sk+1 )表示在第k階段由初始狀態(tài)sk到下階段的初始狀態(tài)sk+|的支路的距離。例如，d (C , D)

6、表示在第3階段，由C到D的距離，即d (C ,D)=2。用f (s )32121321k k表示從第k階段的到終點(diǎn)E的最短距離。例如，f (C )表示從第3階段的C到終點(diǎn)E的最短 距離。f (C)=7。最短路線問題求解階段k=4f4(D1)=3f4 (D2)=4階段k=3f3 (C1)=d3 (C1, D1 )+ f4 (D1)=4+3=7f (C)=mind (C , N)+ f (D ), d (C , D )+ f (D ) = min (5,7)=5 TOC o 1-5 h z 323214132242f (C)=mind (C , D )+ f (D ), d (C , D )+ f

7、 (D ) = min (9,9)=9333314133142階段k=2f (B)=mind (B，C )+ f (C )， d (B，C )+ f (C) = min (14,12)=12212113121232f (B)=mind (B，C )+f (C )， d (B，C )+f (C)， d (B，C )+f (C) =min22221312223222333(11,10,15)=10f (B)=mind (B，C )+ f (C )， d (B，C)+ f (C) = min (10,12)=10232323223333階段k=1f (A)=mind (A，B )+f (B )， d

8、 (A，B )+f (B)， d (A，B )+f (B) =min (15,111211222232316 , 14)=14最短路線問題求解使用逆序遞推法求解例2-5，得到A到E的全過程最短路線為ATBTqTQTE,如圖2-4 中雙線所示，最短距離是14。31二.直達(dá)運(yùn)輸線路優(yōu)化問題在物流系統(tǒng)的設(shè)計(jì)中，如何根據(jù)已有的運(yùn)輸網(wǎng)絡(luò)，制訂調(diào)運(yùn)方案，將貨物運(yùn)到各需求地，而 使總運(yùn)費(fèi)最小，是非常典型的運(yùn)輸決策優(yōu)化問題。已知有m個(gè)生產(chǎn)地點(diǎn)Ai, i=1,2,m,可供應(yīng)某種物資,其供應(yīng)量分別為ai, i=1,2,m,有n個(gè)銷地(需求地)Bj, j=1, 2,n,其需求量分別為bj, j=1, 2,n,從 A

9、i到Bj運(yùn)輸單位物資的運(yùn)價(jià)為Cij。整理成如表6-2所示產(chǎn)銷平衡表和單位運(yùn)價(jià)表。運(yùn)價(jià)系數(shù)表直達(dá)運(yùn)輸優(yōu)化模型直達(dá)運(yùn)輸線路優(yōu)化是一個(gè)產(chǎn)銷平衡的運(yùn)輸模型，即m個(gè)供應(yīng)點(diǎn)的總供應(yīng)量等于n個(gè)需求點(diǎn)的 總需求量，運(yùn)輸問題滿足供需平衡。這時(shí)，由各供應(yīng)點(diǎn)Ai調(diào)出的物質(zhì)總量應(yīng)等于它的供應(yīng)量 ai (i=1,2,m),而每一個(gè)需求點(diǎn)Bj調(diào)入的物資總量應(yīng)等于它的需求量bj, j=1, 2,n。我們?nèi)粲脁ij表示從Ai到Bj的運(yùn)量，其數(shù)學(xué)模型如下：直達(dá)運(yùn)輸數(shù)學(xué)模型直達(dá)運(yùn)輸問題模型求解方法手工求解方法：表上作業(yè)法利用表上作業(yè)法，尋求運(yùn)費(fèi)最少的運(yùn)輸方案，有三個(gè)基本步驟：依據(jù)問題列出運(yùn)輸物資的供需平衡表及運(yùn)價(jià)表。確定一個(gè)初始

10、的調(diào)運(yùn)方案。根據(jù)一個(gè)判定法則，判定初始方案是否為最優(yōu)方案。當(dāng)判定初始方案不是最優(yōu)方案時(shí)，再對(duì)這個(gè)方案進(jìn)行調(diào)整。一般說來，每調(diào)整一次得到一個(gè) 新的方案，而這個(gè)新方案的運(yùn)費(fèi)比前一個(gè)方案要少一些，如此經(jīng)過幾次調(diào)整，就會(huì)得到最優(yōu)方 案。例1已知三個(gè)產(chǎn)地A1, A2, A3，四個(gè)銷地Bl,B2,B3,B4的產(chǎn)銷量及單位運(yùn)價(jià)如表6.1所 示，求使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。運(yùn)價(jià)系數(shù)表最優(yōu)調(diào)運(yùn)方案最低的總運(yùn)費(fèi)Z=4350。產(chǎn)地A：實(shí)際上只調(diào)運(yùn)出200,多余的300只能貯存在原地或者不生產(chǎn)。中轉(zhuǎn)運(yùn)輸優(yōu)化模型問題的提出產(chǎn)地與銷地之間沒有直達(dá)路線，貨物由產(chǎn)地到銷地必須通過某中間站轉(zhuǎn)運(yùn)；某些產(chǎn)地既輸出貨物，也吸收一部分貨

11、物；某銷地既吸收貨物，又輸出部分貨物，即產(chǎn)地 或銷地也可以起中轉(zhuǎn)站的作用，或者既是產(chǎn)地又是銷地；產(chǎn)地與銷地之間雖然有直達(dá)路線，但直達(dá)運(yùn)輸?shù)馁M(fèi)用或運(yùn)輸距離分別比經(jīng)過某些中轉(zhuǎn)站還 要高或遠(yuǎn)。存在以上情況的運(yùn)輸問題，統(tǒng)稱為轉(zhuǎn)運(yùn)問題。中轉(zhuǎn)運(yùn)輸優(yōu)化模型約束分析與數(shù)學(xué)模型解決中轉(zhuǎn)運(yùn)輸問題的思路是先把它化為無轉(zhuǎn)運(yùn)的平衡運(yùn)輸問題。為此，作如下假設(shè)：首先根據(jù)具體問題求出最大可能中轉(zhuǎn)量Q (Q是大于總產(chǎn)量的一個(gè)數(shù))；純中轉(zhuǎn)站可視為輸出量和輸入量均為Q的一個(gè)產(chǎn)地和銷地。兼中轉(zhuǎn)站的產(chǎn)地Ai可視為一個(gè)輸入量為Q的銷地及一個(gè)產(chǎn)量為Q+ai的產(chǎn)地。兼中轉(zhuǎn)站的銷地可視為一個(gè)輸出量為Q的產(chǎn)地及一個(gè)銷量為Q+bi的銷地。在此假設(shè)

12、的基礎(chǔ)上，列出各產(chǎn)地的輸出量，各銷地的輸入量及各產(chǎn)銷地之間的運(yùn)價(jià)表，最后 用表上作業(yè)法求解。中轉(zhuǎn)運(yùn)輸優(yōu)化模型例2轉(zhuǎn)運(yùn)問題，已知A1、A2和A3三個(gè)工廠生產(chǎn)同一規(guī)格的產(chǎn)品，用相同價(jià)格供應(yīng)B1, B2 和B3三個(gè)銷售網(wǎng)點(diǎn)銷售。有兩個(gè)轉(zhuǎn)運(yùn)站T1、T2,并且產(chǎn)品的運(yùn)輸允許在各產(chǎn)地、各銷地及各 轉(zhuǎn)運(yùn)站之間相互轉(zhuǎn)運(yùn)。已知各產(chǎn)地、銷地、中轉(zhuǎn)站相互之間每噸貨物的單位運(yùn)價(jià)和產(chǎn)銷量(見 表)，求合理的調(diào)運(yùn)方案。中轉(zhuǎn)運(yùn)輸優(yōu)化模型中轉(zhuǎn)運(yùn)輸優(yōu)化模型解：將其化成一個(gè)等價(jià)的擴(kuò)大運(yùn)輸問題，應(yīng)做如下處理：將所有的產(chǎn)地、轉(zhuǎn)運(yùn)站和銷地都作為產(chǎn)地，也作為銷地。因此，整個(gè)問題成為林個(gè)產(chǎn)地和 8個(gè)銷地的擴(kuò)大的運(yùn)輸問題對(duì)擴(kuò)大的運(yùn)輸問題建立

13、運(yùn)價(jià)表。對(duì)于沒有運(yùn)輸路線的取任意大的正數(shù)M；對(duì)于自己給自己運(yùn) 輸?shù)模\(yùn)價(jià)記Cij=0。中轉(zhuǎn)運(yùn)輸優(yōu)化模型所有轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷量，即流入量等于流出量。但事先又無法知道該數(shù)量的確切值，因 此可以將調(diào)運(yùn)總量(即總產(chǎn)量或總銷量)作為該數(shù)值的上界。本題中調(diào)運(yùn)總量為60t，取T1,T2 的產(chǎn)量和銷量均為60t。在擴(kuò)大的運(yùn)輸問題中，原來的產(chǎn)地與銷地由于也具有轉(zhuǎn)運(yùn)作用，所以在原來的產(chǎn)量與銷量的 數(shù)值再加上調(diào)運(yùn)總量；同時(shí)原各產(chǎn)地的銷量、原各銷地的產(chǎn)量均取為調(diào)運(yùn)產(chǎn)量。已知調(diào)運(yùn)總量 為60t,三個(gè)工廠的產(chǎn)量改為90t,70t, 80t，銷量均為60t；三個(gè)銷售點(diǎn)的銷量改為75t, 95 t, 70 t,產(chǎn)量均為60

14、 t。多回路問題一一節(jié)約里程法 基本原理三角形兩邊之和大于第三邊 L=L1+L2-L3節(jié)約里程法例題：由配送中心？向A-I等9個(gè)用戶配送貨物，圖中連線上的數(shù)字表示里程(km),括號(hào) 內(nèi)數(shù)字表示用戶需求量(t)。配送中心有2 t和4 t載貨汽車，且汽車一次巡回走行里程不能 超過35km，設(shè)送到時(shí)間均符合用戶要求，求配送中心的最優(yōu)送貨方案。節(jié)約里程法1、計(jì)算配送中心到各用戶之間以及用戶相互之間的最短距離，并列表節(jié)約里程法2、利用節(jié)約法計(jì)算出各用戶之間的節(jié)約里程節(jié)約里程法3、根據(jù)節(jié)約里程表中節(jié)約里程多少的順序，由大到小排列，編制節(jié)約順序表。節(jié)約里程法4、根據(jù)節(jié)約里程的排序表和配送車的載重量(本題忽略

15、容積因素)決定配送路徑節(jié)約里程法結(jié)果路徑A： 4t車,走行32km ,載重量t路徑B： 4 t車，走行31km，載重量t路徑C: 4 t車，走行30km，載重量t總共行走里程93km,節(jié)約里程63公里第三節(jié)配送線路設(shè)計(jì)合理配送路線制定原則行車路線和時(shí)間表制定方法合理路線的制定原則安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸?？ㄜ嚨男熊嚶肪€圍繞相互靠近的站點(diǎn)群進(jìn)行計(jì)劃，以使站點(diǎn)之間的行車時(shí)間最短。合理路線的制定原則安排車輛各日途經(jīng)的站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊從距倉庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線卡車的行車路線應(yīng)呈水滴狀盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式行車路線和時(shí)期表的制定方法掃描法(The Sweep Method)節(jié)約法(The Savings Method)掃描法(The Sweep Method)在地圖或方格圖中確定所有站點(diǎn)(含倉庫)的位置。自倉庫始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交。 考慮，如果在某線路上增加該站點(diǎn)，是否會(huì)超過車輛的載貨能力如果沒有，繼續(xù)旋轉(zhuǎn)直線，直 到與下一個(gè)站點(diǎn)相交。再次計(jì)算累計(jì)貨運(yùn)量是否超過車輛的運(yùn)載能力(先使用最大的車輛)。如 果超過，就剔除最后的那個(gè)站點(diǎn)，并確定路線