六運(yùn)輸及配送路線的優(yōu)化演示文稿

六運(yùn)輸及配送路線的優(yōu)化演示文稿當(dāng)前第1頁\共有103頁\編于星期四\20點(diǎn)優(yōu)選六運(yùn)輸及配送路線的優(yōu)化當(dāng)前第2頁\共有103頁\編于星期四\20點(diǎn)6.1運(yùn)輸系統(tǒng)的重要性與功能運(yùn)輸——指借助公共運(yùn)輸線及其設(shè)施和運(yùn)輸工具來實(shí)現(xiàn)人與物空間位移的一種經(jīng)濟(jì)活動(dòng)和社會(huì)活動(dòng)。交通——與運(yùn)輸反映的同一過程的兩個(gè)方面。同一過程：運(yùn)輸工具在運(yùn)輸網(wǎng)路上的流動(dòng)；兩個(gè)方面：交通關(guān)心的是運(yùn)輸工具的流動(dòng)情況(流量的大小、擁擠的程度)運(yùn)輸關(guān)心的是流動(dòng)中的運(yùn)輸工具上的載運(yùn)情況(載人與物的有無與多少，將其輸送了多遠(yuǎn)的距離)運(yùn)輸是交通的目的運(yùn)輸系統(tǒng)的重要性地域分工專業(yè)化規(guī)模經(jīng)濟(jì)競爭加劇土地價(jià)值的提高當(dāng)前第3頁\共有103頁\編于星期四\20點(diǎn)交通運(yùn)輸系統(tǒng)的構(gòu)成要素：（1）運(yùn)載工具（2）通路（3）場站（4）動(dòng)力（5）通信（6）經(jīng)營管理人員和經(jīng)營機(jī)構(gòu)產(chǎn)品轉(zhuǎn)移運(yùn)輸克服了產(chǎn)品在生產(chǎn)與需求之間存在的空間和時(shí)間上的差異。產(chǎn)品存儲(chǔ)對產(chǎn)品進(jìn)行臨時(shí)存儲(chǔ)是指將運(yùn)輸車輛臨時(shí)作為相當(dāng)昂貴的存儲(chǔ)設(shè)施。運(yùn)輸?shù)墓δ墚?dāng)前第4頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸服務(wù)的特征運(yùn)輸服務(wù)是一種特殊的產(chǎn)品：運(yùn)輸服務(wù)產(chǎn)品具有無形性運(yùn)輸服務(wù)的生產(chǎn)和消費(fèi)不可分離運(yùn)輸服務(wù)具有不可存儲(chǔ)性異質(zhì)性，即同一種服務(wù)的質(zhì)量差別

當(dāng)前第5頁\共有103頁\編于星期四\20點(diǎn)6.2運(yùn)輸方式及其特征一、鐵路運(yùn)輸鐵路是國民經(jīng)濟(jì)的大動(dòng)脈，鐵路運(yùn)輸是我國貨物運(yùn)輸?shù)闹饕绞?。鐵路運(yùn)輸?shù)闹饕攸c(diǎn)是能夠遠(yuǎn)距離運(yùn)輸大量貨物。由于世界上幾乎所有的大都市、我國的絕大部分城市都通鐵路，鐵路在國際、國內(nèi)運(yùn)輸中占有相當(dāng)大的市場份額。雖然設(shè)備和站點(diǎn)等的限制使得鐵路運(yùn)營的固定成本很高，但是鐵路運(yùn)營的變動(dòng)成本（如維修、管理、耗能等）相對較低，這也使得鐵路運(yùn)輸?shù)目偝杀就ǔ１裙泛秃娇者\(yùn)輸?shù)?。高固定成本和低變?dòng)成本使鐵路運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)十分明顯。當(dāng)前第6頁\共有103頁\編于星期四\20點(diǎn)鐵路運(yùn)輸鐵路運(yùn)輸方式的主要優(yōu)點(diǎn)：運(yùn)輸能力大運(yùn)行速度較快，時(shí)速一般在80～120公里適應(yīng)性強(qiáng)，受天氣限制條件少，安全可靠性高運(yùn)輸成本低環(huán)境污染小，環(huán)境成本低

鐵路運(yùn)輸方式的主要缺點(diǎn)：靈活性差對包裝的要求較高存在貨物被偷盜的危險(xiǎn)鐵路設(shè)施修建成本較高，占地多。

綜合考慮，鐵路適于在內(nèi)陸地區(qū)作為長途、大批量運(yùn)送低價(jià)值、高密度的一般貨物和可靠性要求高的特種貨物；從投資的情況來看，在運(yùn)輸量比較大的地區(qū)之間建設(shè)鐵路較為合理。

當(dāng)前第7頁\共有103頁\編于星期四\20點(diǎn)6.2運(yùn)輸方式及其特征二、公路運(yùn)輸公路運(yùn)輸具有規(guī)模巨大，分布極廣的道路基礎(chǔ)設(shè)施體系和機(jī)動(dòng)靈活、適應(yīng)性強(qiáng)的車輛裝備系統(tǒng)。大多數(shù)的消費(fèi)品都是通過公路運(yùn)輸?shù)?。公路運(yùn)輸是任何公司物流系統(tǒng)中重要的一部分。公路運(yùn)輸?shù)墓潭ǔ杀竞艿?。汽車承運(yùn)人在固定基礎(chǔ)設(shè)施的投資相對較少，多數(shù)公路的建設(shè)運(yùn)營由政府進(jìn)行。公路運(yùn)輸?shù)淖儎?dòng)成本相對較高，因?yàn)楣返慕ㄔO(shè)和維修費(fèi)用經(jīng)常是以稅收和收費(fèi)站的形式向承運(yùn)人征收的。此外，汽車的能耗、維修費(fèi)用相對也比較高。燃油稅當(dāng)前第8頁\共有103頁\編于星期四\20點(diǎn)公路運(yùn)輸公路運(yùn)輸方式的主要優(yōu)點(diǎn)：原始投資少，資金周轉(zhuǎn)快，投資回收期短機(jī)動(dòng)靈活，門對門運(yùn)輸快捷可控包裝成本低，貨物損失小公路運(yùn)輸?shù)闹饕秉c(diǎn)：運(yùn)輸能力小勞動(dòng)生產(chǎn)率低，單位運(yùn)價(jià)高公路擁擠與污染，環(huán)境成本高

公路運(yùn)輸不像其它運(yùn)輸方式那樣受到各種線路的限制，其市場覆蓋面要高于其它運(yùn)輸方式。公路運(yùn)輸?shù)奶攸c(diǎn)使得公路運(yùn)輸尤其適于短距離、高價(jià)值產(chǎn)品的裝運(yùn)，在中間產(chǎn)品和輕工產(chǎn)品的運(yùn)輸方面有較大的優(yōu)勢。當(dāng)前第9頁\共有103頁\編于星期四\20點(diǎn)6.2運(yùn)輸方式及其特征三、水路運(yùn)輸水路運(yùn)輸在世界外貿(mào)運(yùn)輸中始終保持主導(dǎo)地位，在經(jīng)濟(jì)合作和交流中起著紐帶作用。受自然條件的制約，水路運(yùn)輸?shù)倪\(yùn)營范圍和運(yùn)輸速度受到限制，但是卻有其它運(yùn)輸方式不可比擬的優(yōu)勢和潛力。水運(yùn)中水道的改良維護(hù)通常由政府負(fù)責(zé)，港口的開發(fā)和維護(hù)各國不同，但一般也由政府統(tǒng)一進(jìn)行，而運(yùn)輸公司只需支付一定的費(fèi)用就可以使用港口和其它碼頭設(shè)施。因此，在固定成本方面，水路運(yùn)輸在鐵路和公路運(yùn)輸之間。水路運(yùn)輸?shù)淖儎?dòng)成本較低，主要包括運(yùn)營中的成本，其規(guī)模經(jīng)濟(jì)的效應(yīng)更加明顯。當(dāng)前第10頁\共有103頁\編于星期四\20點(diǎn)水路運(yùn)輸水路運(yùn)輸方式的主要優(yōu)點(diǎn)：單位運(yùn)輸工具的裝載量大，運(yùn)輸能力高，運(yùn)輸距離長水路運(yùn)輸成本低，基礎(chǔ)設(shè)施投資節(jié)省，單位運(yùn)價(jià)低廉能源消耗少水路運(yùn)輸方式的主要缺點(diǎn)：運(yùn)輸速度慢受天氣和其它自然條件影響大，線路迂回貨物破損較多可靠性差

與上述特點(diǎn)相對應(yīng)，水路運(yùn)輸適于運(yùn)送數(shù)量巨大、低價(jià)值、時(shí)效性要求不高的貨物，如礦石、煤炭、石油農(nóng)產(chǎn)品等。水路運(yùn)輸是大宗貨物長距離運(yùn)輸?shù)睦硐脒x擇。

當(dāng)前第11頁\共有103頁\編于星期四\20點(diǎn)6.2運(yùn)輸方式及其特征四、航空運(yùn)輸航空貨運(yùn)的主要優(yōu)點(diǎn)在于運(yùn)輸速度快。隨著航空運(yùn)輸技術(shù)的不斷成熟，航空運(yùn)輸在遠(yuǎn)距離運(yùn)輸，特別是跨國運(yùn)輸中顯示出無可比擬的優(yōu)勢。只有在運(yùn)輸高價(jià)值的和對時(shí)效性要求高于對成本要求的產(chǎn)品時(shí)，航空運(yùn)輸才有其合理性。航空的固定成本較低。空中航線和管制系統(tǒng)由國家擁有，航空港的建設(shè)運(yùn)營由國家投資，航空公司的固定成本主要與購買飛機(jī)有關(guān)，也與所需的搬運(yùn)系統(tǒng)和貨物集裝箱有關(guān)。航空運(yùn)輸?shù)淖儎?dòng)成本是極高的，其燃料消耗、飛行器的維修保養(yǎng)以及飛行人員和地勤人員的費(fèi)用都是一筆可觀的支出。當(dāng)前第12頁\共有103頁\編于星期四\20點(diǎn)航空運(yùn)輸航空運(yùn)輸?shù)闹饕獌?yōu)點(diǎn)：運(yùn)行速度快靈活、機(jī)動(dòng)性大航空運(yùn)輸服務(wù)質(zhì)量高、安全可靠航空運(yùn)輸?shù)闹饕秉c(diǎn)：運(yùn)輸成本高運(yùn)輸能力小有些貨物禁用空運(yùn)受天氣影響較大

綜合上述優(yōu)缺點(diǎn)，航空運(yùn)輸適用于長途旅客運(yùn)輸和緊急需要的、時(shí)效性要求高的、單位價(jià)值高的貨物運(yùn)輸。當(dāng)前第13頁\共有103頁\編于星期四\20點(diǎn)6.2運(yùn)輸方式及其特征五、管道運(yùn)輸管道是很獨(dú)特的運(yùn)輸方式，它所能運(yùn)送的貨物種類很有限，主要通過管道運(yùn)輸?shù)呢浳锸牵菏图俺善酚汀⑻烊粴?、化學(xué)制品。管道運(yùn)輸?shù)膬?yōu)勢：費(fèi)用低。貨損、貨差率低。另外，因?yàn)楣艿肋\(yùn)輸速度很慢，還可以將管道作為倉庫?？煽啃院?、不受天氣影響、很少有機(jī)械故障管道運(yùn)輸?shù)娜秉c(diǎn)：管道線路是相對固定的，因此有地域靈活性或可達(dá)性的限制。管道運(yùn)輸?shù)漠a(chǎn)品有局限性，并且只能提供單向服務(wù)。當(dāng)前第14頁\共有103頁\編于星期四\20點(diǎn)各種運(yùn)輸方式技術(shù)經(jīng)濟(jì)特征比較表運(yùn)輸方式基建投資運(yùn)載量運(yùn)輸成本速度連續(xù)性靈活性生產(chǎn)率安全性線路運(yùn)具鐵路622431343河運(yùn)343266424海運(yùn)131155515公路455522166管道514343631航空266614252

注：表中數(shù)字表示各種運(yùn)輸方式在某一方面的優(yōu)劣次序。當(dāng)前第15頁\共有103頁\編于星期四\20點(diǎn)影響運(yùn)輸決策的成本因素影響承運(yùn)人定價(jià)的成本因素與運(yùn)距有關(guān)的成本與運(yùn)量有關(guān)的成本與速度有關(guān)的成本直送v.s中轉(zhuǎn)影響承運(yùn)人運(yùn)力組合的成本因素固定成本運(yùn)營成本當(dāng)前第16頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸特性規(guī)模特性隨著一次裝運(yùn)量的增大，使每單位重量的運(yùn)輸成本下降。距離特性隨著一次運(yùn)輸距離的增加，運(yùn)輸費(fèi)用的增加會(huì)變的越來越緩慢，或者說單位運(yùn)輸距離的費(fèi)用減少，運(yùn)輸成本與一次運(yùn)輸?shù)木嚯x有關(guān)。速度特性完成特定的運(yùn)輸所需的時(shí)間越短，其效用價(jià)值越高。單位貨物運(yùn)輸成本運(yùn)輸距離距離與運(yùn)輸成本的關(guān)系單位貨物運(yùn)輸成本裝載重量載重量與運(yùn)輸成本的關(guān)系運(yùn)輸效用送達(dá)時(shí)間送達(dá)時(shí)間與運(yùn)輸效用的關(guān)系當(dāng)前第17頁\共有103頁\編于星期四\20點(diǎn)影響承運(yùn)人運(yùn)力組合的成本因素當(dāng)前第18頁\共有103頁\編于星期四\20點(diǎn)n——thenumberoftimeperiodsintowhichthetimehorizonofayearisdecomposed(forexample,n=52ifthetimeperiodcorrespondstoaweek)v——thedecisionvariablecorrespondingtothenumberofownedvehiclesvt,t=1,...,n,therequirednumberofvehiclesattimeperiodt;m——thenumberoftimeperiodsperyearinwhichvt>v.cF——fixedcost（anownedvehicle）cV——variablecost（anownedvehicle）cH——bethecostpertimeperiodofhiringavehicle(clearly,cF+cV<cH).當(dāng)前第19頁\共有103頁\編于星期四\20點(diǎn)AsthetwosummationsinEquationareequaltotheareasbelowandabovethelinevt=v,respectively,thentheirderivativesareequaltomand?m,respectively.Consequently,C(v)isminimalwhen當(dāng)前第20頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第21頁\共有103頁\編于星期四\20點(diǎn)影響托運(yùn)人決策的成本因素服務(wù)水平成本（運(yùn)輸時(shí)間-速度）運(yùn)輸成本（運(yùn)輸方式、運(yùn)輸規(guī)模）庫存成本交易成本當(dāng)前第22頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸服務(wù)的選擇

運(yùn)輸成本、速度和對庫存的影響是決策者心目中最重要的運(yùn)輸服務(wù)要素，因此，這三項(xiàng)是運(yùn)輸服務(wù)選擇的基礎(chǔ)。運(yùn)輸對庫存的影響有以下幾點(diǎn)：較慢的運(yùn)輸模式會(huì)引起較大的中轉(zhuǎn)或運(yùn)輸庫存；較大運(yùn)量的運(yùn)輸方式會(huì)出現(xiàn)訂單批量超過需求量的情況，從而增加庫存；不可靠的運(yùn)輸模式會(huì)引起安全庫存的提高。在選擇運(yùn)輸方式時(shí)，就需要考慮庫存持有成本可能升高，而抵消運(yùn)輸服務(wù)成本降低的情況。當(dāng)前第23頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸服務(wù)的選擇的定量分析法基于運(yùn)輸成本與庫存成本的總成本分析方法【例】某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位置B的公司自有倉庫，年運(yùn)量D=700000件，產(chǎn)品價(jià)值C=30元，年存貨成本I=產(chǎn)品價(jià)格的30％。公司希望選擇使總成本最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫存成本可以減少1％。各種運(yùn)輸服務(wù)方式的有關(guān)參數(shù)見表：當(dāng)前第24頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸服務(wù)的選擇的定量分析法運(yùn)輸方式費(fèi)率R(元/件)時(shí)間T(天)年運(yùn)送批次平均存貨量Q/2鐵路0.12110100000水運(yùn)0路0.252042000航空1.424020250考慮安全庫存當(dāng)前第25頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸服務(wù)的選擇的定量分析法分析：以年總成本最低為原則來選擇合適的運(yùn)輸方式。這里，總成本=運(yùn)輸費(fèi)用+庫存成本；其中，運(yùn)輸費(fèi)用=運(yùn)輸量費(fèi)率庫存成本=在途運(yùn)輸庫存成本+工廠存貨成本+倉庫存貨成本在途運(yùn)輸庫存費(fèi)用=ICDT/365工廠存貨成本=ICQ/2倉庫存貨成本=I（C+R）Q/2代入各種運(yùn)輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計(jì)算結(jié)果列入表2。D—年運(yùn)量；C—產(chǎn)品單價(jià)；I—年存貨成本（產(chǎn)品價(jià)格的30％）；T—運(yùn)輸時(shí)間；R—費(fèi)率(元/件)；Q/2—平均存貨量當(dāng)前第26頁\共有103頁\編于星期四\20點(diǎn)二、運(yùn)輸方式選擇的定量分析法由表中結(jié)果可知，總成本最低的是公路運(yùn)輸方式，總成本為984821元，其次是水路運(yùn)輸，成本最高的是鐵路運(yùn)輸。按照總成本最低的原則，適合選擇公路運(yùn)輸方式。成本類型計(jì)算公式鐵路運(yùn)輸水路運(yùn)輸公路運(yùn)輸航空運(yùn)輸運(yùn)輸成本RD70000105000140000980000在途庫存ICDT/3653452052416448630134521工廠存貨ICQ/2900000416500378000182250倉庫存貨I(C+R)Q/2903000420593380520190755總成本

221820511857379848211387526當(dāng)前第27頁\共有103頁\編于星期四\20點(diǎn)6.4運(yùn)輸路線的選擇1．起、止點(diǎn)不同的單一路徑規(guī)劃2．多個(gè)起、止點(diǎn)的路徑規(guī)劃3．起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃TravelingSalesmanProblem(TSP)VehicleRoutingProblem(VRP)當(dāng)前第28頁\共有103頁\編于星期四\20點(diǎn)6.4運(yùn)輸路線的選擇1．起、止點(diǎn)不同的單一路徑規(guī)劃這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎(chǔ)的問題之一。問題描述：假設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G（Vn,Em),并且圖中的每條弧（i,j)都有一個(gè)長度cij(或者費(fèi)用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點(diǎn)1到節(jié)點(diǎn)n距離最短（或費(fèi)用最低）的路徑。求解此類最短路徑問題，主要有以下幾種算法：（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法當(dāng)前第29頁\共有103頁\編于星期四\20點(diǎn)1．起、止點(diǎn)不同的單一路徑規(guī)劃例某運(yùn)輸公司簽訂了一項(xiàng)運(yùn)輸合同，要把A市的一批貨物運(yùn)送到B市，該公司根據(jù)這兩個(gè)城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡(luò)。圖中，圓圈也稱節(jié)點(diǎn)，代表起點(diǎn)、目的地和與行車路線相交的其他城市。鏈代表兩個(gè)結(jié)點(diǎn)之間的公路，每一條公路都標(biāo)明運(yùn)輸里程。A市B市當(dāng)前第30頁\共有103頁\編于星期四\20點(diǎn)解答：最短路的計(jì)算方法（1）找出第n個(gè)距起點(diǎn)最近的節(jié)點(diǎn)。對n=1,2,…，重復(fù)此過程，直到所找出的最近節(jié)點(diǎn)是終點(diǎn)。（2）在前面的迭代過程中找出（n-1）個(gè)距起點(diǎn)最近的節(jié)點(diǎn)，及其距起點(diǎn)最短的中徑和距離，這些節(jié)點(diǎn)和起點(diǎn)統(tǒng)稱為已解的節(jié)點(diǎn)，其余的稱為未解節(jié)點(diǎn)。（3）每個(gè)已解的節(jié)點(diǎn)和一個(gè)或多外未解的節(jié)點(diǎn)相連接，就可以得出一個(gè)候選點(diǎn)—連接距離最短的未解點(diǎn)。如果有多個(gè)距離相等的最短連接，則有多個(gè)候選點(diǎn)。（4）將每個(gè)已解節(jié)點(diǎn)與其候選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起點(diǎn)之間最短路徑的距離上，所得出的總距離最短的候選點(diǎn)就是第n個(gè)最近的節(jié)點(diǎn)，其最短路徑就是得出該距離的路徑（若多個(gè)候選點(diǎn)都得出相等的最短距離，則都是已解節(jié)點(diǎn)）。當(dāng)前第31頁\共有103頁\編于星期四\20點(diǎn)步驟直接連接到未解節(jié)點(diǎn)的已解節(jié)點(diǎn)與其直接連接的未解結(jié)點(diǎn)相關(guān)總成本第n個(gè)最近解點(diǎn)最小成本最新連接11123411241-22122345114+7=114+2=6562-5312553446114+7=116+3=96+8=14495-4414453366119+1=109+4=136+8=143104-3534566610+2=129+4=136+8=146123-6通過上表的計(jì)算，最短路徑為1-2-5-4-3-6，最短距離為12。當(dāng)前第32頁\共有103頁\編于星期四\20點(diǎn)Floyd算法F算法的基本思路:F算法使用距離矩陣和路由矩陣。距離矩陣是一個(gè)n╳n矩陣，以圖G的n個(gè)節(jié)點(diǎn)為行和列。記為W=[wij

]n╳n，wij表示圖G中vi和vj兩點(diǎn)之間的路徑長度。路由矩陣是一個(gè)n╳n矩陣，以圖G的n個(gè)節(jié)點(diǎn)為行和列。記為R=[rij

]n╳n

，其中rij表示vi至vj經(jīng)過的轉(zhuǎn)接點(diǎn)（中間節(jié)點(diǎn)）。F算法的思路是首先寫出初始的W陣和R陣，接著按順序依次將節(jié)點(diǎn)集中的各個(gè)節(jié)點(diǎn)作為中間節(jié)點(diǎn)，計(jì)算此點(diǎn)距其他各點(diǎn)的徑長，每次計(jì)算后都以求得的與上次相比較小的徑長去更新前一次較大徑長，若后求得的徑長比前次徑長大或相等則不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間節(jié)點(diǎn)，（按順序，后面的點(diǎn)不作為中間節(jié)點(diǎn)）考察所有通過此中間節(jié)點(diǎn)的路徑當(dāng)前第33頁\共有103頁\編于星期四\20點(diǎn)31056154123451－310∞∞23－∞5∞310∞－6154∞56－45∞∞∞4－W0123451－234521－345312－454123－551234－R0當(dāng)前第34頁\共有103頁\編于星期四\20點(diǎn)31056154123451－310∞∞23－135∞31013－6154∞56－45∞∞∞4－W1123451－234521－145311－454123－551234－R1當(dāng)前第35頁\共有103頁\編于星期四\20點(diǎn)31056154123451－3108∞23－135∞31013－6154856－45∞∞∞4－W2123451－232521－145311－454223－551234－R2當(dāng)前第36頁\共有103頁\編于星期四\20點(diǎn)31056154123451－31082523－1352831013－6154856－45∞∞∞4－W3123451－232321－143311－454223－551234－R3當(dāng)前第37頁\共有103頁\編于星期四\20點(diǎn)31056154123451－31081223－115931011－6104856－45129104－D4123451－232421－444314－444223－554444－S4當(dāng)前第38頁\共有103頁\編于星期四\20點(diǎn)2．多個(gè)起、止點(diǎn)的路徑規(guī)劃當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)要找到供貨地、目的地之間的最佳路徑。例

某公司下屬三個(gè)倉庫，供應(yīng)四個(gè)客戶的需要，三個(gè)倉庫的供應(yīng)量和四個(gè)客戶的需求量，以及由各倉庫到各客戶的運(yùn)輸單價(jià)如下表所示。求運(yùn)輸費(fèi)用最少的運(yùn)輸方案。

銷地客戶1客戶2客戶3客戶4供應(yīng)量運(yùn)價(jià)產(chǎn)地倉庫A311310700倉庫B1928400倉庫C74105900需求量3006005006002000當(dāng)前第39頁\共有103頁\編于星期四\20點(diǎn)表上做業(yè)法，該方法適合于對相對簡單的問題進(jìn)行求解，求解過程方便直觀，而且由于計(jì)算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個(gè)基本步驟：（1）確定初始調(diào)運(yùn)方案最小元素法是按運(yùn)價(jià)表依次挑選運(yùn)費(fèi)小的供-需點(diǎn)組合，盡量優(yōu)先安排運(yùn)費(fèi)最低組合的方法。3113101928734105

銷地客戶1客戶2客戶3客戶4供應(yīng)量運(yùn)價(jià)產(chǎn)地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600表5.4初始調(diào)運(yùn)方案當(dāng)前第40頁\共有103頁\編于星期四\20點(diǎn)（2）初始方案的檢驗(yàn)最優(yōu)方案的數(shù)字特征———檢驗(yàn)數(shù)：閉回路：從理論上講，對于表上作業(yè)法的初始方案來說，從調(diào)運(yùn)方案表上的一個(gè)空格出發(fā)，存在一條且僅存在一條以該空格（用xij表示）為起點(diǎn)，以其他填有數(shù)字的點(diǎn)為其他頂點(diǎn)的閉合回路，簡稱閉回路。這個(gè)閉回路有以下性質(zhì)：每個(gè)頂點(diǎn)都是轉(zhuǎn)角點(diǎn)；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點(diǎn)，則必有兩個(gè)。只有從空格出發(fā)，其余各轉(zhuǎn)角點(diǎn)所對應(yīng)的方格內(nèi)均填寫數(shù)字時(shí)，所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。當(dāng)前第41頁\共有103頁\編于星期四\20點(diǎn)

銷地客戶1客戶2客戶3客戶4供應(yīng)量產(chǎn)地倉庫A400300700倉庫B300100400倉庫C600300900需求量300600500600

表6.5給出了單元格（1，1）和（3，1）所形成的閉回路：（1，1）—（1,3）—(2，3)—（2，1）—（1，1）；（3，1）—（2，1）—（2，3）—（1，3）—（1，4）—（3，4）—（3，1）。其他空格的閉回路與此同理。

在調(diào)運(yùn)方案內(nèi)的每個(gè)空格所形成的閉回路上，作單位物資的運(yùn)量調(diào)整，總可以計(jì)算出相應(yīng)的運(yùn)費(fèi)是增加還是減少。我們把所計(jì)算出來的每條閉回路上調(diào)整單位運(yùn)量而使運(yùn)輸費(fèi)用發(fā)生變化的增減值，稱其為檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)小于0，表示在該空格的閉回路上調(diào)整運(yùn)量會(huì)使運(yùn)費(fèi)減少；相反，如果檢驗(yàn)數(shù)大于0，則會(huì)使運(yùn)費(fèi)增加。表8.5初始調(diào)運(yùn)方案當(dāng)前第42頁\共有103頁\編于星期四\20點(diǎn)用閉回路法求檢驗(yàn)數(shù)時(shí)，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，這種計(jì)算很繁，可以用較為簡便的方法“位勢法”求解。設(shè)u1,u2,…,um；v1,v2,…,vn，是對應(yīng)運(yùn)輸問題的m+n個(gè)約束條件的對偶變量。在初始調(diào)運(yùn)方案中x13,x14,x21,x23,x32,x34是基變量，這時(shí)對應(yīng)的檢驗(yàn)數(shù)是：基變量檢驗(yàn)數(shù)x21c21-(u2+v1)=0設(shè)v1=0，并且c21=1所以u2=1x23c23-(u2+v3)=02-(u2+v3)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0x34c34-(u3+v4)=05-(u3+v4)=0x22c22-(u2+v2)=04-(u2+v2)=0當(dāng)前第43頁\共有103頁\編于星期四\20點(diǎn)通過這些方程可以求得u1=2u2=1u3=-3v1=0v2=7v3=1v4=8在初始解調(diào)運(yùn)方案中增加一行一列，在列中填入ui,在行中填入vi。接著，按σij=cij-(ui+vj)計(jì)算所有空格的檢驗(yàn)數(shù)。完成后的表格見表5.6。3113101928734105

銷地客戶1客戶2客戶3客戶4ui運(yùn)價(jià)產(chǎn)地倉庫A12002倉庫B010-11倉庫C100120-3vi0718表5.6檢驗(yàn)數(shù)表格當(dāng)前第44頁\共有103頁\編于星期四\20點(diǎn)（3）方案調(diào)整判定一個(gè)初始調(diào)運(yùn)方案不是最優(yōu)調(diào)運(yùn)方案的標(biāo)準(zhǔn)，是在檢驗(yàn)數(shù)表格中出現(xiàn)負(fù)值的檢驗(yàn)數(shù)。如果檢驗(yàn)數(shù)的負(fù)值不止個(gè)時(shí)，一般選擇負(fù)檢驗(yàn)數(shù)絕對值最大的空格作為具體調(diào)整對象。從表5.6可以發(fā)現(xiàn)，單元格x24的檢驗(yàn)數(shù)是負(fù)數(shù)，因此對其進(jìn)行調(diào)整，具體過程如表5.7所示。x13400+100=500x14300-100=200x23100-100=0x240+100=100表5.7調(diào)動(dòng)方案調(diào)整表

從單元格x24開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點(diǎn)中挑選運(yùn)量的最小數(shù)值作為調(diào)整量。在此將x23單元格的100作為調(diào)整量，將亮個(gè)數(shù)填入單元格x24內(nèi)，同時(shí)調(diào)整該閉回路中其他轉(zhuǎn)角點(diǎn)上的運(yùn)量，使各行、列保持原來的供需平衡，這樣注得到一個(gè)新的調(diào)運(yùn)方案，如表5.7所示。當(dāng)前第45頁\共有103頁\編于星期四\20點(diǎn)3113101928734105

銷地客戶1客戶2客戶3客戶4供應(yīng)量

運(yùn)價(jià)產(chǎn)地倉庫A500200700倉庫B300100400倉庫C600300900需求量300600500600表6.7調(diào)整后的方案按新方案計(jì)算調(diào)運(yùn)物資的運(yùn)輸費(fèi)用為：3×500+10×200+8×100+4×600+5×300=8500元新方案是否最優(yōu)方案，還需再進(jìn)行檢驗(yàn)。經(jīng)計(jì)算，該新方案的所有檢驗(yàn)數(shù)都是非負(fù)數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。當(dāng)前第46頁\共有103頁\編于星期四\20點(diǎn)運(yùn)輸方案的改進(jìn)的改進(jìn)→找出檢驗(yàn)數(shù)ij為最小負(fù)值的格子的閉回路→在滿足所有約束條件的情況下，盡可能增大這個(gè)格子的xij值→調(diào)整此閉回路上其他頂點(diǎn)的值→檢驗(yàn)新解的最優(yōu)性→重復(fù)上步驟直至得到最優(yōu)解為止。當(dāng)前第47頁\共有103頁\編于星期四\20點(diǎn)3．起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃起點(diǎn)和終點(diǎn)重合的路徑問題一般被稱為“旅行商”問題（TSP,TravelingSalesmanProblem），是運(yùn)籌學(xué)、圖論和組合優(yōu)化中的典型問題。

TSP問題一般描述如下：一個(gè)旅行者從出發(fā)地出發(fā)，經(jīng)過所有要到達(dá)的城市后，返回到出發(fā)地，要求合理安排其旅行路線，使得總旅行距離（或旅行費(fèi)用、旅行時(shí)間等）最短。TSP問題特性：單一車輛無車輛容量限制求解復(fù)雜度屬于NP-hard，大規(guī)模問題難以求得最佳解，現(xiàn)實(shí)中常采取”啟發(fā)式方法(Heuristics)“求解當(dāng)前第48頁\共有103頁\編于星期四\20點(diǎn)TSP問題數(shù)學(xué)規(guī)劃模型

Mins.t.當(dāng)前第49頁\共有103頁\編于星期四\20點(diǎn)TSP問題求解算法真正解法(只能處理非常小的問題)Enumeration窮舉法Assignmentalgorithm指派算法Little’smethod分枝定界法(Branch-and-Bound)傳統(tǒng)啟發(fā)式解法(Heuristics)大致可歸納為以下三種：路線構(gòu)建(routeconstruction)鄰點(diǎn)法、插入法….路線改善(routeimprovement)k-Opt交換法、Or-Opt交換法……綜合型(composite)合并執(zhí)行路線構(gòu)建及路線改善當(dāng)前第50頁\共有103頁\編于星期四\20點(diǎn)AssignmentProcedureForTSP1、將A到A，B到B,C到C…的費(fèi)用轉(zhuǎn)換成無限大，以防止返回。當(dāng)前第51頁\共有103頁\編于星期四\20點(diǎn)AssignmentProcedureForTSP2、應(yīng)用指派問題的匈牙利算法，使得表中不同行、不同列都含有0此時(shí)，若完成路徑的選擇，最少的費(fèi)用為9當(dāng)前第52頁\共有103頁\編于星期四\20點(diǎn)AssignmentProcedureForTSP可行解尚未找到。此時(shí)考慮增加一個(gè)“費(fèi)用最小的非0路徑”，看看是否有可行解。得到：仍然沒有可行解。此時(shí)考慮再增加一個(gè)“費(fèi)用最小的非0路徑”，或增加一個(gè)“費(fèi)用次小的非0”路徑看看是否有可行解。得到：當(dāng)前第53頁\共有103頁\編于星期四\20點(diǎn)Little’smethod分枝定界法(Branch-and-Bound)1、計(jì)算出所有不走“0費(fèi)用”路徑的懲罰成本2、選擇懲罰成本最大的路徑當(dāng)前第54頁\共有103頁\編于星期四\20點(diǎn)3、簡化計(jì)算表，消除已經(jīng)選擇的路徑，形成新的計(jì)算表；繼續(xù)分支定界。同時(shí)，為了防止返回，E到C設(shè)為∞；再檢查是否每一行、每一列都有“0費(fèi)用”路徑，若沒有在此行/列減去最小元素。E行減去1，得到：當(dāng)前第55頁\共有103頁\編于星期四\20點(diǎn)D同時(shí)，為了防止返回，E到B設(shè)為∞；再檢查是否每一行、每一列都有“0費(fèi)用”路徑，若沒有在此行/列減去最小元素。A列減去1，得到：當(dāng)前第56頁\共有103頁\編于星期四\20點(diǎn)假設(shè)選擇E,D路徑，得到：當(dāng)前第57頁\共有103頁\編于星期四\20點(diǎn)假設(shè)不選擇E,D路徑：當(dāng)前第58頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第59頁\共有103頁\編于星期四\20點(diǎn)傳統(tǒng)啟發(fā)式解法1、最近鄰點(diǎn)法(Nearest-neighborHeuristic)任選一節(jié)點(diǎn)為起點(diǎn)x尋找距離節(jié)點(diǎn)x最近的節(jié)點(diǎn)y作為下一個(gè)造訪的節(jié)點(diǎn)尋找距離節(jié)點(diǎn)y最近的節(jié)點(diǎn)z作為下一個(gè)造訪的節(jié)點(diǎn)重復(fù)以上步驟，直到所有節(jié)點(diǎn)均已造訪連接最后一個(gè)節(jié)點(diǎn)與起點(diǎn)，即形成一個(gè)TSP的可行解當(dāng)前第60頁\共有103頁\編于星期四\20點(diǎn)1、最近鄰點(diǎn)法7438755348123451－473824－755377－344353－858548－當(dāng)前第61頁\共有103頁\編于星期四\20點(diǎn)2、插入法(InsertionMethod)任選一節(jié)點(diǎn)為起點(diǎn)a尋找距離節(jié)點(diǎn)a最近的節(jié)點(diǎn)b作為下一個(gè)造訪的節(jié)點(diǎn)，形成a-b-a的子回路尋找距離子回路最近的節(jié)點(diǎn)k作為下一個(gè)插入點(diǎn)尋找插入成本最小的位置(i-j)，將k插入i-j之間，形成新的子回路。插入成本：Cik+Ckj-Cij重復(fù)步驟3~4，直到所有節(jié)點(diǎn)均已插入回路之中，即形成一個(gè)TSP的可行解當(dāng)前第62頁\共有103頁\編于星期四\20點(diǎn)2、插入法74387553483373377455774488844558454當(dāng)前第63頁\共有103頁\編于星期四\20點(diǎn)3、2-opt交換法先構(gòu)建一個(gè)起始可行解在可行解中任選兩個(gè)不相鄰的節(jié)線(a

b,c

d)，以及另外兩條對應(yīng)之替換節(jié)線(a

c,b

d)，計(jì)算替換后總成本是否降低(即檢查替換成本是否小于0)。

?替換成本：Cac+Cbd-Cab-Ccd(對稱型TSP)若替換后總成本有降低，則予以替換，同時(shí)變更中間相關(guān)弧線的行走方向重復(fù)步驟2~3，直到所有可能的替換均無法再降低成本為止當(dāng)前第64頁\共有103頁\編于星期四\20點(diǎn)3、2-opt交換法7438755348當(dāng)前第65頁\共有103頁\編于星期四\20點(diǎn)4、常見的宏啟發(fā)式方法(Meta-heuristics)禁忌搜索法(TabuSearch,TS)基因算法(GeneticAlgorithm,GA)模擬退火法(SimulatedAnnealing,SA)門限值接受法(ThresholdAccepting,TA)神經(jīng)網(wǎng)絡(luò)(NeuralNetwork,NN)蟻群算法(AntColonyOptimization,ACO)其它當(dāng)前第66頁\共有103頁\編于星期四\20點(diǎn)6.4車輛路線、時(shí)間安排車輛路線安排車輛路線安排問題（VRP,VehicleRoutingProblem）是指對物流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問題一般可以描述如下：對一系列裝貨點(diǎn)或（和）卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等）。該問題涉及了多輛交通工具的服務(wù)對象的選擇和路徑（服務(wù)順序）確定兩方面的問題

VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過的基本問題（如旅行商問題、指派問題、最短路問題等），再使用相對比較成熟的基本理論和方法進(jìn)行求解。當(dāng)前第67頁\共有103頁\編于星期四\20點(diǎn)運(yùn)用VRP模型對實(shí)際問題進(jìn)行研究時(shí)，一般需要考慮以下幾個(gè)方面的問題：（1）倉庫。倉庫的級(jí)數(shù)，每級(jí)倉庫的數(shù)量、地點(diǎn)和規(guī)模。（2）車輛。車輛的型號(hào)和數(shù)量，每種車輛的容積和運(yùn)作費(fèi)用，出發(fā)時(shí)間和返回時(shí)間，司機(jī)休息時(shí)間，最大的里程和時(shí)間限制。（3）時(shí)間窗口。由于各處的工作時(shí)間不同，每個(gè)站點(diǎn)每天只允許在特定的時(shí)間內(nèi)取貨和/或送貨。（4）顧客。顧客需求，裝載、卸載，所處的地理位置，分離需求，優(yōu)先等級(jí)。（5）道路信息。車流密度，道路交通費(fèi)用，距離或時(shí)間屬性。（6）貨物信息。貨物的種類多少，兼容性，貨物的保鮮。（7）運(yùn)輸規(guī)章。工人每天的工作時(shí)間，車輛的周期維護(hù)。當(dāng)前第68頁\共有103頁\編于星期四\20點(diǎn)（1）安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。（2）安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)各日服務(wù)的站點(diǎn)不同，就應(yīng)該對一周內(nèi)每天的路線和時(shí)刻表問題分別進(jìn)行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)避免重疊。（3）從距倉庫最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線（4）卡車的行車路線應(yīng)呈水滴狀。（5）盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的。（6）取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。（7）對過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式。（8）避免時(shí)間窗口過短。簡化的原則：當(dāng)前第69頁\共有103頁\編于星期四\20點(diǎn)整數(shù)規(guī)劃法（IntegerProgramming）啟發(fā)式方法（Heuristics）節(jié)約法（ClarkeandWrightProcedure）兩階段法ETS(ExtensionofTravelingSalesmanProcedure)掃描法考慮返程Backtracking當(dāng)前第70頁\共有103頁\編于星期四\20點(diǎn)1、整數(shù)規(guī)劃法當(dāng)前第71頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第72頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第73頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第74頁\共有103頁\編于星期四\20點(diǎn)2、節(jié)約法（ClarkeandWrightProcedure）

節(jié)約法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點(diǎn)提供服務(wù)的卡車數(shù)量最少。該方法先假設(shè)每一個(gè)站點(diǎn)都有一輛虛擬的車輛提供服務(wù)，隨后返回倉庫，如圖(a)所示，這時(shí)的路線里程最長。下一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸車，相應(yīng)地縮短路線里程，選擇節(jié)約距離最多的一對站點(diǎn)合并在一起，修訂后的路線如圖(b)。d0,AdA,0d0,BdB,0ABO倉庫dA,Bd0,AdB,0a)初始路線里程=dO,A+dA,O+dO,B+dB,Ob)兩個(gè)站點(diǎn)合并后的路線里程=dO,A+dA,B+dB,O

節(jié)約里程：dA,O+dB,O-dA,B當(dāng)前第75頁\共有103頁\編于星期四\20點(diǎn)例：1、按距離中心的距離，從小到大排序2、計(jì)算出所有兩點(diǎn)間的節(jié)省距離，寫在左邊CapacityofaTruck=153、按照節(jié)約量，從大到小選取路線，同時(shí)滿足裝載量≤卡車容量當(dāng)前第76頁\共有103頁\編于星期四\20點(diǎn)4、形成一條路線，劃去已經(jīng)過的節(jié)點(diǎn)，繼續(xù)尋找其他路線當(dāng)前第77頁\共有103頁\編于星期四\20點(diǎn)兩階段法ETS

(ExtensionofTravelingSalesmanProcedure)第一階段：1、找到由TSP問題確定的行走路徑；2、根據(jù)貨車容量，初步給出各條貨車的行駛路徑。第二階段：根據(jù)貨車的剩余容量（Slack），對初步行駛路徑進(jìn)行調(diào)整。例：CapacityofaTruck=10當(dāng)前第78頁\共有103頁\編于星期四\20點(diǎn)ThetravelingsalesmanrouteisO-B-A-E-C-D-O根據(jù)貨車容量限制，初步給出各條貨車的行駛路徑，同時(shí)保證節(jié)省距離≥0第一階段：當(dāng)前第79頁\共有103頁\編于星期四\20點(diǎn)當(dāng)前第80頁\共有103頁\編于星期四\20點(diǎn)第二階段：從剩余容量（Slack）最大的線路開始，進(jìn)行節(jié)點(diǎn)的交換調(diào)整，并計(jì)算節(jié)點(diǎn)交換后的節(jié)約里程數(shù)，若為正，則可交換節(jié)點(diǎn)。剩余容量（Slack）最大的線路：O-E-O考慮E點(diǎn)相鄰的A點(diǎn)和C點(diǎn)。將C點(diǎn)交換到O-E-