Enhancing generalization in large-scale HCVRP: A rank-augmented neural solver

Publication Type

Conference Proceeding Article

Publication Date

8-2025

Abstract

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%.

Keywords

attention mechanism, combinatorial optimization, heterogeneous CVRP, rank-augmented, reinforcement learning

Discipline

Artificial Intelligence and Robotics | Databases and Information Systems

Research Areas

Intelligent Systems and Optimization

Publication

KDD '25: Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, Toronto, Canada, 2025 August 3-7

Volume

2

First Page

1845

Last Page

1856

ISBN

9798400714542

Identifier

10.1145/3711896.3736935

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.1145/3711896.3736935

This document is currently not available here.

Share

COinS