  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.
