2.8運(yùn)輸路線優(yōu)化

運(yùn)輸管理實(shí)務(wù)運(yùn)輸管理實(shí)務(wù)課程團(tuán)隊(duì)主講：杜麗茶物流管理省級(jí)示范性特色專業(yè)共享課程項(xiàng)目二：公路運(yùn)輸管理課程內(nèi)容1.運(yùn)輸基礎(chǔ)知識(shí)2.公路運(yùn)輸管理3.水路運(yùn)輸管理4.鐵路運(yùn)輸管理5.航空運(yùn)輸管理6.多式聯(lián)運(yùn)業(yè)務(wù)管理7.綜合技能抽查4運(yùn)輸路線優(yōu)化的目標(biāo)效益最高路程最短成本最低噸公里數(shù)最小準(zhǔn)確性最高運(yùn)輸路線優(yōu)化的目標(biāo)一、物流運(yùn)輸線路的類型單一裝貨地和單一卸貨地的物流運(yùn)輸線路起點(diǎn)與終點(diǎn)為同一地點(diǎn)的物流運(yùn)輸線路多起點(diǎn)、多終點(diǎn)問題的物流運(yùn)輸線路類型一對(duì)一一對(duì)多多對(duì)多

經(jīng)驗(yàn)判斷法綜合評(píng)分法數(shù)學(xué)計(jì)算方法方法

如何制定合理的行車路線？某配送企業(yè)配送路線方案指標(biāo)序號(hào)評(píng)價(jià)指標(biāo)極差差較好良好最優(yōu)0分1分2分3分4分1全過程距離√2行車時(shí)間√3配送準(zhǔn)時(shí)性√4行車難易√5動(dòng)用車輛數(shù)√6油耗√7車輛狀況√8運(yùn)送量√9配送客戶數(shù)√10配送總費(fèi)用√綜合評(píng)分法一對(duì)一一對(duì)多多對(duì)多最短路徑法掃描法節(jié)約里程法圖上作業(yè)法表上作業(yè)法數(shù)學(xué)計(jì)算法

下圖是路路通運(yùn)輸公司簽訂了的一項(xiàng)運(yùn)輸合同，要把A城的一批化肥運(yùn)送到J城，路路通公司根據(jù)這兩個(gè)城市之間可選擇的行車線路繪制的公路網(wǎng)絡(luò)。其中A點(diǎn)表示裝貨地，J點(diǎn)是卸貨地。此類運(yùn)輸線路的特點(diǎn)是A點(diǎn)和J點(diǎn)是兩個(gè)點(diǎn)，不重合。這是運(yùn)輸活動(dòng)中的一種情況。一對(duì)一問題最短路徑法

B

CA

DG

E

H

J

I80KM128KM7474116116140501123812211038146338KM8056

F

公路網(wǎng)絡(luò)示意圖

可以看出，從A市出發(fā)到達(dá)J市，可以有很多條路線可以選擇。但是如何選擇運(yùn)輸路線，才能使總路程的長(zhǎng)度最短？這就是運(yùn)輸規(guī)劃中的最短路徑法。最短路徑法1

B

CA

DG

E

H

J

I80KM128KM7474116116140501123812211038146338KM8056

F

公路網(wǎng)絡(luò)示意圖最優(yōu)線路為A-B-E-I-J，最短的路程的344公里。一對(duì)多掃描法節(jié)約里程法掃描法（臨時(shí)客戶、臨時(shí)線路的送貨計(jì)劃）節(jié)約法（固定客戶，固定線路）路線設(shè)計(jì)中的掃描法很簡(jiǎn)單，即使問題規(guī)模很大，也可以通過手工計(jì)算得出結(jié)果。掃描法可闡述如下：（1）在地圖或方格圖中確定所有站點(diǎn)（含倉(cāng)庫(kù)）的位置。（2）自倉(cāng)庫(kù)始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交?？紤]：如果在某線路上增加該站點(diǎn)，是否會(huì)超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個(gè)站點(diǎn)相交。再次計(jì)算累計(jì)貨運(yùn)量是否超過車輛的運(yùn)載能力（先使用最大的車輛）。如果超過，就剔除最后的那個(gè)站點(diǎn)，確定路線。隨后，從不包含在上一條路線中的站點(diǎn)開始，掃描法繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點(diǎn)都被安排到路線中。（3）排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用“水滴”法。例：某公司用廂式貨車從貨主處取貨，圖(a)是一天的取貨量，單位是件。廂式貨車的載貨量是10000件。完成所有取貨任務(wù)需一天時(shí)間。公司需要多少條運(yùn)輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過哪些站點(diǎn)，每條路線上的站點(diǎn)怎樣排序。掃描法首先，向北畫一條直線，進(jìn)行逆時(shí)針方向“掃描”。這些都是隨機(jī)決定的。逆時(shí)針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件的卡車，同時(shí)又不超載。一旦所有的站點(diǎn)都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點(diǎn)的順序，圖(b)是所列出的最終的路線設(shè)計(jì)。(a)(b)

掃描法設(shè)計(jì)行車路線缺點(diǎn)：在劃分站點(diǎn)群時(shí)，沒有考慮在途總運(yùn)行時(shí)間、各站點(diǎn)的取貨/送貨時(shí)間等。（1）將相互接近的各站點(diǎn)的貨物盡可能安排同一輛車運(yùn)輸。卡車的行車路線圍繞相互靠近的站點(diǎn)群進(jìn)行計(jì)劃，以使站點(diǎn)之間的行車時(shí)間最短，使站點(diǎn)群更加緊湊。

DD掃描法（2）卡車的行車路線不應(yīng)交叉，應(yīng)呈水滴狀。安排行車路線時(shí)各條路線之間應(yīng)該沒有交叉，且呈水滴狀。時(shí)間窗口和送貨之后才能取貨的限制條件可能會(huì)造成線路交叉。掃描法（3）盡可能使用較大載重量的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的；理想狀況下，用一輛足夠大的卡車運(yùn)送所有站點(diǎn)的貨物將使總的行車距離或時(shí)間最小。因此，在車輛可以實(shí)現(xiàn)較高的利用率之時(shí)，應(yīng)該首先安排車隊(duì)中載重量最大的車輛。掃描法（4）對(duì)過于遙遠(yuǎn)而無(wú)法歸入群落的站點(diǎn)，可以采用其他配送方式；那些孤立于其他站點(diǎn)群的站點(diǎn)（特別是貨運(yùn)量較小的站點(diǎn)），為其提供服務(wù)所需的運(yùn)送時(shí)間較長(zhǎng)，運(yùn)送費(fèi)用較高?？紤]到這些站點(diǎn)的偏僻程度和貨運(yùn)量，采用小型卡車進(jìn)行服務(wù)可能更經(jīng)濟(jì)。此外，利用外租的運(yùn)輸服務(wù)也不啻為一個(gè)很好的選擇。掃描法節(jié)約里程法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點(diǎn)提供服務(wù)的卡車數(shù)量最少。節(jié)約里程法

原理：三角形一邊之長(zhǎng)必定小于另外兩邊之和。在汽車載重量允許的情況下，采用巡回發(fā)貨比采用往返發(fā)貨可節(jié)約汽車走行里程為：?L=[2(L1+L2)]-(L1+L2+L3)=L1+L2-L3節(jié)約里程法【例】有某商品發(fā)送點(diǎn)A、B、C、D四處，與四個(gè)接收點(diǎn)a、b、c、d成圈狀，其距離及供需量如表所示，試求最優(yōu)運(yùn)輸路線。距離abcd產(chǎn)量A65KM80KM80B180220150C9075170D6070100銷量130100160110500接收地發(fā)送地多對(duì)多圖上作業(yè)法表上作業(yè)法150100CAD17016010011080130Babcd80KM65KM如上例所述，有多個(gè)貨源地可以服務(wù)于多個(gè)目的地時(shí)，那么我們面臨的問題是，要指定為各目的地服務(wù)的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。該問題常發(fā)生在多個(gè)供應(yīng)商、工廠或倉(cāng)庫(kù)服務(wù)于多個(gè)客戶的情況下，即多起訖點(diǎn)問題。多對(duì)多圖上作業(yè)法表上作業(yè)法圖上作業(yè)法圖上作業(yè)法根據(jù)交通圖的點(diǎn)和線的關(guān)系，把各種路線歸納為道路不成圈（無(wú)圈）和道路成圈兩類。道路不成圈，就是沒有回路的“樹”形路線，包括直線、丁字線、交叉線、分支線等；無(wú)圈的流向圖只要消滅對(duì)流，就是最優(yōu)流向圖。道路成圈，就是形成閉合回路的“環(huán)”狀路線，包括一個(gè)圈和多個(gè)圈；成圈的流向圖要達(dá)到既沒有對(duì)流，又沒有迂回的要求才是最優(yōu)流向圖。圖上作業(yè)法40707080506030BDCabcA403030206020ABCD為產(chǎn)地，圓圈內(nèi)為產(chǎn)量，abc為需求地，方框內(nèi)為需求量道路成圈對(duì)于成圈的交通網(wǎng)絡(luò)，只要先假設(shè)某兩點(diǎn)間線路“不通”，將成圈問題化為不成圈問題考慮，這樣就可得到一個(gè)初始的調(diào)運(yùn)方案。然后進(jìn)一步作優(yōu)化處理，其原則是：里圈、外圈分別算，要求不過半圈長(zhǎng)；如若超過半圈長(zhǎng)，應(yīng)甩運(yùn)量最小段；反復(fù)求算最優(yōu)方案?！纠坑心成唐钒l(fā)送點(diǎn)A、B、C、D四處，與四個(gè)接收點(diǎn)a、b、c、d成圈狀，其距離及供需量如表所示，試求最優(yōu)運(yùn)輸路線。距離abcd產(chǎn)量A658080B180220150C9075170D6070100銷量130100160110500接收地發(fā)送地150100CAD17016010011080130Babcd15020100109070100根據(jù)圖中箭頭將內(nèi)外圈貨流里程匯總，檢查是否超過全圈長(zhǎng)的一半。L/2＝（220+180+65+80+70+60+75+90）/2＝420L內(nèi)＝180+65+80+60+90＝445>L/2L外＝75+70＝145<L/2L內(nèi)大于全圈長(zhǎng)的一半，不是最優(yōu)方案，應(yīng)重新甩段破圈，甩內(nèi)圈運(yùn)量最小區(qū)段aA，尋找最優(yōu)方案。150100CAD17016010011080130Babcd130807090803020計(jì)算內(nèi)外圈長(zhǎng)：L/2＝（220+180+65+80+70+60+75+90）/2＝420L內(nèi)＝180+80+60+90＝410<L/2L外＝70+75+220＝365<L/2將上述運(yùn)輸結(jié)果填入平衡表：表上作業(yè)法當(dāng)某些線性規(guī)劃問題采用圖上作業(yè)法難以進(jìn)行直觀求解時(shí)，就可以將各元素列成相關(guān)表，采用表上作業(yè)法解決。表上作業(yè)法表上作業(yè)法包括以下步驟：確定初始可行方案。方法比較多，一般希望方法既簡(jiǎn)單，又盡可能接近最優(yōu)解，常用最小元素法和伏格爾法。最優(yōu)方案的判別。判別的方法是計(jì)算空格的檢驗(yàn)數(shù)，常用閉回路法和位勢(shì)法。改進(jìn)方案。常使用閉回路調(diào)整法進(jìn)行調(diào)整以得到最優(yōu)的方案?！纠坑心彻窘?jīng)銷一產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為A1＝7噸、A2＝4噸，A3＝9噸，該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)。各個(gè)銷售點(diǎn)每日銷量為B1＝3噸，B2＝6噸，B3＝5噸，B4＝6噸，已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如表