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

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

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