物流配送中車輛路徑問題的模型及算法研究

摘要：本文介紹了車輛路徑問題的分類及限制條件，重點論述了國內外關于車輛路徑問題的模型及算法研究現狀，分析了各種算法的優缺點和適用范圍，并指出了車輛路徑問題的研究前景。

關鍵詞：車輛路徑問題；精確算法；啟發式算法

中圖分類號：TP301.6文獻標識碼：A

文章編號：1002-3100(2007)01-0092-03

Abstract: This paper presents the classifications and constraint conditions about the Vehicle Routing Problem， and discourses emphases upon achievements of models and algorithms for vehicle routing problem at homeland and abroad， and analyzes advantage or disadvantage and its applicable cope of these algorithms. Then it prospects future research orientations of it.

Key words: vehicle routing problem; accurate algorithm; heuristic algorithm

配送中心作為物流活動中專職從事配送工作的組織者，具有規模大、配送能力強的特點，從而使得由配送中心對用戶進行需求物品配送成為物流配送的主要形式，而其中配送車輛的路徑合理與否，對于配送速度、配送費用、運力配備以及配送成本與效益的影響均很大，采用科學合理的方法來確定車輛路徑便成為配送中心進行配送活動的一項重要工作。車輛路徑問題（Vehicle Routing Problem，VRP）是由G．Dantzig和 J．Ramser[1]于1959年首先提出來的，很快引起運籌學、管理學、計算機應用、組合數學、圖論等學科的專家學者的高度重視。他們對此問題進行了大量的理論研究和實驗分析，取得了很大進展。其研究結果在運輸系統、物流配送系統、快遞收發系統中都已得到廣泛應用。現在，對車輛路徑問題的研究仍然相當活躍。車輛路徑問題一般定義為：對一系列發貨點和／或收貨點，組織適當的行車路線，使車輛有序地通過它們，在滿足一定的約束條件（如貨物需求量、發送量、交發貨時間、車輛容量限制、行駛里程限制、時間限制等）下，達到一定的目標（如路程最短、費用最小、時間盡量少、使用車輛盡量少等）。由此定義不難看出，旅行商問題（Traveling Salesman Problem，TSP）是VRP的一個特例：由于Gaery已證明TSP問題是NP難題，因此，VRP也是NP難題。

1車輛路徑問題的分類

在經典VRP的基礎上，車輛路徑問題在學術研究和實際應用上產生了許多不同的延伸和變化型態，包括TSP（當VRP只包括一條路徑，且沒有能力約束時就成為TSP）、帶能力約束的車輛路徑問題（CVRP）、帶時間窗的車輛路徑問題（VRPTW）、追求最佳服務時間的車輛路徑問題（VRPDT）、多車種車輛路徑問題（FSVRP）、車輛多次使用的車輛路徑問題（VRPM）、考慮收集的車輛路徑問題（VRPB）、隨機需求車輛路徑問題（VRPSD）、動態車輛路徑問題（DVRP）、滿載/非滿載VRP、雙向VRP等。雖然VRP具有多種變化型態，事實上，根據研究重點的不同，VRP存在多種分類方式，但總的來說，在VRP中，最常見的附加條件有：

（1）能力約束。與每個客戶或城市對應的需求是個非負的值，任意車輛路徑的總重量不能超過該車輛的能力負荷。

（2）任意路徑所含城市數的上界為q。

（3）總時間約束。任意路徑的長度不能超過預先給定的界L；該長度由車輛在城市間的旅行時間和在該路徑里的每個城市i的停留時間所構成。

（4）時間窗口。必須在時間區間，里訪問城市i，并允許在城市i等待。

（5）多個城市間存在優先級關系，必須在訪問城市i之前訪問城市j。

基于此，文獻[2]按已知信息的特征將VRP分為確定性VRP和非確定性VRP，其中非確定性VRP可進一步分為隨機VRP（SVRP）和模糊VRP（FVRP）；按約束條件可分為CVRP（帶能力約束）、DVRP（帶時間距離約束）、VRPTW（帶時間窗口）；按需求是否可切分，又可分為可切分的VRP和不可切分的VRP。

2車輛路徑問題的算法

在VRP中，問題的算法與所建立的模型密切相關。由于在現有的文獻中，大部分文獻是研究確定性VRP和非確定性VRP的，因此，下文將對確定性VRP和非確定性VRP的算法作詳細介紹。

2.1確定性VRP

確定性VRP是現實中最常見的類型。它指的是這樣一類VRP：（1）在路徑規劃開始之前，規劃人員對有關路徑規劃的所有信息都是清楚的；（2）在路徑構建以后，與路徑規劃有關的信息不再變化。所謂相關信息，包括顧客的所有特征，如顧客的地理位置、所需服務時間、每個顧客的需求量等。解決這類問題的方法一般分為精確算法和啟發式算法兩類。

2.1.1精確算法

精確算法指可求出最優解的算法。到目前為止，已提出的精確算法種類較多，有分支定界法、割平面法、整數規劃算法和動態規劃算法等。

Laporte等用VRP與多重旅行商之間的關系，將VRP變形為旅行商問題后，再用分枝定界法求得問題最優解。隨后，Laporte等又將該方法拓展到具有其他邊約束的問題中。與這種方法略有不同，Christofides等先將問題轉化為“K-度中心樹”后，再采用分枝定界法進行求解。

求解確定性VRP的動態規劃算法最早由Eilon等提出。但由于他們提出的動態規劃方法需要考慮相當龐大的狀態數，故只能精確求解規模非常小的問題。Christofides等通過運用狀態空間松弛技術大大減少了狀態數，使動態規劃算法的性能得到了很大程度上的改善。他們的實驗表明，該方法可有效求解頂點數不超過50的有容量約束VRP。

確定性VRP也可以表示為整數線性規劃模型，主要有三種：集分割模型、貨物流模型和車輛流模型。Balinsk等最早利用集分割模型來研究VRP。然而，這個模型與一般的動態規劃模型有著相同的缺點，即使對于規模較小的問題，模型的變量數在大多數情況下亦是天文數字，比如問題的規模若為10，那么模型中出現的變量數最多可達到1010。除此之外，確定目標函數中的值往往先要求解大量的NP難題（如旅行商問題），這也給問題精確求解帶來困難。采用列生成技術可部分解決這些困難，如Agarwal等，Desrosiers等采用列生成技術求解了規模較小有容量和時間窗約束的確定性VRP。

貨物流模型和車輛流模型是整數線性規劃模型中的另外兩種：貨物流模型明確地考慮通過每條路徑的貨物量，車輛流模型則體現了系統中車輛的最優運行方案。在以往的研究中，采用的流變量主要包括兩類——雙下標變量和三下標變量，如 和 分別表示通過弧i，j的貨物量和通過弧i，j駛往顧客l的貨物量。使用雙下標和三下標變量各有優劣。雙下標變量的特點是簡便，涉及的變量較少，然而卻不能反映不同車輛的成本與特征，因此只適用于車輛類型相同的情況。Desrosiers等，Laporte等分別采用了雙下標變量來建摸，其中Laporte等提出了一種約束松弛算法，應用于約束條件較松的問題，效果較好。相比之下，三下標的VRP模型更通用一些，然而涉及的變量一般較多。Fisher等研究了有容量和時間窗約束VRP的三下標模型，并且基于Bender分解，通過交替求解一般指派問題和有時間窗的旅行商問題來求解該問題。后來Martello等又對該算法進行了一些改進。

2.1.2啟發式算法

啟發式算法是一種尋找近憂解的算法，目前已提出的啟發式算法很多，分類也相當多。按傳統的VRP啟發式算法分類，可分為構造算法、兩階段法、不完全優化算法和改進算法4類。

（1）構造算法

構造算法是根據一定的準則，每一次將一個不在線路上的點增加進線路，直到所有的點都被安排進線路為止。如Clarke-Wright節約算法、Solomon插入法，Salhi等提出的簇插入法，Gendreau等提出GENI插入法，Altinkemer和Gavish提出的并行節約算法以及Paessens提出的節約算法等。

（2）兩階段法（Two-phase Algorithm）

兩階段法的基本做法是在第一階段得到一可行解，第二階段通過對點的調整，在始終保持解可行的情況下，每次迭代產生一個解用以替代原來的解，力圖使目標函數值得以改進，一直繼續到不能再改進目標函數時為止。如Gillett和Miller的Sweep算法，Renaud等的Petal算法，Toth和Vigo提出的先聚類再安排路徑的算法，Lin提出的2-opt和3-opt交換，Or提出的Or-opt交換以及Breedam提出的串重置和串交換，Cordone等提出的改進算法等。

一些基于數學規劃的算法也屬于兩階段法，首先把問題表達成一個數學規劃模型，根據其模型的特殊構形，利用一定技巧進行分劃，進而求解易于處理的子問題。如Kohld等先利用Lagrangian松弛技術將有時間窗的VRP變為較簡單的指派問題，然后用列生成技術來獲得問題的近似解。

另外，還有一些兩階段算法在求解過程中常常采用交互式優化技術，把人的主觀能動作用結合到問題的求解過程中。如Cullew、Jarvis和Ratliff提出的兩階段法。

（3）不完全優化算法

以啟發式準則代替精確算法中的決策準則，以縮小搜索空間，如Christofides， Mingozzi和Toth提出的算法。

（4）改進算法

從一初始解開始，通過對當前的解進行反復地局部擾亂以達到較好的解。基于啟發式的并行算法和亞啟發式算法都屬于此類。

亞啟發式算法包括禁忌搜索算法、模擬退火算法、神經網絡和遺傳算法等方法。進入20世紀90年代，這些亞啟發式算法的應用成為VRP研究中的新趨勢。如Gendreau、Hertz和Laporte，Jiefeng和James，Duhamel、Christophe和Potvin，Barbarosoglu、Gulayhe和Ozgur等將禁忌搜索算法應用于VRP的求解，并取得了較好的效果。另外，模擬退火算法、神經網絡以及遺傳算法等亞啟發式算法也已經較成功地解決了確定性VRP中的一些問題。

2.2非確定性VRP

對應于確定性VRP，非確定性VRP指的是：（1）在路徑規劃開始之前，不是有關路徑規劃的所有信息，計劃人員都是確切知道的，部分信息可能是不確定的、模糊的，甚至是未知的；（2）初始路徑構建以后，信息可能會發生變化。很明顯，與傳統確定型VRP相比，非確定型VRP是一個更一般化的VRP問題。非確定性VRP又可分為隨機VRP（SVRP）和模糊VRP（FVRP）。

2.2.1隨機VRP

對這種類型的問題，目前出現的算法大部分可以歸納為以先驗（即定）序列為基礎的方法。該方法分為兩個階段：在信息不完全（隨機）的情況下確定先驗序列；在獲得確定性信息的情況下進行決策。因此，其隨機模型的選擇基于兩點：第一階段的成本和第二階段的期望成本。先驗序列的確定方法又有兩類：一類是按二元可能性理論來確定，另一類則是基于機會約束規劃。

第一類方法的思想最早是在Jaillet的博士論文中提出的，并在Bertimas的博士論文中基本建立完整的體系。在該方法中，假定需求分布是二元（即在第i點有單位需求的概率為n，則沒有單位需求的概率為）、離散的。根據該假定，可推出先驗序列的期望長度，相應的上下界和漸進特性。Michel Gendreau等人以該理論為基礎，得到目標函數和罰函數，以Clark-Wright算法生成初始解，然后用禁忌搜索算法對初始解進一步優化，可以求解規模為46的問題。而Laporte基于L-Shaped方法，提出一個精確算法，可解決規模小于50的問題。

另一類方法是Stewart，Laporte等人分別使用機會約束規劃，在一定的假定條件下，將SVRP轉化為等價的、確定性的VRP，并找到了解的界，其方法的核心是讓出錯返回的概率不超過一定的界限。機會約束規劃模型均以確定性VRP的三下標流和二下標流模型為基礎，添加可能性約束條件和罰函數后建立起來的。所用的算法，也與確定性的算法有不少相通之處。如M. Dror就是在建立三下標流機會約束規劃模型和罰函數模型后，利用Clark-Wright算法進行求解的。

第二階段的策略為：按照先驗序列，跳過需求為零的客戶，直接訪問下一個客戶，如果車輛負荷超過了車輛最大載重量，則返回出發點卸載，并回到出現超載的地方，繼續提供服務。

2.2.2模糊VRP

D. Teodorovic等人是最早著手研究這類問題的人。他以模糊數表示客戶點的需求信息，以傾向度為基礎建立模糊判定規則，其核心是基于Sweep算法，并省略了Sweep算法的第二階段，即初始化子路徑后對它們的優化過程。

祝崇俊、劉民、吳澄等人以模糊可能性分布，建立了VRP的基于置信度的三下標流模型，并提出了基于可能性分布的2-OPT算法。該算法引入了偽出發點，建立了以置信度為基礎的判定規則，以遍歷為終止條件，從而在全局層次上進行優化，同時避免過多地擴大搜索空間。該算法已可解決較大規模的問題（大于200個客戶）。

3各種算法比較

（1）關于精確算法：由于這些算法都基于嚴格的數學手段，在可以求解的情況下其解通常要優于人工智能算法。但引入嚴格的數學方法后，則無法避開指數爆炸問題，從而使該類算法只能有效求解中小規模的確定性VRP。

（2）關于啟發式算法：在求解中小規模VRP時，啟發式算法與精確算法相比，在精度上不占優勢。但在求解大規模VRP時，啟發式算法總可以在有限時間里，找到滿意的次優解/可行解，這是精確算法難以做到的。因此，在實際應用中，啟發式算法要更廣泛。

（3）確定性VRP是非確定性VRP研究的基礎。目前，我國對復雜的VRP研究還仍處于起步狀態。但現實生活中最常見的還是不確定VRP，大部分確定性VRP是不確定性VRP的簡化。現有的SVRP的成果己經可以解決小規模的SVRP，但不能勝任較大規模的SVRP。解決較大規模的SVRP的現實途徑仍然是人工智能方法，不過要獲得通用的高效算法是困難的，因此應結合鄰域特征來研究并對具有不同鄰域特征的問題提出不同的算法。對于FVRP，應結合模糊可能性理論來進行研究。

4結束語

目前VRP模型方面雖有許多研究，但缺少綜合方面的研究。現代物流中，要求盡量減少庫存，及時配送變得越來越重要，所以今后滿足客戶的時間窗口是制定車輛路線優先考慮的重點。還有現有的配送路線的研究多為開發靜態的模型，很少分析參數隨時間變化的特性，而在現代物流日趨快速化、信息化、實時化的情況下已經有些不適應。例如，倉庫位置的成本將隨時間變化；在一定的時間范圍內，公司需要根據情況的變化來重新決策配送中心及銷售網點的分布。因此，在配送路線模型中加入動態特性，實現實時或在線物流管理，會極大地提高與現實接近的程度。

參考文獻：

[1]Dantzig G， Ramser J. The truck dispatching problem[J]. Managment Science， 1959(6):80-91.

[2] 祝崇雋，劉民，吳澄. 供應鏈中車輛路徑問題的研究進展及前景[J]. 計算機集成制造系統，2001，7(11):1-6.

[3] 張強，荊剛，陳建嶺. 車輛路線問題研究現狀及發展方向[J]. 交通科技，2004(1):60-62.

[4] 荊海霞. 物流配送中雙向運輸車輛路徑優化問題研究[D]. 武漢：武漢大學（碩士學位論文），2004.

[5] 肖增敏，李軍. 動態網絡車輛路徑問題：研究現狀及展望[J]. 系統工程，2004，22(7):68-71.

[6] 尚華艷. 物流配送中車輛路徑問題研究[D]. 武漢：武漢理工大學（碩士學位論文），2005.

[7] 謝秉磊，郭耀煌，郭強. 動態車輛路徑問題：現狀與展望[J]. 系統工程理論方法應用，2002，11(2):116-120.

[8] 張建勇. 模糊信息條件下車輛路徑問題研究[D]. 成都：西南交通大學（博士學位論文），2004.