再探列生成（Column Generation）算法求解VRPTW松弛模型（附java源代码）
再探列生成（Column Generation）算法求解VRPTW松弛模型（附java源代码）
寒假已经过去，小伙伴们这个假期里有没有好好学习呢？
眼看着寒假快结束，小编也赶紧抓住寒假的尾巴，快马加鞭地学习了一下列生成（Column Generation）的方法，并结合往期公众号的代码：
- 干货 | 求解VRPTW松弛模型的Column Generation算法的JAVA代码分享
- 干货 | VRPTW子问题ESPPRC的介绍及其求解算法的C++代码
编写了一份“模型求解主问题+pulse algorithm求解子问题”的求解VRPTW的列生成代码，在这里和大家分享最近学到的知识。
目录：
- 列生成概述
- VRPTW主问题/子问题
- ESPPRC的Pulse Algorithm
- 代码分享&算法性能测试
列生成概述
关于列生成方法，公众号内已经有许多文章介绍了，还不太了解的小伙伴可以点击传送门：
- 干货 | 10分钟带你彻底了解Column Generation（列生成）算法的原理附java代码
- 运筹学教学|列生成（Column Generation）算法（附代码及详细注释）
简单来说，列生成算法就是单纯形法的一种变体，更适合求解大规模线性规划问题。对于一些变量很多的问题，列生成方法在最开始只考虑其中一部分变量并得到最优解，在后续问题中通过求解子问题找到使得主问题非最优的变量，将新的变量加入求解的问题中，相当于在单纯形表中添加一列。
“找到使主问题非最优的变量”就是找最小/最大的reduce cost（这里不懂的小伙伴请复习单纯形法）。求解reduce cost有两种方法：求解原问题的对偶问题，或者利用修正单纯形法得到新问题的
矩阵。上面两篇推文分别采用这两种方法求解，建议大家都能掌握。
VRPTW主问题/子问题
一般来说我们比较熟悉的模型是边-流（arc-flow）模型，即：
但在这里，我们使用Set Covering的建模方法。这种模型是基于可行路径建模的，只要保证路径的可行性，模型形式上可以有很大的简化。
在这个模型中，约束（1）可以设置为等于1；约束（3）可以设置为0-1变量。即使不这样设置，由于目标值要求最小，模型结果也会自动实现这一约束。
求解子问题的部分我们采用“直接求解原问题的对偶问题”的方法。原问题的对偶问题经过转化可以得到一个ESPPRC的子问题：
这里的
是由主问题确定的对偶变量。
模型的细节可以参考论文以及推文干货 | 10分钟带你彻底了解Column Generation（列生成）算法的原理附java代码，或者阅读论文原文（文末获取）。在这里小编就不赘述啦。
ESPPRC的Pulse Algorithm
关于这个算法，公众号文章：
- 干货 | VRPTW子问题ESPPRC的介绍及其求解算法的C++代码
已经有所介绍，这里给大家简单补充一下小编的理解。
pulse算法的思想类似于深度优先搜索。实际上，使用最简单的深度优先搜索求解ESPPRC，只需要在搜索过程中判断是否符合时间窗、容量等约束，也可以成功求解。pulse算法的高明之处在于，在深度优先过程中引入了bounding scheme和roll back两部分，使用类似分支定界的方法进行剪枝，加快搜索速度。
roll back部分通过回滚操作检查新路径是否被旧路径dominate。这种dominance关系非常好判断。如图，路径1：
是通过路径0：
拓展得到的。路径2的容量明显小于路径1，对于满足三角不等式的算例而言，路径2的总时长也小于路径1，因此dominance的判断只需要对比路径1和路径0的reduce cost即可。
bound部分则更类似于一般的分支定界，通过给每条路径一个解的下界判断下界与最优解的关系，进行剪枝。下界通过一个前置的bound函数获得。简单来说，bound函数通过对每一个时间段
的每一个客户点
绘制一个二维表，记录从
出发时间为
执行ESPPRC算法到达终点的最小reduce cost值。那么对于每一条新路径，只需要根据当前时间和节点找到二维表中对应的reduce cost，加上该路径原先的值，就能得到整条路径reduce cost的下界。
bound函数的时间段由用户划分（比方说将总时长划分为5块）。在执行bound函数时，先计算时间较迟的部分，这样在bound函数内部执行ESPPRC时也能起到剪枝效果。
传统的最短路算法一般采用labeling算法求解。关于labeling，公众号内也有推文介绍：
- 标号法(label-setting algorithm)求解带时间窗的最短路问题
相比于pulse算法，labeling算法一般采用广度优先搜索的思想，通过dominance rule进行占优剪枝。两种算法有很多异同，建议小伙伴们都有所了解。
代码分享&算法性能测试
终于到了激动人心的代码环节啦！学习了这么多理论知识，小伙伴们一定忍不住要亲自实现了吧！
在往期推文中，干货 | 求解VRPTW松弛模型的Column Generation算法的JAVA代码分享分享了一份通过模型求解ESPPRC子问题的列生成代码，这份代码中的主问题建模时在目标函数中加入了每个节点的service time，因此模型略有不同。干货 | VRPTW子问题ESPPRC的介绍及其求解算法的C++代码则分享了pulse 算法求解ESPPRC的C++代码。
小编参考了这两份代码，完全按照文中的模型和思路编写了一份列生成+pulse的代码，供大家学习参考。相比于之前另一个小编编写的列生成代码，这份代码相对简单一些，可能更适合新手学习。
在这里，小编简单的测试，模型求解子问题与pulse算法求解子问题两种算法的时间：
算例\算法 | 模型求解 | Pulse Algorithm |
|---|---|---|
C101(25点） | 2.8 | 0.8 |
C101(50点） | 16.3 | 3.9 |
C101(100点） | 126.7 | 44.9 |
可见我们学习的pulse algorithm还是很有效果的，比模型求解快了3-4倍。
那么列生成求解VRPTW的内容就到这里结束了。小编认为在学习列生成的过程中，相比于理论知识的学习，学习编程的过程更加困难，尤其是对CPLEX等求解器的学习，需要阅读大量的API、参考代码。大家在学习的时候也千万不要觉得推文内容简单就小瞧算法，一定要亲手尝试编写才能有进步。
欲获取本文源代码，请移步留言区。
- END -
文案&代码：周航（华中科技大学管理学院本科二年级）
指导老师：秦虎老师（华中科技大学管理学院）
排版：周航（华中科技大学管理学院本科二年级）
如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。
如有需求，可以联系：
秦虎老师（华中科技大学管理学院：professor.qin@qq.com）
周航（华中科技大学管理学院本科二年级：zh20010728@126.com）