配送運(yùn)輸管理最短路徑算法

配送運(yùn)輸管理最短路徑算法2023/4/11第一頁，共三十七頁，2022年，8月28日設(shè)某物流公司要把一批貨物從下圖的公路網(wǎng)絡(luò)中的V1城運(yùn)送到V6城。網(wǎng)絡(luò)中各邊旁的數(shù)字表示相應(yīng)兩城之間的公路里程（公里）。試問:汽車應(yīng)走從V1到V6的什么路線才能使所行駛的里程最少？2023/4/12第二頁，共三十七頁，2022年，8月28日算法1：指定兩點(diǎn)間最短路的Dijkstra標(biāo)號算法Dijkstra算法是典型最短路算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點(diǎn)很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。2023/4/13第三頁，共三十七頁，2022年，8月28日Dijkstra算法的基本過程是采用標(biāo)號法。在操作過程中有兩種標(biāo)號：暫時性標(biāo)號T（TemporaryLabel)和永久性標(biāo)號P(PermanentLabel)。給頂點(diǎn)Vi一個P標(biāo)號P(Vi)時表示從指定點(diǎn)Vs到Vi的最短路的長度為P(Vi)，且Vi的標(biāo)號不再改變。給頂點(diǎn)Vi一個T標(biāo)號T(Vi)時表示從指定點(diǎn)Vs到Vi的估計最短路長的上界為T(Vi)，是一個臨時標(biāo)號。2023/4/14第四頁，共三十七頁，2022年，8月28日算法的每一步都把某一點(diǎn)或幾個點(diǎn)的T標(biāo)號改為P標(biāo)號;當(dāng)指定點(diǎn)Vt得到P標(biāo)號時全部計算結(jié)束。對于有N個頂點(diǎn)的網(wǎng)絡(luò)，最多經(jīng)過N-1步運(yùn)算就可得到從指定點(diǎn)Vs到指定點(diǎn)Vt的最短路的長度。2023/4/15第五頁，共三十七頁，2022年，8月28日算法步驟Step1:給Vs以標(biāo)號P標(biāo)號0，即P(Vs)=0,其他各頂點(diǎn)Vi均給T標(biāo)號，即T(Vi)=∞。Step2:若Vi是剛得到P標(biāo)號的頂點(diǎn)，則考慮與Vi相鄰的有T標(biāo)號的所有頂點(diǎn)Vj,把這些頂點(diǎn)Vj的T標(biāo)號修改為：T(Vj)=min{T(Vj),P(Vi)+Wij}2023/4/16第六頁，共三十七頁，2022年，8月28日Step3:比較所有具有T標(biāo)號的頂點(diǎn)的標(biāo)號，把最小者改為P標(biāo)號，即當(dāng)存在兩個或兩個以上最小T標(biāo)號時，可以同時把它們都改為P標(biāo)號。當(dāng)全部頂點(diǎn)均為P標(biāo)號時，或當(dāng)Vt得到P標(biāo)號時，停止運(yùn)算；否則用代替轉(zhuǎn)回步驟2。2023/4/17第七頁，共三十七頁，2022年，8月28日首先求出從1出發(fā)的一條最短路徑（1-2：4），求次短路徑（2-5：2），

依次類推：（5-6：8），

（5-4-6：7），

（5-4-3-6：6），最短距離

求得的最短路徑是：1-2-5-4-3-6

距離是：4+2+6=12

2023/4/18第八頁，共三十七頁，2022年，8月28日練習(xí)求V1到V6的最短距離。2023/4/19第九頁，共三十七頁，2022年，8月28日Dijkstra標(biāo)號算法還可應(yīng)用于有向網(wǎng)絡(luò)。例2設(shè)有一個原油輸送系統(tǒng)，油庫為，碼頭為是三個中間閥門點(diǎn)。管道長度已知。原油由Vs經(jīng)過中間閥門點(diǎn)流向碼頭。為了使原油盡快輸送到碼頭，應(yīng)該沿哪一條線路輸送。2023/4/110第十頁，共三十七頁，2022年，8月28日㈡一對多配送的最短路線問題——分送式配送運(yùn)輸?shù)谌?jié)配送線路的優(yōu)化

一、配送線路的優(yōu)化方法2023/4/111第十一頁，共三十七頁，2022年，8月28日分送式配送運(yùn)輸分送式配送是指由一個供應(yīng)點(diǎn)對多個客戶的共同送貨?；緱l件：同一條線路上所有客戶的需求量總和不大于一輛車的額定載重量，送貨時，由這一輛車裝著所有客戶的貨物，沿著一條精心挑選的最佳路線依次將貨物送到各個客戶手中，這樣既保證按時按量將用戶需要的貨物及時送到，又節(jié)約了車輛，節(jié)省了費(fèi)用，緩解了交通緊張的壓力，并減少了運(yùn)輸對環(huán)境造成的污染。2023/4/112第十二頁，共三十七頁，2022年，8月28日節(jié)約里程法Clarke和Wright于1964年提出該算法。節(jié)省里程法（SavingsAlgorithm）VSP網(wǎng)絡(luò)法（VehicleSchedulingProgram）節(jié)約里程法的目標(biāo)：根據(jù)配送中心的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對距離來制訂使總的配送車輛噸千米數(shù)達(dá)到或接近最小的配送方案。2023/4/113第十三頁，共三十七頁，2022年，8月28日節(jié)約里程法的基本思想PABbaPABba㈠㈡D1=2(a+b)D2=a+b+cD1-D2=2(a+b)-(a+b+c)=a+b-c＞0第二種方案比第一種方案要節(jié)約a+b-c的里程數(shù)c2023/4/114第十四頁，共三十七頁，2022年，8月28日節(jié)約里程法基本思想：如果一個配送中心分別向N個客戶配送貨物，在汽車載重能力允許的前提下，每輛汽車在配送路線上經(jīng)過的客戶個數(shù)越多，里程節(jié)約量越大，配送線路越合理。2023/4/115第十五頁，共三十七頁，2022年，8月28日節(jié)約法的基本規(guī)定：1.配送的是同種或相似的貨物；2.各客戶的位置及需求量已知；3.配送中心有足夠的運(yùn)輸能力。且滿足：1.滿足所有用戶的要貨需求；2.每輛車不能超載；3.每車每天總運(yùn)行時間或行駛里程不能超出規(guī)定上限；4.方案能滿足所有用戶的到貨時間要求。2023/4/116第十六頁，共三十七頁，2022年，8月28日步驟1：計算網(wǎng)絡(luò)結(jié)點(diǎn)之間的最短距離。步驟2：計算各客戶之間的可節(jié)約的運(yùn)行距離：a+b-c,其中a為P點(diǎn)至各點(diǎn)距離；b為P點(diǎn)至各點(diǎn)距離；c為兩點(diǎn)間最小距離。步驟3：對節(jié)約里程數(shù)按大小順序進(jìn)行排列。步驟4：組成配送路線圖2023/4/117第十七頁，共三十七頁，2022年，8月28日節(jié)約里程法算例配送中心P0向P1,P2,P3,P4,P5共5個客戶配送貨物，該配送中心和5家客戶之間的運(yùn)輸距離以及5家客戶需要送貨的數(shù)量已知（單位：運(yùn)輸距離：km；送貨數(shù)量：噸）。已知該配送中心備有額定載重量為2噸的卡車3輛，額定載重量4噸的卡車2輛。1.試?yán)霉?jié)約里程法制定最優(yōu)配送方案。2.設(shè)卡車行駛速度平均為40km/小時,試比較優(yōu)化后的方案比單獨(dú)向各用戶分送可節(jié)約多少時間？2023/4/118第十八頁，共三十七頁，2022年，8月28日該算例配送路線網(wǎng)絡(luò)圖10 P1

P0

P2

P4

（1.4） P3

P5

（2.4） （0.9） （1.7） （1.5） 12 7

5

12

4

13 6

8

12 16 8 2023/4/119第十九頁，共三十七頁，2022年，8月28日節(jié)約里程法基本步驟Step1:作運(yùn)輸里程表，列出配送中心到用戶及用戶間的最短距離；Step2:由運(yùn)輸里程表、按節(jié)約里程公式，求得相應(yīng)的節(jié)約里程數(shù)，如上表（）內(nèi)

；Step3:將節(jié)約里程進(jìn)行分類，按從大到小順序排列；Step4:按“節(jié)約里程”的大小和客戶的收貨數(shù)量或重量，在車輛載重允許的情況下組成配送巡回路線圖。2023/4/120第二十頁，共三十七頁，2022年，8月28日配送中心與用戶及用戶間最短距離2023/4/121第二十一頁，共三十七頁，2022年，8月28日節(jié)約里程數(shù)2023/4/122第二十二頁，共三十七頁，2022年，8月28日節(jié)約里程數(shù)排序2023/4/123第二十三頁，共三十七頁，2022年，8月28日初始方案P3

P4

7 （1.4）

P0

P2

P5

P1

（2.4） （0.9） （1.7） （1.5） 10 6 8 8 2023/4/124第二十四頁，共三十七頁，2022年，8月28日二次解8

（1.4） P0

P2

P3

P4

P5

P1

（2.4） （0.9） （1.7） （1.5） 10 7 5 4 8 Ⅰ16Ⅱ2023/4/125第二十五頁，共三十七頁，2022年，8月28日節(jié)約里程數(shù)為20km,故節(jié)約時間為20km/40km/小時=0.5小時2023/4/126第二十六頁，共三十七頁，2022年，8月28日練習(xí)：求節(jié)約里程的線路設(shè)計，假定該公司有2T和4T車，每次運(yùn)行距離不超過60KM。142023/4/127第二十七頁，共三十七頁，2022年，8月28日2023/4/128第二十八頁，共三十七頁，2022年，8月28日2023/4/129第二十九頁，共三十七頁，2022年，8月28日cab2023/4/130第三十頁，共三十七頁，2022年，8月28日(a+b-c=5+8-4=9)(5+7-7=5)(8+7-3=12)2023/4/131第三十一頁，共三十七頁，2022年，8月28日2023/4/132第三十二頁，共三十七頁，202