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

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

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

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

5、= 1.7+0.9+1.4= 4t 運(yùn)行距離845724km 用一輛 4t車運(yùn)送 節(jié)約距離 =18km,配送線路2: 運(yùn)量=2.4+1.5=3.9t4t 運(yùn)行距離8101634km 用一輛 4t車運(yùn)送 節(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é)點(diǎn)之間的距離（km）。配送中心現(xiàn)有2t和4t車輛可供使用，并且每輛車配送距離不得超過30km。 請為百家姓配送中心制定最優(yōu)的配送方案。,第一步：計(jì)算最短距離。根據(jù)配送網(wǎng)絡(luò)中的已知條件，計(jì)算配送中心與客戶及客戶之間的最短距離，結(jié)果見表11-11。 第二步：計(jì)算節(jié)約里程sij,結(jié)果見表11-12。,第三步：將節(jié)約sij,進(jìn)行分類，按從大