配送路線優(yōu)化

項目三配送服務(wù)教學(xué)任務(wù)：1.進貨入庫作業(yè)、儲存作業(yè)、盤點作業(yè)、返品處理作業(yè)2.訂單處理與補貨、揀貨作業(yè)3.出貨作業(yè)上——車輛配裝、貨品裝箱、裝卸工安排4.出貨作業(yè)下——配送線路優(yōu)化項目三配送服務(wù)小組PPT介紹互動：提問+分享內(nèi)容補充+總結(jié)任務(wù)3

出貨作業(yè)之配送線路優(yōu)化

一、最短路徑法

二、節(jié)約法任務(wù)3

配送線路優(yōu)化方法

之1：最短路徑法一、最短路徑法

所謂最短路徑法，是指要從網(wǎng)絡(luò)圖中某頂點出發(fā)，經(jīng)過圖中路徑到達另一頂點，而這些路徑不止一條，如何找到一條路徑使各邊的權(quán)值之和為最小。

任務(wù)3配送線路優(yōu)化方法

之1：最短路徑法最短路徑法示例1：

新加坡某配送中心簽訂了一項配送運輸合同，要從配送中心A配送一批貨物到銷售地F,兩點之間可選擇的行車路線如圖所示，求從配送中心A到銷售地F的最短路徑。

DEBACF11428741823任務(wù)3

配送線路優(yōu)化方法

之1：最短路徑法

最短路徑法示例2：

從V0到V6找出最短路徑？

任務(wù)3配送線路優(yōu)化方法

之1：最短路徑法

最短路徑法計算3

任務(wù)3

配送線路優(yōu)化方法

之1：最短路徑法

最短路徑法計算3參考答案：

2的最短距離100路徑1-23的最短距離175路徑1-34的最短距離150路徑1-45的最短距離325路徑1-4-56的最短距離359路徑1-4-67的最短距離425路徑1-4-78的最短距離550路徑1-4-7-89的最短距離550路徑1-4-6-910的最短距離575路徑1-4-6-9-10任務(wù)3配送線路優(yōu)化方法

之1：最短路徑法

最短路徑法練習(xí)題：

某配送公司要將客戶急需的商品從配送中心P運送到商場Q，圖1表示由起點P到終點Q的路線圖，各條弧所對應(yīng)的數(shù)字表示通過該段路線所需時間。試求所需時間最短路線。

任務(wù)3配送線路優(yōu)化方法

之2：節(jié)約法（起止點重合的配送路線選擇）

任務(wù)導(dǎo)入1：

某車一天的貨運任務(wù)如下圖：求最佳行車路線。注：方框為供貨點，橢圓為需求點。K=4噸A=2噸B=1噸C=1噸121116678解：分析：從供貨點到需求點再返回供貨點的線路共4條，距離計算如下：1：K-A-B-C-K,L1=12+6+7+11=362：K-C-B-A-K,L2=11+7+6+12=363：K-A-C-B-K,L3=12+8+7+16=434：K-C-A-B-K,L4=11+8+6+16=415：K-B-A-C-K,L5=16+6+8+11=416：K-B-C-A-K,L6=16+7+8+12=43分析各線路的貨運周轉(zhuǎn)量大小并排序Z1=4*12+2*6+1*7+11*0=48+12+7=67Z2=4*11+3*7+2*6+0*12=44+21+12=77Z3=4*12+2*8+1*7+0*16=48+16+7=71Z4=4*11+3*8+1*6+0*16=44+24+6=74Z5=4*16+3*6+1*8+0*11=64+18+8=90Z6=4*16+3*7+2*8+0*12=64+21+16=101顯然，第一條線路的貨運周轉(zhuǎn)量最小，故選擇第一條線路。任務(wù)3配送線路優(yōu)化方法

之2：節(jié)約法（起止點重合的配送路線選擇）

任務(wù)導(dǎo)入2：

某配送配送中心A向全市4個商店B、C、D、E進行配送，各點相對位置見下圖，運輸距離見表1，求最佳配送路線。任務(wù)3配送線路優(yōu)化方法

之2：節(jié)約法一、節(jié)約法的基本假定

前提假設(shè)：當(dāng)從若干配送據(jù)點向眾多的客戶配送貨物時，各用戶的坐標及需求量均為已知，配送中心有足夠的運輸能力。利用節(jié)約法制定出的配送方案除了使配送里程最小外，還滿足以下條件，方案能滿足所有用戶的要求，不使任何一輛車超載；每輛車每天的總運行時間或行駛里程不超過規(guī)定的上限，能滿足用戶到貨時間要求。二、節(jié)約法的基本原理假如由一家配送中心O向兩個用戶A、B送貨，配送中心到兩客戶的最短距離分別是a和b，A和B間的最短距離為x，AB的貨物需求量分別是Q1和Q2，且Q1+Q2小于車輛裝載量Q，如同7－1所示。圖7-1路線圖ＡＢO從倉庫O要運送貨物給客戶A和B第一條路線是從O到A，再返回，然后再從O到B，再返回O，總距離為a＋a＋b＋b＝2a＋2b外一種路線，從O到A到B，再到O?？偩嚯x為：a＋b＋x。將客戶結(jié)合考慮，在第二種方案下走行路線的節(jié)約里程數(shù)是：（2a＋2b）－（a＋b＋x）即：a＋b－x它從不為負。因為三角形的第三條邊總是小于其他兩條邊之和，因此，它最小為零。將客戶連接起來，增加了節(jié)約?？蛻糁g的距離越近，而且它們距離倉庫越遠，那么節(jié)約就會越大。這個方法也可以用時間來代替距離計算。2314關(guān)于這個公式，注意：

二、節(jié)約法的基本原理為了描述這個方法的使用，考慮下例。例：如圖7-2所示，需要安排從倉庫O送貨給四個客戶A、B、C、D。任何路程不得超過75千米。圖7-2配送路線圖三、節(jié)約法示例1

解：第一步：計算任一對客戶的節(jié)約里程值，見表2-10：表2-10節(jié)約值計算表第二步：從最大的節(jié)約值開始，將客戶連接在一起，直到達到一個限制。三、節(jié)約法示例1

第三步：因此選擇第一條路線O—C—D—O。

從最大節(jié)約值27開始，連接客戶C和D。距離O—C—D—O，和為63千米，沒有超過限制。選擇下一個最大的節(jié)約值，為20，將A、B、C和D連在一起，距離O—A—B—C—D—O，超過了75千米，不予采納。選擇另一個最大的節(jié)約值10，將B、C和D連接在一起，距離O—B—C—D—O，超過了75千米，仍然不采納。選擇另一個最大的節(jié)約值5，將A、C和D連接在一起，距離O—A—C—D—O，大于75千米，不采納。表2-11計算結(jié)果

第五步：重新進行剛才的程序，從最大的20開始，將A和B連接在一起，距離O—A—B—O是50千米，是第二條路線。第四步：劃掉C和D之間的行和列，見表2-11。三、節(jié)約法示例1任務(wù)3配送線路優(yōu)化方法

之2：節(jié)約法（起止點重合的配送路線選擇）

任務(wù)導(dǎo)入：

某配送配送中心A向全市4個商店B、C、D、E進行配送，各點相對位置見下圖，運輸距離見表1，求最佳配送路線?，F(xiàn)在能找到最佳配送路線嗎？

三、節(jié)約法示例2已知配送中心P0向5個用戶Pj配送貨物，其配送路線網(wǎng)絡(luò)、配送中心與用戶的距離以及用戶之間的距離如下圖與表所示：圖中括號內(nèi)的數(shù)字表示客戶的需求量（單位：噸），線路上的數(shù)字表示兩結(jié)點之間的距離，配送中心有3臺2t卡車和2臺4t兩種車輛可供使用。問題：1、試利用節(jié)約里程法制定最優(yōu)的配送方案？2、設(shè)卡車行駛的速度平均為40公里/小時，試比較優(yōu)化后的方案比單獨向各用戶分送可節(jié)約多少時間？

三、節(jié)約法示例2

三、節(jié)約法示例2第1步：作運輸里程表，列出配送中心到用戶及用戶間的最短距離。

三、節(jié)約法示例2第1步：作運輸里程表，列出配送中心到用戶及用戶間的最短距離。

三、節(jié)約法示例2第1步：作運輸里程表，列出配送中心到用戶及用戶間的最短距離。

三、節(jié)約法示例2第2步：由運輸里程表、按節(jié)約里程公式，求得相應(yīng)的節(jié)約里程數(shù)，如下表（）內(nèi)。

三、節(jié)約法示例2第2步：由運輸里程表、按節(jié)約里程公式，求得相應(yīng)的節(jié)約里程數(shù)，如下表（）內(nèi)。

三、節(jié)約法示例2第3步：將節(jié)約里程按從大到小順序排列

三、節(jié)約法示例2第3步：將節(jié)約里程按從大到小順序排列

三、節(jié)約法示例2第4步：根據(jù)載重量約束與節(jié)約里程大小，將各客戶結(jié)點連接起來，形成二個配送路線。即A、B兩配送方案。

三、節(jié)約法示例2第5步：確定單獨送貨的配送線路

計算初始方案配送距離=?

三、節(jié)約法示例2①配送線路A：P0-P2-P3-P4-P0運量=q2+q3+q4=1.7+0.9+1.4=4t,用一輛4t車運送節(jié)約距離SA=10+8=18km②配送線路B:P0-P5-P1-P0運量=q5+q1=2.4+1.5=3.9t<4t,用一輛4t車運送節(jié)約距離SB=2km第6步：與初始單獨送貨方案相比，計算總節(jié)約里程與節(jié)約時間總節(jié)約里程：△S=SA+SB=20km與初始單獨送貨方案相比，可節(jié)約時間：△T=△S/V=20/40=0.5小時

三、節(jié)約法示例3練習(xí)：某連鎖零售店，下設(shè)有一個配送P和9個連鎖分店A-J,配送中心和各連鎖分店及各連鎖分店之間的位置關(guān)系如圖所示。該商品由配送中心統(tǒng)一采購并進行配送運輸，配送中心有最大裝載量為2t和5t的貨車，并限定車輛一次運行距離不超過35km，設(shè)送到時間均符合用戶要求，求配送中心的最優(yōu)配送運輸方案。

三、節(jié)約法示例3練習(xí)：某連鎖零售店，下設(shè)有一個配送P和9個連鎖分店A-J,配送中心和各連鎖分店及各連鎖分店之間的位置關(guān)系如圖所示。該商品由配送中心統(tǒng)一采購并進行配送運輸，配送中心有最大裝載量為2t和5t的貨車，并限定車輛一次運行距離不超過35km，設(shè)送到時間均符合用戶要求，求配送中心的最優(yōu)配送運輸方案。作業(yè)：節(jié)約法示例4

下圖所示為一配送網(wǎng)絡(luò)，P為配送中心所在地，A－J為客戶所在地，括號內(nèi)的數(shù)字為配送量，單位為噸（t），線路上的數(shù)字為道路的距離，單位為公里（km）?，F(xiàn)有可以利用的車輛是最大裝載量為2噸和4噸的兩種廂式貨車，并限制車輛一次運行距離在30公里以內(nèi)?，F(xiàn)求最佳配送路線。第一步：首先計算相互之間最短距離，根據(jù)上圖中配送中心至各用戶之間，用戶與用戶之間的距離，得出配送路線最短的距離矩陣，如圖：第二步：從最短距離矩陣中計算出各用戶之間的節(jié)約行程見下圖。例如，計算AB的節(jié)約距離：PA的距離：a=10，PB的距離：b=9，AB的距離：c=4，a+b-c=15

配送路線節(jié)約里程圖

第三步：對節(jié)約行程按大小順序排列，見下表。

配送線路節(jié)約里程排序表