Revisiting Autoregressive GCNs for Vehicle Routing Problems

Autoregressive (AR) Attention Models have become the dominant paradigm in neural solvers for vehicle routing problems (VRPs), while GCNs are almost exclusively paired with non-autoregressive (NAR) decoding and post-search algorithms. In this work, we revisit the role of decoding strategies and model properties in neural VRP solvers, and challenge the conventional pairing of NAR decoding with GCNs. We propose AR-GCN, an efficient and generalizable architecture for both Symmetric and Asymmetric VRPs (SVRPs and AVRPs). Extensive benchmarks across multiple tasks show that AR-GCN achieves advanced generalization performance, particularly on AVRPs (e.g, achieving an optimality gap of 1.71% on ATSP-1K and -4.46% on ACVRP-1K). In particular, AR-GCN requires only 0.633M learnable parameters and 3-epoch training, providing new insights into the design of AR solvers for general VRPs.