配送路線優(yōu)化

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

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

一、最短路徑法

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

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

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

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

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

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

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

DEBACF11428741823任務(wù)3

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

之1：最短路徑法

最短路徑法示例2：

從V0到V6找出最短路徑？

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

之1：最短路徑法

最短路徑法計(jì)算3

任務(wù)3

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

之1：最短路徑法

最短路徑法計(jì)算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運(yùn)送到商場Q，圖1表示由起點(diǎn)P到終點(diǎn)Q的路線圖，各條弧所對應(yīng)的數(shù)字表示通過該段路線所需時(shí)間。試求所需時(shí)間最短路線。

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

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

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

某車一天的貨運(yùn)任務(wù)如下圖：求最佳行車路線。注：方框?yàn)楣┴淈c(diǎn)，橢圓為需求點(diǎn)。K=4噸A=2噸B=1噸C=1噸121116678解：分析：從供貨點(diǎn)到需求點(diǎn)再返回供貨點(diǎn)的線路共4條，距離計(jì)算如下：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分析各線路的貨運(yùn)周轉(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顯然，第一條線路的貨運(yùn)周轉(zhuǎn)量最小，故選擇第一條線路。任務(wù)3配送線路優(yōu)化方法

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

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

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

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

前提假設(shè)：當(dāng)從若干配送據(jù)點(diǎn)向眾多的客戶配送貨物時(shí)，各用戶的坐標(biāo)及需求量均為已知，配送中心有足夠的運(yùn)輸能力。利用節(jié)約法制定出的配送方案除了使配送里程最小外，還滿足以下條件，方案能滿足所有用戶的要求，不使任何一輛車超載；每輛車每天的總運(yùn)行時(shí)間或行駛里程不超過規(guī)定的上限，能滿足用戶到貨時(shí)間要求。二、節(jié)約法的基本原理假如由一家配送中心O向兩個(gè)用戶A、B送貨，配送中心到兩客戶的最短距離分別是a和b，A和B間的最短距離為x，AB的貨物需求量分別是Q1和Q2，且Q1+Q2小于車輛裝載量Q，如同7－1所示。圖7-1路線圖ＡＢO從倉庫O要運(yùn)送貨物給客戶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它從不為負(fù)。因?yàn)槿切蔚牡谌龡l邊總是小于其他兩條邊之和，因此，它最小為零。將客戶連接起來，增加了節(jié)約。客戶之間的距離越近，而且它們距離倉庫越遠(yuǎn)，那么節(jié)約就會越大。這個(gè)方法也可以用時(shí)間來代替距離計(jì)算。2314關(guān)于這個(gè)公式，注意：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

計(jì)算初始方案配送距離=?

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

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

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

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

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

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

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