六、運輸及配送路線的優(yōu)化

1、六、運輸決策及配送路線的優(yōu)化六、運輸決策及配送路線的優(yōu)化6.1運輸系統(tǒng)的重要性與功能運輸系統(tǒng)的重要性與功能6.2基本運輸方式及其運營特點基本運輸方式及其運營特點6.3運輸合理化運輸合理化6.4運輸路線的選擇運輸路線的選擇6.5車輛路線、時間安排車輛路線、時間安排6.1運輸系統(tǒng)的重要性與功能運輸系統(tǒng)的重要性與功能q運輸運輸指借助公共運輸線及其設施和運輸工具來實現(xiàn)人指借助公共運輸線及其設施和運輸工具來實現(xiàn)人與物空間位移的一種經(jīng)濟活動和社會活動。與物空間位移的一種經(jīng)濟活動和社會活動。q交通交通與運輸反映的同一過程的兩個方面。與運輸反映的同一過程的兩個方面。v 同一過程：運輸工具在運輸網(wǎng)路上的流動；同

2、一過程：運輸工具在運輸網(wǎng)路上的流動；v 兩個方面：兩個方面：v 交通關心的是運輸工具的流動情況交通關心的是運輸工具的流動情況(流量的大小、擁擠的程度流量的大小、擁擠的程度)v 運輸關心的是流動中的運輸工具上的載運情況運輸關心的是流動中的運輸工具上的載運情況(載人與物的有無與載人與物的有無與多少，將其輸送了多遠的距離多少，將其輸送了多遠的距離) v 運輸是交通的目的運輸是交通的目的q運輸系統(tǒng)的重要性運輸系統(tǒng)的重要性v 地域分工專業(yè)化地域分工專業(yè)化v 規(guī)模經(jīng)濟規(guī)模經(jīng)濟v 競爭加劇競爭加劇v 土地價值的提高土地價值的提高q交通運輸系統(tǒng)的構成要素：v（1）運載工具（2）通路（3）場站（4）動力（5）通

3、信（6）經(jīng)營管理人員和經(jīng)營機構q產(chǎn)品轉移v運輸克服了產(chǎn)品在生產(chǎn)與需求之間存在的空間和時間上的差異。q產(chǎn)品存儲v對產(chǎn)品進行臨時存儲是指將運輸車輛臨時作為相當昂貴的存儲設施。運輸?shù)墓δ苓\輸?shù)墓δ苓\輸服務的特征運輸服務的特征q運輸服務是一種特殊的產(chǎn)品：運輸服務是一種特殊的產(chǎn)品：v運輸服務產(chǎn)品具有無形性運輸服務產(chǎn)品具有無形性v運輸服務的生產(chǎn)和消費不可分離運輸服務的生產(chǎn)和消費不可分離v運輸服務具有不可存儲性運輸服務具有不可存儲性v異質性，即同一種服務的質量差別異質性，即同一種服務的質量差別 6.2 運輸方式及其特征運輸方式及其特征一、鐵路運輸一、鐵路運輸l 鐵路是國民經(jīng)濟的大動脈，鐵路運輸是我國貨物運輸

4、的主要鐵路是國民經(jīng)濟的大動脈，鐵路運輸是我國貨物運輸?shù)闹饕绞?。鐵路運輸?shù)闹饕攸c是能夠遠距離運輸大量貨物。由方式。鐵路運輸?shù)闹饕攸c是能夠遠距離運輸大量貨物。由于世界上幾乎所有的大都市、我國的絕大部分城市都通鐵路，于世界上幾乎所有的大都市、我國的絕大部分城市都通鐵路，鐵路在國際、國內運輸中占有相當大的市場份額。鐵路在國際、國內運輸中占有相當大的市場份額。 l 雖然設備和站點等的限制使得鐵路運營的固定成本很高，但雖然設備和站點等的限制使得鐵路運營的固定成本很高，但是鐵路運營的變動成本（如維修、管理、耗能等）相對較低，是鐵路運營的變動成本（如維修、管理、耗能等）相對較低，這也使得鐵路運輸?shù)目偝杀?/p>

5、通常比公路和航空運輸?shù)?。這也使得鐵路運輸?shù)目偝杀就ǔ１裙泛秃娇者\輸?shù)汀 高固定成本和低變動成本使鐵路運輸?shù)囊?guī)模經(jīng)濟十分明顯。鐵路運輸鐵路運輸鐵路運輸方式的鐵路運輸方式的主要優(yōu)點：n運輸能力大運輸能力大 n運行速度較快，時速一般運行速度較快，時速一般在在8080120120公里公里 n適應性強，受天氣限制條適應性強，受天氣限制條件少，安全可靠性高件少，安全可靠性高 n運輸成本低運輸成本低 n環(huán)境污染小，環(huán)境成本低環(huán)境污染小，環(huán)境成本低 鐵路運輸方式的鐵路運輸方式的主要缺點 ：u靈活性差靈活性差u對包裝的要求較高對包裝的要求較高u存在貨物被偷盜的危險存在貨物被偷盜的危險u鐵路設施修建成本較高，

6、鐵路設施修建成本較高，占地多。占地多。6.2 6.2 運輸方式及其特征運輸方式及其特征二、公路運輸二、公路運輸l 公路運輸具有規(guī)模巨大，分布極廣的道路基礎設施體系和公路運輸具有規(guī)模巨大，分布極廣的道路基礎設施體系和機動靈活、適應性強的車輛裝備系統(tǒng)。大多數(shù)的消費品都機動靈活、適應性強的車輛裝備系統(tǒng)。大多數(shù)的消費品都是通過公路運輸?shù)?。是通過公路運輸?shù)?。l 公路運輸是任何公司物流系統(tǒng)中重要的一部分。l 公路運輸?shù)墓潭ǔ杀竞艿?。汽車承運人在固定基礎設施的公路運輸?shù)墓潭ǔ杀竞艿?。汽車承運人在固定基礎設施的投資相對較少，多數(shù)公路的建設運營由政府進行。投資相對較少，多數(shù)公路的建設運營由政府進行。l 公路運輸

7、的變動成本相對較高，因為公路的建設和維修費公路運輸?shù)淖儎映杀鞠鄬^高，因為公路的建設和維修費用經(jīng)常是以稅收和收費站的形式向承運人征收的。此外，用經(jīng)常是以稅收和收費站的形式向承運人征收的。此外，汽車的能耗、維修費用相對也比較高。汽車的能耗、維修費用相對也比較高。l 燃油稅燃油稅公路運輸公路運輸 公路運輸方式的主要優(yōu)點：公路運輸方式的主要優(yōu)點：q原始投資少，資金周轉快，原始投資少，資金周轉快，投資回收期短投資回收期短q機動靈活，門對門運輸機動靈活，門對門運輸 q快捷可控快捷可控 q包裝成本低，貨物損失小包裝成本低，貨物損失小 公路運輸?shù)闹饕秉c公路運輸?shù)闹饕秉c ：運輸能力小運輸能力小勞動生產(chǎn)率低

8、，單位運價勞動生產(chǎn)率低，單位運價高高 公路擁擠與污染，環(huán)境成公路擁擠與污染，環(huán)境成本高本高 公路運輸不像其它運輸方式那樣受到各種線路的限制，其市場覆蓋面要高于其它運輸方式。公路運輸?shù)奶攸c使得公路運輸尤其適于短距離、高價值產(chǎn)品的裝運，在中間產(chǎn)品和輕工產(chǎn)品的運輸方面有較大的優(yōu)勢。 6.26.2運輸方式及其特征運輸方式及其特征三、水路運輸三、水路運輸l 水路運輸在世界外貿運輸中始終保持主導地位，在經(jīng)濟合作水路運輸在世界外貿運輸中始終保持主導地位，在經(jīng)濟合作和交流中起著紐帶作用。和交流中起著紐帶作用。l 受自然條件的制約，水路運輸?shù)倪\營范圍和運輸速度受到限受自然條件的制約，水路運輸?shù)倪\營范圍和運輸速度

9、受到限制，但是卻有其它運輸方式不可比擬的優(yōu)勢和潛力。制，但是卻有其它運輸方式不可比擬的優(yōu)勢和潛力。l 水運中水道的改良維護通常由政府負責，港口的開發(fā)和維護水運中水道的改良維護通常由政府負責，港口的開發(fā)和維護各國不同，但一般也由政府統(tǒng)一進行，而運輸公司只需支付各國不同，但一般也由政府統(tǒng)一進行，而運輸公司只需支付一定的費用就可以使用港口和其它碼頭設施。一定的費用就可以使用港口和其它碼頭設施。l 水路運輸?shù)乃愤\輸?shù)模饕ㄟ\營中的成本，其規(guī)模主要包括運營中的成本，其規(guī)模經(jīng)濟的效應更加明顯。經(jīng)濟的效應更加明顯。水路運輸水路運輸 水路運輸方式的主要優(yōu)點：水路運輸方式的主要優(yōu)點：單位運輸工具的裝載量大

10、，單位運輸工具的裝載量大，運輸能力高，運輸距離長運輸能力高，運輸距離長 水路運輸成本低，基礎設水路運輸成本低，基礎設施投資節(jié)省，單位運價低施投資節(jié)省，單位運價低廉廉 能源消耗少能源消耗少 水路運輸方式的主要缺點：水路運輸方式的主要缺點：q運輸速度慢運輸速度慢 q受天氣和其它自然條件影受天氣和其它自然條件影響大，線路迂回響大，線路迂回 q貨物破損較多貨物破損較多 q可靠性差可靠性差 與上述特點相對應，水路運輸適于運送數(shù)量巨大、低價值、時效性要求不高的貨物，如礦石、煤炭、石油農產(chǎn)品等。水路運輸是大宗貨物長距離運輸?shù)睦硐脒x擇。 6.2 6.2 運輸方式及其特征運輸方式及其特征四、航空運輸四、航空運輸

11、l 航空貨運的主要優(yōu)點在于運輸速度快。航空貨運的主要優(yōu)點在于運輸速度快。l 隨著航空運輸技術的不斷成熟，航空運輸在遠距離運輸，特隨著航空運輸技術的不斷成熟，航空運輸在遠距離運輸，特別是跨國運輸中顯示出無可比擬的優(yōu)勢。別是跨國運輸中顯示出無可比擬的優(yōu)勢。l 只有在運輸高價值的和對時效性要求高于對成本要求的產(chǎn)品只有在運輸高價值的和對時效性要求高于對成本要求的產(chǎn)品時，航空運輸才有其合理性。時，航空運輸才有其合理性。l 航空的固定成本較低。空中航線和管制系統(tǒng)由國家擁有，航航空的固定成本較低。空中航線和管制系統(tǒng)由國家擁有，航空港的建設運營由國家投資，航空公司的固定成本主要與購空港的建設運營由國家投資，航

12、空公司的固定成本主要與購買飛機有關，也與所需的搬運系統(tǒng)和貨物集裝箱有關。買飛機有關，也與所需的搬運系統(tǒng)和貨物集裝箱有關。l 航空運輸?shù)淖儎映杀臼菢O高的，其燃料消耗、飛行器的維修航空運輸?shù)淖儎映杀臼菢O高的，其燃料消耗、飛行器的維修保養(yǎng)以及飛行人員和地勤人員的費用都是一筆可觀的支出。保養(yǎng)以及飛行人員和地勤人員的費用都是一筆可觀的支出。航空運輸航空運輸航空運輸?shù)闹饕獌?yōu)點：航空運輸?shù)闹饕獌?yōu)點：u運行速度快運行速度快 u靈活、機動性大靈活、機動性大 u航空運輸服務質量高、安航空運輸服務質量高、安全可靠全可靠 航空運輸?shù)闹饕秉c：航空運輸?shù)闹饕秉c：u運輸成本高運輸成本高 u運輸能力小運輸能力小 u有些貨

13、物禁用空運有些貨物禁用空運 u受天氣影響較大受天氣影響較大 綜合上述優(yōu)缺點，航空運輸適用于長途旅客運輸和緊急需要的、時效性要求高的、單位價值高的貨物運輸。 6.2 運輸方式及其特征運輸方式及其特征q五、管道運輸五、管道運輸q管道是很獨特的運輸方式，它所能運送的貨物種類很有限，管道是很獨特的運輸方式，它所能運送的貨物種類很有限，主要通過管道運輸?shù)呢浳锸牵菏图俺善酚?、天然氣、化主要通過管道運輸?shù)呢浳锸牵菏图俺善酚汀⑻烊粴?、化學制品。學制品。q管道運輸?shù)膬?yōu)勢：管道運輸?shù)膬?yōu)勢：v 費用低。費用低。v 貨損、貨差率低。貨損、貨差率低。v 另外，因為管道運輸速度很慢，還可以將管道作為倉庫。另外，因為管

14、道運輸速度很慢，還可以將管道作為倉庫。v 可靠性好、不受天氣影響、很少有機械故障可靠性好、不受天氣影響、很少有機械故障q管道運輸?shù)娜秉c：管道運輸?shù)娜秉c：v 管道線路是相對固定的，因此有地域靈活性或可達性的限制。管道線路是相對固定的，因此有地域靈活性或可達性的限制。v 管道運輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務。管道運輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務。各種運輸方式技術經(jīng)濟特征比較表各種運輸方式技術經(jīng)濟特征比較表運輸方運輸方式式基建投資基建投資運載運載量量運輸成運輸成本本速速度度連續(xù)連續(xù)性性靈活靈活性性生產(chǎn)生產(chǎn)率率安全安全性性線路線路運具運具鐵路鐵路6 62 22 24 43 31 13

15、34 43 3河運河運3 34 43 32 26 66 64 42 24 4海運海運1 13 31 11 15 55 55 51 15 5公路公路4 45 55 55 52 22 21 16 66 6管道管道5 51 14 43 34 43 36 63 31 1航空航空2 26 66 66 61 14 42 25 52 2 注：表中數(shù)字表示各種運輸方式在某一方面的優(yōu)劣次序。注：表中數(shù)字表示各種運輸方式在某一方面的優(yōu)劣次序。影響運輸決策的成本因素影響運輸決策的成本因素q影響承運人定價的成本因素影響承運人定價的成本因素v與運距有關的成本與運距有關的成本v與運量有關的成本與運量有關的成本v與速度有關

16、的成本與速度有關的成本直送v.s中轉q影響承運人運力組合的成本因素影響承運人運力組合的成本因素v固定成本固定成本v運營成本運營成本運輸特性運輸特性q規(guī)模規(guī)模特性特性q隨著一次裝運量的增大，使每單位重量的運輸成本下降。隨著一次裝運量的增大，使每單位重量的運輸成本下降。q距離距離特性特性q隨著一次運輸距離的增加，運輸費用的增加會變的越來越緩慢，或者隨著一次運輸距離的增加，運輸費用的增加會變的越來越緩慢，或者說單位運輸距離的費用減少，運輸成本與一次運輸?shù)木嚯x有關。說單位運輸距離的費用減少，運輸成本與一次運輸?shù)木嚯x有關。q速度速度特性特性q完成特定的運輸所需的時間越短，其效用價值越高。完成特定的運輸所

17、需的時間越短，其效用價值越高。單位貨物運輸成本運輸距離單位貨物運輸成本裝載重量運輸效用送達時間影響承運人運力組合的成本因素影響承運人運力組合的成本因素qn the number of time periods into which the time horizon of a year is decomposed (for example, n = 52 if the time period corresponds to a week)qv the decision variable corresponding to the number of owned vehiclesqvt , t = 1

18、,.,n, the required number of vehicles at time period t;qm the number of time periods per year in which vt v.qcF fixed cost （ an owned vehicle）qcV variable cost （ an owned vehicle）qcH be the cost per time period of hiring a vehicle (clearly, c F + c V c H ). qAs the two summations in Equation are equ

19、al to the areas below and above the line vt = v, respectively , then their derivatives are equal to m and m, respectively. qConsequently, C(v) is minimal when影響托運人決策的成本因素影響托運人決策的成本因素v服務水平成本（運輸時間-速度）v運輸成本（運輸方式、運輸規(guī)模）v庫存成本v交易成本運輸服務的選擇運輸服務的選擇q 的影響是決策者心目中的影響是決策者心目中最重要的運輸服務要素，因此，這三項是運輸服最重要的運輸服務要素，因此，這三項是運

20、輸服務選擇的基礎。務選擇的基礎。q運輸對庫存的影響有以下幾點：運輸對庫存的影響有以下幾點：q在選擇運輸方式時，就需要考慮庫存持有成本可在選擇運輸方式時，就需要考慮庫存持有成本可能升高，而抵消運輸服務成本降低的情況。能升高，而抵消運輸服務成本降低的情況。運輸服務的選擇的定量分析法運輸服務的選擇的定量分析法q基于運輸成本與庫存成本的總成本分析方法基于運輸成本與庫存成本的總成本分析方法v【例例】某公司欲將產(chǎn)品從位置某公司欲將產(chǎn)品從位置A的工廠運往位的工廠運往位置置B的公司自有倉庫，年運量的公司自有倉庫，年運量D=700000件，件，產(chǎn)品價值產(chǎn)品價值C=30元，年存貨成本元，年存貨成本I=產(chǎn)品價格的產(chǎn)

21、品價格的30。公司希望選擇使總成本最小的運輸方式。公司希望選擇使總成本最小的運輸方式。據(jù)估計，運輸時間每減少一天，平均庫存成本據(jù)估計，運輸時間每減少一天，平均庫存成本可以減少可以減少1。各種運輸服務方式的有關參數(shù)。各種運輸服務方式的有關參數(shù)見表：見表：運輸服務的選擇的定量分析法運輸服務的選擇的定量分析法運輸方式運輸方式 費率費率R(元元/件件) 時間時間T(天天) 年運送批年運送批次次 平均存貨平均存貨量量Q/2 鐵路鐵路 0.12110100000水運水運 0路公路 0.252042000航空航空1.424020250運輸服務的選擇的定量分析法運輸服務的選擇的定量分

22、析法q分析：分析：v以年總成本最低為原則來選擇合適的運輸方式。這里，以年總成本最低為原則來選擇合適的運輸方式。這里，總成本總成本=運輸費用運輸費用+庫存成本；庫存成本；v其中，其中，運輸費用運輸費用=運輸量運輸量 費率費率v庫存成本庫存成本=在途運輸庫存成本在途運輸庫存成本+工廠存貨成本工廠存貨成本+倉庫存?zhèn)}庫存貨成本貨成本v在途運輸庫存費用在途運輸庫存費用=ICDT/365v工廠存貨成本工廠存貨成本=ICQ/2v倉庫存貨成本倉庫存貨成本=I（C+R）Q/2v代入各種運輸方式的基本數(shù)據(jù)信息，將相應的成本計算代入各種運輸方式的基本數(shù)據(jù)信息，將相應的成本計算結果列入表結果列入表2。vD年運量；年運

23、量；C產(chǎn)品單價；產(chǎn)品單價； I年存貨成本（產(chǎn)品價年存貨成本（產(chǎn)品價格的格的30）；）；vT運輸時間；運輸時間； R費率費率 (元元/件件) ； Q/2平均存貨量平均存貨量二、運輸方式選擇的定量分析法二、運輸方式選擇的定量分析法由表中結果可知，總成本最低的是公路運輸方式，總成本為由表中結果可知，總成本最低的是公路運輸方式，總成本為984821元，其次是水路運輸，成本最高的是鐵路運輸。按照元，其次是水路運輸，成本最高的是鐵路運輸。按照總成本最低的原則，適合選擇公路運輸方式?？偝杀咀畹偷脑瓌t，適合選擇公路運輸方式。 成本類成本類型型 計算公式計算公式 鐵路運輸鐵路運輸 水路運輸水路運輸 公路運輸公路

24、運輸 航空運輸航空運輸 運輸成運輸成本本 R D 70000105000140000980000在途庫在途庫存存 ICDT/365 345205241644 8630134521工廠存工廠存貨貨 ICQ/2 900000416500378000182250倉庫存?zhèn)}庫存貨貨 I(C+R)Q/2903000420593380520190755總成本總成本 2218205118573798482113875266.4運輸路線的選擇運輸路線的選擇q1 1起、止點不同的單一路徑規(guī)劃起、止點不同的單一路徑規(guī)劃q2 2多個起、止點的路徑規(guī)劃多個起、止點的路徑規(guī)劃q3 3起點和終點相同的路徑規(guī)劃起點和終點相同

25、的路徑規(guī)劃vTraveling Salesman Problem (TSP)Traveling Salesman Problem (TSP)vVehicle Routing Problem (VRP)Vehicle Routing Problem (VRP)6.4運輸路線的選擇運輸路線的選擇q1起、止點不同的單一路徑規(guī)劃起、止點不同的單一路徑規(guī)劃q這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎的問題之一。q問題描述：假設有一n個節(jié)點和m條弧的連通圖G（Vn,Em),并且圖中的每條弧（i,j)都有一個長度cij(或者費用cij)，q求解此類最短路徑問題，主要有以下幾種算

26、法：q（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法1起、止點不同的單一路徑規(guī)劃起、止點不同的單一路徑規(guī)劃例例 某運輸公司簽訂了一項運輸合同，要把A市的一批貨物運送到B市，該公司根據(jù)這兩個城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡。圖中，圓圈也稱節(jié)點，代表起點、目的地和與行車路線相交的其他城市。鏈代表兩個結點之間的公路，每一條公路都標明運輸里程。A市市B市市解答：最短路的計算方法解答：最短路的計算方法（1 1）找出第）找出第n n個距起點最近的節(jié)點。對個距起點最近的節(jié)點。對n=1,2,n=1,2,，重復此過程，直到所，重復此過程，直到所找出的最近節(jié)點是終點。找出

27、的最近節(jié)點是終點。（2 2）在前面的迭代過程中找出（）在前面的迭代過程中找出（n-1n-1）個距起點最近的節(jié)點，及其距起）個距起點最近的節(jié)點，及其距起點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為未解節(jié)點。未解節(jié)點。（3 3）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一個候選點個候選點連接距離最短的未解點。如果有多個距離相等的最短連接，連接距離最短的未解點。如果有多個距離相等的最短連接，則有多個候選點。則有多個候選點。（4 4）將每個已解節(jié)點與其候

28、選點之間的距離累加到該已解節(jié)點與起點）將每個已解節(jié)點與其候選點之間的距離累加到該已解節(jié)點與起點之間最短路徑的距離上，所得出的總距離最短的候選點就是第之間最短路徑的距離上，所得出的總距離最短的候選點就是第n n個最近個最近的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的最短距離，則都是已解節(jié)點）。的最短距離，則都是已解節(jié)點）。通過上表的計算，最短路徑為通過上表的計算，最短路徑為1-2-5-4-3-6，最短距離為，最短距離為12。FloydFloyd算法算法qF F算法的基本思路算法的基本思路: :qF算法使用距離矩陣距

29、離矩陣和路由矩陣路由矩陣。q距離矩陣距離矩陣是一個nn矩陣，以圖G的n個節(jié)點為行和列。記為W=w wijij n n， w wijij表示圖G中vi和vj兩點之間的路徑長度。q路由矩陣路由矩陣是一個nn矩陣，以圖G的n個節(jié)點為行和列。記為R =r rijij n n ，其中r rijij表示vi至vj經(jīng)過的轉接點（中間節(jié)點）。F算法的思路是首先寫出初始的W陣和R陣，接著按順序依次將節(jié)點集中的各個節(jié)點作為中間節(jié)點，計算此點距其他各點的徑長，每次計算后都以求得的與上次相比較小的徑長去更新前一次較大徑長，若后求得的徑長比前次徑長大或相等則不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間

30、節(jié)點，（按順序，后面的點不作為（按順序，后面的點不作為中間節(jié)點）中間節(jié)點）考察所有所有通過此中間節(jié)點的路徑1245310561543123451310235310615456454W0123451234521345312454123551234R012453105615431234513102313531013615456454W1123451234521145311454123551234R11245310561543123451310823135310136154856454W2123451232521145311454223551234R2124531056154312345131082

31、52313528310136154856454W3123451232321143311454223551234R3124531056154312345131081223115931011610485645129104D4123451232421444314444223554444S42多個起、止點的路徑規(guī)劃當有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時當有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。要找到供貨地、目的地之間的最佳路徑。例例 某公司下屬三個倉庫，供應四個客戶的需要，三個倉庫的供應量某公司下屬三個倉庫，供應四個客戶的需要，三

32、個倉庫的供應量和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。求運輸費用最少的運輸方案。求運輸費用最少的運輸方案。 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應量供應量運價運價產(chǎn)地產(chǎn)地倉庫倉庫A311310700倉庫倉庫B1928400倉庫倉庫C74105900需求量需求量3006005006002000表上做業(yè)法表上做業(yè)法，該方法適合于對相對簡單的問題進行求解，求解過程方便，該方法適合于對相對簡單的問題進行求解，求解過程方便直觀，而且由于計算量不大，可以用手工直接完成。利用表上作業(yè)法有兩直觀，而且由于計算量不

33、大，可以用手工直接完成。利用表上作業(yè)法有兩個基本步驟：個基本步驟：（1 1）確定初始調運方案）確定初始調運方案 最小元素法是按運價表依次挑選運費小的供最小元素法是按運價表依次挑選運費小的供- -需點組合，盡量優(yōu)需點組合，盡量優(yōu)先安排運費最低組合的方法。先安排運費最低組合的方法。 3113101928734105 銷銷地地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應量供應量運價運價產(chǎn)地產(chǎn)地倉庫倉庫A400300700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500600表表5.4 初始調運方案初始調運方案（2 2）初始方案的檢驗）初始方案的檢驗最優(yōu)方案的數(shù)字

34、特征最優(yōu)方案的數(shù)字特征檢驗數(shù)：檢驗數(shù)：閉回路：閉回路： 從理論上講，對于表上作業(yè)法的初始方案來說，從調運方案從理論上講，對于表上作業(yè)法的初始方案來說，從調運方案表上的一個空格出發(fā)，存在一條且僅存在一條以該表上的一個空格出發(fā)，存在一條且僅存在一條以該空格空格（用（用xijxij表表示）為起點，以示）為起點，以其他填有數(shù)字的點其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉為其他頂點的閉合回路，簡稱閉回路。這個閉回路有以下性質：回路。這個閉回路有以下性質：每個頂點都是轉角點；每個頂點都是轉角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（

35、列）若有閉合回路的頂點，則必有兩個。每一行（列）若有閉合回路的頂點，則必有兩個。 只有從空格出發(fā)，其余各轉角點所對應的方格內均填寫數(shù)字時，只有從空格出發(fā)，其余各轉角點所對應的方格內均填寫數(shù)字時，所構成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉所構成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。合回路不僅是存在的，而且是唯一的。 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應量供應量產(chǎn)地產(chǎn)地倉庫倉庫A400300700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500600 表表6.56.5給出了單元格（

36、給出了單元格（1 1，1 1）和（）和（3 3，1 1）所形成的閉回路：（）所形成的閉回路：（1 1，1 1）（1,31,3）(2(2，3)3)（2 2，1 1）（1 1，1 1）；（）；（3 3，1 1）（2 2，1 1）（2 2，3 3）（1 1，3 3）（1 1，4 4）（3 3，4 4）（3 3，1 1）。其他空格的閉回路與此同）。其他空格的閉回路與此同理。理。 在調運方案內的每個空格所形成的閉回路上，作單位物資的運量調整，在調運方案內的每個空格所形成的閉回路上，作單位物資的運量調整，總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上總可以計算出相應的運費是增加還是減

37、少。我們把所計算出來的每條閉回路上調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。調整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小如果檢驗數(shù)小于于0 0，表示在該空格的閉回路上調整運量會使運費減少；相反，如果檢驗數(shù)大，表示在該空格的閉回路上調整運量會使運費減少；相反，如果檢驗數(shù)大于于0 0，則會使運費增加。，則會使運費增加。表8.5 初始調運方案用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當產(chǎn)銷點很多時，這種計算很繁，可以用較為簡便的方法可以用較為簡便的方法“位勢法位勢法”求解。求解。設u1,u2,um；v1,v2,vn，是對應運輸問題的m+n個約束條件的對偶變

38、量。在初始調運方案中x13,x14,x21,x23,x32,x34是基變量，這時對應的檢驗數(shù)是：基變量基變量 檢驗數(shù)檢驗數(shù)x21 c21-( u2+v1)=0 x21 c21-( u2+v1)=0 設設v1=0v1=0，并且，并且c21=1 c21=1 所以所以 u2=1u2=1x23 c23-(u2+v3)=0 2-( u2+v3)=0 x23 c23-(u2+v3)=0 2-( u2+v3)=0 x13 c13-(u1+v3)=0 3-( u1+v3)=0 x13 c13-(u1+v3)=0 3-( u1+v3)=0 x14 c14-(u1+v4)=0 10-( u1+v4)=0 x14

39、c14-(u1+v4)=0 10-( u1+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x34 c34-(u3+v4)=0 5-( u3+v4)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0 x22 c22-(u2+v2)=0 4-( u2+v2)=0通過這些方程可以求得通過這些方程可以求得u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8u1=2 u2=1 u3= -3 v1=0 v2=7 v3=1 v4=8在初始解調運方案中增加一行一列，在初始解調運方案中增加一行一列，在列中填入在列中填入ui,ui,在行中填入在行中填

40、入vivi。接著，。接著，按按ij=cij-(ui+vj)ij=cij-(ui+vj)計算所有空格的檢驗數(shù)。完成后的表格見表計算所有空格的檢驗數(shù)。完成后的表格見表5.65.6。3113101928734105 銷地銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4ui運價運價產(chǎn)地產(chǎn)地倉庫倉庫A12002倉庫倉庫B010-11倉庫倉庫C100120-3vi0718表表5.6 檢驗數(shù)表格檢驗數(shù)表格（3 3）方案調整）方案調整 判定一個初始調運方案不是最優(yōu)調運方案的標準，是在檢驗數(shù)表格中判定一個初始調運方案不是最優(yōu)調運方案的標準，是在檢驗數(shù)表格中出現(xiàn)負值的檢驗數(shù)。如果檢驗數(shù)的負值不止個時，一般選擇負檢驗數(shù)

41、絕對出現(xiàn)負值的檢驗數(shù)。如果檢驗數(shù)的負值不止個時，一般選擇負檢驗數(shù)絕對值最大的空格作為具體調整對象。值最大的空格作為具體調整對象。 從表從表5.65.6可以發(fā)現(xiàn)，單元格可以發(fā)現(xiàn)，單元格x x2424的檢驗數(shù)是負數(shù)，因此對其進行調整，的檢驗數(shù)是負數(shù)，因此對其進行調整，具體過程如表具體過程如表5.75.7所示。所示。x13400+100=500 x14300-100=200 x23100-100=0 x240+100=100表表5.7 5.7 調動方案調整表調動方案調整表 從單元格從單元格x x2424開始，沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值開始，沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)

42、值作為調整量。在此將作為調整量。在此將x x2323單元格的單元格的100100作為調整量，將亮個數(shù)填入單元格作為調整量，將亮個數(shù)填入單元格x x2424內，內，同時調整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡，同時調整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡，這樣注得到一個新的調運方案，如表這樣注得到一個新的調運方案，如表5.75.7所示。所示。3113101928734105 銷地客戶客戶1客戶客戶2客戶客戶3客戶客戶4供應量供應量 運價產(chǎn)地倉庫倉庫A500200700倉庫倉庫B300100400倉庫倉庫C600300900需求量需求量300600500

43、600表表6.7 6.7 調整后的方案調整后的方案按新方案計算調運物資的運輸費用為：按新方案計算調運物資的運輸費用為：3 3500+10500+10200+8200+8100+4100+4600+5600+5300=8500300=8500元元新方案是否最優(yōu)方案，還需再進行檢驗。經(jīng)計算，該新方案新方案是否最優(yōu)方案，還需再進行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。的所有檢驗數(shù)都是非負數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。找出檢驗數(shù)找出檢驗數(shù) ij為最小負值的格子的閉回路為最小負值的格子的閉回路 在滿足所有約束條件的情況下，盡可能增大這在滿足所有約束條件的情況下，盡可

44、能增大這個格子的個格子的xij值值 調整此閉回路上其他頂點的值調整此閉回路上其他頂點的值 檢驗新解的最優(yōu)性檢驗新解的最優(yōu)性 重復上步驟直至得到最優(yōu)解為止。重復上步驟直至得到最優(yōu)解為止。3起點和終點相同的路徑規(guī)劃起點和終點相同的路徑規(guī)劃起點和終點重合的路徑問題一般被稱為起點和終點重合的路徑問題一般被稱為“旅行商旅行商”問題（問題（TSP, TSP, Traveling Salesman ProblemTraveling Salesman Problem），是運籌學、圖論和組合優(yōu)化中的），是運籌學、圖論和組合優(yōu)化中的典型問題。典型問題。 TSPTSP問題一般描述如下：問題一般描述如下：一個旅行者從

45、出發(fā)地出發(fā)，經(jīng)過所有要到達的城市后，返回到出發(fā)一個旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達的城市后，返回到出發(fā)地，要求合理安排其旅行路線，地，要求合理安排其旅行路線，使得總旅行距離（或旅行費用、旅使得總旅行距離（或旅行費用、旅行時間等）最短。行時間等）最短。TSPTSP問題特性：問題特性：p單一車輛單一車輛p無車輛容量限制無車輛容量限制p求解復雜度屬于求解復雜度屬于NP-hard，大規(guī)模問題難以求得最佳解，現(xiàn)，大規(guī)模問題難以求得最佳解，現(xiàn)實中常采取實中常采取”啟發(fā)式方法啟發(fā)式方法(Heuristics)“求解求解TSPTSP問題數(shù)學規(guī)劃模型問題數(shù)學規(guī)劃模型 Mins.t.ijijijxcAin al

46、lfor 1 , 011ijxNjxNixijiijjijTSPTSP問題求解算法問題求解算法q真正解法真正解法(只能處理非常小的問題只能處理非常小的問題)vEnumeration窮舉法窮舉法vAssignment algorithm指派算法指派算法vLittles method分枝定界法分枝定界法(Branch-and-Bound)q傳統(tǒng)啟發(fā)式解法傳統(tǒng)啟發(fā)式解法(Heuristics)大致可歸納為以下大致可歸納為以下三種：三種：v路線構建路線構建(route construction)鄰點法、插入法.v路線改善路線改善(route improvement)k-Opt交換法、Or-Opt交換法

47、v綜合型綜合型(composite)合并執(zhí)行路線構建及路線改善Assignment Procedure For TSP1 1、將、將A A到到A A，B B到到B,CB,C到到C C的費用轉換成無限的費用轉換成無限大，以防止返回。大，以防止返回。Assignment Procedure For TSPq2、應用指派、應用指派問題的匈牙利問題的匈牙利算法，使得表算法，使得表中不同行、不中不同行、不同列都含有同列都含有0q此時，若完成此時，若完成路徑的選擇，路徑的選擇，最少的費用為最少的費用為9Assignment Procedure For TSPq可行解尚未找到?？尚薪馍形凑业健此時考慮此時

48、考慮 增加一增加一個個“費用最小的費用最小的非非0路徑路徑” ，看，看看是否有可行解。看是否有可行解。得到：得到：仍然沒有可行解。仍然沒有可行解。此時考慮此時考慮 再再增加一個增加一個“費用最小的非費用最小的非0 0路徑路徑” ，或增加一個或增加一個“費用次小的費用次小的非非0 0”路徑看看是否有可行路徑看看是否有可行解。解。得到：得到：Littles method分枝定界法分枝定界法(Branch-and-Bound)q1、計算出所有不、計算出所有不走走“0費用費用”路徑路徑的懲罰成本的懲罰成本q2、選擇懲罰成本、選擇懲罰成本最大的路徑最大的路徑q3、簡化計算表，消除已經(jīng)選擇的路徑，形成新的

49、計算表；、簡化計算表，消除已經(jīng)選擇的路徑，形成新的計算表；繼續(xù)分支定界。繼續(xù)分支定界。同時，為了防止返回，同時，為了防止返回，E到到C設為設為；再檢查是否每一行、每；再檢查是否每一行、每一列都有一列都有“0費用費用”路徑，若沒有在此行路徑，若沒有在此行/列減去最小元素。列減去最小元素。E行減去行減去1，得到：，得到：D同時，為了防止返回，同時，為了防止返回，E到到B設為設為；再檢查是否每一行、每；再檢查是否每一行、每一列都有一列都有“0費用費用”路徑，若沒有在此行路徑，若沒有在此行/列減去最小元素。列減去最小元素。A列減去列減去1，得到：，得到：假設選擇假設選擇E,D路徑，得到：路徑，得到：假

50、設不選擇假設不選擇E,D路徑：路徑：傳統(tǒng)啟發(fā)式解法傳統(tǒng)啟發(fā)式解法q1、最近鄰點法、最近鄰點法(Nearest-neighbor Heuristic)1. 任選一節(jié)點為起點任選一節(jié)點為起點x2. 尋找距離節(jié)點尋找距離節(jié)點x最近的節(jié)點最近的節(jié)點y作為下一個造訪的節(jié)點作為下一個造訪的節(jié)點3. 尋找距離節(jié)點尋找距離節(jié)點y最近的節(jié)點最近的節(jié)點z作為下一個造訪的節(jié)點作為下一個造訪的節(jié)點4. 重復以上步驟，直到所有節(jié)點均已造訪重復以上步驟，直到所有節(jié)點均已造訪5. 連接最后一個節(jié)點與起點，即形成一個連接最后一個節(jié)點與起點，即形成一個TSP的可行解的可行解1、最近鄰點法、最近鄰點法14235743875534

51、8142351234514738247553773443538585482、插入法插入法(Insertion Method)(Insertion Method)1. 任選一節(jié)點為起點任選一節(jié)點為起點a2. 尋找距離節(jié)點尋找距離節(jié)點a最近的節(jié)點最近的節(jié)點b作為下一個造訪的節(jié)點，作為下一個造訪的節(jié)點，形成形成a-b-a的子回路的子回路3. 尋找距離子回路最近的節(jié)點尋找距離子回路最近的節(jié)點k作為下一個插入點作為下一個插入點4. 尋找插入成本最小的位置尋找插入成本最小的位置(i-j)，將，將k插入插入i-j之間，形之間，形成新的子回路。成新的子回路。插入成本：插入成本：Cik+Ckj-Cij5. 重復

52、步驟重復步驟34，直到所有節(jié)點均已插入回路之中，即，直到所有節(jié)點均已插入回路之中，即形成一個形成一個TSP的可行解的可行解2、插入法插入法14235743875534814141333373337317224525727421455885845455582145543 3、 2-opt 2-opt 交換交換法法1.先構建一個起始可行解先構建一個起始可行解2.在可行解中任選兩個不相鄰的節(jié)線在可行解中任選兩個不相鄰的節(jié)線(a b, c d)，以及另外兩條對應之替換節(jié)線，以及另外兩條對應之替換節(jié)線(a c, b d)，計算替換后總成本是否降低，計算替換后總成本是否降低 (即檢查即檢查替換成本是否小于

53、替換成本是否小于0)。 替換成本：替換成本：Cac+Cbd-Cab-Ccd (對稱型對稱型TSP)3.若替換后總成本有降低，則予以替換，同時若替換后總成本有降低，則予以替換，同時變更中間相關弧線的行走方向變更中間相關弧線的行走方向4.重復步驟重復步驟23，直到所有可能的替換均無法，直到所有可能的替換均無法再降低成本為止再降低成本為止3 3、 2-opt 2-opt 交換交換法法1423574387553484 4、常見的宏啟發(fā)式方法、常見的宏啟發(fā)式方法(Meta-heuristics)(Meta-heuristics)v禁忌搜索法禁忌搜索法(Tabu Search, TS)v基因算法基因算法(

54、Genetic Algorithm, GA)v模擬退火法模擬退火法(Simulated Annealing, SA)v門限值接受法門限值接受法(Threshold Accepting, TA)v神經(jīng)網(wǎng)絡神經(jīng)網(wǎng)絡(Neural Network, NN)v蟻群算法蟻群算法(Ant Colony Optimization, ACO)v其它其它6.4 車輛路線、時間安排車輛路線、時間安排車輛路線安排車輛路線安排車輛路線安排問題（車輛路線安排問題（VRP, Vehicle Routing ProblemVRP, Vehicle Routing Problem）是指對物流配送的車輛進行優(yōu)化調度。該問題一般

55、可以描述如下：對一系列裝貨點或（和）卸貨點，組織適當合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時間、車輛容量、數(shù)目限制、車輛行駛里程、時間限制等）下，達到一定的目標（如最短路程、最小費用、最短時間、最少車輛等）。該問題涉及了多輛交通工具的服務對象的選擇和路徑（服務順序）確定兩方面的問題 VRP問題是組合優(yōu)化領域著名的NP難題之一，求解方法一般相當復雜，通常的做法是應用相關技術問題分解或者轉化為一個或多個已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對比較成熟的基本理論和方法進行求解。運用VRP模型對實際問題進行研究時，一般

56、需要考慮以下幾個方面的問題：u（1 1）倉庫）倉庫。倉庫的級數(shù)，每級倉庫的數(shù)量、地點和規(guī)模。u（2 2）車輛。）車輛。車輛的型號和數(shù)量，每種車輛的容積和運作費用，出發(fā)時間和返回時間，司機休息時間，最大的里程和時間限制。u（3 3）時間窗口。）時間窗口。由于各處的工作時間不同，每個站點每天只允許在特定的時間內取貨和/或送貨。u（4 4）顧客。）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級。u（5 5）道路信息。）道路信息。車流密度，道路交通費用，距離或時間屬性。u（6 6）貨物信息。）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。u（7 7）運輸規(guī)章。）運輸規(guī)章。工人每天的工作

57、時間，車輛的周期維護。u（1 1）安排車輛負責相互距離最接近的站點的貨物運輸。）安排車輛負責相互距離最接近的站點的貨物運輸。u（2 2）安排車輛各日途經(jīng)站點時，應注意使站點群更加緊湊。如果一周內）安排車輛各日途經(jīng)站點時，應注意使站點群更加緊湊。如果一周內各日服務的站點不同，就應該對一周內每天的路線和時刻表問題分別進各日服務的站點不同，就應該對一周內每天的路線和時刻表問題分別進行站點群劃分。各日站點群的劃分應避免重疊。行站點群劃分。各日站點群的劃分應避免重疊。u（3 3）從距倉庫最遠的站點開始設計路線）從距倉庫最遠的站點開始設計路線u（4 4）卡車的行車路線應呈水滴狀。）卡車的行車路線應呈水滴狀

58、。u（5 5）盡可能使用最大的車輛進行運送，這樣設計出的路線是最有效的。）盡可能使用最大的車輛進行運送，這樣設計出的路線是最有效的。u（6 6）取貨、送貨應該混合安排，不應該在完成全部送貨任務之后再取貨。）取貨、送貨應該混合安排，不應該在完成全部送貨任務之后再取貨。u（7 7）對過于遙遠而無法歸入群落的站點，可以采用其它配送方式。）對過于遙遠而無法歸入群落的站點，可以采用其它配送方式。u（8 8）避免時間窗口過短。）避免時間窗口過短。簡化的原則：簡化的原則：q整數(shù)規(guī)劃法（整數(shù)規(guī)劃法（Integer Programming）q啟發(fā)式方法（啟發(fā)式方法（Heuristics）v節(jié)約法（節(jié)約法（Cla

59、rke and Wright Procedure）v兩階段法兩階段法 ETS (Extension of Traveling Salesman Procedure)v掃描法掃描法v考慮返程考慮返程 Backtracking1、整數(shù)規(guī)劃法、整數(shù)規(guī)劃法2、節(jié)約法（、節(jié)約法（Clarke and Wright Procedure） 節(jié)約法的目標是使所有車輛的行駛總里程最短，并且為所有站點提供節(jié)約法的目標是使所有車輛的行駛總里程最短，并且為所有站點提供服務的卡車數(shù)量最少。該方法先假設每一個站點都有一輛虛擬的車輛服務的卡車數(shù)量最少。該方法先假設每一個站點都有一輛虛擬的車輛提供服務，隨后返回倉庫，如圖提供

60、服務，隨后返回倉庫，如圖(a)所示，這時的路線里程最長。下所示，這時的路線里程最長。下一步，將兩個站點合并到同一條行車路線上，減少一輛運輸車，相應一步，將兩個站點合并到同一條行車路線上，減少一輛運輸車，相應地縮短路線里程，選擇節(jié)約距離最多的一對站點合并在一起，修訂后地縮短路線里程，選擇節(jié)約距離最多的一對站點合并在一起，修訂后的路線如圖的路線如圖(b)。d0,AdA,0d0,BdB,0ABO倉倉庫庫dA,Bd0,AdB,0a) a) 初始路線初始路線里程里程=d=dO,AO,A+d+dA,OA,O+d+dO,BO,B+d+dB,OB,Ob) b) 兩個站點合并后的路線兩個站點合并后的路線里程里程