干货 | 10分钟教你用column generation求解vehicle routing problems

OUTLINE

• 前言
• VRPTW description
• column generation
• Illustration
• code
• reference

00 前言

此前向大家介绍了列生成算法的详细过程，以及下料问题的代码。相信各位小伙伴对column generation已经有了一个透彻的了解了。今天我们在来一点干货，用column generation求解vehicle routing problems。

01 VRPTW description

关于VRPTW问题的描述，以及建模方式，可以参照此文干货|十分钟快速掌握CPLEX求解VRPTW数学模型（附JAVA代码及CPLEX安装流程）。不过今天给大家带来的是VRPTW的另外一个建模方式，它是在传统的模型上利用了Dantzig-Wolfe decomposition分解算法得到的。

关于Dantzig-Wolfe decomposition分解算法，可以参照文章：

• 运筹学教学|Benders decomposition（一）技术介绍篇
• 运筹学教学|Berders decomposition （二）应用实例及算法实现（附源代码及详细的代码注释）

Formulation：[1]

• $\Omega $ ：the set of feasible vehicle routes, i.e., the set of paths in G issued from the
  depot, going to the depot, satisfying capacity and time window constraints and visiting
  at most once each customer.
• $c_k$ ：the cost of route $r_k \in \Omega$.
• $ a_{ik}$ ：= 1 if route$r_k$visits customer$v_i$ and = 0 otherwise.
• $ b_{ijk}$ ：= 1 if route$r_k$uses arc$(v_i,v_j)$and = 0 otherwise.

The VRPTW can be described with the following set covering model:

where $θ_k$ indicates whether route $r_k$ is selected ($θ_k$ = 1) or not ($θ_k$ = 0) in the solution.其中$v_0$是depot点。

其中：

• 约束1保证了每个Customer都至少被服务一次。
• 约束2限制了车辆的使用数量。
• $\theta_k $定义为整数，但显然当$\theta_k > 1$时解都不是最优的。这样做的目的是为了后续使用column generation时获得一个更好的线性松弛。

02 column generation

从上面的模型中，先来讨论一个点，用$S(\Omega)$表示集合$\Omega$里面的路径数量，n表示Customer的点数，那么
$S(\Omega)$和n的关系可以看下表：

$S(\Omega)$	n
10	$(A_{10}^2+A_{10}^3+A_{10}^4+...+A_{10}^{10})/2$
20	$(A_{20}^2+A_{20}^3+A_{20}^4+...+A_{20}^{20})/2$
...	...
100	$(A_{100}^2+A_{100}^3+A_{100}^4+...+A_{100}^{100})/2$

可以看出，变量$\theta$的数目随着问题规模n的增长会爆炸式的增长。这时候，显然branch and bound这类的算法已经无能为力了，因为变量数目太多太多，搜索树会有多少个分支想都不敢想。

所以，我们上一节课讲的column generation就派上用场辣。如果相关概念还不清楚的就赶紧回去翻一翻上一次课的内容吧。

2.1 Master Problem(MP)

我们知道，column generation是求解linear program的，因为上面的model是一个整数规划模型，还不能直接挪过来当Master Problem。

在此之前，我们需要将$\theta_k \in N$给线性松弛一下变成$\theta_k >= 0$。这下$\theta_k$就从整数变量松弛为线性变量了。由此我们可以得出问题的Master Problem如下：

2.2 Restricted Master Problem(RMP)

在上述模型中，约束5中的列直观表现为一条可行的路径$r_k$，现在要Restricted一下我们的Master Problem，直接Restricted Master Problem中的 $\Omega$即可。我们设$\Omega_1 \subset \Omega$，那么Restricted Master Problem可以表示为：

然后我们再顺便把RMP的对偶model也写出来，便于后续对偶变量的求解：

在对偶模型中：

• $\lambda_i$是非负的对偶变量，对应着约束(9)。
• $\lambda_0$是非负的对偶变量，对应着约束(10)。

2.3 Subproblem

子问题要做的就是找一条路$r_k \in \Omega \setminus \Omega_1$使得，

其中，$r_k$受到的约束：

• 从depot出发，最终回到depot。
• 满足容量和时间窗的约束。

03 Illustration

在这一节我们将会给大家带来一个简单的VRPTW实例，详细演示一下column generation求解VRPTW的过程。大家可以再次熟悉一下column generation的原理。

假如我们有以下的一个very simple的VRPTW问题：

其中：

• 边上数字表示路径的距离。
• 点上的区间表示时间窗。
• 为了更加简化问题，我们假设车的容量足够大（总是能容量约束），车的数量足够多（总是能满足数量约束）。

Start

一开始我们很容易找到一个初始的路径集合$\Omega_1 = {(v_0,v_1,v_0),(v_0,v_2,v_0),(v_0,v_3,v_0) } $。
服务所有的Customer。所以得到的Restricted Master Problem和Dual programs如下：

Iteration 1

RMP ( $\Omega_1 = {(v_0,v_1,v_0),(v_0,v_2,v_0),(v_0,v_3,v_0) } $ )：

很容易求得上述模型的最优解为$\theta = (1,1,1), \lambda = (2,2.8,2)$。

现在假如subproblem通过启发式或者什么方法找到了一条路径$ r_4 = (v_0,v_1,v_2,v_0)$，路径$r_4$的reduce cost 为3.4-2-2.8 = -1.4 < 0。现在将$r_4$加入到$\Omega_1 $中，开始下一轮迭代。

Iteration 2

RMP ( $\Omega_1 = {(v_0,v_1,v_0),(v_0,v_2,v_0),(v_0,v_3,v_0), (v_0,v_1,v_2,v_0)} $ )：

Again，很容易求得上述模型的最优解为$\theta = (0,0,1,1), \lambda = (2,1.4,2)$。

subproblem找到了一条路径$ r_5 = (v_0,v_1,v_2,v_3,v_0)$，路径$r_5$的reduce cost 为4-2-1.4-2 = -1.4 < 0。现在将$r_5$加入到$\Omega_1 $中，开始下一轮迭代。

Iteration 3

RMP( $\Omega_1 = {(v_0,v_1,v_0),(v_0,v_2,v_0),(v_0,v_3,v_0), (v_0,v_1,v_2,v_0),(v_0,v_1,v_2,v_3,v_0)} $ )：

求解得到最优解为$\theta = (0,0,0,0,1), \lambda = (2,1.4,0.6)$。

现在我们可以easily发现，还剩下两条route不在$\Omega_1$之中了。而这两条route的reduce cost都非负，列生成算法停止。并且在这个例子中，linear relaxation的解是integer optimal solution。

至此，列生成算法求解VRPTW的过程结束，相信这么详细的过程大家已经看懂了。

04 code

关于列生成算法求解VRPTW的算法将会在下一期呈现，大家可以先把这两期的内容好好消化了先。请关注我们的公众号以获取最新的消息，在第一时间获取代码：

可以关注我们的公众号哦！获取更多精彩消息！

05 reference

-[1]A tutorial on column generation and branch-and-price for vehicle routing problems, Dominique Feillet