技术分析：最短路问题中的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算法进行加速。这个,以后有时间我再介绍啦!

最后,关于最短路问题,公众号之前已经做过系列更专业的教程了,大家可以去翻翻历史消息。