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

2、3654 1 1運(yùn)輸線路不成圈的圖上作業(yè)法運(yùn)輸線路不成圈的圖上作業(yè)法 2運(yùn)輸線路成圈的圖上作業(yè)法 運(yùn)輸線路成圈，就是形成閉合回路的“環(huán)形路線，包括一個(gè)圈有三角形、四邊形、多邊形和多個(gè)圈。成圈的線路流向圖要同時(shí)達(dá)到既無(wú)對(duì)流現(xiàn)象、又無(wú)迂回現(xiàn)象的要求才是最優(yōu)流向圖。 對(duì)于成圈運(yùn)輸線路的圖上作業(yè)法，可按下述三個(gè)步驟尋求最優(yōu)方案，如表所示。表 成圈運(yùn)輸線路的圖上作業(yè)法的步驟 步驟詳 述去段破圈確定初始運(yùn)輸方案 就是在成圈的線路中，先假設(shè)某兩點(diǎn)間的線路“不通”，去掉這段線路，把成圈線路轉(zhuǎn)化為不成圈的線路，即破圈；按照運(yùn)輸線路不成圈的圖上作業(yè)法，即可得到初始運(yùn)輸方案。檢查有無(wú)迂回現(xiàn)象 因?yàn)榱飨蚣^都統(tǒng)一畫(huà)在

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

4、存在迂回現(xiàn)象，此方案為最優(yōu)運(yùn)輸方案。第一步第一步 作出初始方案作出初始方案ABCDEFGHI+20-30-50+20-20+100-70+60-30(36)(23)(13)(29)(25)(23)(45)(18) 2運(yùn)輸線路成圈的圖上作業(yè)法ABCDEFGHI+20-30-50+20-20+100-70+60-3030208050102060外圈長(zhǎng)=45+25+18+23=111公里里圈長(zhǎng)=23公里全圈長(zhǎng)=45+23+25+18+23+36=170公里半圈長(zhǎng)=170/2=85公里ABCDEFGHI+20-30-50+20-20+100-70+60-3020102080303040外圈長(zhǎng)=25+1

5、8+23=66公里里圈長(zhǎng)=23+36=59公里全圈長(zhǎng)=45+23+25+18+23+36=170公里半圈長(zhǎng)=170/2=85公里調(diào)整流向調(diào)整流向 3運(yùn)輸線路成兩圈的圖上作業(yè)法甲圈甲圈乙圈乙圈5818324甲圈： 乙圈：半圈長(zhǎng)=7+2+3+6+4+3/2=12.5公里 半圈長(zhǎng)=4+4+5+8/2=10.5公里外圈長(zhǎng)=4公里 外圈長(zhǎng)=0公里里圈長(zhǎng)=2+3+6+3=14公里 里圈長(zhǎng)=4+4+5=13公里初始方案甲圈甲圈乙圈乙圈4716223甲圈： 乙圈：半圈長(zhǎng)=7+2+3+6+4+3/2=12.5公里 半圈長(zhǎng)=4+4+5+8/2=10.5公里外圈長(zhǎng)=4+7=11公里 外圈長(zhǎng)=8公里里圈長(zhǎng)=2+3+3

6、=8公里 里圈長(zhǎng)=4+5=9公里調(diào)整方案練習(xí)練習(xí)最短路徑問(wèn)題最短路徑問(wèn)題例例1 1 多階段決策法多階段決策法 下圖表示從起點(diǎn)下圖表示從起點(diǎn)A A到終點(diǎn)到終點(diǎn)E E之間各點(diǎn)的距離。求之間各點(diǎn)的距離。求A A到到E E的最短路徑。的最短路徑。BACBDBCDEC412312312322164724838675611064375118討論：討論： 1 1、以上求從、以上求從A A到到E E的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從規(guī)模較小的子問(wèn)題，即分別從Di Di 、CiCi、BiBi、A A到到E E的最短路徑問(wèn)題。的最

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

8、三個(gè)始點(diǎn)第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有，終點(diǎn)有D1，D2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求討論分別求C1，C2，C3到到D1，D2 的最短路徑問(wèn)題：的最短路徑問(wèn)題： 表表2分析得知：如果經(jīng)過(guò)分析得知：如果經(jīng)過(guò)C1，則最短路為，則最短路為C1-D2-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)C2，則最短路為，則最短路為C2-D2-E； 如果經(jīng)過(guò)如果經(jīng)過(guò)C3，則最短路為，則最短路為C3-D1-E。 階段階段3本階段始點(diǎn)本階段始點(diǎn)（狀態(tài)）（狀態(tài)）本階段各終點(diǎn)（決策）本階段各終點(diǎn)（決策）到到E的最短距離的最短距離本階段最優(yōu)終點(diǎn)本階段最優(yōu)終點(diǎn)（最優(yōu)決策（最優(yōu)決策) D1 D2 C1 C

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

10、走，則走B4-C3-D1-E。 階段階段2本階段始點(diǎn)本階段始點(diǎn)（狀態(tài)）（狀態(tài)） 本階段各終點(diǎn)（決策）本階段各終點(diǎn)（決策）到到E的最的最短距離短距離本階段最優(yōu)終本階段最優(yōu)終點(diǎn)（最優(yōu)決策點(diǎn)（最優(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個(gè)始點(diǎn)個(gè)始點(diǎn)A，終點(diǎn)有，終點(diǎn)有B1,B2,B3,B4 。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論。

11、對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求分別求A到到B1,B2,B3,B4的最短路徑問(wèn)題：的最短路徑問(wèn)題： 表表4最后，可以得到：從最后，可以得到：從A到到E的最短路徑為的最短路徑為A B4 C3 D1 E 階段階段1本階段始本階段始點(diǎn)點(diǎn)(狀態(tài)狀態(tài)) 本階段各終點(diǎn)（決策）本階段各終點(diǎn)（決策）到到E的最的最短距離短距離本階段最優(yōu)終本階段最優(yōu)終點(diǎn)點(diǎn)(最優(yōu)決策最優(yōu)決策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 14 C22222 以上計(jì)算過(guò)程及結(jié)果，可用圖以上計(jì)算過(guò)程及結(jié)果，可用圖2表示，可以看到，以上方法不僅表示，可以看到，以上方法不僅得到了從得到了從A到到

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

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

14、612111517ABCDEFHIJKG11106651171441189710109424重復(fù)計(jì)算，可得最優(yōu)的路線圖，如下圖。011612111517ABCDEFHIJKG1110665117144118971010942418313438車輛路線安排3030 車輛路線安排問(wèn)題車輛路線安排問(wèn)題VRP, Vehicle Routing Problem是指對(duì)物是指對(duì)物流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問(wèn)題一般可以描述如下：對(duì)一系列裝貨流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問(wèn)題一般可以描述如下：對(duì)一系列裝貨點(diǎn)或和卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過(guò)他們，點(diǎn)或和卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序

15、地通過(guò)他們，在滿足一定的約束條件下如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛在滿足一定的約束條件下如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等下，達(dá)到一定的目標(biāo)容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等下，達(dá)到一定的目標(biāo)如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等）。該問(wèn)題涉及了多如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等）。該問(wèn)題涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑服務(wù)順序確定兩方面的問(wèn)題。輛交通工具的服務(wù)對(duì)象的選擇和路徑服務(wù)順序確定兩方面的問(wèn)題。 VRP問(wèn)題是組合優(yōu)化領(lǐng)域著名的問(wèn)題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)難題之一，求解方法一般相當(dāng)復(fù)雜

16、，通常的做法是應(yīng)用相關(guān)技術(shù)問(wèn)題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問(wèn)題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過(guò)的基本問(wèn)題如旅行商問(wèn)題、指派問(wèn)題、最短路問(wèn)題等），再使研究過(guò)的基本問(wèn)題如旅行商問(wèn)題、指派問(wèn)題、最短路問(wèn)題等），再使用相對(duì)比較成熟的基本理論和方法進(jìn)行求解。用相對(duì)比較成熟的基本理論和方法進(jìn)行求解。3131運(yùn)用VRP模型對(duì)實(shí)際問(wèn)題進(jìn)行研究時(shí)，一般需要考慮以下幾個(gè)方面的問(wèn)題：（1倉(cāng)庫(kù)。倉(cāng)庫(kù)的級(jí)數(shù)，每級(jí)倉(cāng)庫(kù)的數(shù)量、地點(diǎn)和規(guī)模。（2車輛。車輛的型號(hào)和數(shù)量，每種車輛的容積和運(yùn)作費(fèi)用，出發(fā)時(shí)間和返回時(shí)間，司機(jī)休息時(shí)間，最大的里程和時(shí)間限制。（3時(shí)間窗口。由于各處的工作時(shí)間不同，每個(gè)站

17、點(diǎn)每天只允許在特定的時(shí)間內(nèi)取貨和/或送貨。（4顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級(jí)。（5道路信息。車流密度，道路交通費(fèi)用，距離或時(shí)間屬性。（6貨物信息。貨物的種類多少，兼容性，貨物的保鮮。（7運(yùn)輸規(guī)章。工人每天的工作時(shí)間，車輛的周期維護(hù)。3232u（1安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。u（2安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)各日服務(wù)的站點(diǎn)不同，就應(yīng)該對(duì)一周內(nèi)每天的路線和時(shí)刻表問(wèn)題分別進(jìn)行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)避免重疊。u（3從距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)開(kāi)始設(shè)計(jì)路線u（4卡車的行車路線應(yīng)呈水滴狀。u（5盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)

18、計(jì)出的路線是最有效的。u（6取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。u（7對(duì)過(guò)于遙遠(yuǎn)而無(wú)法歸入群落的站點(diǎn)，可以采用其它配送方式。u（8避免時(shí)間窗口過(guò)短。簡(jiǎn)化的原則：簡(jiǎn)化的原則：33331掃描法掃描法路線設(shè)計(jì)中的掃描法很簡(jiǎn)單，即使問(wèn)題規(guī)模很大，也可以通過(guò)手工計(jì)算路線設(shè)計(jì)中的掃描法很簡(jiǎn)單，即使問(wèn)題規(guī)模很大，也可以通過(guò)手工計(jì)算得出結(jié)果。得出結(jié)果。掃描法可闡述如下：掃描法可闡述如下：（1在地圖或方格圖中確定所有站點(diǎn)含倉(cāng)庫(kù)的位置。在地圖或方格圖中確定所有站點(diǎn)含倉(cāng)庫(kù)的位置。（2自倉(cāng)庫(kù)始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針?lè)较蛐D(zhuǎn)自倉(cāng)庫(kù)始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針?lè)?/p>

19、向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交。思索：如果在某線路上增加該站點(diǎn)，是否會(huì)該直線直到與某站點(diǎn)相交。思索：如果在某線路上增加該站點(diǎn)，是否會(huì)超過(guò)車輛的載貨能力？如果沒(méi)有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個(gè)站點(diǎn)相超過(guò)車輛的載貨能力？如果沒(méi)有，繼續(xù)旋轉(zhuǎn)直線，直到與下一個(gè)站點(diǎn)相交。再次計(jì)算累計(jì)貨運(yùn)量是否超過(guò)車輛的運(yùn)載能力先使用最大的車交。再次計(jì)算累計(jì)貨運(yùn)量是否超過(guò)車輛的運(yùn)載能力先使用最大的車輛）。如果超過(guò)，就剔除最后的那個(gè)站點(diǎn)，并確定路線。隨后，從不包輛）。如果超過(guò)，就剔除最后的那個(gè)站點(diǎn)，并確定路線。隨后，從不包含在上一條路線中的站點(diǎn)開(kāi)始，繼續(xù)旋轉(zhuǎn)直線以尋找新路線。繼續(xù)該過(guò)含在上一條路線中的站點(diǎn)開(kāi)始，繼續(xù)旋轉(zhuǎn)直線以尋

20、找新路線。繼續(xù)該過(guò)程直到所有的站點(diǎn)都被安排到路線中。程直到所有的站點(diǎn)都被安排到路線中。（3排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用“水滴法或求解水滴法或求解“流動(dòng)推銷員問(wèn)題的任何算法。流動(dòng)推銷員問(wèn)題的任何算法。3434例例 某公司用廂式貨車從貨主處取貨，圖某公司用廂式貨車從貨主處取貨，圖 (a) (a)是一天的取貨量，單位是一天的取貨量，單位是件。廂式貨車的載貨量是是件。廂式貨車的載貨量是1000010000件。完成所有取貨任務(wù)需一天時(shí)間。件。完成所有取貨任務(wù)需一天時(shí)間。公司需要多少條運(yùn)輸路線即多少部車），每條路線上應(yīng)該經(jīng)

21、過(guò)哪些站公司需要多少條運(yùn)輸路線即多少部車），每條路線上應(yīng)該經(jīng)過(guò)哪些站點(diǎn)，每條路線上的站點(diǎn)怎樣排序。點(diǎn)，每條路線上的站點(diǎn)怎樣排序。 首先，向北畫(huà)一條直線，進(jìn)行逆時(shí)針?lè)较蚴紫龋虮碑?huà)一條直線，進(jìn)行逆時(shí)針?lè)较颉皰呙钂呙琛薄＿@些都是隨。這些都是隨機(jī)決定的。逆時(shí)針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重機(jī)決定的。逆時(shí)針旋轉(zhuǎn)該直線，直到裝載的貨物能裝上一輛載重1000010000件的卡車，同時(shí)又不超載。一旦所有的站點(diǎn)都分派有車輛，就可以利用件的卡車，同時(shí)又不超載。一旦所有的站點(diǎn)都分派有車輛，就可以利用“水滴水滴法安排經(jīng)過(guò)各站點(diǎn)的順序，圖法安排經(jīng)過(guò)各站點(diǎn)的順序，圖 (b) (b)是所列出的最終的路線設(shè)計(jì)。是

22、所列出的最終的路線設(shè)計(jì)。圖圖 掃描法設(shè)計(jì)行車路線掃描法設(shè)計(jì)行車路線汽車站汽車站100040002000300020002000200010002000200030003000a 停留點(diǎn)提貨量數(shù)據(jù)停留點(diǎn)提貨量數(shù)據(jù)汽車站汽車站100040002000300020002000200010002000200030003000b 掃描法解決方案掃描法解決方案2 2 節(jié)約里程法節(jié)約里程法分送式配送運(yùn)輸分送式配送運(yùn)輸分送式配送運(yùn)輸是一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)用戶的共同送貨基本條件：所有客戶的需求量總和不大于一輛車的額定載重量配送路線確定的原則：成本低、效益高、路線短、準(zhǔn)確性高、勞動(dòng)消耗少、運(yùn)力合理等配送路線確定的限制

23、條件：用戶對(duì)貨物品種、規(guī)格、數(shù)量的要求；用戶對(duì)發(fā)到時(shí)間的要求；車輛載重量的限制；配送能力的約束等配送路線確定的方法：節(jié)約里程法PiPjP0PiPjP0分別送貨同時(shí)送貨圖圖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 配送中心

24、節(jié)約里程排序表配送中心節(jié)約里程排序表序號(hào)序號(hào)連接點(diǎn)連接點(diǎn)節(jié)約里程節(jié)約里程序號(hào)序號(hào)連接點(diǎn)連接點(diǎn)節(jié)約里程節(jié)約里程1AB1513FG52AJ1314GH53BC1115HI54CD1016AD45DE1017BI46AI918FH47EF919BE38IJ920DF39AC821GI210BJ822CJ111BD723EG112CE624FI1552695EDBAFGPIJHC(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

25、.5)(0.8)(0.6)(0.8)265(0.5)(0.6)(0.7)794354710764圖3-11 最優(yōu)解3、安排車輛運(yùn)行時(shí)間 將所有運(yùn)輸路線首尾相連順序排列，使車輛的空閑時(shí)間最短，就此決定車輛數(shù)，并排出配車計(jì)劃。最優(yōu)運(yùn)輸計(jì)劃安排表最優(yōu)運(yùn)輸計(jì)劃安排表1 1號(hào)線號(hào)線1010號(hào)線號(hào)線6 6號(hào)線號(hào)線9 9號(hào)線號(hào)線4 4號(hào)線號(hào)線5 5號(hào)線號(hào)線8 8號(hào)線號(hào)線2 2號(hào)線號(hào)線7 7號(hào)線號(hào)線3 3號(hào)線號(hào)線節(jié)約里程法應(yīng)用案例節(jié)約里程法應(yīng)用案例 由配送中心P向AI等9個(gè)用戶配送貨物。圖中連線上的數(shù)字表示公路里程km）?？拷饔脩衾ㄌ?hào)內(nèi)的數(shù)字，表示各用戶對(duì)貨物的需求量t）。配送中心備有2t和4t載重量的汽車

26、，且汽車一次巡回走行里程不能超過(guò)35km，設(shè)送到時(shí)間均符合用戶要求，求該配送中心的最優(yōu)送貨方案。ABCDEFGHIP(0.9)(1.2)(1.6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5)444555556663777891010111214某配送中心配送網(wǎng)絡(luò)圖計(jì)算配送中心至各用戶以及各用戶之間的最短距離，列表得最短距離表： 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é)約法計(jì)算出各用戶之間的節(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é)約