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

1、第三節(jié) 配送線路的優(yōu)化一、配送線路的優(yōu)化方法兩點(diǎn)間直送式配送運(yùn)輸規(guī)劃 一對(duì)一配送的最短路線問(wèn)題供應(yīng)商客戶 設(shè)某物流公司要把一批貨物從下圖的公路網(wǎng)絡(luò)中的v1城運(yùn)送到v6城。網(wǎng)絡(luò)中各邊旁的數(shù)字表示相應(yīng)兩城之間的公路里程（公里）。試問(wèn):汽車(chē)應(yīng)走從v1到v6的什么路線才能使所行駛的里程最少？算法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算法是很有代表性的最短路

2、算法，在很多專(zhuān)業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。 dijkstra算法的基本過(guò)程是采用標(biāo)號(hào)法。在操作過(guò)程中有兩種標(biāo)號(hào)：暫時(shí)性標(biāo)號(hào)t（temporary label) 和永久性標(biāo)號(hào)p(permanent label)。 給頂點(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)。 算法的每一步都把某一點(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)算就可得

3、到從指定點(diǎn)vs到指定點(diǎn)vt的最短路的長(zhǎng)度。算法步驟 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)=mint(vj),p(vi)+wij 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。)v(tmin)v(pjji)v(ti首先求出從1出發(fā)的一條最短路徑（1-2：

4、4），求次短路徑（2-5：2），依次類(lèi)推： （5-6：8）， （5-4-6：7）， （5-4-3-6：6），最短距離求得的最短路徑是：1-2-5-4-3-6距離是：4+2+6=12 練習(xí) 求v1到v6的最短距離。 dijkstra標(biāo)號(hào)算法還可應(yīng)用于有向網(wǎng)絡(luò)。 例2 設(shè)有一個(gè)原油輸送系統(tǒng)，油庫(kù)為，碼頭為是三個(gè)中間閥門(mén)點(diǎn)。管道長(zhǎng)度已知。原油由vs經(jīng)過(guò)中間閥門(mén)點(diǎn)流向碼頭。為了使原油盡快輸送到碼頭，應(yīng)該沿哪一條線路輸送。一對(duì)多配送的最短路線問(wèn)題分送式配送運(yùn)輸?shù)谌?jié) 配送線路的優(yōu)化一、配送線路的優(yōu)化方法分送式配送運(yùn)輸 分送式配送是指由一個(gè)供應(yīng)點(diǎn)對(duì)多個(gè)客戶的共同送貨。 基本條件：同一條線路上所有客戶的需求

5、量總和不大于一輛車(chē)的額定載重量，送貨時(shí)，由這一輛車(chē)裝著所有客戶的貨物，沿著一條精心挑選的最佳路線依次將貨物送到各個(gè)客戶手中，這樣既保證按時(shí)按量將用戶需要的貨物及時(shí)送到，又節(jié)約了車(chē)輛，節(jié)省了費(fèi)用，緩解了交通緊張的壓力，并減少了運(yùn)輸對(duì)環(huán)境造成的污染。節(jié)約里程法 clarke 和wright 于1964年提出該算法。 節(jié)省里程法（savings algorithm） vsp網(wǎng)絡(luò)法（vehicle scheduling program） 節(jié)約里程法的目標(biāo)：根據(jù)配送中心的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對(duì)距離來(lái)制訂使總的配送車(chē)輛噸千米數(shù)達(dá)到或接近最小的配送方案。節(jié)約里程法的基本思想pabba

6、pabbad1=2(a+b) d2=a+b+cd1-d2=2(a+b)-(a+b+c)=a+b-c0第二種方案比第一種方案要節(jié)約a+b-c的里程數(shù)c 節(jié)約里程法基本思想：節(jié)約里程法基本思想： 如果一個(gè)配送中心分別向n個(gè)客戶配送貨物，在汽車(chē)載重能力允許的前提下，每輛汽車(chē)在配送路線上經(jīng)過(guò)的客戶個(gè)數(shù)越多，里程節(jié)約量越大，配送線路越合理。 節(jié)約法的基本規(guī)定節(jié)約法的基本規(guī)定：1.配送的是同種或相似的貨物；2.各客戶的位置及需求量已知；3.配送中心有足夠的運(yùn)輸能力。且滿足：1.滿足所有用戶的要貨需求；2.每輛車(chē)不能超載；3.每車(chē)每天總運(yùn)行時(shí)間或行駛里程不能超出規(guī)定上限；4.方案能滿足所有用戶的到貨時(shí)間要求

7、。步驟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：組成配送路線圖節(jié)約里程法算例 配送中心p0向p1,p2,p3,p4,p5共 5個(gè)客戶配送貨物，該配送中心和5家客戶之間的運(yùn)輸距離以及5家客戶需要送貨的數(shù)量已知（單位：運(yùn)輸距離：km；送貨數(shù)量：噸）。已知該配送中心備有額定載重量為2噸的卡車(chē)3輛，額定載重量4噸的卡車(chē)2輛。 1.試?yán)霉?jié)約里程法制定最優(yōu)配送方案。 2.設(shè)卡車(chē)行駛速度平均為40km/小時(shí),試比較優(yōu)化后的方案比單獨(dú)向各用戶分送可

8、節(jié)約多少時(shí)間？該算例配送路線網(wǎng)絡(luò)圖10p1p0p2p4（1.4）p3p5（2.4）（0.9）（1.7）（1.5）1275124136812168節(jié)約里程法基本步驟 step1:作運(yùn)輸里程表，列出配送中心到用戶及用戶間的最短距離； step2:由運(yùn)輸里程表、按節(jié)約里程公式，求得相應(yīng)的節(jié)約里程數(shù)，如上表（）內(nèi) ； step3:將節(jié)約里程進(jìn)行分類(lèi)，按從大到小順序排列； step4:按“節(jié)約里程”的大小和客戶的收貨數(shù)量或重量，在車(chē)輛載重允許的情況下組成配送巡回路線圖。配送中心與用戶及用戶間最短距離節(jié)約里程數(shù)節(jié)約里程數(shù)排序初始方案p3p47（1.4）p0p2p5p1（2.4）（0.9）（1.7）（1.5）10688二次解8 （1.4）p0p2p3p4p5p1（2.4）（0.9）（1.7）（1.5）10754816 節(jié)約里程數(shù)為20km,故節(jié)約時(shí)間為20km/40km/小時(shí)=0.5小時(shí)練習(xí)：練習(xí)： 求節(jié)