模塊八---配送路線的規(guī)劃作業(yè)

1、模塊八模塊八 配送路線的規(guī)劃作業(yè)配送路線的規(guī)劃作業(yè) 知識目標知識目標 配送路線規(guī)劃的意義及原則 配送路線規(guī)劃的目標 影響配送路線規(guī)劃的因素影響配送路線規(guī)劃的因素 配送路線優(yōu)化的方法 第一節(jié)第一節(jié) 配送路線規(guī)劃的意義及原則配送路線規(guī)劃的意義及原則 近近年來年來,由于小批量由于小批量,多批次的及時配送方式的發(fā)展多批次的及時配送方式的發(fā)展,運輸費用正運輸費用正 在逐年提升在逐年提升,許多企業(yè)的運費已經(jīng)超越了庫存費用許多企業(yè)的運費已經(jīng)超越了庫存費用. 選擇有效的配選擇有效的配 送路線送路線,已成為控制物流成本的主要措施已成為控制物流成本的主要措施. 那么如何選擇有效的配那么如何選擇有效的配 送路線呢送

2、路線呢? 有有效的配送路線，實際上是在保證商品準時到達客戶指定點的前效的配送路線，實際上是在保證商品準時到達客戶指定點的前 提下，盡可能的減少運輸?shù)能嚧魏瓦\輸?shù)目偮烦烫嵯拢M可能的減少運輸?shù)能嚧魏瓦\輸?shù)目偮烦? 在這種思想的指在這種思想的指 導下，節(jié)約法已成為選擇配送路線的主要方法導下，節(jié)約法已成為選擇配送路線的主要方法,并受到國內外物流并受到國內外物流 界的青睞界的青睞. 通通常認為，配送是近距離，小批量，品種比較復雜，按用戶需要搭配品常認為，配送是近距離，小批量，品種比較復雜，按用戶需要搭配品 種與數(shù)量的服務體系。從配送中心把貨物送到所需要的各個用戶，有很種與數(shù)量的服務體系。從配送中心把貨

3、物送到所需要的各個用戶，有很 多不同的路線選擇方案。合理的選擇配送路線，對企業(yè)和社會具有很重多不同的路線選擇方案。合理的選擇配送路線，對企業(yè)和社會具有很重 要的意義：要的意義： 優(yōu)化配送路線，可以提高配送效率，對配送車輛做到優(yōu)化配送路線，可以提高配送效率，對配送車輛做到 物盡其用盡物盡其用盡 可能的降低配送成本可能的降低配送成本。 可以準時、快速地把貨物送到客戶的手中，能極大地可以準時、快速地把貨物送到客戶的手中，能極大地 提高提高 客戶滿意度?？蛻魸M意度。 有利于企業(yè)提高效益。有利于企業(yè)提高效益。 對社會而言對社會而言，它可以節(jié)省運輸車輛，緩解交通緊張狀況，減少噪音、尾，它可以節(jié)省運輸車輛，

4、緩解交通緊張狀況，減少噪音、尾 氣排放等運輸污染，為保護生態(tài)平衡、創(chuàng)造美好家園做出貢獻。氣排放等運輸污染，為保護生態(tài)平衡、創(chuàng)造美好家園做出貢獻。 進行配送路線優(yōu)化時，必須有明確的目，遵循基本的原則。配送 路線方案目標的選擇可以從以下幾個方面來考慮： 配送效益最高或配送成本最低配送效益最高或配送成本最低 配送里程最短配送里程最短 配送服務水準最優(yōu)配送服務水準最優(yōu) 配送勞動的消耗最小配送勞動的消耗最小 考考 慮慮 因因 素素 配送路線規(guī)劃的目標 以效益最高為目標以效益最高為目標 以成本最低為目標以成本最低為目標 以路程最短為目標以路程最短為目標 以噸千米最小為目標以噸千米最小為目標 以準確性最高為

5、目標以準確性最高為目標 以運力最合理為目標以運力最合理為目標 以勞動消耗最小為目標以勞動消耗最小為目標 影響配送路線規(guī)劃的因素影響配送路線規(guī)劃的因素 道道 路路 交交 通通 網(wǎng)網(wǎng) 配配 送送 中中 心心 位位 置置 客客 戶戶 分分 布布 狀狀 況況 車車 輛輛 運運 行行 限限 制制 車車 輛輛 額額 定定 載載 重重 量量 道道 路路 狀狀 況況 ； 如如 最最 大大 承承 載載 力力 車車車車 流輛流輛 量通量通 的行的行 變高變高 化潮化潮 ； 如如 上上 下下 班班 配送路線優(yōu)化的方法配送路線優(yōu)化的方法 標號法標號法 節(jié)約里程法節(jié)約里程法 優(yōu) 化 的 方 法 需求網(wǎng)絡中兩點需求網(wǎng)絡中

6、兩點 間最短線路的方法，間最短線路的方法， 叫做標號法叫做標號法 當由一個配送中心向多個客戶進行共當由一個配送中心向多個客戶進行共 同送貨，在同一條線路上的所有客戶同送貨，在同一條線路上的所有客戶 的需求量總和不大于一輛車的額定載的需求量總和不大于一輛車的額定載 重時有這一輛車配裝著所有客戶需求重時有這一輛車配裝著所有客戶需求 的貨物按照預先設計好的最佳路線一的貨物按照預先設計好的最佳路線一 次講貨物送給到客戶中。次講貨物送給到客戶中。 10 1 1、雙標號法、雙標號法 o最短路問題：對一個賦權的有向圖最短路問題：對一個賦權的有向圖D中的指定的兩個點中的指定的兩個點Vs和和Vt找到一找到一 條

7、從條從 Vs 到到 Vt 的路，使得這條路上所有弧的權數(shù)的總和最小，這條的路，使得這條路上所有弧的權數(shù)的總和最小，這條 路被稱之為從路被稱之為從Vs到到Vt的最短路。這條路上所有弧的權數(shù)的總和被稱為的最短路。這條路上所有弧的權數(shù)的總和被稱為 從從Vs到到Vt的距離。的距離。 一、求解最短路的一、求解最短路的Dijkstra算法算法(雙標號法）雙標號法） 步驟：步驟： 1.給出點給出點V1以標號以標號(0,s) 2.找出已標號的點的集合找出已標號的點的集合I，沒標號的點的集合，沒標號的點的集合J以及弧的集合以及弧的集合 3. 如果上述弧的集合是空集，則計算結束。如果如果上述弧的集合是空集，則計算

8、結束。如果vt已標號（已標號（lt,kt），則），則 vs到到vt的距離為的距離為lt，而從，而從 vs到到vt的最短路徑，則可以從的最短路徑，則可以從kt 反向追蹤反向追蹤 到起點到起點vs 而得到。如果而得到。如果vt 未標號，則可以斷言不存在從未標號，則可以斷言不存在從 vs到到vt的有的有 向路。如果上述的弧的集合不是空集，則轉下一步。向路。如果上述的弧的集合不是空集，則轉下一步。 4. 對上述弧的集合中的每一條弧，計算對上述弧的集合中的每一條弧，計算 sij=li+cij 。在所有的。在所有的 sij中，找中，找 到其值為最小的弧。不妨設此弧為（到其值為最小的弧。不妨設此弧為（Vc,

9、Vd），則給此弧的終點以雙），則給此弧的終點以雙 標號（標號（scd,c）,返回步驟返回步驟2。 ( ,)|, ijij v vvI vJ 1,6 圖上標號法圖上標號法: v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,1 1, 1, 1, 1,3 1,6 圖上標號法圖上標號法: v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 1, 1,1 1, 1, 1, 1,3 1,6v5 v2 2 3 4 6 4 v3 v1 v

10、4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 圖上標號法圖上標號法: 1,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 1,6 圖上標號法圖上標號法: 1,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1, 1,3 3,5 圖上標號法圖上標號法: 3,5v5 v2

11、2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1,3 1, 圖上標號法圖上標號法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 1, 4,11 1,1 1, 1, 1,3 1, 圖上標號法圖上標號法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, 2,6 1, 1,3 1, 圖上標號法圖上標號法:

12、 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 4,11 1,1 1, 2,6 1, 1,3 1, 圖上標號法圖上標號法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 1, 2,6 5,12 1,3 5,9 圖上標號法圖上標號法: 3,5v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10v8 v9 v7 2 3 6 3 v6 0,0 5,10 1,1 1, 2,6 5,12 1

13、,3 5,9 圖上標號法圖上標號法: 22 例例1 求下圖中求下圖中v1到到v6的最短路的最短路 解：采用解：采用Dijkstra算法，可解得最短路徑為算法，可解得最短路徑為v1 v3 v4 v6 各點的標號圖如下：各點的標號圖如下： v2 3 5 2 7 5 3 1 5 12 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 12 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 2、節(jié)約里程算法基本原理、節(jié)約里程算法基本原理 o 基本原理是幾何學中三角形一邊之長必定小 于另外兩邊之和。 o 節(jié)約里程法核心思想是依次將運輸問題中的

14、兩個回路合并為一個回路，每次使合并后的 總運輸距離減小的幅度最大，直到達到一輛 車的裝載限制時，再進行下一輛車的優(yōu)化。 優(yōu)化過程分為并行方式和串行方式兩種。 o 假如一家配送中心（DC）向兩個用戶A、B運 貨，配送中心到兩用戶的最短距離分別是La 和Lb，A和B間的最短距離為Lab，A、B的貨 物需求量分別是Qa和Qb，且（Qa+Qb）小于 運輸裝載量Q，如圖所示，如果配送中心分別 送貨，那么需要兩個車次，總路程為：L1=2 （La+Lb）。 AB DC La Lb AB DC La Lb Lab 如果改用一輛車對兩客戶進行巡回送貨，則只需一個車 次,行走的總路程為： L2=La+Lb+Lab

15、 有三角形的性質我們知道： Lab（La+Lb） 所以第二次的配送方案明顯優(yōu)于第一種，且行走總路程 節(jié)約： L=（La+Lb）Lab 如果配送中心的供貨范圍內還存在著：3,4,5，n個 用戶，在運載車輛載重和體積都允許的情況下，可將它 們按著節(jié)約路程的大小依次連入巡回線路，直至滿載為 止，余下的用戶可用同樣方法確定巡回路線，另外派車。 例題：例題：由配送中心由配送中心P P向向AIAI等等9 9個用戶配送貨物。個用戶配送貨物。 圖中連線上的數(shù)字表示公路里程（圖中連線上的數(shù)字表示公路里程（kmkm）。靠）。靠 近各用戶括號內的數(shù)字，表示各用戶對貨物近各用戶括號內的數(shù)字，表示各用戶對貨物 的需求量

16、（的需求量（t t）。配送中心備有）。配送中心備有2t2t和和4t4t載重量載重量 的汽車，且汽車一次巡回走行里程不能超過的汽車，且汽車一次巡回走行里程不能超過 35km35km，設送到時間均符合用戶要求，求該配，設送到時間均符合用戶要求，求該配 送中心的最優(yōu)送貨方案。送中心的最優(yōu)送貨方案。 A B C D E F G H I P (0.9) (1.2) (1.6) (1.1) (0.9) (0.9) (0.6) (1.7) (0.5) 4 4 4 5 5 5 5 5 6 6 6 3 7 7 7 8 9 10 10 11 12 14 o計算配送中心至各用戶以及各用戶之 間的最短距離，列表得最短

17、距離表： P A B C D E F G H I P A B C D E F G H I 11 10 9 6 7 10 10 8 7 5 10 14 18 21 21 13 6 5 9 15 20 20 18 11 4 10 19 19 17 16 6 15 16 14 13 9 17 15 14 14 18 17 12 17 7 由最短距離表，利用節(jié)約法計算出各用由最短距離表，利用節(jié)約法計算出各用 戶之間的節(jié)約里程，編制節(jié)約里程表：戶之間的節(jié)約里程，編制節(jié)約里程表： AB:LA+LBLAB=11+10-5=16 AC:LA+LCLAC=11+9-10=10 AD:LA+LDLAD=11+6-

18、14=3 AE:LA+LELAE=11+7-18=0 AF:LA+LFLAF=11+10-21=0 AG:LA+LGLAG=11+10-21=0 A B C D E F G H I A B C D E F G H I 16 10 3 0 0 0 6 12 14 7 2 0 0 0 6 11 6 0 0 0 0 7 1 0 0 0 8 0 0 0 6 0 0 6 0 8 節(jié)約里程表 根據(jù)節(jié)約里程表中節(jié)約里程多少的順根據(jù)節(jié)約里程表中節(jié)約里程多少的順 序，由大到小排列，編制節(jié)約里程順序，由大到小排列，編制節(jié)約里程順 序表，以便盡量使節(jié)約里程最多的點序表，以便盡量使節(jié)約里程最多的點 組合裝車配送。組合

19、裝車配送。 順位 號 里程節(jié)約里 程 順位 號 里程節(jié)約里 程 順位 號 里程節(jié)約里 程 1A-B166H-I810F-G6 2B-C148B-D710G-H6 3A-I128D-E715A-D3 4C-D1110A-H616B-E2 5A-C1010B-I617D-F1 6E-F810C-E6 根據(jù)節(jié)約里程排序表和配車（車輛的載重和容積因素）、根據(jù)節(jié)約里程排序表和配車（車輛的載重和容積因素）、 車輛行駛里程等約束條件，漸進繪出配送路徑：車輛行駛里程等約束條件，漸進繪出配送路徑： A A B B C C D D E E F F G G H H I I P P (0.9)(0.9) (1.2)(

20、1.2) (1.6)(1.6) (1.1)(1.1) (0.9)(0.9) (0.9)(0.9) (0.6)(0.6) (1.7)(1.7) (0.5)(0.5) 4 4 7 5 5 5 5 8 8 6 6 6 6 6 6 9 9 1010 1010 1212 路徑路徑A 路徑路徑B 路徑路徑C o路徑A：4t車，走行32km，載重量 3.7t； o路徑B：4t車，走行31km，載重量 3.9t； o路徑C：2t車，走行30km，載重量 1.8t。 總共走行里程93km，共節(jié)約里程 （16+14+12）+（8+7） +6=63km。 優(yōu)缺點分析 優(yōu)點： 節(jié)約法是一種簡便、易行的方法，一方面體現(xiàn)

21、出優(yōu)化節(jié)約法是一種簡便、易行的方法，一方面體現(xiàn)出優(yōu)化 運輸過程，與一般方法相比縮短了運輸路程；另一方面，運輸過程，與一般方法相比縮短了運輸路程；另一方面， 它也體現(xiàn)了物流配送網(wǎng)絡的優(yōu)勢，實現(xiàn)了企業(yè)物流活動它也體現(xiàn)了物流配送網(wǎng)絡的優(yōu)勢，實現(xiàn)了企業(yè)物流活動 的整合，而且思路簡單清晰、便于執(zhí)行。的整合，而且思路簡單清晰、便于執(zhí)行。 缺點： 第一，利用節(jié)約法選擇配送路線過于強調節(jié)約路程，第一，利用節(jié)約法選擇配送路線過于強調節(jié)約路程， 而沒考慮行程中的時間因素，在許多情況下，時間更能而沒考慮行程中的時間因素，在許多情況下，時間更能 決定物流配送的成本與服務質量。例如城市間配送時對決定物流配送的成本與服務

22、質量。例如城市間配送時對 高速公路的選擇，城市內部上下班時間的道路擁擠，一高速公路的選擇，城市內部上下班時間的道路擁擠，一 個巡回配送過程中的時間長短，直接影響配送人員的精個巡回配送過程中的時間長短，直接影響配送人員的精 神狀態(tài)，而人員的精神狀態(tài)又與交通事故和配送錯誤相神狀態(tài)，而人員的精神狀態(tài)又與交通事故和配送錯誤相 連等，所以時間對配送路線的選擇有時更重要。連等，所以時間對配送路線的選擇有時更重要。 第二，利用節(jié)約法選擇配送路線不能對客戶的需求進行第二，利用節(jié)約法選擇配送路線不能對客戶的需求進行 靈活多變的處理。由于現(xiàn)代的消費者的需求傾向于個性靈活多變的處理。由于現(xiàn)代的消費者的需求傾向于個性

23、 化，引起企業(yè)的生產(chǎn)、銷售和配送也愈來愈傾向于小批化，引起企業(yè)的生產(chǎn)、銷售和配送也愈來愈傾向于小批 量，多品種，多批次。而節(jié)約法更適合需求穩(wěn)定或是需量，多品種，多批次。而節(jié)約法更適合需求穩(wěn)定或是需 求的時間不緊迫，這顯然不能滿足現(xiàn)代多變得市場環(huán)境。求的時間不緊迫，這顯然不能滿足現(xiàn)代多變得市場環(huán)境。 最后值得一提的是，節(jié)約法計算的配送路線 并不是總路程最短。 原因是節(jié)約法一方面要 縮短總路程,另一方面又要充分利用車輛的運 輸空間(載重 / 容積) ，減少配送車次，而 且只要在前一條預設路線上運行的配送車輛 的運輸空間允許，就必須按著節(jié)約路程的大 小順序進行選擇而不考慮其它的預設路線， 在事實情況下選擇的路線并不能“節(jié)約”路 程和有效利用運輸空間，而且運輸?shù)能嚧我?不一