论文标题
学习反复解决路由问题
Learning to repeatedly solve routing problems
论文作者
论文摘要
在过去的几年中，人们对基于机器学习的启发式方法引起了极大的兴趣，以解决NP-HARD组合优化问题。开发的方法在许多优化问题上显示出潜力。在本文中，我们提出了一个学识渊博的启发式方法，用于在其数据发生较小的变化后重新优化问题。我们专注于静态客户（即同一客户位置）的电容车辆路由问题的情况，并改变了需求。鉴于原始解决方案的边缘，目标是预测和修复那些在改变客户需求后有很大机会留在最佳解决方案的机会。解决方案的部分预测降低了问题的复杂性，并加快了解决方案的速度，同时产生了质量良好的解决方案。提出的方法在合理的计算时间内在不同的基准实例上产生了最佳差距的解决方案。
In the last years, there has been a great interest in machine-learning-based heuristics for solving NP-hard combinatorial optimization problems. The developed methods have shown potential on many optimization problems. In this paper, we present a learned heuristic for the reoptimization of a problem after a minor change in its data. We focus on the case of the capacited vehicle routing problem with static clients (i.e., same client locations) and changed demands. Given the edges of an original solution, the goal is to predict and fix the ones that have a high chance of remaining in an optimal solution after a change of client demands. This partial prediction of the solution reduces the complexity of the problem and speeds up its resolution, while yielding a good quality solution. The proposed approach resulted in solutions with an optimality gap ranging from 0\% to 1.7\% on different benchmark instances within a reasonable computing time.
