運輸及配送路線的優(yōu)化-課件

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

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

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

綜合考慮，鐵路適于在內(nèi)陸地區(qū)作為長途、大批量運送低價值、高密度的一般貨物和可靠性要求高的特種貨物；從投資的情況來看，在運輸量比較大的地區(qū)之間建設(shè)鐵路較為合理。66.2運輸方式及其特征二、公路運輸公路運輸具有規(guī)模巨大，分布極廣的道路基礎(chǔ)設(shè)施體系和機(jī)動靈活、適應(yīng)性強的車輛裝備系統(tǒng)。大多數(shù)的消費品都是通過公路運輸?shù)?。公路運輸是任何公司物流系統(tǒng)中重要的一部分。公路運輸?shù)墓潭ǔ杀竞艿?。汽車承運人在固定基礎(chǔ)設(shè)施的投資相對較少，多數(shù)公路的建設(shè)運營由政府進(jìn)行。公路運輸?shù)淖儎映杀鞠鄬^高，因為公路的建設(shè)和維修費用經(jīng)常是以稅收和收費站的形式向承運人征收的。此外，汽車的能耗、維修費用相對也比較高。燃油稅7公路運輸公路運輸方式的主要優(yōu)點：原始投資少，資金周轉(zhuǎn)快，投資回收期短機(jī)動靈活，門對門運輸快捷可控包裝成本低，貨物損失小公路運輸?shù)闹饕秉c：運輸能力小勞動生產(chǎn)率低，單位運價高公路擁擠與污染，環(huán)境成本高

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

與上述特點相對應(yīng)，水路運輸適于運送數(shù)量巨大、低價值、時效性要求不高的貨物，如礦石、煤炭、石油農(nóng)產(chǎn)品等。水路運輸是大宗貨物長距離運輸?shù)睦硐脒x擇。116.2運輸方式及其特征四、航空運輸航空貨運的主要優(yōu)點在于運輸速度快。隨著航空運輸技術(shù)的不斷成熟，航空運輸在遠(yuǎn)距離運輸，特別是跨國運輸中顯示出無可比擬的優(yōu)勢。只有在運輸高價值的和對時效性要求高于對成本要求的產(chǎn)品時，航空運輸才有其合理性。航空的固定成本較低?？罩泻骄€和管制系統(tǒng)由國家擁有，航空港的建設(shè)運營由國家投資，航空公司的固定成本主要與購買飛機(jī)有關(guān)，也與所需的搬運系統(tǒng)和貨物集裝箱有關(guān)。航空運輸?shù)淖儎映杀臼菢O高的，其燃料消耗、飛行器的維修保養(yǎng)以及飛行人員和地勤人員的費用都是一筆可觀的支出。12航空運輸航空運輸?shù)闹饕獌?yōu)點：運行速度快靈活、機(jī)動性大航空運輸服務(wù)質(zhì)量高、安全可靠航空運輸?shù)闹饕秉c：運輸成本高運輸能力小有些貨物禁用空運受天氣影響較大

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

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

運輸成本、速度和對庫存的影響是決策者心目中最重要的運輸服務(wù)要素，因此，這三項是運輸服務(wù)選擇的基礎(chǔ)。運輸對庫存的影響有以下幾點：較慢的運輸模式會引起較大的中轉(zhuǎn)或運輸庫存；較大運量的運輸方式會出現(xiàn)訂單批量超過需求量的情況，從而增加庫存；不可靠的運輸模式會引起安全庫存的提高。在選擇運輸方式時，就需要考慮庫存持有成本可能升高，而抵消運輸服務(wù)成本降低的情況。23運輸服務(wù)的選擇的定量分析法基于運輸成本與庫存成本的總成本分析方法【例】某公司欲將產(chǎn)品從位置A的工廠運往位置B的公司自有倉庫，年運量D=700000件，產(chǎn)品價值C=30元，年存貨成本I=產(chǎn)品價格的30％。公司希望選擇使總成本最小的運輸方式。據(jù)估計，運輸時間每減少一天，平均庫存成本可以減少1％。各種運輸服務(wù)方式的有關(guān)參數(shù)見表：24運輸服務(wù)的選擇的定量分析法考慮安全庫存25運輸服務(wù)的選擇的定量分析法分析：以年總成本最低為原則來選擇合適的運輸方式。這里，總成本=運輸費用+庫存成本；其中，運輸費用=運輸量費率庫存成本=在途運輸庫存成本+工廠存貨成本+倉庫存貨成本在途運輸庫存費用=ICDT/365工廠存貨成本=ICQ/2倉庫存貨成本=I（C+R）Q/2代入各種運輸方式的基本數(shù)據(jù)信息，將相應(yīng)的成本計算結(jié)果列入表2。D—年運量；C—產(chǎn)品單價；I—年存貨成本（產(chǎn)品價格的30％）；T—運輸時間；R—費率(元/件)；Q/2—平均存貨量26二、運輸方式選擇的定量分析法由表中結(jié)果可知，總成本最低的是公路運輸方式，總成本為984821元，其次是水路運輸，成本最高的是鐵路運輸。按照總成本最低的原則，適合選擇公路運輸方式。276.4運輸路線的選擇1．起、止點不同的單一路徑規(guī)劃2．多個起、止點的路徑規(guī)劃3．起點和終點相同的路徑規(guī)劃TravelingSalesmanProblem(TSP)VehicleRoutingProblem(VRP)286.4運輸路線的選擇1．起、止點不同的單一路徑規(guī)劃這類路徑規(guī)劃問題稱為最短路問題。最短路徑問題是線路優(yōu)化模型理論中最為基礎(chǔ)的問題之一。問題描述：假設(shè)有一n個節(jié)點和m條弧的連通圖G（Vn,Em),并且圖中的每條?。╥,j)都有一個長度cij(或者費用cij)，則最短路徑問題為：在連通圖中找到一條從節(jié)點1到節(jié)點n距離最短（或費用最低）的路徑。求解此類最短路徑問題，主要有以下幾種算法：（1）Dijkstra算法；（2）Floyd算法；（3）逐次逼近法291．起、止點不同的單一路徑規(guī)劃例某運輸公司簽訂了一項運輸合同，要把A市的一批貨物運送到B市，該公司根據(jù)這兩個城市之間可選擇的行車路線的地圖繪制了如圖所示的公路網(wǎng)絡(luò)。圖中，圓圈也稱節(jié)點，代表起點、目的地和與行車路線相交的其他城市。鏈代表兩個結(jié)點之間的公路，每一條公路都標(biāo)明運輸里程。A市B市30解答：最短路的計算方法（1）找出第n個距起點最近的節(jié)點。對n=1,2,…，重復(fù)此過程，直到所找出的最近節(jié)點是終點。（2）在前面的迭代過程中找出（n-1）個距起點最近的節(jié)點，及其距起點最短的中徑和距離，這些節(jié)點和起點統(tǒng)稱為已解的節(jié)點，其余的稱為未解節(jié)點。（3）每個已解的節(jié)點和一個或多外未解的節(jié)點相連接，就可以得出一個候選點—連接距離最短的未解點。如果有多個距離相等的最短連接，則有多個候選點。（4）將每個已解節(jié)點與其候選點之間的距離累加到該已解節(jié)點與起點之間最短路徑的距離上，所得出的總距離最短的候選點就是第n個最近的節(jié)點，其最短路徑就是得出該距離的路徑（若多個候選點都得出相等的最短距離，則都是已解節(jié)點）。31通過上表的計算，最短路徑為1-2-5-4-3-6，最短距離為12。32Floyd算法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)過的轉(zhuǎn)接點（中間節(jié)點）。F算法的思路是首先寫出初始的W陣和R陣，接著按順序依次將節(jié)點集中的各個節(jié)點作為中間節(jié)點，計算此點距其他各點的徑長，每次計算后都以求得的與上次相比較小的徑長去更新前一次較大徑長，若后求得的徑長比前次徑長大或相等則不變。以此不斷更新和，直至W中的數(shù)值收斂。按順序，依次作為中間節(jié)點，（按順序，后面的點不作為中間節(jié)點）考察所有通過此中間節(jié)點的路徑3331056154W0R03431056154W12R23631056154W3R33731056154D4S4382．多個起、止點的路徑規(guī)劃當(dāng)有多個貨源和多個目的地時，就需要指定目的地的供貨地，同時要找到供貨地、目的地之間的最佳路徑。例

某公司下屬三個倉庫，供應(yīng)四個客戶的需要，三個倉庫的供應(yīng)量和四個客戶的需求量，以及由各倉庫到各客戶的運輸單價如下表所示。求運輸費用最少的運輸方案。39表上做業(yè)法，該方法適合于對相對簡單的問題進(jìn)行求解，求解過程方便直觀，而且由于計算量不大，可以用手工直接完成。利用表上作業(yè)法有兩個基本步驟：（1）確定初始調(diào)運方案最小元素法是按運價表依次挑選運費小的供-需點組合，盡量優(yōu)先安排運費最低組合的方法。3113101928734105表5.4初始調(diào)運方案40（2）初始方案的檢驗最優(yōu)方案的數(shù)字特征———檢驗數(shù)：閉回路：從理論上講，對于表上作業(yè)法的初始方案來說，從調(diào)運方案表上的一個空格出發(fā)，存在一條且僅存在一條以該空格（用xij表示）為起點，以其他填有數(shù)字的點為其他頂點的閉合回路，簡稱閉回路。這個閉回路有以下性質(zhì)：每個頂點都是轉(zhuǎn)角點；閉合回路是一條封閉折線，每一條邊都是水平或垂直的；每一行（列）若有閉合回路的頂點，則必有兩個。只有從空格出發(fā)，其余各轉(zhuǎn)角點所對應(yīng)的方格內(nèi)均填寫數(shù)字時，所構(gòu)成的閉合回路才是我們所說的閉回路；另外，過任一空格的閉合回路不僅是存在的，而且是唯一的。41

表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)整，總可以計算出相應(yīng)的運費是增加還是減少。我們把所計算出來的每條閉回路上調(diào)整單位運量而使運輸費用發(fā)生變化的增減值，稱其為檢驗數(shù)。如果檢驗數(shù)小于0，表示在該空格的閉回路上調(diào)整運量會使運費減少；相反，如果檢驗數(shù)大于0，則會使運費增加。表8.5初始調(diào)運方案42用閉回路法求檢驗數(shù)時，需給每一空格找一條閉回路。當(dāng)產(chǎn)銷點很多時，這種計算很繁，可以用較為簡便的方法“位勢法”求解。設(shè)u1,u2,…,um；v1,v2,…,vn，是對應(yīng)運輸問題的m+n個約束條件的對偶變量。在初始調(diào)運方案中x13,x14,x21,x23,x32,x34是基變量，這時對應(yīng)的檢驗數(shù)是：基變量檢驗數(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)=043通過這些方程可以求得u1=2u2=1u3=-3v1=0v2=7v3=1v4=8在初始解調(diào)運方案中增加一行一列，在列中填入ui,在行中填入vi。接著，按σij=cij-(ui+vj)計算所有空格的檢驗數(shù)。完成后的表格見表5.6。3113101928734105表5.6檢驗數(shù)表格44（3）方案調(diào)整判定一個初始調(diào)運方案不是最優(yōu)調(diào)運方案的標(biāo)準(zhǔn)，是在檢驗數(shù)表格中出現(xiàn)負(fù)值的檢驗數(shù)。如果檢驗數(shù)的負(fù)值不止個時，一般選擇負(fù)檢驗數(shù)絕對值最大的空格作為具體調(diào)整對象。從表5.6可以發(fā)現(xiàn)，單元格x24的檢驗數(shù)是負(fù)數(shù)，因此對其進(jìn)行調(diào)整，具體過程如表5.7所示。表5.7調(diào)動方案調(diào)整表

從單元格x24開始，沿閉回路在各奇數(shù)次轉(zhuǎn)角點中挑選運量的最小數(shù)值作為調(diào)整量。在此將x23單元格的100作為調(diào)整量，將亮個數(shù)填入單元格x24內(nèi)，同時調(diào)整該閉回路中其他轉(zhuǎn)角點上的運量，使各行、列保持原來的供需平衡，這樣注得到一個新的調(diào)運方案，如表5.7所示。453113101928734105表6.7調(diào)整后的方案按新方案計算調(diào)運物資的運輸費用為：3×500+10×200+8×100+4×600+5×300=8500元新方案是否最優(yōu)方案，還需再進(jìn)行檢驗。經(jīng)計算，該新方案的所有檢驗數(shù)都是非負(fù)數(shù)，說明該方案已經(jīng)是最優(yōu)方案了。46運輸方案的改進(jìn)的改進(jìn)→找出檢驗數(shù)ij為最小負(fù)值的格子的閉回路→在滿足所有約束條件的情況下，盡可能增大這個格子的xij值→調(diào)整此閉回路上其他頂點的值→檢驗新解的最優(yōu)性→重復(fù)上步驟直至得到最優(yōu)解為止。473．起點和終點相同的路徑規(guī)劃起點和終點重合的路徑問題一般被稱為“旅行商”問題（TSP,TravelingSalesmanProblem），是運籌學(xué)、圖論和組合優(yōu)化中的典型問題。

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

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

b,c

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

c,b

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

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

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

節(jié)約法的目標(biāo)是使所有車輛的行駛總里程最短，并且為所有站點提供服務(wù)的卡車數(shù)量最少。該方法先假設(shè)每一個站點都有一輛虛擬的車輛提供服務(wù)，隨后返回倉庫，如圖(a)所示，這時的路線里程最長。下一步，將兩個站點合并到同一條行車路線上，減少一輛運輸車，相應(yīng)地縮短路線里程，選擇節(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,B75例：1、按距離中心的距離，從小到大排序2、計算出所有兩點間的節(jié)省距離，寫在左邊CapacityofaTruck=153、按照節(jié)約量，從大到小選取路線，同時滿足裝載量≤卡車容量764、形成一條路線，劃去已經(jīng)過的節(jié)點，繼續(xù)尋找其他路線77兩階段法ETS

(ExtensionofTravelingSalesmanProcedure)第一階段：1、找到由TSP問題確定的行走路徑；2、根據(jù)貨車容量，初步給出各條貨車的行駛路徑。第二階段：根據(jù)貨車的剩余容量（Slack），對初步行駛路徑進(jìn)行調(diào)整。例：CapacityofaTruck=1078ThetravelingsalesmanrouteisO-B-A-E-C-D-O根據(jù)貨車容量限制，初步給出各條貨車的行駛路徑，同時保證節(jié)省距離≥0第一階段：7980第二階段：從剩余容量（Slack）最大的線路開始，進(jìn)行節(jié)點的交換調(diào)整，并計算節(jié)點交換后的節(jié)約里程數(shù)，若為正，則可交換節(jié)點。剩余容量（Slack）最大的線路：O-E-