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

六、運(yùn)輸決策及配送路線的優(yōu)化6.1運(yùn)輸系統(tǒng)的重要性與功能6.2根本運(yùn)輸方式及其運(yùn)營(yíng)特點(diǎn)6.3運(yùn)輸合理化6.4運(yùn)輸路線的選擇6.5車輛路線、時(shí)間安排.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ì)競(jìng)爭(zhēng)加劇土地價(jià)值的提高.交通運(yùn)輸系統(tǒng)的構(gòu)成要素：〔1〕運(yùn)載工具〔2〕通路〔3〕場(chǎng)站〔4〕動(dòng)力〔5〕通信〔6〕經(jīng)營(yíng)管理人員和經(jīng)營(yíng)機(jī)構(gòu)產(chǎn)品轉(zhuǎn)移運(yùn)輸克服了產(chǎn)品在生產(chǎn)與需求之間存在的空間和時(shí)間上的差異。產(chǎn)品存儲(chǔ)對(duì)產(chǎn)品進(jìn)行臨時(shí)存儲(chǔ)是指將運(yùn)輸車輛臨時(shí)作為相當(dāng)昂貴的存儲(chǔ)設(shè)施。運(yùn)輸?shù)墓δ?運(yùn)輸效勞的特征運(yùn)輸效勞是一種特殊的產(chǎn)品：運(yùn)輸效勞產(chǎn)品具有無形性運(yùn)輸效勞的生產(chǎn)和消費(fèi)不可別離運(yùn)輸效勞具有不可存儲(chǔ)性異質(zhì)性，即同一種效勞的質(zhì)量差異

.6.2運(yùn)輸方式及其特征一、鐵路運(yùn)輸鐵路是國(guó)民經(jīng)濟(jì)的大動(dòng)脈，鐵路運(yùn)輸是我國(guó)貨物運(yùn)輸?shù)闹饕绞?。鐵路運(yùn)輸?shù)闹饕攸c(diǎn)是能夠遠(yuǎn)距離運(yùn)輸大量貨物。由于世界上幾乎所有的大都市、我國(guó)的絕大局部城市都通鐵路，鐵路在國(guó)際、國(guó)內(nèi)運(yùn)輸中占有相當(dāng)大的市場(chǎng)份額。雖然設(shè)備和站點(diǎn)等的限制使得鐵路運(yùn)營(yíng)的固定本錢很高，但是鐵路運(yùn)營(yíng)的變動(dòng)本錢〔如維修、管理、耗能等〕相對(duì)較低，這也使得鐵路運(yùn)輸?shù)目偙惧X通常比公路和航空運(yùn)輸?shù)?。高固定本錢和低變動(dòng)本錢使鐵路運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)十清楚顯。.鐵路運(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)：靈活性差對(duì)包裝的要求較高存在貨物被偷盜的危險(xiǎn)鐵路設(shè)施修建本錢較高，占地多。綜合考慮，鐵路適于在內(nèi)陸地區(qū)作為長(zhǎng)途、大批量運(yùn)送低價(jià)值、高密度的一般貨物和可靠性要求高的特種貨物；從投資的情況來看，在運(yùn)輸量比較大的地區(qū)之間建設(shè)鐵路較為合理。.6.2運(yùn)輸方式及其特征二、公路運(yùn)輸公路運(yùn)輸具有規(guī)模巨大，分布極廣的道路根底設(shè)施體系和機(jī)動(dòng)靈活、適應(yīng)性強(qiáng)的車輛裝備系統(tǒng)。大多數(shù)的消費(fèi)品都是通過公路運(yùn)輸?shù)?。公路運(yùn)輸是任何公司物流系統(tǒng)中重要的一局部。公路運(yùn)輸?shù)墓潭ū惧X很低。汽車承運(yùn)人在固定根底設(shè)施的投資相對(duì)較少，多數(shù)公路的建設(shè)運(yùn)營(yíng)由政府進(jìn)行。公路運(yùn)輸?shù)淖儎?dòng)本錢相對(duì)較高，因?yàn)楣返慕ㄔO(shè)和維修費(fèi)用經(jīng)常是以稅收和收費(fèi)站的形式向承運(yùn)人征收的。此外，汽車的能耗、維修費(fèi)用相對(duì)也比較高。燃油稅.公路運(yùn)輸公路運(yùn)輸方式的主要優(yōu)點(diǎn)：原始投資少，資金周轉(zhuǎn)快，投資回收期短機(jī)動(dòng)靈活，門對(duì)門運(yùn)輸快捷可控包裝本錢低，貨物損失小公路運(yùn)輸?shù)闹饕秉c(diǎn)：運(yùn)輸能力小勞動(dòng)生產(chǎn)率低，單位運(yùn)價(jià)高公路擁擠與污染，環(huán)境本錢高

公路運(yùn)輸不像其它運(yùn)輸方式那樣受到各種線路的限制，其市場(chǎng)覆蓋面要高于其它運(yùn)輸方式。公路運(yùn)輸?shù)奶攸c(diǎn)使得公路運(yùn)輸尤其適于短距離、高價(jià)值產(chǎn)品的裝運(yùn)，在中間產(chǎn)品和輕工產(chǎn)品的運(yùn)輸方面有較大的優(yōu)勢(shì)。

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

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

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

綜合上述優(yōu)缺點(diǎn)，航空運(yùn)輸適用于長(zhǎng)途旅客運(yùn)輸和緊急需要的、時(shí)效性要求高的、單位價(jià)值高的貨物運(yùn)輸。.6.2運(yùn)輸方式及其特征五、管道運(yùn)輸管道是很獨(dú)特的運(yùn)輸方式，它所能運(yùn)送的貨物種類很有限，主要通過管道運(yùn)輸?shù)呢浳锸牵菏图俺善酚?、天然氣、化學(xué)制品。管道運(yùn)輸?shù)膬?yōu)勢(shì)：費(fèi)用低。貨損、貨差率低。另外，因?yàn)楣艿肋\(yùn)輸速度很慢，還可以將管道作為倉(cāng)庫(kù)?？煽啃院?、不受天氣影響、很少有機(jī)械故障管道運(yùn)輸?shù)娜秉c(diǎn)：管道線路是相對(duì)固定的，因此有地域靈活性或可達(dá)性的限制。管道運(yùn)輸?shù)漠a(chǎ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)劣次序。.影響運(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)營(yíng)本錢.運(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)系.影響承運(yùn)人運(yù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)..AsthetwosummationsinEquationareequaltotheareasbelowandabovethelinevt=v,respectively,thentheirderivativesareequaltomand?m,respectively.Consequently,C(v)isminimalwhen..影響托運(yùn)人決策的本錢因素效勞水平本錢〔運(yùn)輸時(shí)間-速度〕運(yùn)輸本錢〔運(yùn)輸方式、運(yùn)輸規(guī)模〕庫(kù)存本錢交易本錢.運(yùn)輸效勞的選擇運(yùn)輸本錢、速度和對(duì)庫(kù)存的影響是決策者心目中最重要的運(yùn)輸效勞要素，因此，這三項(xiàng)是運(yùn)輸效勞選擇的根底。運(yùn)輸對(duì)庫(kù)存的影響有以下幾點(diǎn)：較慢的運(yùn)輸模式會(huì)引起較大的中轉(zhuǎn)或運(yùn)輸庫(kù)存；較大運(yùn)量的運(yùn)輸方式會(huì)出現(xiàn)訂單批量超過需求量的情況，從而增加庫(kù)存；不可靠的運(yùn)輸模式會(huì)引起平安庫(kù)存的提高。在選擇運(yùn)輸方式時(shí)，就需要考慮庫(kù)存持有本錢可能升高，而抵消運(yùn)輸效勞本錢降低的情況。.運(yùn)輸效勞的選擇的定量分析法基于運(yùn)輸本錢與庫(kù)存本錢的總本錢分析方法【例】某公司欲將產(chǎn)品從位置A的工廠運(yùn)往位置B的公司自有倉(cāng)庫(kù)，年運(yùn)量D=700000件，產(chǎn)品價(jià)值C=30元，年存貨本錢I=產(chǎn)品價(jià)格的30％。公司希望選擇使總本錢最小的運(yùn)輸方式。據(jù)估計(jì)，運(yùn)輸時(shí)間每減少一天，平均庫(kù)存本錢可以減少1％。各種運(yùn)輸效勞方式的有關(guān)參數(shù)見表：.運(yùn)輸效勞的選擇的定量分析法運(yùn)輸方式費(fèi)率R(元/件)時(shí)間T(天)年運(yùn)送批次平均存貨量Q/2鐵路0.12110100000水運(yùn)0路0.252042000航空1.424020250考慮平安庫(kù)存.運(yùn)輸效勞的選擇的定量分析法分析：以年總本錢最低為原那么來選擇適宜的運(yùn)輸方式。這里，總本錢=運(yùn)輸費(fèi)用+庫(kù)存本錢；其中，運(yùn)輸費(fèi)用=運(yùn)輸量費(fèi)率庫(kù)存本錢=在途運(yùn)輸庫(kù)存本錢+工廠存貨本錢+倉(cāng)庫(kù)存貨本錢在途運(yùn)輸庫(kù)存費(fèi)用=ICDT/365工廠存貨本錢=ICQ/2倉(cāng)庫(kù)存貨本錢=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—平均存貨量.二、運(yùn)輸方式選擇的定量分析法由表中結(jié)果可知，總本錢最低的是公路運(yùn)輸方式，總本錢為984821元，其次是水路運(yùn)輸，本錢最高的是鐵路運(yùn)輸。按照總本錢最低的原那么，適合選擇公路運(yùn)輸方式。成本類型計(jì)算公式鐵路運(yùn)輸水路運(yùn)輸公路運(yùn)輸航空運(yùn)輸運(yùn)輸成本R

D70000105000140000980000在途庫(kù)存ICDT/3653452052416448630134521工廠存貨ICQ/2900000416500378000182250倉(cāng)庫(kù)存貨I(C+R)Q/2903000420593380520190755總成本

221820511857379848211387526.6.4運(yùn)輸路線的選擇1．起、止點(diǎn)不同的單一路徑規(guī)劃2．多個(gè)起、止點(diǎn)的路徑規(guī)劃3．起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃TravelingSalesmanProblem(TSP)VehicleRoutingProblem(VRP).6.4運(yùn)輸路線的選擇1．起、止點(diǎn)不同的單一路徑規(guī)劃這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為根底的問題之一。問題描述：假設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G〔Vn,Em),并且圖中的每條弧〔i,j)都有一個(gè)長(zhǎng)度cij(或者費(fèi)用cij)，那么最短路徑問題為：在連通圖中找到一條從節(jié)點(diǎn)1到節(jié)點(diǎn)n距離最短〔或費(fèi)用最低〕的路徑。求解此類最短路徑問題，主要有以下幾種算法：〔1〕Dijkstra算法；〔2〕Floyd算法；〔3〕逐次逼近法.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市.解答：最短路的計(jì)算方法〔1〕找出第n個(gè)距起點(diǎn)最近的節(jié)點(diǎn)。對(duì)n=1,2,…，重復(fù)此過程，直到所找出的最近節(jié)點(diǎn)是終點(diǎn)?！?〕在前面的迭代過程中找出〔n-1〕個(gè)距起點(diǎn)最近的節(jié)點(diǎn)，及其距起點(diǎn)最短的中徑和距離，這些節(jié)點(diǎn)和起點(diǎn)統(tǒng)稱為已解的節(jié)點(diǎn)，其余的稱為未解節(jié)點(diǎn)?！?〕每個(gè)已解的節(jié)點(diǎn)和一個(gè)或多外未解的節(jié)點(diǎn)相連接，就可以得出一個(gè)候選點(diǎn)—連接距離最短的未解點(diǎn)。如果有多個(gè)距離相等的最短連接，那么有多個(gè)候選點(diǎn)?！?〕將每個(gè)已解節(jié)點(diǎn)與其候選點(diǎn)之間的距離累加到該已解節(jié)點(diǎn)與起點(diǎn)之間最短路徑的距離上，所得出的總距離最短的候選點(diǎn)就是第n個(gè)最近的節(jié)點(diǎn)，其最短路徑就是得出該距離的路徑〔假設(shè)多個(gè)候選點(diǎn)都得出相等的最短距離，那么都是已解節(jié)點(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。.Floyd算法F算法的根本思路:F算法使用距離矩陣和路由矩陣。距離矩陣是一個(gè)n╳n矩陣，以圖G的n個(gè)節(jié)點(diǎn)為行和列。記為W=[wij]n╳n，wij表示圖G中vi和vj兩點(diǎn)之間的路徑長(zhǎng)度。路由矩陣是一個(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)的徑長(zhǎng)，每次計(jì)算后都以求得的與上次相比較小的徑長(zhǎng)去更新前一次較大徑長(zhǎng)，假設(shè)后求得的徑長(zhǎng)比前次徑長(zhǎng)大或相等那么不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間節(jié)點(diǎn)，〔按順序，后面的點(diǎn)不作為中間節(jié)點(diǎn)〕考察所有通過此中間節(jié)點(diǎn)的路徑.31056154123451－310∞∞23－∞5∞310∞－6154∞56－45∞∞∞4－W0123451－234521－345312－454123－551234－R0.31056154123451－310∞∞23－135∞31013－6154∞56－45∞∞∞4－W1123451－234521－145311－454123－551234－R1.31056154123451－3108∞23－135∞31013－6154856－45∞∞∞4－W2123451－232521－145311－454223－551234－R2.31056154123451－31082523－1352831013－6154856－45∞∞∞4－W3123451－232321－143311－454223－551234－R3.31056154123451－31081223－115931011－6104856－45129104－D4123451－232421－444314－444223－554444－S4.2．多個(gè)起、止點(diǎn)的路徑規(guī)劃當(dāng)有多個(gè)貨源和多個(gè)目的地時(shí)，就需要指定目的地的供貨地，同時(shí)要找到供貨地、目的地之間的最正確路徑。例某公司下屬三個(gè)倉(cāng)庫(kù)，供給四個(gè)客戶的需要，三個(gè)倉(cāng)庫(kù)的供給量和四個(gè)客戶的需求量，以及由各倉(cāng)庫(kù)到各客戶的運(yùn)輸單價(jià)如下表所示。求運(yùn)輸費(fèi)用最少的運(yùn)輸方案。

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

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

銷地客戶1客戶2客戶3客戶4供應(yīng)量產(chǎn)地倉(cāng)庫(kù)A400300700倉(cāng)庫(kù)B300100400倉(cāng)庫(kù)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)方案.用閉回路法求檢驗(yàn)數(shù)時(shí)，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，這種計(jì)算很繁，可以用較為簡(jiǎn)便的方法“位勢(shì)法〞求解。設(shè)u1,u2,…,um；v1,v2,…,vn，是對(duì)應(yīng)運(yùn)輸問題的m+n個(gè)約束條件的對(duì)偶變量。在初始調(diào)運(yùn)方案中x13,x14,x21,x23,x32,x34是基變量，這時(shí)對(duì)應(yīng)的檢驗(yàn)數(shù)是：基變量檢驗(yàn)數(shù)x21c21-(u2+v1)=0設(shè)v1=0，并且c21=1所以u(píng)2=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.通過這些方程可以求得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)地倉(cāng)庫(kù)A12002倉(cāng)庫(kù)B010-11倉(cāng)庫(kù)C100120-3vi0718表5.6檢驗(yàn)數(shù)表格.〔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ù)絕對(duì)值最大的空格作為具體調(diào)整對(duì)象。從表5.6可以發(fā)現(xiàn)，單元格x24的檢驗(yàn)數(shù)是負(fù)數(shù)，因此對(duì)其進(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所示。.3113101928734105

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

運(yùn)價(jià)產(chǎn)地倉(cāng)庫(kù)A500200700倉(cāng)庫(kù)B300100400倉(cāng)庫(kù)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)方案了。.運(yùn)輸方案的改進(jìn)的改進(jìn)→找出檢驗(yàn)數(shù)

ij為最小負(fù)值的格子的閉回路→在滿足所有約束條件的情況下，盡可能增大這個(gè)格子的xij值→調(diào)整此閉回路上其他頂點(diǎn)的值→檢驗(yàn)新解的最優(yōu)性→重復(fù)上步驟直至得到最優(yōu)解為止。.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問題特性：?jiǎn)我卉囕v無車輛容量限制求解復(fù)雜度屬于NP-hard，大規(guī)模問題難以求得最正確解，現(xiàn)實(shí)中常采取〞啟發(fā)式方法(Heuristics)“求解.TSP問題數(shù)學(xué)規(guī)劃模型

Mins.t..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)建及路線改善.AssignmentProcedureForTSP1、將A到A，B到B,C到C…的費(fèi)用轉(zhuǎn)換成無限大，以防止返回。.AssignmentProcedureForTSP2、應(yīng)用指派問題的匈牙利算法，使得表中不同行、不同列都含有0此時(shí)，假設(shè)完成路徑的選擇，最少的費(fèi)用為9.AssignmentProcedureForTSP可行解尚未找到。此時(shí)考慮增加一個(gè)“費(fèi)用最小的非0路徑〞，看看是否有可行解。得到：仍然沒有可行解。此時(shí)考慮再增加一個(gè)“費(fèi)用最小的非0路徑〞，或增加一個(gè)“費(fèi)用次小的非0〞路徑看看是否有可行解。得到：.Little’smethod分枝定界法(Branch-and-Bound)1、計(jì)算出所有不走“0費(fèi)用〞路徑的懲罰本錢2、選擇懲罰本錢最大的路徑.3、簡(jiǎn)化計(jì)算表，消除已經(jīng)選擇的路徑，形成新的計(jì)算表；繼續(xù)分支定界。同時(shí)，為了防止返回，E到C設(shè)為∞；再檢查是否每一行、每一列都有“0費(fèi)用〞路徑，假設(shè)沒有在此行/列減去最小元素。E行減去1，得到：.D同時(shí)，為了防止返回，E到B設(shè)為∞；再檢查是否每一行、每一列都有“0費(fèi)用〞路徑，假設(shè)沒有在此行/列減去最小元素。A列減去1，得到：.假設(shè)選擇E,D路徑，得到：.假設(shè)不選擇E,D路徑：..傳統(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的可行解.1、最近鄰點(diǎn)法7438755348123451－473824－755377－344353－858548－.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的可行解.2、插入法74387553483373377455774488844558454.3、2-opt交換法先構(gòu)建一個(gè)起始可行解在可行解中任選兩個(gè)不相鄰的節(jié)線(ab,cd)，以及另外兩條對(duì)應(yīng)之替換節(jié)線(ac,bd)，計(jì)算替換后總本錢是否降低(即檢查替換本錢是否小于0)。

?替換本錢：Cac+Cbd-Cab-Ccd(對(duì)稱型TSP)假設(shè)替換后總本錢有降低，那么予以替換，同時(shí)變更中間相關(guān)弧線的行走方向重復(fù)步驟2~3，直到所有可能的替換均無法再降低本錢為止.3、2-opt交換法7438755348.4、常見的宏啟發(fā)式方法(Meta-heuristics)禁忌搜索法(TabuSearch,TS)基因算法(GeneticAlgorithm,GA)模擬退火法(SimulatedAnnealing,SA)門限值接受法(ThresholdAccepting,TA)神經(jīng)網(wǎng)絡(luò)(NeuralNetwork,NN)蟻群算法(AntColonyOptimization,ACO)其它.6.4車輛路線、時(shí)間安排車輛路線安排車輛路線安排問題〔VRP,VehicleRoutingProblem〕是指對(duì)物流配送的車輛進(jìn)行優(yōu)化調(diào)度。該問題一般可以描述如下：對(duì)一系列裝貨點(diǎn)或〔和〕卸貨點(diǎn)，組織適當(dāng)合理的行車路線，使車輛有序地通過他們，在滿足一定的約束條件下〔如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量、數(shù)目限制、車輛行駛里程、時(shí)間限制等〕下，到達(dá)一定的目標(biāo)〔如最短路程、最小費(fèi)用、最短時(shí)間、最少車輛等〕。該問題涉及了多輛交通工具的效勞對(duì)象的選擇和路徑〔效勞順序〕確定兩方面的問題VRP問題是組合優(yōu)化領(lǐng)域著名的NP難題之一，求解方法一般相當(dāng)復(fù)雜，通常的做法是應(yīng)用相關(guān)技術(shù)問題分解或者轉(zhuǎn)化為一個(gè)或多個(gè)已經(jīng)研究過的根本問題〔如旅行商問題、指派問題、最短路問題等〕，再使用相比照較成熟的根本理論和方法進(jìn)行求解。.運(yùn)用VRP模型對(duì)實(shí)際問題進(jìn)行研究時(shí)，一般需要考慮以下幾個(gè)方面的問題：〔1〕倉(cāng)庫(kù)。倉(cāng)庫(kù)的級(jí)數(shù)，每級(jí)倉(cāng)庫(kù)的數(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)取貨和/或送貨?！?〕顧客。顧客需求，裝載、卸載，所處的地理位置，別離需求，優(yōu)先等級(jí)?！?〕道路信息。車流密度，道路交通費(fèi)用，距離或時(shí)間屬性?！?〕貨物信息。貨物的種類多少，兼容性，貨物的保鮮?！?〕運(yùn)輸規(guī)章。工人每天的工作時(shí)間，車輛的周期維護(hù)。.〔1〕安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸?！?〕安排車輛各日途經(jīng)站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊。如果一周內(nèi)各日效勞的站點(diǎn)不同，就應(yīng)該對(duì)一周內(nèi)每天的路線和時(shí)刻表問題分別進(jìn)行站點(diǎn)群劃分。各日站點(diǎn)群的劃分應(yīng)防止重疊?！?〕從距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線〔4〕卡車的行車路線應(yīng)呈水滴狀?！?〕盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的?！?〕取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。〔7〕對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式?！?〕防止時(shí)間窗口過短。簡(jiǎn)化的原那么：.整數(shù)規(guī)劃法〔IntegerProgramming〕啟發(fā)式方法〔Heuristics〕節(jié)約法〔ClarkeandWrightProcedure〕兩階段法ETS(ExtensionofTravelingSalesmanProcedure)掃描法考慮返程Backtracking.1、整數(shù)規(guī)劃法....2、節(jié)約法〔ClarkeandWrightProcedure〕節(jié)約法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點(diǎn)提供效勞的卡車數(shù)量最少。該方法先假設(shè)每一個(gè)站點(diǎn)都有一輛虛擬的車輛提供效勞，隨后返回倉(cāng)庫(kù)，如圖(a)所示，這時(shí)的路線里程最長(zhǎng)。下一步，將兩個(gè)站點(diǎn)合并到同一條行車路線上，減少一輛運(yùn)輸車，相應(yīng)地縮短路線里程，選擇節(jié)約距離最多的一對(duì)站點(diǎn)合并在一起，修訂后的路線如圖(b)。d0,AdA,0d0,BdB,0ABO倉(cāng)庫(kù)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.例：1、按距離中心的距離，從小到大排序2、計(jì)算出所有兩點(diǎn)間的節(jié)省距離，寫在左邊CapacityofaTruck=153、按照節(jié)約量，從大到小選取路線，同時(shí)滿足裝載量≤卡車容量.4、形成一條路線，劃去已經(jīng)過的節(jié)點(diǎn)，繼續(xù)尋找其他路線.兩階段法ETS

(ExtensionofTravelingSalesmanProcedure)第一階段：1、找到由TSP問題確定的行走路徑；2、根據(jù)貨車容量，初步給出各條貨車的行駛路徑。第二階段：根據(jù)貨車的剩余容量〔Slack〕，對(duì)初步行駛路徑進(jìn)行調(diào)整。例：CapacityofaTruck=10.ThetravelingsalesmanrouteisO