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

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

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

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

4、尾氣排放等運(yùn)輸污染，為保護(hù)生態(tài)平衡、創(chuàng)造美好家園做出貢獻(xiàn)。氣排放等運(yùn)輸污染，為保護(hù)生態(tài)平衡、創(chuàng)造美好家園做出貢獻(xiàn)。 進(jìn)行配送路線優(yōu)化時(shí)，必須有明確的目，遵循基本的原則。配送路線方案目標(biāo)的選擇可以從以下幾個(gè)方面來考慮： 配送效益最高或配送成本最低配送效益最高或配送成本最低 配送里程最短配送里程最短 配送服務(wù)水準(zhǔn)最優(yōu)配送服務(wù)水準(zhǔn)最優(yōu) 配送勞動(dòng)的消耗最小配送勞動(dòng)的消耗最小 考考慮慮因因素素配送路線規(guī)劃的目標(biāo) 以效益最高為目標(biāo)以效益最高為目標(biāo)以成本最低為目標(biāo)以成本最低為目標(biāo)以路程最短為目標(biāo)以路程最短為目標(biāo) 以噸千米最小為目標(biāo)以噸千米最小為目標(biāo) 以準(zhǔn)確性最高為目標(biāo)以準(zhǔn)確性最高為目標(biāo) 以運(yùn)力最合理為目標(biāo)以

5、運(yùn)力最合理為目標(biāo) 以勞動(dòng)消耗最小為目標(biāo)以勞動(dòng)消耗最小為目標(biāo) 影響配送路線規(guī)劃的因素影響配送路線規(guī)劃的因素 道道路路交交通通網(wǎng)網(wǎng)配配送送中中心心位位置置客客戶戶分分布布狀狀況況車車輛輛運(yùn)運(yùn)行行限限制制車車輛輛額額定定載載重重量量道道路路狀狀況況；如如最最大大承承載載力力車車車車流輛流輛量通量通的行的行變高變高化潮化潮； 如如 上上 下下 班班 配送路線優(yōu)化的方法配送路線優(yōu)化的方法 標(biāo)號法標(biāo)號法 節(jié)約里程法節(jié)約里程法優(yōu)化的方法 需求網(wǎng)絡(luò)中兩點(diǎn)需求網(wǎng)絡(luò)中兩點(diǎn)間最短線路的方法，間最短線路的方法，叫做標(biāo)號法叫做標(biāo)號法當(dāng)由一個(gè)配送中心向多個(gè)客戶進(jìn)行共當(dāng)由一個(gè)配送中心向多個(gè)客戶進(jìn)行共同送貨，在同一條線路上的

6、所有客戶同送貨，在同一條線路上的所有客戶的需求量總和不大于一輛車的額定載的需求量總和不大于一輛車的額定載重時(shí)有這一輛車配裝著所有客戶需求重時(shí)有這一輛車配裝著所有客戶需求的貨物按照預(yù)先設(shè)計(jì)好的最佳路線一的貨物按照預(yù)先設(shè)計(jì)好的最佳路線一次講貨物送給到客戶中。次講貨物送給到客戶中。101 1、雙標(biāo)號法、雙標(biāo)號法o最短路問題：對一個(gè)賦權(quán)的有向圖最短路問題：對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)中的指定的兩個(gè)點(diǎn)Vs和和Vt找到一找到一條從條從 Vs 到到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從路被稱之為從Vs到到Vt的最短路。這條路上

7、所有弧的權(quán)數(shù)的總和被稱為的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從從Vs到到Vt的距離。的距離。一、求解最短路的一、求解最短路的Dijkstra算法算法(雙標(biāo)號法）雙標(biāo)號法）步驟：步驟：1.給出點(diǎn)給出點(diǎn)V1以標(biāo)號以標(biāo)號(0,s)2.找出已標(biāo)號的點(diǎn)的集合找出已標(biāo)號的點(diǎn)的集合I，沒標(biāo)號的點(diǎn)的集合，沒標(biāo)號的點(diǎn)的集合J以及弧的集合以及弧的集合3. 如果上述弧的集合是空集，則計(jì)算結(jié)束。如果如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號（已標(biāo)號（lt,kt），則），則 vs到到vt的距離為的距離為lt，而從，而從 vs到到vt的最短路徑，則可以從的最短路徑，則可以從kt 反向追蹤反向追蹤到起點(diǎn)到起點(diǎn)

8、vs 而得到。如果而得到。如果vt 未標(biāo)號，則可以斷言不存在從未標(biāo)號，則可以斷言不存在從 vs到到vt的有的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4. 對上述弧的集合中的每一條弧，計(jì)算對上述弧的集合中的每一條弧，計(jì)算 sij=li+cij 。在所有的。在所有的 sij中，找中，找到其值為最小的弧。不妨設(shè)此弧為（到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙），則給此弧的終點(diǎn)以雙標(biāo)號（標(biāo)號（scd,c）,返回步驟返回步驟2。( ,)|,ijijv vvI vJ1,6圖上標(biāo)號法圖上標(biāo)號法:v5v223464v3v1v4121

9、0 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6圖上標(biāo)號法圖上標(biāo)號法:v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 1, 1,11, 1, 1, 1,31,6v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,3圖上標(biāo)號法圖上標(biāo)號法:1,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,31,6圖上標(biāo)號法圖上標(biāo)號法:1,5v5v223464v3v1v41210

10、6 1210v8v9v72363v60,01, 4,111,11, 1, 1, 1,33,5圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,01, 4,111,11, 1, 1,31, 圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v

11、3v1v41210 6 1210v8v9v72363v60,04,111,11, 2,61, 1,31,圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,9圖上標(biāo)號法圖上標(biāo)號法:3,5v5v223464v3v1v41210 6 1210v8v9v72363v60,05,101,11, 2,65,121,35,9圖上標(biāo)號法圖上標(biāo)號法:22例例1 求下圖中求下圖中v1到到v6的最短路的最短路解：采用解：采用Dijkstra算法，可解得最短路徑為算法，可解得最短路徑為v1 v3 v4 v6 各點(diǎn)的

12、標(biāo)號圖如下：各點(diǎn)的標(biāo)號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512 V1（0,s)v5 (8,4) v6(2,1)v3(3,3)v42、節(jié)約里程算法基本原理、節(jié)約里程算法基本原理o 基本原理是幾何學(xué)中三角形一邊之長必定小于另外兩邊之和。o 節(jié)約里程法核心思想是依次將運(yùn)輸問題中的兩個(gè)回路合并為一個(gè)回路，每次使合并后的總運(yùn)輸距離減小的幅度最大，直到達(dá)到一輛車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。優(yōu)化過程分為并行方式和串行方式兩種。o 假如一家配送中心（DC）向兩個(gè)用戶A、B運(yùn)貨，配送中心到兩用戶的最短距離分別是La和Lb，A和B間的最短距離為Lab，A、B的

13、貨物需求量分別是Qa和Qb，且（Qa+Qb）小于運(yùn)輸裝載量Q，如圖所示，如果配送中心分別送貨，那么需要兩個(gè)車次，總路程為：L1=2（La+Lb）。ABDCLaLbABDCLaLb Lab 如果改用一輛車對兩客戶進(jìn)行巡回送貨，則只需一個(gè)車次,行走的總路程為： L2=La+Lb+Lab 有三角形的性質(zhì)我們知道： Lab（La+Lb） 所以第二次的配送方案明顯優(yōu)于第一種，且行走總路程節(jié)約： L=（La+Lb）Lab 如果配送中心的供貨范圍內(nèi)還存在著：3,4,5，n個(gè)用戶，在運(yùn)載車輛載重和體積都允許的情況下，可將它們按著節(jié)約路程的大小依次連入巡回線路，直至滿載為止，余下的用戶可用同樣方法確定巡回路線，

14、另外派車。 例題：例題：由配送中心由配送中心P P向向AIAI等等9 9個(gè)用戶配送貨物。個(gè)用戶配送貨物。圖中連線上的數(shù)字表示公路里程（圖中連線上的數(shù)字表示公路里程（kmkm）?？浚？拷饔脩衾ㄌ杻?nèi)的數(shù)字，表示各用戶對貨物近各用戶括號內(nèi)的數(shù)字，表示各用戶對貨物的需求量（的需求量（t t）。配送中心備有）。配送中心備有2t2t和和4t4t載重量載重量的汽車，且汽車一次巡回走行里程不能超過的汽車，且汽車一次巡回走行里程不能超過35km35km，設(shè)送到時(shí)間均符合用戶要求，求該配，設(shè)送到時(shí)間均符合用戶要求，求該配送中心的最優(yōu)送貨方案。送中心的最優(yōu)送貨方案。ABCDEFGHIP(0.9)(1.2)(1.

15、6)(1.1)(0.9)(0.9)(0.6)(1.7)(0.5)444555556663777891010111214o計(jì)算配送中心至各用戶以及各用戶之間的最短距離，列表得最短距離表： P A B C D E F G H I PABCDEF GHI 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é)約法計(jì)算出各用由最短距離表，利用節(jié)約法計(jì)算出各用戶之間的節(jié)約里程，編制節(jié)約里程表：戶之

16、間的節(jié)約里程，編制節(jié)約里程表：AB:LA+LBLAB=11+10-5=16AC:LA+LCLAC=11+9-10=10AD:LA+LDLAD=11+6-14=3AE:LA+LELAE=11+7-18=0AF:LA+LFLAF=11+10-21=0AG:LA+LGLAG=11+10-21=0 A B C D E F G H I ABCDEF GHI 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é)約里程多少的順序，由大到小排列，編

17、制節(jié)約里程順序，由大到小排列，編制節(jié)約里程順序表，以便盡量使節(jié)約里程最多的點(diǎn)序表，以便盡量使節(jié)約里程最多的點(diǎn)組合裝車配送。組合裝車配送。順位號里程節(jié)約里程順位號里程節(jié)約里程順位號里程節(jié)約里程1A-B166H-I810F-G62B-C148B-D710G-H63A-I128D-E715A-D34C-D1110A-H616B-E25A-C1010B-I617D-F16E-F810C-E6 根據(jù)節(jié)約里程排序表和配車（車輛的載重和容積因素）、根據(jù)節(jié)約里程排序表和配車（車輛的載重和容積因素）、車輛行駛里程等約束條件，漸進(jìn)繪出配送路徑：車輛行駛里程等約束條件，漸進(jìn)繪出配送路徑：A AB BC CD DE

18、EF FG GH HI IP P(0.9)(0.9)(1.2)(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 475 55 58 86 66 66 69 9101010101212路徑路徑A路徑路徑B路徑路徑Co路徑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)缺點(diǎn)分析優(yōu)點(diǎn)： 節(jié)約法是一種簡便、易行的方法，一方面體現(xiàn)

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

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

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