Rethinking Constraint Awareness for Efficient State Embedding of Neural Routing Solver
2026-05-11 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors studied a type of neural network called Heavy-Encoder-Light-Decoder (HELD) used to solve vehicle routing problems (VRPs). They found that current methods limit what information the model can use when making decisions, which lowers solution quality. To fix this, they introduced a new module called Constraint-Aware Residual Modulation (CARM) that helps the model understand problem constraints better while using all the information available. Their experiments show that adding CARM improves the solvers, especially for larger and more complex routing problems.
Vehicle Routing ProblemNeural Routing SolversHeavy-Encoder-Light-DecoderState EmbeddingAttention MechanismConstraint AwarenessGlobal Observation SpaceResidual ModulationMulti-task LearningScaling in Neural Networks
Authors
Canhong Yu, Changliang Zhou, Rongsheng Chen, Zhenkun Wang, Yu Zhou
Abstract
Heavy-Encoder-Light-Decoder (HELD) neural routing solvers have emerged as a promising paradigm due to their broad applicability across multiple vehicle routing problems (VRPs). However, they typically struggle with VRP variants with complex constraints. To address this limitation, this paper systematically revisits existing neural solvers from the perspective of the generation mechanism for state embeddings (i.e., query vector prior to compatibility calculation) during decoding. We identify that current mechanisms restrict the observation space during attention computation, introducing a key bottleneck to achieving high-quality solutions. Through detailed empirical analysis, we demonstrate the necessity of preserving a global observation space. To overcome the constraint-agnostic drawback inherent to global observation spaces, we propose a simple yet powerful Constraint-Aware Residual Modulation (CARM) module. By adaptively modulating the context embedding with constraint-relevant variables, CARM effectively enhances constraint awareness, enabling the neural solver to fully leverage the global observation space and generate an efficient state embedding. Extensive experimental results across two single-task and five multi-task neural routing solvers confirm that the CARM module consistently boosts baseline performance. Notably, solvers equipped with our CARM achieve substantial improvements in scaling to large-scale instances and in generalizing to unseen VRP variants. These findings provide valuable insights for the architectural design of neural routing solvers.