基于集合劃分的車輛路徑優化精確算法研究

王維杰

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

1 引言

車輛路徑優化（Vehicle Routing Problem）是運輸問題的基礎模型，絕大多數實際應用中的場景都是基于該模型的某種變形。Dantzig和Ramser在1959年首次研究了汽油配送卡車的最優車輛路線問題[l]。Clarke和Wright于1964年提出了一個有效的貪婪啟發式算法[2]。這很快引起運籌學、管理學、計算機科學、圖論等學科專家學者的高度重視。該問題的求解效率直接影響實際作業的效率，車輛配送路徑的優化對于降低物流成本、減少污染和緩解交通壓力等方面均具有重要的社會意義。

在VRP中，按已知信息的特征將VRP分為確定性VRP和非確定性VRP[3]。在VRP剛提出時，研究的結點數的規模比較小，故研究學者對精確算法的研究比較多，各種精確算法紛紛涌現，整數規劃的應用則更為廣泛，其主要的求解方法是割平面法、分支定界法以及列生成法。George Dantzig和Phil Wolfe使列生成法適合于具有可分解結構的線性規劃問題并提出了 Dantzig-Wolfe分解。Desrochers，Desrosiers，Solomon則在D-W分解的基礎上最早應用列生成算法并提出了Solomon基準測試包[3]。本文主要通過研究VRPTW的子問題—帶資源約束的基本最短路徑問題（Elementary Shortest Path Problem with Resource Constraints，ESPPRC）來對算法進行改善，該問題的松弛版本就是帶資源約束的最短路徑問題（Shortest Path Problem with Resource Constraints，SPPRC），兩者唯一不同的地方就在于是否允許重復的點出現在路徑中。大多數子問題的修改后行駛成本都是負數，允許最短路徑中包含回路（重復的點形成的循環路徑）能夠使其求得更小成本的路徑。同時在動態規劃算法的框架下，利用帕累托最優的原則能夠刪除更多的冗余路徑。因此，SPPRC的應用非常成功，越來越多的學者選擇研究SPPRC而避開ESPPRC。但是該方法有個顯著的缺點，它產生的下界質量難以保證，用ESPPRC來描述子問題則能夠保證更好的下界。

2 基于集合劃分的數學模型

帶時間窗的車輛路徑問題（Vehicle Routing Problem with Time Window）可以通過D-W分解劃分為主問題為集合劃分問題（Set-partitioning problem）及子問題為帶資源約束的基本最短路徑問題的模型。用P表示所有可能的路徑集合（其中的所有路徑均滿足時間窗與容量約束），對于每條路徑p∈P，cp表示路徑p的行駛成本，對于每個客戶點i，當路徑p訪問了客戶點i則aip取值為1，否則取值為0。定義路徑變量yp，代表該路徑是否在最優路徑上，如果路徑p在最優路徑中則yp=1，若不在則取0。VRPTW的主問題數學模型如下：

目標函數：

約束條件：

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

將約束條件（4）替代（3）加入到主問題模型中，就得到了線性主問題的線性模型。此時，變量yp代表每條路徑p的權重，可以得到限制主問題（restricted master problem，RMP）的數學模型如下：

目標函數：

約束條件：

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

子問題為帶資源約束的基本最短路徑問題（ESPPRC），如何產生合適的路徑p是解決該問題的關鍵，其常見的求解模型則是基于整數線性規劃。定義是邊（i，j）上修改后的成本代表客戶點i上的服務開始時間。

子問題數學模型：

目標函數（8）表示總行駛路程最短，即總成本（修改后）最小。約束條件（9）是容量約束；約束條件（13）和（14）是時間窗約束，Mij通常代表一個非常大的常數 max{bi-aj+sti+tij，0},(i,j)∈A 。約束條件（10）、（11）和（12）是流（flow）約束，保證了一條不含循環的路徑從倉庫點0到倉庫點n+1。約束條件（15）定義了一個0-1變量。作為VRPTW的子問題，cij是一個非負實數，而可以是任意實數（在大多數情況下都為負數）。假設λ和π分別是當前RMP的原始最優解和對偶最優解，給定一個集合A，它由列aj,j∈J組成，目標函數的成本系數cj可以通過關于aj的函數式c計算得到，由此得到子問題的修改成本：

如果-c*≥0，且不存在負的-cj,j∈J，那么就說限制主問題的解λ就是主問題的最優解。另一方面，向RMP添加的列都來自子問題的最優解，并且不斷對RMP進行重新優化。為了提升子問題的求解效率，將以下三組不等式加入子問題模型用以減少子回路。

2.1 點邊不等式

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

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

2.2 時間前后不等式

2.3 順序前后不等式

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

Pre代表一些只能出現在i點之前的點，Suc代表一些只能出現在i點之后的點?？紤]所有從集合Pre中出發到集合Suc的路徑，故順序前后不等式如下：

在利用列生成算法解決基于集合劃分的數學模型時，會得到線性主問題的下界（檢驗成本為0時），二維車流模型相比于經典的三維多商品網絡流模型，整數變量x減少了一維，我們用該模型替代列生成算法中得到主問題線性最優解后的分支-切割過程。其中定義K是所需車輛的數量，即路徑數量，模型如下：

目標函數（20）同樣是求總行駛路程最短。入度（indegree）和出度（outdegree）約束條件（21）和（22）保證每個客戶點進入的邊數與離開的邊數均為1；（23）與（24）保證了從倉庫點0出發的車輛數與到達倉庫點n+1的車輛數就是圖中的路徑數量；（25）和（26）確保了容量約束的滿足；（27）與（28）確保了時間窗約束的滿足；（29）定義了一個0-1變量。

3 兩點割集不等式

定義一個多面體（polyhedron）P?Rn，代表一組滿足有限個線性不等式的點的集合，即P={x?Rn:Ax≤b}，其中(A,b)是一個m×(n+1)階的矩陣，R表示所有實數集合。為了避免額外的時間變量s對模型多面體結構的影響，Ascheuer在2000年提出了不可行路徑約束條件，并將它應用在帶時間窗的非對稱旅行商問題（Asymmetric Traveling Salesman Problem with Time Windows，ATSPTW）中，用來替代傳統的時間窗約束與容量約束，效果很好[4]。2007年，Kallehauge把這項技術應用在VRPTW上，首次探討VRPTW的多面體結構[5]。接下來我們對Kallehauge的數學模型進行描述，定義路徑P是邊的集合{(vi,vi+1)|i=1,…,k-1}，也可以表示為P=(v1,v2,…vk)，其中|P|=k-1，若i≠j則有vi≠vj。最小不可行路徑 P={(vi,vi+1)∈A|i=1,…,k-1}，即P{(v1,v2)}和P{(vp-1,vp)}均為可行路徑。定義在圖G中的所有最小不可行路徑的集合為PG。定義xij是0-1變量，如果邊(i,j)∈A在最優路徑中則xij=1，若不在則取0。數學模型如下：

目標函數：

約束條件：

目標函數（30）是求圖中總路線長度最短。約束條件（31）與（32）保證了每個客戶點剛好訪問一次；約束條件（33）是子回路不等式，確保了圖中的路線不包含子回路；約束條件（34）是路徑不等式，保證了所有路徑都滿足時間窗和容量約束。為了得到更易進行多面體理論分析的模型，選取約束條件（10）、（11）、（12）與基于路徑不等式模型中的約束條件（33）、（34）進行混合，得到新的模型：定義路徑P是邊（arc）的集合{(vi,vi+1)|i=1,…,k-1}，也可以表示為P=(v1,v2,…vk)，其中|P|=k-1，若i≠j則有vi≠vj。

目標函數：

目標函數與約束條件的含義與前文描述的一致，由此可以定義ESPPRC的多胞形（polytope）為：

經典的Dantzig-Fulkerson-Johnson子回路刪除（subtour elimination）約束可以等價地用一組廣義割集不等式（generalized cutset inequalities，GCS）來表示：

GCS（43）對ESPPRC的多胞形（polytope）是有效的。

定義滿足以下形式的可行路徑集合P={(0,i,j,k)i,j∈C,k∈N}，對于任意一條可行路徑p∈P，兩點加強GCS不等式:

兩點情況是加強割集不等式的最小應用示例，如果將它們全部加入子問題的數學模型中，會增加N（N-1）個不等式，數量并不多，但由于已直接將三組有效不等式直接加入子問題數學模型中，本次添加更會導致部分已滿足該條件的節點求解時間變長，降低整體模型及算法的效率。本文將采用割平面回調形式加入兩點加強割集不等式，即不直接將不等式加入至子問題的數學模型，而是將兩點加強割集不等式加在根節點上，通過在每個根節點處檢查每個兩點加強割集不等式，查找調用該回調的根節點當前線性松弛解所違反的不等式，根據該節點檢查的順序逐次將所違反的不等式作為割平面加入到當前根節點中。

4 實驗結果

將CVRP中的二維車流模型擴展至VRPTW中，用它來替代列生成算法中得到主問題線性最優解后的分支-切割過程以及加入子問題中的三組不等式已被證明有效[6]。為了進一步檢驗兩點加強割集不等式的性能，本文將以未加入割集不等式的實驗組作為對照組對VRPTW進行實驗：

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

子問題：加入兩點加強割集不等式的整數線性規劃模型。

實驗數據來自于經典的Solomon基準測試包，它是目前求解VRPTW各類算法最常用的標準測試集[3]。測試包中的數據集合分為三類：

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

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

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

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

算法主要思路如下：通過D-W分解將VRPTW劃分為主問題為集合劃分以及子問題為帶資源約束的基本最短路徑問題。針對主問題：通過對其進行線性松弛得到原始的限制主問題。接著將僅含有一個客戶點的初始解帶入限制主問題后，對其用單純形法求解，同時生成每個客戶點的對偶變量（π）并求得其值。針對子問題：根據主問題所生成的對偶變量對目標函數中的路線行駛成本進行修改，通過割平面回調形式加入兩點割集不等式，求解子問題。子問題的解值稱為檢驗成本，解可以構成一條新的路徑。如果檢驗成本為負數，則將新的路徑作為一列加入到限制主問題當中重新求解，生成新的對偶變量，如此循環直到檢驗成本非負。最后對主問題進行求解，若可以求得整數解，則該解為最優解；若求得為非整數解，則該值為此問題的下界，不帶入下界用二維車流模型來進行求解。

得到主問題的下界后用基于二維車流的數學模型求最優解，該方法簡稱為ILP算法。ILP算法是通過在Ilog Cplex中的Cplex優化器上建立列生成結構與數學模型進行求解，Cplex參數設置為默認。計算實驗都是在含有2.5GHz的Intel（i7-4710MQ）處理器、12GB內存以及配有64位Windows操作系統的戴爾一體機上運行。使用Python（編譯版本2.7）進行算法編譯，借助IBM Ilog Cplex/Concert 12.6進行建模優化。具體指標定義如下：

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

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

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

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

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

TT：總時間（Total Time）。

表1 原VRPTW實驗結果（25個點窄時間窗算例）

從表1、表2對比可以看出以割平面回調形式加入兩點割集不等式后模型的求解時間全面優于原始模型，在均能求出最優解的22個算例中，改進模型的平均運行時間均小于未改進模型，可以認為兩點加強割集不等式的加入有效提升了模型的運算效率，具體數據見表3。

表2 加入兩點GCS后VRPTW實驗結果（25個點窄時間窗算例）表3 VRPTW 平均時間對比表

表2 加入兩點GCS后VRPTW實驗結果（25個點窄時間窗算例）表3 VRPTW 平均時間對比表

5 結束語

帶時間窗的車輛路徑優化是現實生活中最常見的運輸問題之一，具有很高的研究價值。但國內外學者大都將研究方向集中于啟發式算法，因其通用性及較強的可擴展性，研究方向更加豐富。但某種程度上也導致了啟發式算法的精確性不足。而針對組合優化問題，若無完整的理論分析及精確算法作為基礎，就很難建立適合的啟發式算法，更不能保證其求解質量。我們建立了基于集合劃分的數學模型，證明了兩點加強割集不等式對于子問題的多胞形是有效的，并通過割平面回調的形式對子問題加入兩點加強割集不等式，有效提升了算法的求解速度。