Distance-aware Attention Reshaping: Enhance Generalization of Neural
  Solver for Large-scale Vehicle Routing Problems
Yang Wang Ya-Hui Jia Wei-Neng Chen Yi Mei
Neural solvers based on attention mechanism have demonstrated remarkable
effectiveness in solving vehicle routing problems. However, in the
generalization process from small scale to large scale, we find a phenomenon of
the dispersion of attention scores in existing neural solvers, which leads to
poor performance. To address this issue, this paper proposes a distance-aware
attention reshaping method, assisting neural solvers in solving large-scale
vehicle routing problems. Specifically, without the need for additional
training, we utilize the Euclidean distance information between current nodes
to adjust attention scores. This enables a neural solver trained on small-scale
instances to make rational choices when solving a large-scale problem.
Experimental results show that the proposed method significantly outperforms
existing state-of-the-art neural solvers on the large-scale CVRPLib dataset.