車輛調(diào)度方法

1、車輛調(diào)度方法車輛調(diào)度方法圖上作業(yè)法圖上作業(yè)法物資調(diào)撥物資調(diào)撥 圖上作業(yè)法 圖上作業(yè)法的原則可以歸納為： 流向劃右方，對流不應(yīng)當(dāng)； 里圈、外圈分別算，要求不能過半圈長； 如若超過半圈長，應(yīng)去運量最小段； 反復(fù)運算可得最優(yōu)方案。 1運輸線路不成圈的圖上作業(yè)法 對于運輸線路不成圈的流向圖，只要不出現(xiàn)對流現(xiàn)象，就是最優(yōu)調(diào)運方案。 運輸線路不成圈的圖上作業(yè)法較簡單。就是從各端點開始，按“各站供需就近調(diào)撥”的原則進行調(diào)配。ABCDEFG+10-2-5+3-11+9-4 1運輸線路不成圈的圖上作業(yè)法ABCDEFG+10-2-5+3-11+9-41083654 1運輸線路不成圈的圖上作業(yè)法 2運輸線路成圈的圖

2、上作業(yè)法 運輸線路成圈，就是形成閉合回路的“環(huán)”形路線，包括一個圈（有三角形、四邊形、多邊形）和多個圈。成圈的線路流向圖要同時達到既無對流現(xiàn)象、又無迂回現(xiàn)象的要求才是最優(yōu)流向圖。 對于成圈運輸線路的圖上作業(yè)法，可按下述三個步驟尋求最優(yōu)方案，如表所示。表 成圈運輸線路的圖上作業(yè)法的步驟 步驟詳 述去段破圈確定初始運輸方案 就是在成圈的線路中，先假設(shè)某兩點間的線路“不通”，去掉這段線路，把成圈線路轉(zhuǎn)化為不成圈的線路，即破圈；按照運輸線路不成圈的圖上作業(yè)法，即可得到初始運輸方案。檢查有無迂回現(xiàn)象 因為流向箭頭都統(tǒng)一畫在線路右邊，所以圈內(nèi)圈外都畫有一些流向。分別檢查每個小圈，如果圈內(nèi)和圈外流向的總長度

3、都不超過全圈總長度的1/2 ，那么，全圈就沒有迂回現(xiàn)象了，這個線路流向圖就是最優(yōu)的，對應(yīng)的就是最優(yōu)運輸方案。否則轉(zhuǎn)向第三步。重新去段破圈，調(diào)整流向 在超過全圈總長1/2 的里（外）圈各段流向線上減去最小運量，然后在相反方向的外（里）圈流向線上和原來沒有流向線的各段上，加上減去的最小運量，這樣可以得到一個新的線路流向圖，然后轉(zhuǎn)到第二步檢查有無迂回現(xiàn)象。如此反復(fù)，直到得到最優(yōu)線路流向圖為止。 如果全圈存在兩個及兩個以上的圈，則需分別對各圈進行是否存在迂回線路的檢查，如果各圈的里、外圈都不超過全圈總線長的1/2 ，則不存在迂回現(xiàn)象，此方案為最優(yōu)運輸方案。第一步第一步 作出初始方案作出初始方案ABCD

4、EFGHI+20-30-50+20-20+100-70+60-30(36)(23)(13)(29)(25)(23)(45)(18) 2運輸線路成圈的圖上作業(yè)法ABCDEFGHI+20-30-50+20-20+100-70+60-3030208050102060外圈長=45+25+18+23=111公里里圈長=23公里全圈長=45+23+25+18+23+36=170公里半圈長=170/2=85公里ABCDEFGHI+20-30-50+20-20+100-70+60-3020102080303040外圈長=25+18+23=66公里里圈長=23+36=59公里全圈長=45+23+25+18+23

5、+36=170公里半圈長=170/2=85公里調(diào)整流向調(diào)整流向 3運輸線路成兩圈的圖上作業(yè)法甲圈甲圈乙圈乙圈5818324甲圈： 乙圈：半圈長=7+2+3+6+4+3/2=12.5公里 半圈長=4+4+5+8/2=10.5公里外圈長=4公里 外圈長=0公里里圈長=2+3+6+3=14公里 里圈長=4+4+5=13公里初始方案甲圈甲圈乙圈乙圈4716223甲圈： 乙圈：半圈長=7+2+3+6+4+3/2=12.5公里 半圈長=4+4+5+8/2=10.5公里外圈長=4+7=11公里 外圈長=8公里里圈長=2+3+3=8公里 里圈長=4+5=9公里調(diào)整方案練習(xí)練習(xí)最短路徑問題最短路徑問題例例1 1

6、 多階段決策法多階段決策法 下圖表示從起點下圖表示從起點A A到終點到終點E E之間各點的距離。求之間各點的距離。求A A到到E E的最短路徑。的最短路徑。BACBDBCDEC412312312322164724838675611064375118討論：討論： 1 1、以上求從、以上求從A A到到E E的最短路徑問題，可以轉(zhuǎn)化為的最短路徑問題，可以轉(zhuǎn)化為四個性質(zhì)完全相同，但四個性質(zhì)完全相同，但規(guī)模較小的子問題規(guī)模較小的子問題，即分別從，即分別從D Di i 、C Ci i、B Bi i、A A到到E E的最短路徑問題。的最短路徑問題。 最優(yōu)化原理的應(yīng)用：從最短路上的每一點到終點的部分道路，也一

7、定是最優(yōu)化原理的應(yīng)用：從最短路上的每一點到終點的部分道路，也一定是從該點到終點的最短路。從該點到終點的最短路。 第四階段：兩個始點第四階段：兩個始點D D1 1和和D D2 2，終點只有一個；，終點只有一個； 表表1 1分析得知：從分析得知：從D D1 1和和D D2 2到到E E的最短路徑唯一。的最短路徑唯一。 階段階段4本階段始點本階段始點（狀態(tài)）（狀態(tài)）本階段各終點（決策）本階段各終點（決策）到到E的最短距離的最短距離本階段最優(yōu)終點本階段最優(yōu)終點（最優(yōu)決策（最優(yōu)決策) E D1 D2 10 6 10 6 E E1919 第三階段：有三個始點第三階段：有三個始點C1，C2，C3，終點有，終

8、點有D1，D2，對始點和終點進行分析和討，對始點和終點進行分析和討論論分別分別求求C1，C2，C3到到D1，D2 的最短路徑問題：的最短路徑問題： 表表2分析得知：如果經(jīng)過分析得知：如果經(jīng)過C1，則最短路為，則最短路為C1-D2-E； 如果經(jīng)過如果經(jīng)過C2，則最短路為，則最短路為C2-D2-E； 如果經(jīng)過如果經(jīng)過C3，則最短路為，則最短路為C3-D1-E。 階段階段3本階段始點本階段始點（狀態(tài)）（狀態(tài)）本階段各終點（決策）本階段各終點（決策）到到E的最短距離的最短距離本階段最優(yōu)終點本階段最優(yōu)終點（最優(yōu)決策（最優(yōu)決策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11

9、 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D12020第二階段：有第二階段：有4個始點個始點B1,B2,B3,B4，終點有，終點有C1,C2,C3。對始點和終點進行。對始點和終點進行分析和討論分別求分析和討論分別求B1,B2,B3,B4到到C1,C2,C3 的最短路徑問題：的最短路徑問題： 表表3 分析得知：如果經(jīng)過分析得知：如果經(jīng)過B1，則走，則走B1-C2-D2-E； 如果經(jīng)過如果經(jīng)過B2，則走，則走B2-C3-D1-E； 如果經(jīng)過如果經(jīng)過B3，則走，則走B3-C3-D1-E； 如果經(jīng)過如果經(jīng)過B4，則走，則走B4-C3-D1-E。 階段階段2本階段始點本階

10、段始點（狀態(tài)）（狀態(tài)） 本階段各終點（決策）本階段各終點（決策）到到E的最的最短距離短距離本階段最優(yōu)終本階段最優(yōu)終點（最優(yōu)決策點（最優(yōu)決策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C32121第一階段：只有第一階段：只有1個始點個始點A，終點有，終點有B1,B2,B3,B4 。對始點和終點進行分析和討論。對始點和終點進行分析和討論分別求分別求A到到B1,B2,

11、B3,B4的最短路徑問題：的最短路徑問題： 表表4最后，可以得到：從最后，可以得到：從A到到E的最短路徑為的最短路徑為A B4 C3 D1 E 階段階段1本階段始本階段始點點(狀態(tài)狀態(tài)) 本階段各終點（決策）本階段各終點（決策）到到E的最的最短距離短距離本階段最優(yōu)終本階段最優(yōu)終點點(最優(yōu)決策最優(yōu)決策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 C22222 以上計算過程及結(jié)果，可用圖以上計算過程及結(jié)果，可用圖2表示，可以看到，以上方法不僅表示，可以看到，以上方法不僅得到了從得到了從A到到D的最短路徑，同時，也得到了從圖中任一點到的最短路徑，同

12、時，也得到了從圖中任一點到E的最的最短路徑。短路徑。 BACBDBCDEC412312312332164724838675161060106121111121314144B127512練習(xí)計算V1到V7的最短距離例例2 2 位勢法位勢法計算CK的最短路1）取VC=0；2）確定與C點相連的結(jié)點位勢；3）取所有位勢中最小者，標(biāo)注在結(jié)點旁，并用箭頭連出；ABCDEFHIJKG111066511714411897101094120114）以D為初始結(jié)點，計算與之相連的點的位勢值；5）從剩余位勢中剩余位勢中選出最小者，標(biāo)注箭頭和位勢值；66）以E為初始結(jié)點，計算與之相連的點的位勢值；7）從剩余位勢中剩余

13、位勢中選出最小者，標(biāo)注箭頭和位勢值；1211ABCDEFHIJKG1110665117144118971010948）以B為初始結(jié)點，計算與之相連的點的位勢值；9）從剩余位勢中剩余位勢中選出最小者，標(biāo)注箭頭和位勢值；10）以F為初始結(jié)點，計算與之相連的點的位勢值；11）從剩余位勢中剩余位勢中選出最小者，標(biāo)注箭頭和位勢值；011612111517ABCDEFHIJKG11106651171441189710109412）以A為初始結(jié)點，計算與之相連的點的位勢值；13）從剩余位勢中剩余位勢中選出最小者，標(biāo)注箭頭和位勢值；10）以G為初始結(jié)點，計算與之相連的點的位勢值；11）從剩余位勢中剩余位勢中選

14、出最小者，標(biāo)注箭頭和位勢值；011612111517ABCDEFHIJKG11106651171441189710109424重復(fù)計算，可得最優(yōu)的路線圖，如圖所示。011612111517ABCDEFHIJKG1110665117144118971010942418313438車輛路線安排3030 車輛路線安排問題（車輛路線安排問題（VRP, Vehicle Routing Problem）是指對物流配送的車輛進行優(yōu)化調(diào)度。該問題一般可以描述如下：對一系列裝貨點或（和）卸貨點，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量、數(shù)目

15、限制、車輛行駛里程、時間限制等）下，達到一定的目標(biāo)（如最短路程、最小費用、最短時間、最少車輛等）。該問題涉及了多輛交通工具的服務(wù)對象的選擇和路徑（服務(wù)順序）確定兩方面的問題。 VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個或多個已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對比較成熟的基本理論和方法進行求解。3131運用VRP模型對實際問題進行研究時，一般需要考慮以下幾個方面的問題：u（1）倉庫。倉庫的級數(shù)，每級倉庫的數(shù)量、地點和規(guī)模。u（2）車輛。車輛的型號和數(shù)量，每種車輛的容積和運作費用，出發(fā)時間和返

16、回時間，司機休息時間，最大的里程和時間限制。u（3）時間窗口。由于各處的工作時間不同，每個站點每天只允許在特定的時間內(nèi)取貨和/或送貨。u（4）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級。u（5）道路信息。車流密度，道路交通費用，距離或時間屬性。u（6）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。u（7）運輸規(guī)章。工人每天的工作時間，車輛的周期維護。3232u（1）安排車輛負責(zé)相互距離最接近的站點的貨物運輸。u（2）安排車輛各日途經(jīng)站點時，應(yīng)注意使站點群更加緊湊。如果一周內(nèi)各日服務(wù)的站點不同，就應(yīng)該對一周內(nèi)每天的路線和時刻表問題分別進行站點群劃分。各日站點群的劃分應(yīng)避免重疊

17、。u（3）從距倉庫最遠的站點開始設(shè)計路線u（4）卡車的行車路線應(yīng)呈水滴狀。u（5）盡可能使用最大的車輛進行運送，這樣設(shè)計出的路線是最有效的。u（6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。u（7）對過于遙遠而無法歸入群落的站點，可以采用其它配送方式。u（8）避免時間窗口過短。簡化的原則：簡化的原則：33331掃描法掃描法路線設(shè)計中的掃描法很簡單，即使問題規(guī)模很大，也可以通過手工計算得出結(jié)果。掃描法可闡述如下：（1 1）在地圖或方格圖中確定所有站點（含倉庫）的位置。）在地圖或方格圖中確定所有站點（含倉庫）的位置。（2 2）自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向

18、旋轉(zhuǎn)）自倉庫始沿任一方向向外劃一條直線。沿順時針或逆時針方向旋轉(zhuǎn)該直線直到與某站點相交?？紤]：如果在某線路上增加該站點，是否會該直線直到與某站點相交?？紤]：如果在某線路上增加該站點，是否會超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相超過車輛的載貨能力？如果沒有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個站點相交。再次計算累計貨運量是否超過車輛的運載能力（先使用最大的車交。再次計算累計貨運量是否超過車輛的運載能力（先使用最大的車輛）。如果超過，就剔除最后的那個站點，并確定路線。隨后，從不包輛）。如果超過，就剔除最后的那個站點，并確定路線。隨后，從不包含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以尋

19、找新路線。繼續(xù)該過含在上一條路線中的站點開始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過程直到所有的站點都被安排到路線中。程直到所有的站點都被安排到路線中。（3 3）排定各路線上每個站點的順序使行車距離最短。排序時可以使用）排定各路線上每個站點的順序使行車距離最短。排序時可以使用“水滴水滴”法或求解法或求解“流動推銷員流動推銷員”問題的任何算法。問題的任何算法。3434例例 某公司用廂式貨車從貨主處取貨，圖某公司用廂式貨車從貨主處取貨，圖 (a) (a)是一天的取貨量，單位是一天的取貨量，單位是件。廂式貨車的載貨量是是件。廂式貨車的載貨量是1000010000件。完成所有取貨任務(wù)需一天時間。件。完成所

20、有取貨任務(wù)需一天時間。公司需要多少條運輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過哪些站公司需要多少條運輸路線（即多少部車），每條路線上應(yīng)該經(jīng)過哪些站點，每條路線上的站點怎樣排序。點，每條路線上的站點怎樣排序。 首先，向北畫一條直線，進行逆時針方向“掃描”。這些都是隨機決定的。逆時針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重10000件的卡車，同時又不超載。一旦所有的站點都分派有車輛，就可以利用“水滴”法安排經(jīng)過各站點的順序，圖 (b)是所列出的最終的路線設(shè)計。圖圖 掃描法設(shè)計行車路線掃描法設(shè)計行車路線汽車站汽車站1000400020003000200020002000100020002000300

21、03000a 停留點提貨量數(shù)據(jù)停留點提貨量數(shù)據(jù)汽車站汽車站100040002000300020002000200010002000200030003000b 掃描法解決方案掃描法解決方案2 2 節(jié)約里程法節(jié)約里程法分送式配送運輸分送式配送運輸分送式配送運輸是一個供應(yīng)點對多個用戶的共同送貨基本條件：所有客戶的需求量總和不大于一輛車的額定載重量配送路線確定的原則：成本低、效益高、路線短、準(zhǔn)確性高、勞動消耗少、運力合理等配送路線確定的限制條件：用戶對貨物品種、規(guī)格、數(shù)量的要求；用戶對發(fā)到時間的要求；車輛載重量的限制；配送能力的約束等配送路線確定的方法：節(jié)約里程法PiPjP0PiPjP0分別送貨同時送

22、貨圖圖3-8 配送網(wǎng)絡(luò)圖配送網(wǎng)絡(luò)圖GEDBAFPIJHC5(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)52695(0.5)(0.6)(0.7)36875942364107811107464圖3-9 配送初始方案EDBAFGPIJHC5(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)52695(0.5)(0.6)(0.7)36875942354107811107464表表3-2 配送中心節(jié)約里程排序表配送中心節(jié)約里程排序表序號序號連接點連接點節(jié)約里程節(jié)約里程序號序號連接點連接點節(jié)約里程節(jié)約里程1AB1513FG52AJ1314GH53BC1115H

23、I54CD1016AD45DE1017BI46AI918FH47EF919BE38IJ920DF39AC821GI210BJ822CJ111BD723EG112CE624FI1552695EDBAFGPIJHC(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)(0.5)(0.6)(0.7)36875942354107811107464圖3-10 第一修正方案EDBAFGPIJHC(1.5)(0.4)(1.4)(1.5)(0.8)(0.6)(0.8)265(0.5)(0.6)(0.7)794354710764圖3-11 最優(yōu)解3、安排車輛運行時間 將所有運輸路線首尾相連順序排

24、列，使車輛的空閑時間最短，就此決定車輛數(shù)，并排出配車計劃。最優(yōu)運輸計劃安排表最優(yōu)運輸計劃安排表1 1號線號線1010號線號線6 6號線號線9 9號線號線4 4號線號線5 5號線號線8 8號線號線2 2號線號線7 7號線號線3 3號線號線節(jié)約里程法應(yīng)用案例節(jié)約里程法應(yīng)用案例 由配送中心P向AI等9個用戶配送貨物。圖中連線上的數(shù)字表示公路里程（km）?？拷饔脩衾ㄌ杻?nèi)的數(shù)字，表示各用戶對貨物的需求量（t）。配送中心備有2t和4t載重量的汽車，且汽車一次巡回走行里程不能超過35km，設(shè)送到時間均符合用戶要求，求該配送中心的最優(yōu)送貨方案。ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0

25、.9)(0.9)(0.6)(1.7)(0.5)444555556663777891010111214某配送中心配送網(wǎng)絡(luò)圖計算配送中心至各用戶以及各用戶之間的最短距離，列表得最短距離表： P A B C D E F G H I PABCDEF GHI 11 10 9 6 7 10 10 8 7 5 10 14 18 21 21 13 6 5 9 15 20 20 18 11 4 10 19 19 17 16 6 15 16 14 13 9 17 15 14 14 18 17 12 17 7 由最短距離表，利用節(jié)約法計算出各用戶之間的節(jié)約里程，編制節(jié)約里程表： A B C D E F G H I ABCDEF GHI 16 10 3 0 0 0 6 12 14 7 2 0 0 0 6 11 6 0 0 0 0 7 1 0 0 0 8 0 0 0 6 0 0 6 0 8 根據(jù)節(jié)約里程表中節(jié)約里程多少的順序，由大到小排列，編制節(jié)約里程順序表，以便盡量使節(jié)約里程最多的點組合裝車配送。順位號里程節(jié)約里程順位號里程節(jié)約里程