干货|干货 | Column Generation算法求解VRPTW松弛模型（附java代码）干货|ColumnGeneration算法求解VR

寒假已经过去，小伙伴们这个假期里有没有好好学习呢？
【干货|干货 | 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即是影子价格，又是对偶变量，所以求解reduce cost也有两种方法：求解原问题的对偶问题，或者利用修正单纯形法得到新问题的 B n ? 1 B_n^{-1} Bn?1?矩阵。上面两篇推文分别采用这两种方法求解，建议大家都能掌握。
VRPTW主问题/子问题一般来说我们比较熟悉的模型是边-流模型，即：

干货|干货 | Column Generation算法求解VRPTW松弛模型（附java代码）

文章图片

但在这里，我们使用Set Covering的建模方法。这种模型是基于可行路径建模的，只要保证路径的可行性，模型形式上可以有很大的简化。

文章图片

在这个模型中，约束（1）可以设置为等于1；约束（3）可以设置为0-1变量。即使不这样设置，由于目标值要求最小，模型结果也会自动实现这一约束。
求解子问题的部分我们采用“直接求解原问题的对偶问题”的方法。原问题的对偶问题经过转化可以得到一个ESPPRC的子问题：

文章图片

这里的 λ i ? \lambda_i^* λi??是由主问题确定的对偶变量。
模型的细节可以参考论文以及推文干货 | 10分钟带你彻底了解Column Generation（列生成）算法的原理附java代码，或者阅读论文原文（文末获取）。在这里小编就不赘述啦。
ESPPRC的Pulse Algorithm 关于这个算法，公众号文章：

干货 | VRPTW子问题ESPPRC的介绍及其求解算法的C++代码

已经有所介绍，这里给大家简单补充一下小编的理解。
pulse算法的思想类似于深度优先搜索。实际上，使用最简单的深度优先搜索求解ESPPRC，只需要在搜索过程中判断是否符合时间窗、容量等约束，也可以成功求解。pulse算法的高明之处在于，在深度优先过程中引入了bounding scheme和roll back两部分，使用类似分支定界的方法进行剪枝，加快搜索速度。

文章图片

roll back部分通过回滚操作检查新路径是否被旧路径dominate。这种dominance关系非常好判断。如图，路径1： v s → v i → v k → v j v_s → v_i → v_k → v_j vs?→vi?→vk?→vj? 是通过路径0： v s → v i → v j v_s → v_i → v_j vs?→vi?→vj?拓展得到的。路径2的容量明显小于路径1，对于满足三角不等式的算例而言，路径2的总时长也小于路径1，因此dominance的判断只需要对比路径1和路径0的reduce cost即可。
bound部分则更类似于一般的分支定界，通过给每条路径一个解的下界判断下界与最优解的关系，进行剪枝。下界通过一个前置的bound函数获得。简单来说，bound函数通过对每一个时间段 t t t的每一个客户点 c c c绘制一个二维表，记录从 c c c出发时间为 t t t执行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、参考代码。大家在学习的时候也千万不要觉得推文内容简单就小瞧算法，一定要亲手尝试编写才能有进步。
关注公众号【数据魔术师】，在公众号内输入【cgvrptw2】
或访问github：https://github.com/zll-hust/CG-VRPTW
即可获得本文代码文献！