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

　　關(guān)鍵詞：論文發(fā)表代理機(jī)構(gòu),車輛調(diào)度,路徑優(yōu)化,啟發(fā)式算法

　　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 引 言

　　由國(guó)家發(fā)展和改革委員會(huì)、國(guó)家統(tǒng)計(jì)局和中國(guó)物流與采購(gòu)聯(lián)合會(huì)2014年3月7日聯(lián)合發(fā)布的《2013年全國(guó)物流運(yùn)行情況通報(bào)》[1]顯示，2013年中國(guó)社會(huì)物流總費(fèi)用10.2萬億元，同比增長(zhǎng)9.3%，與GDP的比率為18%。這一比率遠(yuǎn)高于美國(guó)的8.5%，日本的8.7%和德國(guó)的8.3%，高于全球平均水平約6.5個(gè)百分點(diǎn)。這些數(shù)據(jù)反映出中國(guó)物流成本偏高的現(xiàn)狀。物流總費(fèi)用中運(yùn)輸費(fèi)用5.4萬億元，同比增長(zhǎng)9.2%，占社會(huì)物流總費(fèi)用的比重為52.5%。同時(shí)，2013年中國(guó)物流業(yè)增加值3.9萬億元，同比增長(zhǎng)8.5%。可以看出，全社會(huì)物流企業(yè)收入增速低于物流費(fèi)用增速，物流企業(yè)普遍盈利能力偏低。報(bào)告總結(jié)性的指出，2013年，我國(guó)物流運(yùn)行總體平穩(wěn)，物流需求規(guī)模保持較高增幅，物流業(yè)增加值平穩(wěn)增長(zhǎng)，但經(jīng)濟(jì)運(yùn)行中的物流成本依然較高。

　　隨著人們對(duì)環(huán)境問題給予越來越多的關(guān)注，關(guān)于要求企業(yè)保護(hù)環(huán)境的法律條文相繼增加。其中，減少?gòu)U物的排放量和能源的消耗成為法律規(guī)定的兩個(gè)重要內(nèi)容。物流作為一個(gè)與環(huán)境關(guān)系密切的行業(yè)，車輛調(diào)度配送路徑優(yōu)化問題同時(shí)涉及能源消耗和廢物的排放問題，因而其一直是國(guó)內(nèi)外研究的熱點(diǎn)。

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

　　1 車輛調(diào)度問題描述

　　物流配送車輛路徑優(yōu)化問題最早是由線性規(guī)劃之父Dantzig和Ramser[2]在1959年提出，該問題是交通運(yùn)輸管理、智能救災(zāi)調(diào)度指揮系統(tǒng)、網(wǎng)絡(luò)作業(yè)調(diào)度管理系統(tǒng)、現(xiàn)代物流系統(tǒng)、物流網(wǎng)等應(yīng)用、研究領(lǐng)域中的基本問題之一，也是最重要的調(diào)度問題之一。

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

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

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

　　由以上各要素組成的VRP簡(jiǎn)單示意圖如圖1所示：

　　3 VRP的分類

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

　　4 VRP的基礎(chǔ)理論

　　4.1 線性規(guī)劃理論。線性規(guī)劃(Linear Programming)是一種在科學(xué)與工程領(lǐng)域廣泛應(yīng)用的數(shù)學(xué)模型。作為運(yùn)籌學(xué)的一個(gè)基本分支，線性規(guī)劃是實(shí)現(xiàn)管理現(xiàn)代化的有力工具。線性規(guī)劃問題研究的是一個(gè)線性函數(shù)在一組線性等式或不等式組成的約束條件下的極值。主要分為兩類：(1)對(duì)于一項(xiàng)確定的任務(wù)進(jìn)行統(tǒng)籌安排，達(dá)到在使用最少的人力物力資源的情況下完成這一任務(wù)的目標(biāo)。(2)對(duì)確定數(shù)量的人力物力資源，通過合理安排使用達(dá)到完成任務(wù)最多的目標(biāo)。

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

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

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

　　4.2 組合優(yōu)化理論。組合優(yōu)化(Combinatorial Optimization)，又稱離散優(yōu)化，是運(yùn)籌學(xué)的一個(gè)經(jīng)典分支。它研究的是在離散的、有限的數(shù)學(xué)結(jié)構(gòu)即問題的可行解集中，求滿足約束條件的目標(biāo)函數(shù)最大化(max)或最小化(min)。

　　組合優(yōu)化問題的數(shù)學(xué)模型可描述為：

　　maxminfx

　　s.t.■

　　其中，fx為目標(biāo)函數(shù)，gx為約束函數(shù)，x為決策變量，D表示有限個(gè)點(diǎn)組成的集合。一個(gè)組合優(yōu)化問題可以簡(jiǎn)單地表示為三個(gè)參數(shù)D，F(xiàn)，f。其中D為決策變量定義域，F(xiàn)為可行解區(qū)域，滿足F=x|x∈D， gx≥0，F(xiàn)中的任何一個(gè)元素稱為該組合優(yōu)化問題的可行解，f為目標(biāo)函數(shù)，滿足的可行解稱為該組合優(yōu)化問題的最優(yōu)解[7]。組合優(yōu)化的特點(diǎn)是可行解集合為有限點(diǎn)集，且有可行解一定有最優(yōu)解。由直觀可知，只要將D中的有限個(gè)點(diǎn)逐一判別是否滿足條件函數(shù)gx的約束和比較各自所對(duì)應(yīng)的目標(biāo)值fx的大小，即可得到該問題的最優(yōu)解。在現(xiàn)實(shí)生活中，大量?jī)?yōu)化問題就是從有限個(gè)狀態(tài)中選取最好的一個(gè)，因而屬于組合優(yōu)化問題。

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

　　minZ=■■x■y■

　　s.t.■

　　5 VRP的優(yōu)化算法

　　車輛運(yùn)輸調(diào)度問題的求解算法有很多種，但究其本質(zhì)來講，基本可分為最優(yōu)化算法(Exact Algorithm)和啟發(fā)式算法(Heuristic Algorithm)[9]。

　　5.1 最優(yōu)化算法。最優(yōu)化算法，也稱為精確算法，是指能夠通過有限的嚴(yán)謹(jǐn)計(jì)算和推理，運(yùn)用整數(shù)規(guī)劃、線性規(guī)劃和非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù)或數(shù)據(jù)結(jié)構(gòu)得到優(yōu)化問題的最優(yōu)解的算法。在物流車輛運(yùn)輸調(diào)度問題中，所謂最優(yōu)化算法就是找到一組路徑集合，使得其目標(biāo)函數(shù)值比其它任何一組可行路徑集合的目標(biāo)函數(shù)值更好。

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

　　5.2 啟發(fā)式算法。啟發(fā)式算法是相對(duì)于最優(yōu)化算法提出的，指通過對(duì)過去經(jīng)驗(yàn)的歸納推理及實(shí)驗(yàn)分析來解決問題的方法，即基于直觀推斷或經(jīng)驗(yàn)構(gòu)造的算法。因此，啟發(fā)式算法要求分析人員運(yùn)用自己的感知和洞察力，從與研究問題有關(guān)且比較具體的模型及算法中尋求相互間的聯(lián)系，從中得到啟發(fā)，發(fā)現(xiàn)適合于解決該問題的思路和途徑。

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

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

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

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

　　6 結(jié)束語

　　關(guān)于物流配送車輛優(yōu)化調(diào)度研究的算法已廣泛應(yīng)用于生產(chǎn)和生活的各個(gè)方面，并已經(jīng)取得了良好的經(jīng)濟(jì)效益。隨著我國(guó)國(guó)民經(jīng)濟(jì)健康穩(wěn)步地向前發(fā)展，尤其是在電子商務(wù)發(fā)展迅速的大背景下，現(xiàn)代物流業(yè)發(fā)展十分迅速，這些都對(duì)以運(yùn)輸為中心的物流配送活動(dòng)提出了更高的要求。如何針對(duì)各種地形的條件和各行業(yè)物流配送運(yùn)輸?shù)奶攸c(diǎn)，結(jié)合不同的啟發(fā)式算法進(jìn)行優(yōu)勢(shì)互補(bǔ)和消除缺陷，設(shè)計(jì)出通用性好、運(yùn)算速度快、精度高的優(yōu)良算法，這將是今后研究發(fā)展的方向。

　　參考文獻(xiàn)：

　　[1] 國(guó)家統(tǒng)計(jì)局. 2013年全國(guó)物流運(yùn)行情況通報(bào)[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] 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 北京：中國(guó)物資出版社，2001.

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

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

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

　　[7] 郎茂祥. 配送車輛優(yōu)化調(diào)度模型與算法[M]. 北京：電子工業(yè)出版社，2009.

　　[8] 劉東圓. 運(yùn)輸能力限制下的運(yùn)輸問題研究[D]. 北京：北京交通大學(xué)(碩士學(xué)位論文)，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