An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem

最近，神经网络在组合优化方面取得了巨大进展。然而，当解决容量限制弧路线问题（CARP）时，神经网络面临挑战，即在满足容量限制的情况下，找到覆盖图上所有必需边的最小成本路径。在解决CARP时，基于神经网络的方法往往落后于先进的元启发式方法，因为它们缺乏针对复杂CARP的有向弧建模和高效学习方法。在本文中，我们介绍了一种基于神经网络的求解器，可以显著缩小与先进元启发式方法之间的差距，同时表现出卓越的效率。首先，我们提出了方向感知注意力模型（DaAM）来将方向性纳入嵌入过程，从而促进更有效的单阶段决策。其次，我们设计了一种监督增强学习方案，其中包括监督预训练，以建立强健的初始策略，以便进行后续的增强微调。这对于解决比节点路由问题（NRPs）更复杂的CARP尤其有价值。最后，我们提出了一种路径优化方法，以调整DaAM生成的路径中的车辆回到起点的位置。实验证明，我们的方法超越了启发式方法，首次实现了与最先进的元启发式方法相当的决策质量，同时保持卓越的效率。

解决问题：本论文旨在解决容量限制下的弧路线问题（CARP），提出一种基于神经网络的求解器，以缩小与先进元启发式算法之间的差距，并展示出更高的效率。

关键思路：本论文提出了方向感知注意力模型（DaAM）来将方向性纳入嵌入过程，从而促进更有效的单阶段决策制定。其次，设计了一种监督强化学习方案，其中包括监督预训练，以建立强大的初始策略，用于后续的强化微调。最后，提出了一种路径优化方法，用于调整DaAM生成的路径中的车场返回位置。

其他亮点：本文的实验表明，该方法优于启发式算法，并首次达到与最先进的元启发式算法相当的决策质量，同时保持卓越的效率。

相关研究：最近在这个领域中，也有其他相关研究，如《A Hybrid Approach to Capacitated Arc Routing Problem Based on Ant Colony Optimization and Variable Neighborhood Search》、《A hybrid genetic algorithm for the capacitated arc routing problem》等。