教你使用Column Generation求解VRPTW的线性松弛模型

00

前言

此前向大家介绍了列生成算法的详细过程，以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。

今天我们再来一点干货，用Column Generation求解带时间窗的车辆路径问题(VRPTW)的线性松弛模型。千万注意，Column Generaton可不能直接用来求解VRPTW的最优整数解哦。

01

VRPTW Description

今天给大家带来的是VRPTW的Set Covering建模方式，它是基于传统的模型，通过Dantzig-Wolfe分解法得到的。VRPTW的Set Covering模型如下：

其中：

- 约束（1）保证了每个顾客至少被服务一次。

- 约束（2）限制了车辆的使用数量。

-

定义为整数，但显然最优解里面不会出现

的情况（不理解的话，仔细独自想想哦）。

这个Set Covering模型就被称为VRPTW的主问题（Master Problem）。

02

Column Generation

从上面的模型中，先来讨论一个点，用

表示集合

里的路径数量，n表示顾客数量，那么

和n的关系如下表所示：

可以看出，变量

的数目随着问题规模n的增长会爆炸式地增长。这时候，当n较大时，我们无法将主问题显性的写出来（变量太多，计算机的内存估计都不够了）。

所以，我们上一篇推文讲的Column Generation就派上用场辣。如果相关概念还不清楚的话就赶紧回去翻一翻上一篇推文的内容吧。

2.1

Linear Master Problem(LMP)

我们知道，Column Generation是求解线性规划模型的，但是上面的主问题是一个整数规划模型，所以……

我们需要将

线性松弛为

，这样

就从整数变量松弛为线性变量了。因此，我们可以得到的问题的Linear Master Problem如下：

2.2

Restricted Linear Master Problem (RLMP)

在上述模型中，约束（5）中的列直观表现为一条可行的路径

，现在要Restrict（真不知道怎么翻译这个单词？┭┮﹏┭┮）我们的Linear Master Problem，直接缩小变量集合

的范围即可。定义

，那么Restricted Linear Master Problem可以表示为：

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

在对偶模型中：

-

是非负的对偶变量，对应着约束(9)。

-

是非负的对偶变量，对应着约束(10)。

2.3

Pricing Subproblem

子问题要做的就是找一条路

使得，

其中，

需要满足的约束如下：

• 从depot出发，最终回到depot；
• 每个顾客最多只能访问一次
• 满足容量和时间窗的约束。

03

Illustration

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

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

其中：

- 边上数字表示路径的距离。

- 点上的区间表示时间窗。

为了更加简化问题，我们假设车的容量足够大（总是能满足容量约束），车的数量足够多（总是能满足数量约束）。

Start

一开始我们很容易找到一个初始的路径集合

来服务所有的顾客。所以得到的RLMP和相应的对偶问题如下：

Iteration 1

RLMP (

)：

很容易求得上述模型的最优解为

。

现在假如subproblem通过启发式或者什么其他方法找到了一条路径

，且

的reduced cost 为3.4-2-2.8 = -1.4 < 0。那么，我们需要将

加入到

中，开始下一轮迭代。

Iteration 2

RLMP (

)：

Again，很容易求得上述模型的最优解为

。

subproblem找到了一条路径

，路径

的reduced cost为4-2-1.4-2 = -1.4 < 0。现在将

加入到

中，开始下一轮迭代。

Iteration 3

RLMP(

)：

求解得到最优解为

。

现在我们可以easily发现，还剩下两条route不在

之中了。而这两条route的reduced cost都非负，列生成算法停止。并且在这个例子中，linear relaxation的解是integer optimal solution，也就是说，LMP的解是整数解，就是Master Problem的最优解。不要高兴的太早，这只是一个巧合而已。通常列生成算法只能求得Master Problem的一个下界。

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