内容纲要

前言

VRPTW Description

Column Generation

Illustration

Code

References

 

00 前言

 

此前向大家介绍了列生成算法的详细过程，以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。如果不熟悉的请再回去复习一下：干货 | 10分钟带你彻底了解Column Generation（列生成）算法的原理附java代码

 

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

 

 

01VRPTW Description

关于VRPTW的描述，以及建模方式，可以参照此文:干货|十分钟快速掌握CPLEX求解VRPTW数学模型（附JAVA代码及CPLEX安装流程）。

 

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

 

 

 

其中：

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

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

- 定义为整数，但显然最优解里面不会出现的情况（不理解的话，仔细独自想想哦）。

 

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

 

02Column 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；

• 每个顾客最多只能访问一次

• 满足容量和时间窗的约束。

 

03Illustration

 

在这一节我们将会给大家带来一个简单的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的过程结束，相信这么详细的过程大家已经看懂了。

 

04Code

 

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

 

如果觉得写得不错，请多多分享转发支持我们，谢谢！

 

 

05References

 

[1] A tutorial on column generation and branch-and-price for vehicle routing problems, Dominique Feillet，4OR，December 2010, Volume 8, Issue 4, pp 407–424.

 

注：参考文献下载请在公众号后台回复【cgref】不包括【】即可下载。

 

END

 

【如对代码有疑问，可联系小编，可以提供有偿辅导服务】