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

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

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

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

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

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

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

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

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

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

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

注：表中數(shù)字表示各種運輸方式在某一方面的優(yōu)劣次序。.影響運輸決策的成本因素影響承運人定價的成本因素與運距有關的成本與運量有關的成本與速度有關的成本直送v.s中轉影響承運人運力組合的成本因素固定成本運營成本.運輸特性規(guī)模特性隨著一次裝運量的增大，使每單位重量的運輸成本下降。距離特性隨著一次運輸距離的增加，運輸費用的增加會變的越來越緩慢，或者說單位運輸距離的費用減少，運輸成本與一次運輸?shù)木嚯x有關。速度特性完成特定的運輸所需的時間越短，其效用價值越高。單位貨物運輸成本運輸距離距離與運輸成本的關系單位貨物運輸成本裝載重量載重量與運輸成本的關系運輸效用送達時間送達時間與運輸效用的關系.影響承運人運力組合的成本因素.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..影響托運人決策的成本因素服務水平成本（運輸時間-速度）運輸成本（運輸方式、運輸規(guī)模）庫存成本交易成本.運輸服務的選擇

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

221820511857379848211387526.6.4運輸路線的選擇1．起、止點不同的單一路徑規(guī)劃2．多個起、止點的路徑規(guī)劃3．起點和終點相同的路徑規(guī)劃TravelingSalesmanProblem(TSP)VehicleRoutingProblem(VRP).6.4運輸路線的選擇1．起、止點不同的單一路徑規(guī)劃這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎的問題之一。問題描述：假設有一n個節(jié)點和m條弧的連通圖G（Vn,Em),并且圖中的每條?。╥,j)都有一個長度cij(或者費用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點1到節(jié)點n距離最短（或費用最低）的路徑。求解此類最短路徑問題，主要有以下幾種算法：（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法.1．起、止點不同的單一路徑規(guī)劃例某運輸公司簽訂了一項運輸合同，要把A市的一批貨物運送到B市，該公司根據(jù)這兩個城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡。圖中，圓圈也稱節(jié)點，代表起點、目的地和與行車路線相交的其他城市。鏈代表兩個結點之間的公路，每一條公路都標明運輸里程。A市B市.解答：最短路的計算方法（1）找出第n個距起點最近的節(jié)點。對n=1,2,…，重復此過程，直到所找出的最近節(jié)點是終點。（2）在前面的迭代過程中找出（n-1）個距起點最近的節(jié)點，及其距起點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為未解節(jié)點。（3）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一個候選點—連接距離最短的未解點。如果有多個距離相等的最短連接，則有多個候選點。（4）將每個已解節(jié)點與其候選點之間的距離累加到該已解節(jié)點與起點之間最短路徑的距離上，所得出的總距離最短的候選點就是第n個最近的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的最短距離，則都是已解節(jié)點）。.步驟直接連接到未解節(jié)點的已解節(jié)點與其直接連接的未解結點相關總成本第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通過上表的計算，最短路徑為1-2-5-4-3-6，最短距離為12。.Floyd算法F算法的基本思路:F算法使用距離矩陣和路由矩陣。距離矩陣是一個n╳n矩陣，以圖G的n個節(jié)點為行和列。記為W=[wij

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

]n╳n

，其中rij表示vi至vj經(jīng)過的轉接點（中間節(jié)點）。F算法的思路是首先寫出初始的W陣和R陣，接著按順序依次將節(jié)點集中的各個節(jié)點作為中間節(jié)點，計算此點距其他各點的徑長，每次計算后都以求得的與上次相比較小的徑長去更新前一次較大徑長，若后求得的徑長比前次徑長大或相等則不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間節(jié)點，（按順序，后面的點不作為中間節(jié)點）考察所有通過此中間節(jié)點的路徑.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．多個起、止點的路徑規(guī)劃當有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。例

某公司下屬三個倉庫，供應四個客戶的需要，三個倉庫的供應量和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。求運輸費用最少的運輸方案。

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

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

銷地客戶1客戶2客戶3客戶4供應量產(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)運方案內(nèi)的每個空格所形成的閉回路上，作單位物資的運量調(diào)整，總可以計算出相應的運費是增加還是減少。我們把所計算出來的每條閉回路上調(diào)整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于0，表示在該空格的閉回路上調(diào)整運量會使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。表8.5初始調(diào)運方案.用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當產(chǎn)銷點很多時，這種計算很繁，可以用較為簡便的方法“位勢法”求解。設u1,u2,…,um；v1,v2,…,vn，是對應運輸問題的m+n個約束條件的對偶變量。在初始調(diào)運方案中x13,x14,x21,x23,x32,x34是基變量，這時對應的檢驗數(shù)是：基變量檢驗數(shù)x21c21-(u2+v1)=0設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.通過這些方程可以求得u1=2u2=1u3=-3v1=0v2=7v3=1v4=8在初始解調(diào)運方案中增加一行一列，在列中填入ui,在行中填入vi。接著，按σij=cij-(ui+vj)計算所有空格的檢驗數(shù)。完成后的表格見表5.6。3113101928734105

銷地客戶1客戶2客戶3客戶4ui運價產(chǎn)地倉庫A12002倉庫B010-11倉庫C100120-3vi0718表5.6檢驗數(shù)表格.（3）方案調(diào)整判定一個初始調(diào)運方案不是最優(yōu)調(diào)運方案的標準，是在檢驗數(shù)表格中出現(xiàn)負值的檢驗數(shù)。如果檢驗數(shù)的負值不止個時，一般選擇負檢驗數(shù)絕對值最大的空格作為具體調(diào)整對象。從表5.6可以發(fā)現(xiàn)，單元格x24的檢驗數(shù)是負數(shù)，因此對其進行調(diào)整，具體過程如表5.7所示。x13400+100=500x14300-100=200x23100-100=0x240+100=100表5.7調(diào)動方案調(diào)整表

從單元格x24開始，沿閉回路在各奇數(shù)次轉角點中挑選運量的最小數(shù)值作為調(diào)整量。在此將x23單元格的100作為調(diào)整量，將亮個數(shù)填入單元格x24內(nèi)，同時調(diào)整該閉回路中其他轉角點上的運量，使各行、列保持原來的供需平衡，這樣注得到一個新的調(diào)運方案，如表5.7所示。.3113101928734105

銷地客戶1客戶2客戶3客戶4供應量

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

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

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

b,c

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

c,b

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

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

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

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

節(jié)約里程：dA,O+dB,O-dA,B.例：1、按距離中心的距離，從小到大排序2、計算出所有兩點間的節(jié)省距離，寫在左邊CapacityofaTruck=153、按照節(jié)約量，從大到小選取路線，同時滿足裝載量≤卡車容量.4、形成一條路線，劃去已經(jīng)過的節(jié)點，繼續(xù)尋找其他路線.兩階段法ETS

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