00
前言
此前向大家介绍了列生成算法的详细过程,以及下料问题的代码。相信各位小伙伴对Column Generation已经有了一个透彻的了解了。如果不熟悉的请再回去复习一下:带你彻底了解Column Generation(列生成)算法的原理附java代码
今天我们再来一点干货,用Column Generation求解带时间窗的车辆路径问题(VRPTW)的线性松弛模型。千万注意,Column Generaton可不能直接用来求解VRPTW的最优整数解哦。
01
VRPTW Description
关于VRPTW的描述,以及建模方式,可以参照此文:干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)。
不过今天给大家带来的是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
子问题要做的就是找一条路
使得,
其中,
需要满足的约束如下:
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的过程结束,相信这么详细的过程大家已经看懂了。
04
Code
关于列生成算法求解VRPTW的算法将会在下一期呈现,大家可以先把这两期的内容好好消化了先。
05
References
[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.