干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

内容纲要干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

前言

VRPTW Description

Column Generation

Illustration

Code

References

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

00 前言

 

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

 

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

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

01VRPTW Description


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

 

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

 

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

其中:

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

- 约束(2)限制了车辆的使用数量。

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型定义为整数,但显然最优解里面不会出现干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型的情况(不理解的话,仔细独自想想哦)。

 

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

 

02Column Generation

 

从上面的模型中,先来讨论一个点,用干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型表示集合干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型里的路径数量,n表示顾客数量,那么干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型和n的关系如下表所示:

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

可以看出,变量干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型的数目随着问题规模n的增长会爆炸式地增长。这时候,当n较大时,我们无法将主问题显性的写出来(变量太多,计算机的内存估计都不够了)。

 

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

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

2.1

Linear Master Problem(LMP)

 

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

 

我们需要将干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型线性松弛为干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型,这样干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型就从整数变量松弛为线性变量了。因此,我们可以得到的问题的Linear Master Problem如下:

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

2.2

Restricted Linear Master Problem (RLMP)

 

在上述模型中,约束(5)中的列直观表现为一条可行的路径干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型,现在要Restrict(真不知道怎么翻译这个单词?┭┮﹏┭┮)我们的Linear Master Problem,直接缩小变量集合干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型的范围即可。定义干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型,那么Restricted Linear Master Problem可以表示为:

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

 

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

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

 

在对偶模型中:

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型是非负的对偶变量,对应着约束(9)。

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型是非负的对偶变量,对应着约束(10)。

 

2.3

Pricing Subproblem

 

子问题要做的就是找一条路干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型使得,

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

 

其中,干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型需要满足的约束如下:

  • 从depot出发,最终回到depot;

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

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

 

03Illustration

 

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

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

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

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

其中:

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

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

 

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

 

Start

一开始我们很容易找到一个初始的路径集合干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型来服务所有的顾客。所以得到的RLMP和相应的对偶问题如下:

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

Iteration 1

RLMP ( 干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型 ):

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

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

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

现在假如subproblem通过启发式或者什么其他方法找到了一条路径干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型,且干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型的reduced cost 为3.4-2-2.8 = -1.4 < 0。那么,我们需要将干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型加入到干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型中,开始下一轮迭代。

 

Iteration 2

RLMP (  干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型):

 

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

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

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

subproblem找到了一条路径干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型,路径干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型的reduced cost为4-2-1.4-2 = -1.4 < 0。现在将干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型加入到干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型中,开始下一轮迭代。

 

Iteration 3

RLMP(干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型 ):

 

 

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

求解得到最优解为

干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型

 

现在我们可以easily发现,还剩下两条route不在干货 | 10分钟教你使用Column Generation求解VRPTW的线性松弛模型之中了。而这两条route的reduced cost都非负,列生成算法停止。并且在这个例子中,linear relaxation的解是integer optimal solution,也就是说,LMP的解是整数解,就是Master Problem的最优解。不要高兴的太早,这只是一个巧合而已。通常列生成算法只能求得Master Problem的一个下界。

 

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

 

04Code

 

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

 

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

 

干货 | 10分钟教你使用Column Generation求解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

 

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

 

 

上一篇:干货 | Branch and Price算法求解VRPTW问题(附JAVA代码分享)


下一篇:zhs_oh_my_zhs命令行高亮插件安装2021