摘 要：近年來，我國物流運行總體平穩，物流需求規模保持較高增幅，物流業增加值平穩增長，但經濟運行中的物流成本與其他發達國家相比依然較高。車輛調度配送路徑優化問題同時涉及能源消耗和廢物的排放問題，隨著人們對環境問題給予越來越多的關注，因而其一直是國內外研究的熱點。同時物流配送車輛調度問題在企業運營中起著重要的作用。文章首先簡介了車輛調度問題，然后從研究的精確算法和啟發式算法兩方面較為詳細地論述了國內外有關車輛調度問題的研究現狀，總結了研究中存在的問題，并對物流算法的發展進行了展望。

　　關鍵詞：論文發表代理機構,車輛調度,路徑優化,啟發式算法

　　Abstract： In recent years， domestic logistics is developing steady in a whole， the demand of logistics is also in a high amplification. The logistics industry is in a stable increase while the operating cost is still higher than that of developed countries. For that vehicle routing problem both relates to energy consumption and wastage emission， VRP is a research hotspot at home and abroad under the case that more and more attention are paid to environment protection. Vehicle scheduling holds an important position in enterprise operating. This article first gives a brief description of VRP， then gives a detailed overview of existing algorithms including exact algorithm and heuristic algorithm from home and abroad. Based on the above in formation， this article makes a prospect of algorithms on logistics.

　　Key words： vehicle scheduling; routing optimization; heuristic algorithm

　　0 引 言

　　由國家發展和改革委員會、國家統計局和中國物流與采購聯合會2014年3月7日聯合發布的《2013年全國物流運行情況通報》[1]顯示，2013年中國社會物流總費用10.2萬億元，同比增長9.3%，與GDP的比率為18%。這一比率遠高于美國的8.5%，日本的8.7%和德國的8.3%，高于全球平均水平約6.5個百分點。這些數據反映出中國物流成本偏高的現狀。物流總費用中運輸費用5.4萬億元，同比增長9.2%，占社會物流總費用的比重為52.5%。同時，2013年中國物流業增加值3.9萬億元，同比增長8.5%。可以看出，全社會物流企業收入增速低于物流費用增速，物流企業普遍盈利能力偏低。報告總結性的指出，2013年，我國物流運行總體平穩，物流需求規模保持較高增幅，物流業增加值平穩增長，但經濟運行中的物流成本依然較高。

　　隨著人們對環境問題給予越來越多的關注，關于要求企業保護環境的法律條文相繼增加。其中，減少廢物的排放量和能源的消耗成為法律規定的兩個重要內容。物流作為一個與環境關系密切的行業，車輛調度配送路徑優化問題同時涉及能源消耗和廢物的排放問題，因而其一直是國內外研究的熱點。

　　綜上所述，作為繼原材料、勞動力以外的“第三利潤源泉”，實現物流合理化具有重要的經濟意義與現實意義。一方面，物流配送車輛路徑優化有助于企業降低物流成本，提高運作效率，從而增加企業利潤。另一方面，通過緩解交通壓力，減少資源消耗和對環境的污染真正做到環保物流。

　　1 車輛調度問題描述

　　物流配送車輛路徑優化問題最早是由線性規劃之父Dantzig和Ramser[2]在1959年提出，該問題是交通運輸管理、智能救災調度指揮系統、網絡作業調度管理系統、現代物流系統、物流網等應用、研究領域中的基本問題之一，也是最重要的調度問題之一。

　　配送車輛調度問題要解決的問題[3]是車輛從配送中心(這里的配送中心是個廣義概念，指的是車輛的出發地，包括物流中心、配送中心、倉庫、車場等)出發去完成一些配送任務，當各任務量較小(小于車輛容量)時，為了提高車輛的利用率，可安排一輛車執行幾項運輸任務。這時，如何安排車輛的路線，使得既滿足各任務的需求并完成任務，而又使總成本最小(這里的總成本指的是一個廣義概念，包括時間最少、運營費用最少等)涉及的就是配送車輛路徑優化問題。

　　在學術研究方面一般把這個問題抽象解釋為路線安排問題或者車輛路徑問題(Vehicle Routing Problem，VRP)，可描述如下：有一個或幾個配送中心D■i=1，2，…，n，每個配送中心有K種不同的車型，每種車型有n量車。有一批配送業務R■i=1，2，…，n，已知每個配送業務的需求量q■i=1，2，…，n，要求在一定的時間范圍內E■，L■完成，求在滿足不超過配送車輛載重量等的約束條件下，安排配送車輛在合適的時間及最優路線等約束條件下總成本最小。 　　2 VRP的構成要素分析

　　配送車輛調度問題主要包括道路、貨物、車輛、物流中心、客戶、運輸網絡、約束條件和目標函數等要素。VRP問題主要是以下幾個因素的多個組合[4]：(1)道路。道路是貨物運輸的基礎，也是構成VRP的核心要素之一。通常用從中心倉庫出發按照一定的路線依次經過各個客戶點，最后返回配送中心所形成的網絡圖表示。(2)貨物。貨物是配送的對象，包括品名、包裝、重量、體積、要求送到(或取走)的時間和地點、能否分批配送等屬性。(3)車輛。車輛是貨物的運載工具。其主要屬性包括車輛的類型、轉載量、一次配送的最大行駛距離、配送前的停放位置及完成任務的停放位置等。(4)物流中心。也稱為物流基地、物流據點，是指進行集貨、分貨、配貨、送貨作業的配送中心、倉庫、車站、港口等。(5)客戶。也稱為用戶，包括分倉庫、零售商店等。客戶的屬性包括需求(或供應)貨物的數量、需求(或供應)貨物的時間、需求(或供應)貨物的次數及需求(或供應)貨物的滿足程度等。(6)運輸網絡。運輸網絡由頂點(指物流中心、客戶、停車場)、無向邊和有向弧組成。邊、弧的屬性包括方向、權值和交通流量限制等。(7)約束條件。配送車輛調度問題應滿足的約束條件主要包括：①在允許通行的時間進行配送。②在物流中心現有運行能力范圍內等。③滿足客戶對貨物發到時間范圍的要求。④滿足所有客戶對貨物品種、規格、數量的要求。⑤車輛在配送過程中的實際載貨量不得超過車輛的最大允許裝載量。(8)目標函數。配送車輛調度問題可以只選用一個目標，也可以選用多個目標。經常選用的目標函數主要有：①最大化準時性。②最小化勞動消耗。③最大化運力利用。④最小化綜合費用。⑤最小化配送總里程。⑥最小化配送車輛的噸位公里數。

　　由以上各要素組成的VRP簡單示意圖如圖1所示：

　　3 VRP的分類

　　根據研究重點的不同，VRP存在多種分類方式[5]：(1)按照需求是否可切分，可以分為可切分的VRP和不可切分的VRP;(2)按照每個顧客需求量是否超過車的容量，可以分為滿載車輛路徑問題和非滿載車輛路徑問題;(3)按照約束條件的不同可以分為帶有容量限制的車輛路徑問題(CVRP)、帶時間距離約束的車輛路徑問題(DVRP)以及帶有時間窗的車輛路徑問題(VRPTW)等;(4)按照已知信息的特征可以分為確定性VRP和不確定性VRP。其中不確定性VRP可進一步分為隨機車輛路徑問題(SVRP)和模糊車輛路徑問題(FVRP);(5)按照配送中心的數量可以分為單車場車輛路徑問題(SVRP)，即一般車輛路徑問題(VRP)，以及多車場車輛路徑問題(MVRP)，其中MVRP可以根據是否每輛車都有固定的終點車場分為終點車場固定的MVRP和終點車場不固定的MVRP。

　　4 VRP的基礎理論

　　4.1 線性規劃理論。線性規劃(Linear Programming)是一種在科學與工程領域廣泛應用的數學模型。作為運籌學的一個基本分支，線性規劃是實現管理現代化的有力工具。線性規劃問題研究的是一個線性函數在一組線性等式或不等式組成的約束條件下的極值。主要分為兩類：(1)對于一項確定的任務進行統籌安排，達到在使用最少的人力物力資源的情況下完成這一任務的目標。(2)對確定數量的人力物力資源，通過合理安排使用達到完成任務最多的目標。

　　線性規劃問題的共同特征為：(1)每一個問題都是求一組變量(稱為決策變量)的值。這組變量的每一組定值分別代表一個具體方案。通常這組變量的取值是非負的。(2)存在一定的限制條件，稱為約束條件。這些約束條件都可以用一組線性等式或不等式來表示。(3)都有一個期望達到的目標，并且這個目標可以表示為決策變量的線性函數(稱為目標函數)。按照所研究問題的不同，要求目標函數值最大化(max)或者最小化(min)。

　　由共同特征可以得出線性規劃問題模型的一般形式為[6]：(1)決策變量：X=x■，x■，…，x■■;(2)目標函數：maxminz

　　=c■x■+c■x■+…+c■x■;(3)約束條件：■;其中，“max(min)”是“maximize(minimize)”的縮寫，含義為“最大化(最小化)”。

　　4.2 組合優化理論。組合優化(Combinatorial Optimization)，又稱離散優化，是運籌學的一個經典分支。它研究的是在離散的、有限的數學結構即問題的可行解集中，求滿足約束條件的目標函數最大化(max)或最小化(min)。

　　組合優化問題的數學模型可描述為：

　　maxminfx

　　s.t.■

　　其中，fx為目標函數，gx為約束函數，x為決策變量，D表示有限個點組成的集合。一個組合優化問題可以簡單地表示為三個參數D，F，f。其中D為決策變量定義域，F為可行解區域，滿足F=x|x∈D， gx≥0，F中的任何一個元素稱為該組合優化問題的可行解，f為目標函數，滿足的可行解稱為該組合優化問題的最優解[7]。組合優化的特點是可行解集合為有限點集，且有可行解一定有最優解。由直觀可知，只要將D中的有限個點逐一判別是否滿足條件函數gx的約束和比較各自所對應的目標值fx的大小，即可得到該問題的最優解。在現實生活中，大量優化問題就是從有限個狀態中選取最好的一個，因而屬于組合優化問題。

　　4.3 運輸問題。運輸問題(Transportation Problem)是一類具有特殊結構的組合優化問題。其具體數學描述為：某種產品有m個產地A■，A■，…，A■，產量分別為a■，a■，…，a■，有n個銷售地B■，B■，…，B■銷售該產品，銷量分別為b■，b■，…，b■，從產地A■i=1，2，…，m調到銷售地B■j=1，2，…，n的調運量為x■，單位產品運價為y■。假定產銷平衡，即總產量等于總銷量，則有■a■ 　　=■b■。求如何確定運輸方案，使得調運產品的總運費最小[8]?該問題的數學模型為：求x■，使得：

　　minZ=■■x■y■

　　s.t.■

　　5 VRP的優化算法

　　車輛運輸調度問題的求解算法有很多種，但究其本質來講，基本可分為最優化算法(Exact Algorithm)和啟發式算法(Heuristic Algorithm)[9]。

　　5.1 最優化算法。最優化算法，也稱為精確算法，是指能夠通過有限的嚴謹計算和推理，運用整數規劃、線性規劃和非線性規劃等數學規劃技術或數據結構得到優化問題的最優解的算法。在物流車輛運輸調度問題中，所謂最優化算法就是找到一組路徑集合，使得其目標函數值比其它任何一組可行路徑集合的目標函數值更好。

　　對于精確算法，Desrochers[10]，Kohland Madsen[11]，Fisher[12]等人做過相關的研究，其中又可以分為分支定界法(Branch-and-bound)、動態規劃法(Dynamic Programming)、切平面法(Cutting Planes)等。精確算法可以求得模型的精確解，但是它只能解決規模比較小的問題，即配送車輛數和客戶數都比較少的問題。通常情況下，由于車輛路徑優化問題是NP難題，問題規模較大，導致計算量會呈現組合爆炸(Combination Explosion)的現象。同時，求解時間也呈指數函數的增長趨勢。由于這兩方面的限制，在解決實際問題中精確算法的應用范圍有限，因此相應的研究也越來越少。

　　5.2 啟發式算法。啟發式算法是相對于最優化算法提出的，指通過對過去經驗的歸納推理及實驗分析來解決問題的方法，即基于直觀推斷或經驗構造的算法。因此，啟發式算法要求分析人員運用自己的感知和洞察力，從與研究問題有關且比較具體的模型及算法中尋求相互間的聯系，從中得到啟發，發現適合于解決該問題的思路和途徑。

　　使用啟發式算法求解問題時強調主體對所求解的“滿意度”，即常常是得到滿意解，而不去追求最優解。之所以這樣是因為：(1)很多問題不存在嚴格的最優解，此時對目標的滿意性比最優性更能描述所需的選擇行為。(2)得到某些問題最優解的成本太大。(3)從實際出發，有時探求問題的最優解沒有實際意義。

　　啟發式算法指根據某種啟發式的信息對已知的可行解進行改善，通過若干次的迭代獲得相對滿意的解。與精確算法相比，啟發式算法得到的解不一定是最優解，但很有可能是近似解。同時，啟發式算法實現起來相對簡單，并且可以在相對短的時間內快速地找到滿意解。為此研究人員主要把精力放在構造高質量的啟發式算法上。目前專家已提出很多求解車輛運輸調度問題的啟發式算法，主要分為經典啟發式算法和現代啟發式算法兩類。

　　車輛路徑的啟發式算法最早由Clarke和Wright提出的用于解決車輛數不固定的節約法(The Savings Method)[13]，Gillett和Miller提出的先分群再安排路線的掃描法(Sweep Method)[14]，Bramel和Simchi-Levi提出的基于選址問題轉化的LBH算法[15]，Cullew，Jarvis和Ratliff提出的兩段法[16]，Fisher和Jaikumar建立的先分組后安排路線的一般分配算法[17]，Christofides和Minggozzi等建立的不完全樹搜索算法[18]，Pureza和Franca研究的禁忌搜索算法(Tabu Research，TS)[19]等。這些算法為求解車輛路徑問題提供了有效的方法，但也存在著一系列問題。如節約法可以列出各點對時間的節約量，并按節約量從大到小構造路徑，因此具有運算速度快的優點，但存在未組合點零亂、邊緣點難于組合的缺點;掃描法屬于非漸近優化;LBH算法則存在問題轉化麻煩且選址問題本身難解等。

　　針對車輛路徑問題的特點，構造運算簡單、尋優性能優異的啟發式算法，這不僅對于配送系統而且對于許多可轉化為車輛路徑問題求解的優化組合問題具有十分重要的意義。很多學者運用新的算法來求解車輛調度問題，如：由N. Metropolis等人于1953年提出的模擬退火算法(Simulated Annealing Algorithm，SA)[20]、由美國Michigan大學J.Holland教授于1975年提出的遺傳算法(Genetic Algorithm，GA)[21]、由M. Dorigo等人于1991年提出的蟻群算法(Ant Colony Optimization，ACO)[22]、由Kennedy和Eberhart于1995年提出的粒子群算法(Particle Swarm Optimization，PSO)[23]、由劍橋大學的楊新社教授(Xin-She Yang)提出的螢火蟲算法(Firefly Algorithm，FA)[24]等優化方法。

　　6 結束語

　　關于物流配送車輛優化調度研究的算法已廣泛應用于生產和生活的各個方面，并已經取得了良好的經濟效益。隨著我國國民經濟健康穩步地向前發展，尤其是在電子商務發展迅速的大背景下，現代物流業發展十分迅速，這些都對以運輸為中心的物流配送活動提出了更高的要求。如何針對各種地形的條件和各行業物流配送運輸的特點，結合不同的啟發式算法進行優勢互補和消除缺陷，設計出通用性好、運算速度快、精度高的優良算法，這將是今后研究發展的方向。

　　參考文獻：

　　[1] 國家統計局. 2013年全國物流運行情況通報[EB/OL]. (2014-03-06)[2014-11-20]. http：//www.stats.gov.cn/tjsj/zxfb/201403/t20140306_520357.html. 　　[2] Dantzig G， Ramser J. The Truck Dispatching Problem[J]. Management Science， 1959，6(1)：80-91.

　　[3] 李軍，郭耀煌. 物流配送車輛優化調度理論與方法[M]. 北京：中國物資出版社，2001.

　　[4] 陳震. VPN技術及其應用的研究[J]. 電腦知識與技術，2009(4)：798-799.

　　[5] 占書芳. 并行遺傳算法在帶軟時間窗車輛路徑問題中的應用研究[D]. 武漢：武漢理工大學(碩士學位論文)，2006.

　　[6] 劉寶碇，趙瑞清，王綱. 不確定規劃及應用[M]. 北京：清華大學出版社，2003.

　　[7] 郎茂祥. 配送車輛優化調度模型與算法[M]. 北京：電子工業出版社，2009.

　　[8] 劉東圓. 運輸能力限制下的運輸問題研究[D]. 北京：北京交通大學(碩士學位論文)，2009.

　　[9] Sung-Chul Hong， Yang-Byung Park. A Heuristic for Constraints[J]. International Journal of Production Economics， 1999，62：249-258.

　　[10] Desrocher M.， Desroslers J.， Solomom M.. A New Optimization Algorithm for the Vehicle Routi