教你使用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的过程结束,相信这么详细的过程大家已经看懂了。

原文发布于微信公众号 - 程序猿声(ProgramDream)

原文发表时间:2019-08-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券