1、車輛路徑問題：研究綜述及展望Vehicle Routing Problem: Research Status and Prospect摘要：車輛路徑問題是物流系統(tǒng)優(yōu)化中的關(guān)鍵內(nèi)容之一，是現(xiàn)代物流管理研究中的重要內(nèi)容。本文梳理分析了車輛路徑問題 (VRP)的分類、模型及算法等，詳細(xì)綜述了多車型、多車場、時間窗車輛路徑問題研究現(xiàn)狀，指出聯(lián)盟車輛調(diào)度問題、考慮車輛（供應(yīng)）時間窗的車輛調(diào)度問題可能是VRP問題未來的新的研究趨勢。關(guān)鍵詞：車輛路徑；多車型；多車場；時間窗中圖分類號：F253.4 文獻(xiàn)標(biāo)識碼：A 最后指出Abstract: Vehicle routing problem as a key

2、content in the logistics system optimization, is an important component of modern logistics management study. This paper summarizes the classification, model and algorithm of the vehicle routing problems, and then detailed reviews the research status of the HVRP , MDVRP and VRPTW. The article finall

3、y points out that the AVRP and considering the vehicle (supply) time window of the VRP may be the new research trends of the future. Key words: vehicle routing; heterogeneous vehicle; multi-depot; time window車輛路徑問題是運(yùn)輸組織優(yōu)化中的核心問題，也是運(yùn)籌學(xué)中的一類經(jīng)典的組合優(yōu)化問題，旨在借助構(gòu)造適當(dāng)?shù)能囕v行駛路線以實(shí)現(xiàn)運(yùn)輸成本的最優(yōu)化。隨著市場經(jīng)濟(jì)的發(fā)展和物流專業(yè)化水平的提高，車輛路徑問

4、題從提出之初就受到廣泛關(guān)注。到目前為止，該問題的應(yīng)用不僅僅局限在汽車交通運(yùn)輸領(lǐng)域，在航空、通訊、電力、工業(yè)管理和計算機(jī)應(yīng)用等領(lǐng)域也有一定的應(yīng)用。1 車輛路徑問題車輛路徑問題來源于交通運(yùn)輸，最早是由Dantzig和 Ramser于1959 年發(fā)表在Management Science上的文章The truck dispatching Problem中首次研究了亞特蘭大煉油廠向各加油站發(fā)送汽油的運(yùn)輸路徑優(yōu)化問題，并提出了基于線性規(guī)劃的求解過程。在隨后的幾十年里，VRP問題得到不斷的擴(kuò)充和發(fā)展。1.1 分類自車輛路徑問題被提出后，Linus（1981），Bodin和Golden（1981），Assa

5、d（1988），Desrochers（1990）等許多學(xué)者從不同視角，按不同標(biāo)準(zhǔn)對該問題進(jìn)行了分類 Dantzig G, Ramser J. The truck dispatching problem. Management science,1959, (6): 80-91.，例如：按車輛類型分，可分為單車型問題和多車型問題；按配送中心（車場）數(shù)目分，可分為單配送中心（車場）問題和多配送中心（車場）問題；按任務(wù)特征分，可分為純送（取）貨問題和裝卸混合問題；按有無時間約束分，可分為無時間窗問題和有時間窗問題，另外可以按車輛裝載情況、按優(yōu)化目標(biāo)數(shù)、按車輛對車場的所屬關(guān)系、按已知信息的確定性分等不同

6、分類標(biāo)準(zhǔn)進(jìn)行分類。1.2 模型及算法車輛調(diào)度問題是一個較為復(fù)雜的組合優(yōu)化問題, 可以從不同的角度進(jìn)行建模。一般來說，車輛調(diào)度問題可以構(gòu)造成整數(shù)規(guī)劃模型，也可以構(gòu)造成圖論及其他模型，這些模型之間存在著某種聯(lián)系，但從建立模型時的出發(fā)點(diǎn)考慮，大多數(shù)模型均可看作是幾種模型的變形與組合。自車輛路徑問題提出以來，國內(nèi)外學(xué)者對于不同類型的車輛調(diào)度問題提出了許多不同的數(shù)學(xué)模型，并提出了許多獲得問題最優(yōu)解或次優(yōu)解的算法。車輛路徑問題的求解方法，基本上可分為精確算法、啟發(fā)式算法和亞啟發(fā)式算法三大類，具體分類情況如表2所示。表1 車輛路徑問題的算法分類 李軍，郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法.北京：中國物資

7、出版社，2001,6.技術(shù)路線算法名稱學(xué)者精確算法分支定界法Laporte1986)割平面法Kelley(1960)動態(tài)規(guī)劃法Eilon (1971)網(wǎng)絡(luò)流算法 XU和KELIY(1996)啟發(fā)式算法節(jié)約法 Clarke和Wright (1964)兩階段法Lin(1965)掃描法 Gillett和Miller (1974)數(shù)學(xué)規(guī)劃方法Kohld(1997)亞啟發(fā)式算法遺傳算法John Holland(1975)模擬退火算法Kirkpatrick (1983) 禁忌搜索算法Gendrean等(1994)蟻群算法Dorigo(1991)目前在車輛路徑問題模型研究方面，都是從不同角度、不同方向開展，

8、例如結(jié)合實(shí)際考慮時間窗、車場數(shù)、車型等要素，各有側(cè)重。在算法研究中，國內(nèi)外都進(jìn)行了大量的算法研究，從六十年代的集中在各種形式的節(jié)約算法，到七、八十年代提出了各式各樣的基于數(shù)學(xué)規(guī)劃的算法，八十年代后期時至今日，各種智能算法和并行算法的廣泛應(yīng)用 唐連生,梁劍. 突發(fā)事件下的車輛路徑問題研究綜述J. 鐵道運(yùn)輸與經(jīng)濟(jì),2008,12:56-60.。由于基本VRP問題屬于NP-hard問題，使得各類VRP問題求解難度更加復(fù)雜，仍值得進(jìn)一步研究。從現(xiàn)有研究文獻(xiàn)看，圍繞車輛路徑問題的研究非常廣泛，在此我們從多車場、多車型、有時間窗VRP問題三方向?qū)ΜF(xiàn)有研究文獻(xiàn)進(jìn)行綜述，并結(jié)合社會經(jīng)濟(jì)發(fā)展所帶來的新變化，對V

9、RP問題未來研究趨勢提出看法。2 多車型車輛路徑問題綜述多車型車輛路徑問題是車輛路徑問題的一種擴(kuò)展。根據(jù)車輛的型號是否相同，可將車輛路徑問題分為單車型問題(Homogeneous Vehicle Routing Problem, VRP)和多車型問題(Heterogeneous Vehicle Routing Problem, HVRP)。單車型問題假定車輛的型號相同，即具有相同的最大載重量與最大行駛距離以及相同的固定成本與變動成本，而多車型問題則不同，通常各車型的最大載重不同或使用成本不同。自1984年Golden等首先研究了多車型車輛路徑問題以來，國內(nèi)外學(xué)者針對多車型車輛路徑問題的求解算法

10、進(jìn)行廣泛探索。例如：Gendreau等 Fisher M L, Vehicle routing problemJ, Operations Research and Management Science,1995(8),P1-33.(1999)用禁忌搜索研究了每種車型的數(shù)量是無限的HVRP問題，即FSMVRP問題。Taillard等 Gendreau M,Laporte G, Musaraganyi C,et al. A tabu search heuristic for the heterogenous fleet vehicle routing problem J. Computers &a

11、mp; Operations Research, 1999,26(12):1153-1173.(1996) 提出了列產(chǎn)生啟發(fā)式算法求解多車型的車輛路徑問題。葉志堅，葉懷珍等 Taillard E D. A heuristic column generation method for the heterogeneous fleetVRP. Report: Centre for research on transportation, University of Montreal.1999, 1-14. (2005)總結(jié)了國外五種求解多車型問題的啟發(fā)式算法的優(yōu)缺點(diǎn)，并提出了禁忌搜索算法和大旅程法相結(jié)

12、合的混合啟發(fā)式算法。3 多車場車輛路徑問題綜述多車場車輛路徑問題(Multi-Depot Vehicle Routing Problem, MDVRP)是基本車輛路徑問題的擴(kuò)展，指的是有數(shù)個車場同時對多個用戶進(jìn)行服務(wù)，要求對各車場的車輛和行駛路線進(jìn)行適當(dāng)?shù)陌才?，在保證滿足各用戶的需求的前提下，使總的運(yùn)輸成本最低。多車場車輛路徑問題，實(shí)際上不僅是路徑問題，它還涉及到了場站的選擇和分配問題，一般可以分解為兩個子問題：將顧客分派給場站；為每個場站優(yōu)化線路。目前國內(nèi)外關(guān)于多車場車輛調(diào)度問題的研究主要集中在算法的改進(jìn)上，從傳統(tǒng)的啟發(fā)式算法的應(yīng)用到現(xiàn)在集中于現(xiàn)代啟發(fā)式算法的應(yīng)用，同時注重結(jié)合實(shí)際運(yùn)行情況，

13、對多車場問題進(jìn)行擴(kuò)充。例如：Klots等葉志堅,葉懷珍,周道平,易海燕. 多車型車輛路徑問題的算法J. 公路交通科技,2005,05:147-151.（1992）將線性規(guī)劃和啟發(fā)式算法結(jié)合起來求解MDVRP；Polacek等 Klots B, Gal S, Harpaz A. Multi-depot and multi-product delivery optimization problem with time and service constraintsR.IBM Israel, Haifa,Israel, 1992.（2004）提出一種求解MDVRPTW的變鄰域搜索算法算法；鄒彤等Po

14、lacek M, Hartl R F, Doerner K. A variable neighborhood search for the multi depot vehicle routing problem with time windowsJ.Journal of heuristics, 2004, 10(6):613-627.（2005）用遺傳算法求解MDVRP問題。此外，在MDVRP基礎(chǔ)上增添時間窗、路況情況、客戶優(yōu)先級等約束條件，使問題更具研究價值，例如：陳美軍等鄒彤,李寧,孫德寶,李菁.多車場車輛路徑問題的遺傳算法J.計算機(jī)工程與應(yīng)用,2004(21):82-83.（2007）在

15、研究考慮了客戶優(yōu)先級、路況影響、時間窗等多約束情形下的MDVRP問題。4 帶時間窗的車輛路徑問題綜述帶時間窗的車輛路徑問題(Vehicle Routing Problems with Time Windows, VRPTW)是基本車輛路徑問題的擴(kuò)展問題，即在VRP問題的基礎(chǔ)上給每個客戶加上服務(wù)所允許的時間窗約束。時間窗則是一個時間段，由客戶要求的最早服務(wù)時間和最晚服務(wù)時間確定的一個服務(wù)時間區(qū)間。這里的時間窗是從客戶角度出發(fā)，即可稱為客戶（需求）時間窗。因此考慮VRPTW問題，不僅需要在空間上進(jìn)行車輛路徑規(guī)劃，而且還需要在時間上進(jìn)行合理的安排。目前國內(nèi)外學(xué)者對VRPTW問題的研究主要集中在算法研

16、究上。Cordeau等陳美軍,張志勝,史金飛.MDVRPMC問題的智能多態(tài)蟻群算法研究C/會議/論文集缺失,2007:621-628.（2001）提出了求解VRPTW問題的通用的禁忌搜索算法；李寧，鄒彤等 Cordeau J F, Laporte G, Mercier A. A unified tabu search heuristics for vehicle routing problems with time windows J. Journal of the Operational Research Society, 2001, 52(8):928-936.（2004）將粒子群算法(P

17、SO)應(yīng)用于帶時間窗車輛路徑問題(VRPTW)中。而且在研究VRPTW問題的過程中，同時也注重對VRPTW問題的擴(kuò)充，例如結(jié)合多車場、滿載、開放式、車輛租賃等因素，使研究點(diǎn)更具現(xiàn)實(shí)意義。例如：于濱，靳鵬歡等李寧,鄒彤,孫德寶. 帶時間窗車輛路徑問題的粒子群算法J. 系統(tǒng)工程理論與實(shí)踐,2004,04:130-135.（2012）提出一個兩階段的啟發(fā)式算法來求解MDVRPTW；孫國華（2012）于濱,靳鵬歡,楊忠振. 兩階段啟發(fā)式算法求解帶時間窗的多中心車輛路徑問題J. 系統(tǒng)工程理論與實(shí)踐,2012,08:1793-1800.建立帶時間窗的開放式滿載車輛路徑問題模型，并設(shè)計了改進(jìn)的自適應(yīng)遺傳算法進(jìn)行開環(huán)路徑求解。 5 車輛路徑問題研究趨勢隨著社會經(jīng)濟(jì)的快速發(fā)展，消費(fèi)者對服務(wù)質(zhì)量要求越來越高，物流作為生產(chǎn)性服務(wù)產(chǎn)業(yè)，作用日益凸顯。車輛路徑問題作為物流系統(tǒng)優(yōu)化中的關(guān)鍵一環(huán)，也對之提出更高要求。然而市場競爭的日趨激烈，使得企業(yè)間的競爭更加白熱化，企業(yè)與企業(yè)間的競爭，開始轉(zhuǎn)變?yōu)槁?lián)盟與聯(lián)盟的競爭，企業(yè)面臨更大的壓力與挑戰(zhàn)。隨著信息技術(shù)與互聯(lián)網(wǎng)技術(shù)的突飛猛進(jìn)，特別是電子商務(wù)的快速發(fā)展，聯(lián)盟車輛調(diào)度問題則會成為車輛路徑問題的一個新的應(yīng)用研究領(lǐng)域。例如：菜鳥網(wǎng)絡(luò)科技有限公司、重慶市農(nóng)業(yè)電子商務(wù)產(chǎn)業(yè)發(fā)展聯(lián)盟的成立，都是通過組建聯(lián)盟方式，利用互聯(lián)網(wǎng)技術(shù)，有效整合資源