第8章物流配送路線優(yōu)化

1、8.1 8.1 物流配送概述物流配送概述 8.2 8.2 物流配送路線的優(yōu)化設(shè)計(jì)物流配送路線的優(yōu)化設(shè)計(jì) 第八章第八章 物流配送路線優(yōu)化設(shè)計(jì)物流配送路線優(yōu)化設(shè)計(jì) 8.1.1配送的概念配送的概念 是指根據(jù)用戶(hù)的要求，在物流據(jù)點(diǎn)（中心）進(jìn)行分貨、是指根據(jù)用戶(hù)的要求，在物流據(jù)點(diǎn)（中心）進(jìn)行分貨、 配貨工作，并將配好的貨以最合適的方式送交收貨人。配貨工作，并將配好的貨以最合適的方式送交收貨人。 包包 含含5點(diǎn)：點(diǎn)： 1、配送的實(shí)質(zhì)、配送的實(shí)質(zhì) ：送貨（：送貨（ Delivery） 2、配送是一種中轉(zhuǎn)形式，是特殊的送貨、配送是一種中轉(zhuǎn)形式，是特殊的送貨 3、配送是配和送的有機(jī)結(jié)合、配送是配和送的有機(jī)結(jié)合

2、4、配送以用戶(hù)要求為出發(fā)點(diǎn)、配送以用戶(hù)要求為出發(fā)點(diǎn) 5、以最合適的方式、以最合適的方式 8.1 物流配送概述物流配送概述 發(fā)達(dá)國(guó)家：發(fā)達(dá)國(guó)家： 一般送貨一般送貨 戰(zhàn)略配送：戰(zhàn)略配送： （促銷(xiāo)手段）（促銷(xiāo)手段） 配送共同化、配送計(jì)劃化、配送共同化、配送計(jì)劃化、 配送區(qū)域擴(kuò)大、直達(dá)配送、配送區(qū)域擴(kuò)大、直達(dá)配送、 計(jì)算機(jī)管理、自動(dòng)化、計(jì)算機(jī)管理、自動(dòng)化、 配送方式多樣化、配送集約化配送方式多樣化、配送集約化 我國(guó)：我國(guó)： 60年代：貨郎擔(dān)、背簍商店年代：貨郎擔(dān)、背簍商店 70年代：送貨上門(mén)年代：送貨上門(mén) 80年代：在理論上探索配送（三次革命）年代：在理論上探索配送（三次革命） 8.1.2 配送的發(fā)展

3、配送的發(fā)展 8.1.3 配送在現(xiàn)代物流中的作用配送在現(xiàn)代物流中的作用 （一）有利于提高物流的經(jīng)濟(jì)效益（一）有利于提高物流的經(jīng)濟(jì)效益 （二）使企業(yè)實(shí)現(xiàn)零庫(kù)存成為可能（二）使企業(yè)實(shí)現(xiàn)零庫(kù)存成為可能 （三）有利于促進(jìn)物流的社會(huì)化（三）有利于促進(jìn)物流的社會(huì)化 （四）改善生產(chǎn)企業(yè)的外部環(huán)境，提高物資供應(yīng)的保證（四）改善生產(chǎn)企業(yè)的外部環(huán)境，提高物資供應(yīng)的保證 程度。程度。 （五）有利于完善運(yùn)輸過(guò)程，提高運(yùn)輸?shù)慕?jīng)濟(jì)效益（五）有利于完善運(yùn)輸過(guò)程，提高運(yùn)輸?shù)慕?jīng)濟(jì)效益 8.2.1配送形式的選擇配送形式的選擇 （一）按配送物資的種類(lèi)和數(shù)量分類(lèi)（一）按配送物資的種類(lèi)和數(shù)量分類(lèi) 1少品種或單品種、大批量配送。少品種或單

4、品種、大批量配送。 2多品種、少批量、多批次配送。多品種、少批量、多批次配送。 3設(shè)備成套、配套配送。設(shè)備成套、配套配送。 （二）按配送的組織形式不同分類(lèi)（二）按配送的組織形式不同分類(lèi) 共同配送。共同配送。 分散配送。分散配送。 8.2 物流配送路線的優(yōu)化設(shè)計(jì)物流配送路線的優(yōu)化設(shè)計(jì) 共同配送共同配送是由幾個(gè)物流據(jù)是由幾個(gè)物流據(jù) 點(diǎn)共同協(xié)作制定的計(jì)劃，共點(diǎn)共同協(xié)作制定的計(jì)劃，共 同組織車(chē)輛設(shè)備，對(duì)某一地同組織車(chē)輛設(shè)備，對(duì)某一地 區(qū)的用戶(hù)進(jìn)行配送。區(qū)的用戶(hù)進(jìn)行配送。 （三）按配送的時(shí)間和數(shù)量不同分類(lèi)（三）按配送的時(shí)間和數(shù)量不同分類(lèi) 1定量配送。定量配送。 2定時(shí)配送。定時(shí)配送。 3定時(shí)定量配送。定

5、時(shí)定量配送。 4定時(shí)定量定點(diǎn)配送。定時(shí)定量定點(diǎn)配送。 5即時(shí)配送。即時(shí)配送。 8.2.2配送線路的優(yōu)化配送線路的優(yōu)化 （二）分送式配送：節(jié)約里程法（二）分送式配送：節(jié)約里程法 配送線路設(shè)計(jì)就是整合影響配送運(yùn)輸?shù)母髋渌途€路設(shè)計(jì)就是整合影響配送運(yùn)輸?shù)母?種因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具種因素，適時(shí)適當(dāng)?shù)乩矛F(xiàn)有的運(yùn)輸工具 和道路狀況，和道路狀況，及時(shí)、安全、方便、經(jīng)濟(jì)及時(shí)、安全、方便、經(jīng)濟(jì)地地 將客戶(hù)所需的商品準(zhǔn)確地送達(dá)客戶(hù)手中。將客戶(hù)所需的商品準(zhǔn)確地送達(dá)客戶(hù)手中。 在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶(hù)在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶(hù) 群的特點(diǎn)和要求，選擇不同的線路設(shè)計(jì)方群的特點(diǎn)和要求，選

6、擇不同的線路設(shè)計(jì)方 法，最終達(dá)到法，最終達(dá)到節(jié)省時(shí)間、運(yùn)距節(jié)省時(shí)間、運(yùn)距和和降低配送降低配送 運(yùn)輸成本運(yùn)輸成本的目的。的目的。 適用方法適用方法最短路徑法最短路徑法 適用條件：適用條件： 1 1、由配送中心向每一位客戶(hù)開(kāi)展專(zhuān)門(mén)送貨；、由配送中心向每一位客戶(hù)開(kāi)展專(zhuān)門(mén)送貨； 2 2、該客戶(hù)的送貨量一般必須滿(mǎn)足配送車(chē)輛滿(mǎn)載。、該客戶(hù)的送貨量一般必須滿(mǎn)足配送車(chē)輛滿(mǎn)載。 配送效果：配送效果： 1.1.配送車(chē)輛滿(mǎn)載運(yùn)輸；配送車(chē)輛滿(mǎn)載運(yùn)輸； 2.2.配送運(yùn)輸路線距離最短。配送運(yùn)輸路線距離最短。 適用方法適用方法 適用條件：適用條件： 1 1、由配送中心向多位客戶(hù)開(kāi)展拼裝送貨；、由配送中心向多位客戶(hù)開(kāi)展拼裝送

7、貨； 2 2、每位客戶(hù)的送貨量都不能滿(mǎn)足配送車(chē)輛、每位客戶(hù)的送貨量都不能滿(mǎn)足配送車(chē)輛 滿(mǎn)載。滿(mǎn)載。 配送效果：配送效果： 1.1.配送車(chē)輛滿(mǎn)載運(yùn)輸；配送車(chē)輛滿(mǎn)載運(yùn)輸； 2.2.配送運(yùn)輸路線距離最短。配送運(yùn)輸路線距離最短。 送貨時(shí)，由一輛車(chē)裝載所有客戶(hù)的貨送貨時(shí)，由一輛車(chē)裝載所有客戶(hù)的貨 物，沿著一條精心設(shè)計(jì)的最佳路線依次將物，沿著一條精心設(shè)計(jì)的最佳路線依次將 貨物送到各位客戶(hù)手中，這樣既保證按時(shí)貨物送到各位客戶(hù)手中，這樣既保證按時(shí) 按量將用戶(hù)需要的貨物及時(shí)送達(dá)，又節(jié)約按量將用戶(hù)需要的貨物及時(shí)送達(dá)，又節(jié)約 了車(chē)輛，節(jié)省了費(fèi)用，緩解了交通緊張的了車(chē)輛，節(jié)省了費(fèi)用，緩解了交通緊張的 壓力，并減少了運(yùn)

8、輸對(duì)環(huán)境造成的污染。壓力，并減少了運(yùn)輸對(duì)環(huán)境造成的污染。 1.節(jié)約里程法確定配送路徑的基本原理 n尋求配送方案的常用的方法很 多，這里介紹車(chē)輛運(yùn)行計(jì)劃法 。車(chē)輛運(yùn)行計(jì)劃法(VSP， Vehicles Scheduling Program)又稱(chēng)里程節(jié)約法（ VSP方法）。 n適用于實(shí)際工作中為求得較優(yōu) 解或最優(yōu)的近似解時(shí)采用。 n它的基本原理是三角形的一邊 之長(zhǎng)必定小于另外兩邊之和。 如圖所示。 12 2 () T LLL 123T LLLL 12123123 2 ()() T LLLLLLLLL n為實(shí)現(xiàn)配送所節(jié)約里程?？筛鶕?jù)用戶(hù)要求、道路條件等設(shè)計(jì)幾種巡回 配送方案，再計(jì)算節(jié)約里程，以其中節(jié)

9、約里程最大者為優(yōu)選的配送方 案。VSP方法可對(duì)所有配送地點(diǎn)計(jì)算其節(jié)約里程，按節(jié)約量的大小順序， 優(yōu)選確定配送路線。 原 現(xiàn) 14 2. 按節(jié)約里程法制定配送計(jì)劃的步驟按節(jié)約里程法制定配送計(jì)劃的步驟 第一步：選擇初始方案：從第一步：選擇初始方案：從Q點(diǎn)向各點(diǎn)分別派車(chē)送貨。點(diǎn)向各點(diǎn)分別派車(chē)送貨。 第二步：作出最短距離矩陣，從配送網(wǎng)絡(luò)圖中列出配送第二步：作出最短距離矩陣，從配送網(wǎng)絡(luò)圖中列出配送 中心至用戶(hù)及用戶(hù)相互間的最短距離矩陣中心至用戶(hù)及用戶(hù)相互間的最短距離矩陣 。 第三步：從最短矩陣中，計(jì)算用戶(hù)相互間的節(jié)約里程。第三步：從最短矩陣中，計(jì)算用戶(hù)相互間的節(jié)約里程。 第四步：將節(jié)約里程按大小順序排列

10、分類(lèi)。第四步：將節(jié)約里程按大小順序排列分類(lèi)。 第五步：按節(jié)約里程大小順序，組成配送線路。第五步：按節(jié)約里程大小順序，組成配送線路。 第六步：按上述方法，逐次選代，優(yōu)化配送線路第六步：按上述方法，逐次選代，優(yōu)化配送線路 。 位于牡丹江市內(nèi)的百家姓配送中心（位于牡丹江市內(nèi)的百家姓配送中心（P P0 0）向）向 它旗下的它旗下的1010家連鎖商店家連鎖商店p pi i(i=1,2,(i=1,2,10),10)配配 送商品，其配送網(wǎng)絡(luò)如下圖所示。送商品，其配送網(wǎng)絡(luò)如下圖所示。 圖中括號(hào)內(nèi)的數(shù)字表示每一家連鎖店的需圖中括號(hào)內(nèi)的數(shù)字表示每一家連鎖店的需 求量（求量（t t），），線路上的數(shù)字表示兩節(jié)點(diǎn)之間

11、線路上的數(shù)字表示兩節(jié)點(diǎn)之間 的距離（的距離（kmkm）。配送中心現(xiàn)有）。配送中心現(xiàn)有2 2t t和和4 4t t車(chē)輛車(chē)輛 可供使用，并且每輛車(chē)配送距離不得超過(guò)可供使用，并且每輛車(chē)配送距離不得超過(guò) 30km30km。 配送網(wǎng)絡(luò)圖配送網(wǎng)絡(luò)圖 P 0 9 e 1. 4 8 6 1 0 7 6 f 1. 5 8 g 0. 6 3 2 9 h 0. 8 4 i 0. 5 1 0 j 0. 6 7 a 0. 7 1 0 b 1. 5 9 c 0. 8 7 d 0. 4 8 55 4 4 1 1 8 配送網(wǎng)絡(luò)圖配送網(wǎng)絡(luò)圖 P 0 e 1. 4 8 f 1. 5 8 g 0. 6 3 h 0. 8 4 i 0

12、. 5 1 0 j 0. 6 7 a 0. 7 1 0 b 1. 5 9 c 0. 8 7 d 0. 4 8 初始方案運(yùn)行結(jié)果：初始方案運(yùn)行結(jié)果： 1 1、從百家姓配送中心出發(fā)，需要設(shè)計(jì)、從百家姓配送中心出發(fā)，需要設(shè)計(jì)1010條條 配送線路，分別向配送線路，分別向1010家連鎖店配送商品；家連鎖店配送商品； 2 2、需要、需要1010輛輛2t2t的配送車(chē)輛（每家連鎖店的的配送車(chē)輛（每家連鎖店的 需要量都低于需要量都低于2t2t），總配送距離為），總配送距離為148km148km。 P 10 94 795 814105 8181496 8181715137 313121011106 414131

13、112 1282 10111517181817119 a b c d e f g h i j7481315151510118 a b c d e f g h i j 15 811 4710 03610 00039 000015 0000045 94000125 a b c d e f g h i P b c d e f g h i j1381000009 節(jié)約里程計(jì)算過(guò)程節(jié)約里程計(jì)算過(guò)程 1 1a ab b1515 2 2a aj j1313 3 3b bc c1111 1313f fg g5 5 1313g gh h5 5 1313h hi i5 5 1616a ad d4 4 1616b

14、bi i4 4 1616f fh h4 4 4 4c cd d1010 4 4d de e1010 6 6a ai i9 9 6 6e ef f9 9 6 6i ij j9 9 9 9a ac c8 8 9 9b bj j8 8 1111b bd d7 7 1212c ce e6 6 2121g gi i2 2 1919b be e3 3 1919d df f3 3 2222c cj j1 1 2222e eg g1 1 2222f fi i1 1 序號(hào)序號(hào)連接點(diǎn)連接點(diǎn) 節(jié)約里程節(jié)約里程序號(hào)序號(hào)連接點(diǎn)連接點(diǎn)節(jié)約里程節(jié)約里程 修正結(jié)果：運(yùn)距修正結(jié)果：運(yùn)距109km109km，車(chē)輛，車(chē)輛4t14t

15、1輛，輛，2t62t6輛輛 ） 修正結(jié)果：運(yùn)距修正結(jié)果：運(yùn)距85km85km，車(chē)輛，車(chē)輛4t24t2輛，輛，2t22t2輛輛 ） 修正結(jié)果：運(yùn)距修正結(jié)果：運(yùn)距80km80km，車(chē)輛，車(chē)輛4t24t2輛，輛，2t12t1輛輛 ） 如下圖所示某配送中心的配送網(wǎng)絡(luò)圖。由配送中心如下圖所示某配送中心的配送網(wǎng)絡(luò)圖。由配送中心P P向向A A、B B、C C、 D D、E5E5個(gè)用戶(hù)配送物品。圖中連線上的數(shù)字表示運(yùn)距（個(gè)用戶(hù)配送物品。圖中連線上的數(shù)字表示運(yùn)距（kmkm）。）。 圖中靠近各用戶(hù)括號(hào)里的數(shù)字，表示對(duì)貨物的需求量（圖中靠近各用戶(hù)括號(hào)里的數(shù)字，表示對(duì)貨物的需求量（t t）。）。 配送中心備有配送中

16、心備有2t2t和和4t4t載質(zhì)量的汽車(chē)，且汽車(chē)一次巡回行駛里程載質(zhì)量的汽車(chē)，且汽車(chē)一次巡回行駛里程 不能超過(guò)不能超過(guò)30km30km。求解該配送中心滿(mǎn)意的送貨方案。求解該配送中心滿(mǎn)意的送貨方案。 P PA AB BC CD DE E P P- -8 83 310108 87 7 A A- -8 8171715159 9 B B- -9 911111010 C C- -7 71313 D D- -6 6 E E- - - -A AB BC CD DE E A A- -3 31 11 16 6 B B- -4 40 00 0 C C- -11114 4 D D- -9 9 E E- - 序號(hào)序號(hào)路程路程節(jié)約數(shù)額節(jié)約數(shù)額 1 1C-DC-D1111 2 2D-ED-E9 9 3 3A-EA-E6 6 4 4B-CB-C4 4 5 5C-EC-E4 4 6 6A-BA-B3 3 7 7A-CA-C1 1 8 8A-DA-D1 1 表表3 3：節(jié)約里程數(shù)額排序表：節(jié)約里程數(shù)額排序表 從上圖中可以看出，依次確定的從上圖中可以看出，