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

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

經(jīng)驗判斷法綜合評分法數(shù)學(xué)計算方法方法

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

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

B

CA

DG

E

H

J

I80KM128KM7474116116140501123812211038146338KM8056

F

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

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

B

CA

DG

E

H

J

I80KM128KM7474116116140501123812211038146338KM8056

F

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

掃描法設(shè)計行車路線缺點：在劃分站點群時，沒有考慮在途總運行時間、各站點的取貨/送貨時間等。（1）將相互接近的各站點的貨物盡可能安排同一輛車運輸?？ㄜ嚨男熊嚶肪€圍繞相互靠近的站點群進行計劃，以使站點之間的行車時間最短，使站點群更加緊湊。

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

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