帶時間窗的車輛路徑問題的精確算法研究

答家瑞，鄭瀾波

（武漢理工大學 物流工程學院，湖北 武漢 430063）

帶時間窗的車輛路徑問題的精確算法研究

答家瑞，鄭瀾波

（武漢理工大學 物流工程學院，湖北 武漢 430063）

將CVRP（Capacitated Vehicle Routing Problem）中的二維車流模型擴展至VRPTW中，用它來替代列生成算法中的分支-切割過程，為解決VRPTW提供了一種新思路。同時對最少車輛數量的理論上界進行了猜想，并用Solomon基準測試包進行了實驗，求解出的算例均肯定了這一猜想。

時間窗；車輛路徑問題；運籌學；整數線性規劃；列生成；精確算法

1 引言

帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW）是對車輛路徑問題的擴展，最早由Pullen在1967年提出[1]，其主要不同點在于添加了一個時間窗來限制每個客戶地點的服務時間，該限制可以針對于客戶服務的最早開始時間、車輛停留在客戶點的最短時間以及客戶服務的最晚開始時間等，這些限制統稱為時間窗約束。

VRPTW可以定義為一組車輛(V)，一些客戶(C)和一個有向圖(G)。該有向圖中包括|C|+2個點，其中客戶點用1，2，…，n表示，倉庫點用點0（開始點）和n+1（結束點）表示。用N來表示所有點的集合，A表示所有邊的集合，即G(N,A) 。對于每條邊（i，j），cij表示該邊上的行駛成本，tij表示途經該邊的行駛時間。對于每個客戶點i都有一個時間窗[ai,bi]，即到達i點的車輛最早開始服務時間為ai，最晚開始服務時間為bi，每個點的服務時間長度為sti，需要裝載的貨物重量（容量）為di。對于每輛車都有一個相同的載重量（最大容量）q。

2 列生成算法

列生成（Column generation）[2]是一種求解大規模整數線性規劃的方法。使用它進行求解時，不需要用到原始問題中所有的變量，而是求解一個子集（subset）。具體來說列生成通常會產生一個主問題，這個主問題的解依賴于一個或多個子問題的多重解（repeated solution）。

接下來用數學的方法來描述，我們用線性規劃的方法定義主問題（master problem，MP），數學模型如下：

目標函數：

約束條件：

這是一個通用的線性規劃模型，其中集合J代表所有的列（column）。MP的對偶變量用非負向量π來表示，根據對偶理論，我們希望找到一個 j∈J能夠使得：=cj-πtaj的值最小。當 ||J的值很大時，這種直接定價（pricing）的方法運算成本很高。所以我們考慮取一個合理的子集 j'∈J來操作，用間接枚舉（implicit enumeration）的方法來計算檢驗成本（reduced cost），它被稱為限制主問題（restricted master problem，RMP）。假設λ和π分別是當前RMP的原始最優解和對偶最優解，給定一個集合A，它由列（column）aj,j∈J組成，目標函數的成本系數cj可以通過關于aj的函數式c計算得到，由此得到子問題的修改成本：

帶時間窗的車輛路徑問題（VRPTW）可以用集合劃分問題（Set-partitioning problem）的模型來構造[3]。用P來表示所有可能的路徑集合（其中的所有路徑均滿足時間窗與容量約束），對于每條路徑p∈P，cp表示路徑p的行駛成本，對于每個客戶點i，當路徑p訪問了客戶點i則aip取值為1，否則取值為0。定義路徑變量Yp，代表該路徑是否在最優路徑上，如果路徑p在最優路徑中則Yp=1，若不在則取0。數學模型如下：

目標函數：

約束條件：

目標函數（5）所有路徑的總成本最小。集合劃分約束（6）保證了每個客戶點剛好被一輛車訪問一次。

對約束條件（7）進行線性松弛，使Yp∈R，得到：

將約束條件（8）替代（7）加入到主問題模型中，就得到了線性主問題的線性模型。此時，變量Yp代表每條路徑p的權重，約束條件（6）等式左側用矩陣的方式描述可以表示為：每一列代表一條可行路徑乘以權重Yp，每一行代表一個客戶點乘以權重Yp。

基于列生成的理論，可以得到限制主問題的數學模型：

目標函數：

約束條件：

集合P'?P，僅包含所有已經生產的路徑。限制主問題（RMP）的初始解我們選擇所有只含有一個客戶點的路徑，即路徑0→i→n+1（i∈C），此時約束條件（6）等式左側的矩陣為單位矩陣。

算法主要思路如下：首先對主問題進行線性松弛，得到原始的限制主問題。接著將初始解放入限制主問題后，對其用單純形法求解，同時生成每個客戶點的對偶變量（π）并求得其值。接著對子問題目標函數中的路線行駛成本進行修改是邊（i，j）上修改后的成本，=cij-(πi+πj)/2，并求解子問題，子問題的解值稱為檢驗成本（reduced cost），解（solution）可以構成一條新的路徑。如果檢驗成本為負數（negative reduced cost），則將新的路徑作為一列（column）加入到限制主問題（restricted master problem）當中，重新求解，生成新的對偶變量，如此循環直到檢驗成本非負。最后對主問題進行求解，若可以求得整數解，則該解為最優解；若求得不為整數解，則該值為此問題的下界，接著用分支-切割法進行求解，重復上述循環直到求得最優解。

3 基于二維車流的數學模型

傳統的帶容量約束的車輛路徑問題（Capacitated VRP，CVRP）的數學模型十分豐富，但由于時間窗的約束，能夠應用到VRPTW的數學模型很少，主要是因為時間窗的約束難以和傳統的容量-子回路消除約束相結合。我們嘗試著將CVRP的經典二維車流模型加以改進，演變為適用于VRPTW的數學模型。

首先介紹傳統的容量-子回路消除約束，以下描述中出現的變量與參數均與前文敘述一致。給定一個集合W?C，定義r(W)代表W集合中能夠服務所有客戶點并滿足車輛容量約束的最小車輛數，定義，代表W集合中的所有貨物總重量。根據裝箱問題（Bin Packing Problem，BPP）的理論研究，r(W)的上界（upper bound）為d(W)/q（向上取整），憑借對CVRP整數規劃模型的多面體結構分析，學者們將該上界提高到2d(W)/q（向上取整）?；诖?，引出兩個重要的約束條件，容量切割約束（Capacity-Cut Constraints，CCCs）：

與通用子回路消除約束（Generalized Subtour Elimination Constraints,GSECs）：

可以看出這類約束在模型中的個數是指數級的，需要用分離（separation）的算法來尋找違反約束條件的集合，加入時間窗約束后，分離問題變得更加復雜，難以快速得到所需子集。由于理論上界研究的突破，應用這類約束處理CVRP十分有效，但該下界無法應用在VRPTW中。

在VRPTW中得出類似r(W)的下界，即W集合中能夠服務所有客戶點并滿足車輛容量約束和時間窗約束的最小車輛數目十分困難，所以我們考慮使用1960年Miller，Tucker和Zemlin對非對稱旅行商問題（ATSP）進行子回路消除的思路進行處理（簡稱MTZ）。引入一個額外變量ui∈R,i∈C，MTZ的約束可表述為：

不難看出經典的三維多商品網絡流模型中的時間窗約束就是由MTZ演變而來。1990年Desrochers和Laporte對MTZ進行了增強，提出了新的約束條件（簡稱DL）：

這種構造保證了當xij=1時，ui+1=uj，從而使得其多面體結構更小。

我們將這種思路應用在容量-子回路消除約束中，提出新的數學模型，其中定義K是所需車輛的數量，即路徑數量，模型如下：

目標函數：

約束條件：

目標函數（5）同樣是求總行駛路程最短。入度（indegree）和出度（outdegree）約束條件（17）和（18）保證每個客戶點進入的邊數與離開的邊數均為1；（19）與（20）保證了從倉庫點0出發的車輛數與到達倉庫點n+1的車輛數就是圖中的路徑數量；（21）和（22）確保了容量約束的滿足；（23）與（24）確保了時間窗約束的滿足，其中Mij通常代表一個非常大的常數，在該問題中它的值可以減少為

該模型相比于經典的三維多商品網絡流模型[4]，整數變量x減少了一維，但增加了一個線性變量u。提升該模型計算性能的關鍵在于如何降低K的上界，即至少需要多少輛車可以形成最優路徑。在利用列生成算法解決基于集合劃分的數學模型時，會得到線性主問題的下界（檢驗成本為0時），同時產生線性解中的路徑數量值K'（該數量值可能不是整數），我們認為K'（向上取整）或K'+1（向上取整）很有可能就是K的理論上界，所以用該模型來替代列生成算法中得到主問題線性最優解后的分支-切割過程，以測試模型質量與最優性。

4 帶資源約束的基本最短路徑問題

帶資源約束的基本最短路徑問題（Elementary Shortest Path Problem with Resource Constraints,ESPPRC）是VRPTW基于列生成算法的子問題。當用集合劃分模型作為主問題，利用列生成算法來解決VRPTW時，子問題被分解成多個性質相同的ESPPRC。更加明確地來說，子問題是一個帶時間窗與容量約束的基本最短路徑問題（Elementary Shortest Path Problem with Time Windows and Capacity Constraints，ESPPTWCC），其中“基本”（elementary）的意思是每個客戶點只能出現一次，即最優解中不存在回路（cycle）[5]。

本文基于整數線性規劃，加入以下三組有效不等式對子問題進行了建模求解。

4.1 點邊不等式

定義集合M?N，給出不等式：

M集合僅包含同時滿足以下兩個條件的點k。i→j→k是可行路徑，即在時間窗和容量約束下車輛能夠按順序依次訪問點i，j，k；邊（i，j）、（j，k）與（i，k）的修改后成本滿足

4.2 時間前后不等式

如果i點在時間窗約束下不能到達j點，即ai-bj+sti+tij＞0時，則i點只能在j點訪問后再進行訪問或者不訪問。當ai-bj-stj-tji≤0時，時間前后不等式可以表述為：

4.3 順序前后不等式

對任意客戶點i，定義兩組集合Pre,Suc?N，描述如下：

Pre代表一些只能出現在i點之前的點，Suc代表一些只能出現在i點之后的點。

考慮所有從集合Pre中出發到集合Suc的路徑，如果點i在最短路徑上，則該路徑一定會經過i點，故順序前后不等式如下：

5 實驗結果

實驗數據來自于經典的Solomon基準測試包[3]，測試包中的數據集合分為三類，

r組：客戶點坐標呈隨機分布；

c組：客戶點坐標呈現分塊聚集分布；

rc組：客戶點坐標既有隨機分布又有分塊聚集分布。

每個算例都包括100個客戶點、50個客戶點和25個客戶點三種規模，后兩種分別是取包括100個客戶點的完整算例中的前50個和25個客戶點。

計算實驗都是在含有2.5GHz的Intel（i7-4710MQ）處理器、12GB內存以及配有64位Windows操作系統的戴爾一體機上運行。使用Java（編譯版本1.7）在Eclipse上進行算法編譯，借助IBM Ilog Cplex/Concert 12.6進行建模優化。

主問題：基于集合劃分的數學模型；

子問題：加入三種有效不等式后的整數線性規劃模型。

得到主問題的下界后用基于二維車流的數學模型求最優解，該方法簡稱為ILP算法。

ILP算法是通過在Ilog Cplex中的Cplex優化器上建立列生成結構與數學模型進行求解，Cplex參數設置為默認。

實驗在求解完所有子問題得到主問題的下界后，會得到一個線性解中的路徑數量值K'，我們將二維車流模型中的K（所需的車輛數量或路徑數量）定義為整數變量，其取值范圍設置為[K ',K'+1]，直接求解該模型，輸出最優解。為了測試修改后二維車流模型的性能，我們不會將下界加入到模型中去。

目前Solomon基準測試包對于我們的算法過于困難，僅選擇其中25個客戶點的數據進行測試，以驗證修改后的二維車流模型的性能。

表中具體說明如下：

LB：下界（Lower Bound），空白格代表500秒內未求解出下界；

Opt：最優解（Opimal solution），空白格代表500秒內未求解出最優解；

Num：子問題的迭代次數，即求解了Num個子問題；

Paths：產生的路徑數量之和，即加入到主問題中列（column）的數量；

LBT：求解到下界的時間，單位是s；

OptT：修改后二維車流模型的求解時間，單位是s；

TT：總時間（Total Time）。

表1 r組25個點的VRPTW測試結果

表2 rc組25個點的VRPTW測試結果

在表1、表2和表3中，可以看出在求解出下界后，用修改后的二維車流模型來求解得最優解的時間（OptT）非常短，可以認為它能夠替代列生成算法后期的分支-定界部分。在目前求解出的所有算例中，二維車流模型的解與前人提供的最優解相同，但由于尚未求解出更多的算例，無法肯定K'+1（向上取整）就是K（最優解中的路徑數量）的理論上界，目前的結果都傾向于肯定這一猜想。

表3 c組25個點的VRPTW測試結果

6 結束語

帶時間窗的車輛路徑問題是經典的組合優化問題，也是目前應用最廣泛的運輸問題之一，具有很高的研究價值。國內的研究往往傾向于用啟發式方法解決該問題，精確算法的研究非常匱乏。對于啟發式方法，我們認為它最大的優勢在于高效性和通用性，而這也在一定程度上導致了它精確性的不足。針對一個NP-hard問題，如果沒有透徹的理論分析和精確算法做支撐，就很難建立適合的啟發式算法，更不能保證其求解質量。

我們將CVRP中的二維車流模型擴展至VRPTW中，用它來替代列生成算法中得到主問題線性最優解后的分支-切割過程，為解決VRPTW提供了一種新思路。

[1]Pullen H G M,Webb M H J.A Computer Application to a Transport Scheduling Problem[J].Computer Journal,1967,10(1).

[2]Danzig G B,Wolfe P.The decomposition algorithm for linear programming[J].Econometrica,1961,(4)：767-778.

[3]Desrochers M,Desrosiers J,Solomon M.A new optimization algorithm for the vehicle routing problem with time windows[J].Operations research,1992,40(2)：342-354.

[4]Toth P,Vigo D.The vehicle routing problem[M].Beijing：Tsinghua University Press,2011.

[5]Jepsen M K,Petersen B,Spoorendonk S,et al.A branch-andcut algorithm for the capacitated profitable tour problem[J].Discrete Optimization,2014,14(C)：78-96.

Study on Exact Algorithm for Vehicle Routing Problem with Time Window

Da Jiarui,Zheng Lanbo
(School of Logistics Engineering,Wuhan University of Technology,Wuhan 430063,China)

In this paper,we extended the 2D car flow model from the capacitated vehicle routing problem(CVRP)to the vehicle routing problem with time window(VRPTW)to replace the branch-and-cut process of the column generation algorithm and provide a new line of thinking for the solution of the VRPTW.At the same time,we hypothesized the theoretical upper bound of the minimal vehicle quantity and tested and verified it using the Solomon benchmark test package.

time window;vehicle routing problem;operations research;integer linear programming;column generation;exact algorithm

F224.0

A

1005-152X(2017)06-0095-05

10.3969/j.issn.1005-152X.2017.06.023

2017-05-01

國家自然科學基金（71501152）

答家瑞（1992-），男，湖北武漢人，碩士研究生，研究方向：運籌學與供應鏈網絡；鄭瀾波（1980-），女，武漢理工大學副教授，博士，研究方向：運籌學與供應鏈網絡。