配送運輸管理最短路徑算法

1、第三節(jié) 配送線路的優(yōu)化一、配送線路的優(yōu)化方法兩點間直送式配送運輸規(guī)劃 一對一配送的最短路線問題供應商客戶 設某物流公司要把一批貨物從下圖的公路網絡中的v1城運送到v6城。網絡中各邊旁的數字表示相應兩城之間的公路里程（公里）。試問:汽車應走從v1到v6的什么路線才能使所行駛的里程最少？算法1：指定兩點間最短路的dijkstra標號算法 dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。 dijkstra算法是很有代表性的最短路

2、算法，在很多專業(yè)課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。 dijkstra算法的基本過程是采用標號法。在操作過程中有兩種標號：暫時性標號t（temporary label) 和永久性標號p(permanent label)。 給頂點vi一個p標號p(vi)時表示從指定點vs到vi的最短路的長度為p(vi)，且vi的標號不再改變。 給頂點vi一個t標號t(vi)時表示從指定點vs到vi的估計最短路長的上界為t(vi)，是一個臨時標號。 算法的每一步都把某一點或幾個點的t標號改為p標號;當指定點vt得到p標號時全部計算結束。 對于有n個頂點的網絡，最多經過n-1步運算就可得

3、到從指定點vs到指定點vt的最短路的長度。算法步驟 step1:給vs以標號p標號0，即p(vs)=0,其他各頂點vi均給t標號，即t(vi)=。 step2: 若vi是剛得到p標號的頂點，則考慮與vi相鄰的有t標號的所有頂點vj,把這些頂點vj的t標號修改為：t(vj)=mint(vj),p(vi)+wij step3:比較所有具有t標號的頂點的標號，把最小者 改為p標號，即 當存在兩個或兩個以上最小t標號時，可以同時把它們都改為p標號。當全部頂點均為p標號時，或當vt得到p標號時，停止運算；否則用代替轉回步驟2。)v(tmin)v(pjji)v(ti首先求出從1出發(fā)的一條最短路徑（1-2：

4、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 練習 求v1到v6的最短距離。 dijkstra標號算法還可應用于有向網絡。 例2 設有一個原油輸送系統，油庫為，碼頭為是三個中間閥門點。管道長度已知。原油由vs經過中間閥門點流向碼頭。為了使原油盡快輸送到碼頭，應該沿哪一條線路輸送。一對多配送的最短路線問題分送式配送運輸第三節(jié) 配送線路的優(yōu)化一、配送線路的優(yōu)化方法分送式配送運輸 分送式配送是指由一個供應點對多個客戶的共同送貨。 基本條件：同一條線路上所有客戶的需求

5、量總和不大于一輛車的額定載重量，送貨時，由這一輛車裝著所有客戶的貨物，沿著一條精心挑選的最佳路線依次將貨物送到各個客戶手中，這樣既保證按時按量將用戶需要的貨物及時送到，又節(jié)約了車輛，節(jié)省了費用，緩解了交通緊張的壓力，并減少了運輸對環(huán)境造成的污染。節(jié)約里程法 clarke 和wright 于1964年提出該算法。 節(jié)省里程法（savings algorithm） vsp網絡法（vehicle scheduling program） 節(jié)約里程法的目標：根據配送中心的運輸能力及其到客戶之間的距離和各客戶之間的相對距離來制訂使總的配送車輛噸千米數達到或接近最小的配送方案。節(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的里程數c 節(jié)約里程法基本思想：節(jié)約里程法基本思想： 如果一個配送中心分別向n個客戶配送貨物，在汽車載重能力允許的前提下，每輛汽車在配送路線上經過的客戶個數越多，里程節(jié)約量越大，配送線路越合理。 節(jié)約法的基本規(guī)定節(jié)約法的基本規(guī)定：1.配送的是同種或相似的貨物；2.各客戶的位置及需求量已知；3.配送中心有足夠的運輸能力。且滿足：1.滿足所有用戶的要貨需求；2.每輛車不能超載；3.每車每天總運行時間或行駛里程不能超出規(guī)定上限；4.方案能滿足所有用戶的到貨時間要求

7、。步驟1：計算網絡結點之間的最短距離。步驟2：計算各客戶之間的可節(jié)約的運行距離： a+b-c ,其中a 為p點至各點距離；b為p點至各點距離；c為兩點間最小距離。步驟3：對節(jié)約里程數按大小順序進行排列。步驟4：組成配送路線圖節(jié)約里程法算例 配送中心p0向p1,p2,p3,p4,p5共 5個客戶配送貨物，該配送中心和5家客戶之間的運輸距離以及5家客戶需要送貨的數量已知（單位：運輸距離：km；送貨數量：噸）。已知該配送中心備有額定載重量為2噸的卡車3輛，額定載重量4噸的卡車2輛。 1.試利用節(jié)約里程法制定最優(yōu)配送方案。 2.設卡車行駛速度平均為40km/小時,試比較優(yōu)化后的方案比單獨向各用戶分送可

8、節(jié)約多少時間？該算例配送路線網絡圖10p1p0p2p4（1.4）p3p5（2.4）（0.9）（1.7）（1.5）1275124136812168節(jié)約里程法基本步驟 step1:作運輸里程表，列出配送中心到用戶及用戶間的最短距離； step2:由運輸里程表、按節(jié)約里程公式，求得相應的節(jié)約里程數，如上表（）內 ； step3:將節(jié)約里程進行分類，按從大到小順序排列； step4:按“節(jié)約里程”的大小和客戶的收貨數量或重量，在車輛載重允許的情況下組成配送巡回路線圖。配送中心與用戶及用戶間最短距離節(jié)約里程數節(jié)約里程數排序初始方案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é)約里程數為20km,故節(jié)約時間為20km/40km/小時=0.5小時練習：練習： 求節(jié)