基于集合划分的车辆路径优化精确算法研究

王维杰

（武汉理工大学 物流工程学院，湖北 武汉 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 结束语

带时间窗的车辆路径优化是现实生活中最常见的运输问题之一，具有很高的研究价值。但国内外学者大都将研究方向集中于启发式算法，因其通用性及较强的可扩展性，研究方向更加丰富。但某种程度上也导致了启发式算法的精确性不足。而针对组合优化问题，若无完整的理论分析及精确算法作为基础，就很难建立适合的启发式算法，更不能保证其求解质量。我们建立了基于集合划分的数学模型，证明了两点加强割集不等式对于子问题的多胞形是有效的，并通过割平面回调的形式对子问题加入两点加强割集不等式，有效提升了算法的求解速度。