来聊聊最短路问题中的label-setting算法
时间过得真快！转眼间一年又过去了，我记得上一次写推文还是在去年。前段时间一直在做Label Setting相关的研究，今天趁着有空了，赶紧来聊一下吧~
一、最短路问题(SPP)
最短路问题（Shortest Path Problems）相信学过运筹学的小伙子们都不陌生了，就是给定一个网络，网络的边上有权重，找一条从给定起点到给定终点的路径使路径上的边权重总和最小。其实从广义上来说，他是一个非常大的分类。在近几十年的研究中，涌现了很多最短路问题的变种。
最简单的就是下面这种，不带任何约束的，只要路是想通的，就随便你怎么走，反正最后是cost最低就好了。
稍微难一点的就是在上面的基础上，加上资源约束，变成了带资源约束的最短路问题。也就是说，不仅要cost最低，还得满足一些奇奇怪怪的约束。比如下面的这种。定点上面[]表示的是时间窗，边上面()第一个元素表示经过这条边所需要时间，第二个元素表示经过这条边所需要花费的成本。一般来说成本和时间是正相关的，但是也有例外，比如车辆下坡的时候成本是很低。
第三种常见的，就是在上面的基础上再加一个约束，即限定每个点只能被经过一次，变成了Elemental Shortest Path Problems。这个问题可以变成很多利用column generation求解车辆路径问题的子问题。
二、label-setting算法
对于最简单的最短路问题，比较流行的算法就是Floyd算法和Dijkstra算法，这个相信大家学过运筹学都懂的啦。Dijkstra算法跟贪心有点像，而Floyd算法跟动态规划又有点像，这两个都是精确算法哦。
而对于带资源约束的最短路问题，目前比较流行的精确算法有modeling（构建arc-flow或者什么模型，调用solver进行求解）、label-setting、label-currenting以及前些年提出来的pulse算法。
而labeling算法其实就是动态规划，算法从起始点开始，不断往后进行扩展，用label记录当前的资源使用情况以及累计的cost，进行新扩展时通过当前label，判断下一个可达点是否满足扩展的条件，满足资源约束时才前往到下一个节点。如图中画虚线的就是资源不满足的情况
通常来说，在写labeling算法时，为了加快算法的运行速度，都需要加上dominance规则，即把一些潜在的比较差的label给干掉，避免它继续往下扩展浪费时间。注意，我上面用了潜在，因为如果要完全确定一个label比另一个label差的话，得一直扩展到终点。而dominance rule能通过一些判断，把扩展到中间的一些没有潜力的label给干掉。
接下来讲讲dominance rules，通常来说，对于到达了同一个点的两个Label 和, 我们假定表示从出发扩展到终点的所有子路径集合，而表示一条完整路径的cost，能把干掉，需要满足以下两个条件：
- 。
- 。
对于第一个条件的判断是非常容易的，通过记录已访问的点，即可得出未访问的点集合，假设未访问的点集合，如果，那么久等同于能扩展的路径数≥。当然你结合当前点的到达时间+时间窗（如果有的话），也能进行这个判断，并且后面这种方式可能会快点，大家可以在课后想想。
但是第二个条件比较复杂一点，因为要枚举中所有的子路径，这个枚举量随着节点数的增加，将是非常大的。因此我们往往在label中记录一些资源的消耗情况，从而通过这些情况推导出第二个条件。比如，路径的cost为整条路径的距离时（记为），在满足第一个条件的基础上，只需要即可。这是很容易想明白的，因为，我们有
当然使用距离作为cost这个是比较容易证明的，其他情况的话，可能会比较复杂一点。
所有的dominance rules都是以这两条为基础的，也就是说dominance rules生效的前提是得满足上面那两个条件，不然你把不该dominance的label给干掉了，很可能就得不出最优解了。总的来说，labeling算法的实现还是比较简单的，前提是你要把dominance rules推好，把extension condition和extension function都写好。
三、小结
其实labeling算法是解决最短路问题一种比较有效的方法，现在很多branch and price的文献中都是用的labeling，其实这个东西难点就在于如何推导dominance rules加快算法的速度。并且对于大多数dominance rules都需要给出严格的证明。
还有双向labeling，就是同时前向和后向进行扩展，然后对两个前后向的标签进行拼接。通过限制扩展迭代的条件，对整个branch and price算法进行加速。这个，以后有时间我再介绍啦！
最后，关于最短路问题，公众号之前已经做过系列更专业的教程了，大家可以去翻翻历史消息。
关于labeling的代码，可以参照以下推文：