浮萍萍，葉春明，李佳桐

FU Ping-ping, YE Chun-ming, LI Jia-tong

（上海理工大學(xué) 管理學(xué)院，上海200093）

(Management School, University of Shanghai for Science and Technology, Shanghai 200093, China)

0 引 言

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

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

綜上所述，作為繼原材料、勞動(dòng)力以外的“第三利潤源泉”，實(shí)現(xiàn)物流合理化具有重要的經(jīng)濟(jì)意義與現(xiàn)實(shí)意義。一方面，物流配送車輛路徑優(yōu)化有助于企業(yè)降低物流成本，提高運(yùn)作效率，從而增加企業(yè)利潤。另一方面，通過緩解交通壓力，減少資源消耗和對(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ā)地，包括物流中心、配送中心、倉庫、車場等） 出發(fā)去完成一些配送任務(wù)，當(dāng)各任務(wù)量較?。ㄐ∮谲囕v容量） 時(shí)，為了提高車輛的利用率，可安排一輛車執(zhí)行幾項(xiàng)運(yùn)輸任務(wù)。這時(shí)，如何安排車輛的路線，使得既滿足各任務(wù)的需求并完成任務(wù)，而又使總成本最?。ㄟ@里的總成本指的是一個(gè)廣義概念，包括時(shí)間最少、運(yùn)營費(fèi)用最少等） 涉及的就是配送車輛路徑優(yōu)化問題。

在學(xué)術(shù)研究方面一般把這個(gè)問題抽象解釋為路線安排問題或者車輛路徑問題（Vehicle Routing Problem，VRP），可描述如下：有一個(gè)或幾個(gè)配送中心Di（i=1,2,…,n），每個(gè)配送中心有K種不同的車型，每種車型有n量車。有一批配送業(yè)務(wù)Ri（i=1,2,…,n），已知每個(gè)配送業(yè)務(wù)的需求量qi（i=1,2,…,n），要求在一定的時(shí)間范圍內(nèi)[Ei,Li]完成，求在滿足不超過配送車輛載重量等的約束條件下，安排配送車輛在合適的時(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ù)幕A(chǔ)，也是構(gòu)成VRP 的核心要素之一。通常用從中心倉庫出發(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è)的配送中心、倉庫、車站、港口等。（5） 客戶。也稱為用戶，包括分倉庫、零售商店等?？蛻舻膶傩园ㄐ枨螅ɑ蚬?yīng)） 貨物的數(shù)量、需求（或供應(yīng)） 貨物的時(shí)間、需求（或供應(yīng)） 貨物的次數(shù)及需求（或供應(yīng)） 貨物的滿足程度等。（6） 運(yùn)輸網(wǎng)絡(luò)。運(yùn)輸網(wǎng)絡(luò)由頂點(diǎn)（指物流中心、客戶、停車場）、無向邊和有向弧組成。邊、弧的屬性包括方向、權(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 簡單示意圖如圖1 所示：

圖1 VRP 示意圖

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ù)量可以分為單車場車輛路徑問題（SVRP），即一般車輛路徑問題（VRP），以及多車場車輛路徑問題（MVRP），其中MVRP 可以根據(jù)是否每輛車都有固定的終點(diǎn)車場分為終點(diǎn)車場固定的MVRP 和終點(diǎn)車場不固定的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） 決策變量目標(biāo)函數(shù)：max （minz）約束條件其中，“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é)模型可描述為：其中，f（x）為目標(biāo)函數(shù)，g（x）為約束函數(shù)，x為決策變量，D表示有限個(gè)點(diǎn)組成的集合。一個(gè)組合優(yōu)化問題可以簡單地表示為三個(gè)參數(shù)（D,F,f）。其中D為決策變量定義域，F(xiàn)為可行解區(qū)域，滿足F=｛x|x∈D,g（x）≥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ù)g（x）的約束和比較各自所對(duì)應(yīng)的目標(biāo)值f（x）的大小，即可得到該問題的最優(yōu)解。在現(xiàn)實(shí)生活中，大量優(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)地A1,A2,…,Am，產(chǎn)量分別為a1,a2,…,am，有n個(gè)銷售地B1,B2,…,Bn銷售該產(chǎn)品，銷量分別為b1,b2,…,bn，從產(chǎn)地Ai（i=1,2,…,m）調(diào)到銷售地Bj（j=1,2,…,n）的調(diào)運(yùn)量為xij，單位產(chǎn)品運(yùn)價(jià)為yij。假定產(chǎn)銷平衡，即總產(chǎn)量等于總銷量，則有求如何確定運(yùn)輸方案，使得調(diào)運(yùn)產(chǎn)品的總運(yùn)費(fèi)最小[8]？該問題的數(shù)學(xué)模型為：求xij，使得：

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-andbound）、動(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ù)的增長趨勢。由于這兩方面的限制，在解決實(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)椋海?） 很多問題不存在嚴(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ì)簡單，并且可以在相對(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)算簡單、尋優(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]、由美國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ì)效益。隨著我國國民經(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)勢互補(bǔ)和消除缺陷，設(shè)計(jì)出通用性好、運(yùn)算速度快、精度高的優(yōu)良算法，這將是今后研究發(fā)展的方向。

[1] 國家統(tǒng)計(jì)局. 2013 年全國物流運(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]. 北京：中國物資出版社，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 Routing Problem with Time Windows[J]. Operations Research, 1992,40:342-354.

[11] Kohl N., Madsen O.. An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangean Relocation[J]. Operations Research, 1997,45:395-406.

[12] Fisher M., Jornsten K., Madsen O.. Vehicle Routing with Time Windows: Two Optimization Algorithms[J]. Operations Research, 1997,45:488-492.

[13] Clarke G., Wright J.. Scheduling of Vehicles from a Central Depot to Number of Delivery Points[J]. Operations Research,1964,12(4):12-18.

[14] Gillitt B. E., Millier L. R.. A Heuristic Algorithm for the Vehicle Dispatch Problem[J]. Operations Research, 1974,22:340-349.

[15] Bramel J., Simchi-Levl D.. A Location Based Heuristic for General Routing Problems[J]. Operations Research, 1995,43:649-660.

[16] Desrochers M, Lcustra J. K., Savelsbergh M. W.. A Classification Scheme for Vehicle Routing and Scheduling Problems[J].European Journal of Operational Research, 1990,46(3):322-332.

[17] Fisher M. L., Jaikumar R.. A Generalized Assignment Heuristic for Vehicle Routing[J]. Networks, 1981,11:109-124.

[18] Christofides N., Minggozzi A., Toth P.. The Vehicle Routing Problem[M]. Combinatorial Optimization. Chechester: Wiley,1979:315-338.

[19] Pureza V. M., Franca P. M.. Vehicle Routing Problems Via Tabu Search Metaheuristics[R]. Technical Report CRT-747,Centre de Recherchesurles Transports, Montreal, 1991.

[20] Metropolis N, Rosenbluth A, Rosenbluth M, et al. Equation of State Calculations by Fast Computing Machines[J]. Journal of Chemical Physics, 1953(21):1087-1092.

[21] Holland J. H. Adaptation in Natural and Artificial System[M]. Cambridge. Massachusetts: MIT Press, 1975.

[22] Colorni A, Dorigo M, Maniezzo V, et al. Distributed Optimization by Ant Colonies[C] // Proceedings of European Conference on Artificial Life, Paris, 1991:134-142.

[23] Kennedy J, Eberhart R. Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks,1995:1942-1948.

[24] Yang Xin-she. Nature-inspired Metaheuristic Algorithms[M]. Luniver Press, UK. 2008.