第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ù)用戶的要求，在物流據(jù)點(diǎn)（中心）進(jìn)行分貨、是指根據(jù)用戶的要求，在物流據(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、配送以用戶要求為出發(fā)點(diǎn)、配送以用戶要求為出發(fā)點(diǎn) 5、以最合適的方式、以最合適的方式 8.1 物流配送概述物流配送概述 發(fā)達(dá)國家：發(fā)達(dá)國家： 一般送貨一般送貨 戰(zhàn)略配送：戰(zhàn)略配送： （促銷手段）（促銷手段） 配送共同化、配送計(jì)劃化、配送共同化、配送計(jì)劃化、 配送區(qū)域擴(kuò)大、直達(dá)配送、配送區(qū)域擴(kuò)大、直達(dá)配送、 計(jì)算機(jī)管理、自動化、計(jì)算機(jī)管理、自動化、 配送方式多樣化、配送集約化配送方式多樣化、配送集約化 我國：我國： 60年代：貨郎擔(dān)、背簍商店年代：貨郎擔(dān)、背簍商店 70年代：送貨上門年代：送貨上門 80年代：在理論上探索配送（三次革命）年代：在理論上探索配送（三次革命） 8.1.2 配送的發(fā)展

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

4、品種、大批量配送。 2多品種、少批量、多批次配送。多品種、少批量、多批次配送。 3設(shè)備成套、配套配送。設(shè)備成套、配套配送。 （二）按配送的組織形式不同分類（二）按配送的組織形式不同分類 共同配送。共同配送。 分散配送。分散配送。 8.2 物流配送路線的優(yōu)化設(shè)計(jì)物流配送路線的優(yōu)化設(shè)計(jì) 共同配送共同配送是由幾個(gè)物流據(jù)是由幾個(gè)物流據(jù) 點(diǎn)共同協(xié)作制定的計(jì)劃，共點(diǎn)共同協(xié)作制定的計(jì)劃，共 同組織車輛設(shè)備，對某一地同組織車輛設(shè)備，對某一地 區(qū)的用戶進(jìn)行配送。區(qū)的用戶進(jìn)行配送。 （三）按配送的時(shí)間和數(shù)量不同分類（三）按配送的時(shí)間和數(shù)量不同分類 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ì)地地 將客戶所需的商品準(zhǔn)確地送達(dá)客戶手中。將客戶所需的商品準(zhǔn)確地送達(dá)客戶手中。 在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶在配送運(yùn)輸線路設(shè)計(jì)中，需根據(jù)不同客戶 群的特點(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、由配送中心向每一位客戶開展專門送貨；、由配送中心向每一位客戶開展專門送貨； 2 2、該客戶的送貨量一般必須滿足配送車輛滿載。、該客戶的送貨量一般必須滿足配送車輛滿載。 配送效果：配送效果： 1.1.配送車輛滿載運(yùn)輸；配送車輛滿載運(yùn)輸； 2.2.配送運(yùn)輸路線距離最短。配送運(yùn)輸路線距離最短。 適用方法適用方法 適用條件：適用條件： 1 1、由配送中心向多位客戶開展拼裝送貨；、由配送中心向多位客戶開展拼裝送

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

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

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

10、分類。第四步：將節(jié)約里程按大小順序排列分類。 第五步：按節(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ò)如下圖所示。 圖中括號內(nèi)的數(shù)字表示每一家連鎖店的需圖中括號內(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車輛車輛 可供使用，并且每輛車配送距離不得超過可供使用，并且每輛車配送距離不得超過 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的配送車輛（每家連鎖店的的配送車輛（每家連鎖店的 需要量都低于需要量都低于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ì)算過程節(jié)約里程計(jì)算過程 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 序號序號連接點(diǎn)連接點(diǎn) 節(jié)約里程節(jié)約里程序號序號連接點(diǎn)連接點(diǎn)節(jié)約里程節(jié)約里程 修正結(jié)果：運(yùn)距修正結(jié)果：運(yùn)距109km109km，車輛，車輛4t14t

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

16、心備有2t2t和和4t4t載質(zhì)量的汽車，且汽車一次巡回行駛里程載質(zhì)量的汽車，且汽車一次巡回行駛里程 不能超過不能超過30km30km。求解該配送中心滿意的送貨方案。求解該配送中心滿意的送貨方案。 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- - 序號序號路程路程節(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ù)額排序表 從上圖中可以看出，依次確定的從上圖中可以看出，