Distance-Aware Attention Reshaping for Enhancing Generalization of Neural Solvers.

Abstract

Neural solvers (NSs) based on the attention mechanism have demonstrated remarkable effectiveness in solving routing problems like traveling salesman problems (TSPs) and vehicle routing problems (VRPs). However, in the generalization process, we find a phenomenon of the dispersion of attention scores in existing NSs, which leads to poor performance. To improve the generalization ability of NSs, this article proposes a distance-aware attention reshaping (DAR) method. Specifically, without increasing any parameter of the neural network (NN), we utilize the distance information between nodes to adjust attention scores. This enables an NS trained on small-scale instances with a certain distribution to make rational choices when solving large-scale problems with different distributions. Its effectiveness is verified both theoretically and empirically. Extensive experiments on the TSP, asymmetric TSP (ATSP), capacitated VRP (CVRP), VRP with time windows (VRPTW), capacitated arc routing problem (CARP), and knapsack problem (KP) demonstrate the advantages of our method. Our code is available at https://github.com/ftwangyang/DAR.