1、配送線路優(yōu)化方法,（一）直送式配送運輸,適用方法最短路徑法 適用條件： 1、由配送中心向每一位客戶開展專門送貨； 2、該客戶的送貨量一般必須滿足配送車輛滿載。 配送效果： 1.配送車輛滿載運輸； 2.配送運輸路線距離最短。,標(biāo)點法設(shè)計最短線路,一對一配送的最短路線問題,【例】 求1-6的 最短距 離。,供應(yīng)商,客戶,首先求出從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,（二）分送式配送運輸,適用方法節(jié)約里程法 適用條件： 1、由

2、配送中心向多位客戶開展拼裝送貨； 2、每位客戶的送貨量都不能滿足配送車輛滿載。 配送效果： 1.配送車輛滿載運輸； 2.配送運輸路線距離最短。,一對多配送的最短路線問題,節(jié)約里程法的意義,送貨時，由一輛車裝載所有客戶的貨物，沿著一條精心設(shè)計的最佳路線依次將貨物送到各位客戶手中，這樣既保證按時按量將用戶需要的貨物及時送達，又節(jié)約了車輛，節(jié)省了費用，緩解了交通緊張的壓力，并減少了運輸對環(huán)境造成的污染。,1.滿足客戶配送需要,2.減少配送車輛使用,3.緩解交通緊張壓力,節(jié)約里程法(Saving Algorithm),車輛調(diào)度程序法(Vehicle Scheduling Program:VSP) 又稱

3、節(jié)約算法，是指用來解決運輸車輛數(shù)目不確定的問題的最有名的啟發(fā)式算法。 核心思想: 節(jié)約里程法核心思想是依次將運輸問題中的兩個回路合并為一個回路，每次使合并后的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。,節(jié)約里程法,利用節(jié)約法制定出的配送方案除了使配送總噸公里數(shù)最小外，還應(yīng)滿足以下條件： 滿足所有用戶的需求 不使任何一輛車超載 每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限； 用戶到貨時間要求。不得超過規(guī)定時間。,節(jié)約里程法,運行距離為：2a+2b,運行距離為：a+b+c,節(jié)約行程：a + bc,節(jié)約里程法,例題：已知配送中

4、心P0向5個用戶Pj配送貨物，其配送路線網(wǎng)絡(luò)、配送中心與用戶的距離以及用戶之間的距離如下圖所示，配送中心有3臺2t卡車和2臺4t兩種車輛可供使用。利用節(jié)約里程法制定最優(yōu)的配送方案。,節(jié)約里程法,第1 步：作運輸里程表，列出配送中心到用戶及用戶間的最短距離。,節(jié)約里程法,第2步：按節(jié)約里程公式求得相應(yīng)的節(jié)約里程數(shù),節(jié)約里程法,第 3 步：將節(jié)約里程按從大到小順序排列,節(jié)約里程法,第4步：根據(jù)載重量約束與節(jié)約里程大小，順序連接各客戶結(jié)點,形成二個配送路線 .,P2P3 P3P4P2P4P4P5 P1P2 P1P5 P1P3 P2P5 P3P5 P1P4,節(jié)約里程法,節(jié)約里程法,配送線路1： 運量

5、= 1.7+0.9+1.4= 4t 運行距離845724km 用一輛 4t車運送 節(jié)約距離 =18km,配送線路2: 運量=2.4+1.5=3.9t4t 運行距離8101634km 用一輛 4t車運送 節(jié)約距離=2km,節(jié)約里程法,初始方案：配送線路5條， 需要車5輛 配送距離=392=78KM,節(jié)約里程法,初始方案： 配送線路5條， 需要車5輛 配送距離：392=78KM 優(yōu)化后的方案： 2條配送線路，2輛4t車 配送距離：243458km,練習(xí),位于牡丹江市內(nèi)的百家姓配送中心（P0）向它旗下的10家連鎖商店pi(i=1,2,10)配送商品，其配送網(wǎng)絡(luò)如下圖所示。 圖中括號內(nèi)的數(shù)字表示每一家連鎖店的需求量（t），線路上的數(shù)字表示兩節(jié)點之間的距離（km）。配送中心現(xiàn)有2t和4t車輛可供使用，并且每輛車配送距離不得超過30km。 請為百家姓配送中心制定最優(yōu)的配送方案。,第一步：計算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計算配送中心與客戶及客戶之間的最短距離，結(jié)果見表11-11。 第二步：計算節(jié)約里程sij,結(jié)果見表11-12。,第三步：將節(jié)約sij,進行分類，按從大