Enhancing Generalization in Large-Scale HCVRP: A Rank-Augmented Neural Solver

The Heterogeneous Capacitated Vehicle Routing Problem (HCVRP) is an NP-hard combinatorial optimization problem. State-of-the-art neural solvers face difficulties in generalizing to large-scale scenarios after training on small-scale instances. Our experiments reveal that performance degradation is primarily due to the low-rank nature of attention matrix in large-scale instances. This results in insufficient distinction among node features, impacting the accuracy of Markov Decision Processes. Additionally, these models utilize self-attention for vehicle information interaction, but overly incorporate features from others, which suppresses individual features and leads to a deviation from the optimal route. To address these challenges, we propose the Rank-Augmented Neural Solver (RANS), which introduces two key innovations: 1) A simple yet effective mechanism to increase and approximate the upper bound of the attention matrix's rank, enabling the generation of more distinctive node features. 2) A Dual Cross-Attention Module within the vehicle encoder that accurately captures each vehicle's optimal routes while maintaining balanced vehicle collaboration. The experimental results show that RANS performs favorably against the baselines. Notably, when applied to instances with up to 10,000 nodes, RANS achieves an inference time that is merely 13.42% of the best baseline among the neural solvers, while simultaneously reducing the min-max travel time by 23.72%.