Abstract
The neural combinatorial optimization (NCO) approach has shown great potential for solving routing problems without the requirement of expert knowledge. However, existing constructive NCO methods cannot directly solve large-scale instances, which significantly limits their application prospects. To address these crucial shortcomings, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural combinatorial optimization. In particular, we design a powerful yet lightweight instance-conditioned adaptation module for the NCO model to generate better solutions for instances across different scales. In addition, we develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution. Experimental results show that our proposed method is capable of obtaining excellent results with a very fast inference time in solving Traveling Salesman Problems (TSPs) and Capacitated Vehicle Routing Problems (CVRPs) across different scales. To the best of our knowledge, our model achieves state-of-the-art performance among all RL-based constructive methods for TSP and CVRP with up to 1,000 nodes.
Abstract (translated)
神经组合优化（NCO）方法在解决无需专家知识的路由问题方面具有巨大的潜力。然而，现有的构建性NCO方法无法直接解决大规模实例，这严重限制了它们的应用前景。为了应对这些关键不足，本文提出了一个新的事例条件适应模型（ICAM）来更好地处理大规模神经组合优化。 特别是，我们为NCO模型设计了一个强大而轻量级的实例条件适应模块，以生成更好的实例解。此外，我们开发了一个高效的基于强化学习的三阶段训练计划，使模型能够在没有任何有标签最优解的情况下学习跨规模特征。 实验结果表明，与不同规模下的旅行商问题（TSPs）和容量车辆路由问题（CVRPs）相比，我们提出的方法具有极快的推理速度。据我们所知，我们的模型在所有基于RL的构建性方法中取得了最先进的性能，节点数量达到1000个以上。
URL
https://arxiv.org/abs/2405.01906
