Learning Constraints-Based adaptive hypergraph neural networks for solving vehicle routing problems.

Abstract

The application of learning-based methods, particularly neural network based methods, to Vehicle Routing Problems (VRP) has emerged as a pivotal area of research within combinatorial optimization. VRPs are characterized by expansive solution spaces and complex constraints, often compounded by uncertainties, which render traditional approaches, such as exact mathematical models or heuristic methods, prone to substantial computational overhead. Although some recent learning-based methods have demonstrated good performance for VRPs with straightforward constraint scenarios, they often struggle to effectively handle the complex, hard constraints commonly encountered in practice. As the first work to incorporate hypergraph learning into routing problems, this study introduces an end-to-end framework that integrates constraint-oriented hypergraph neural networks with reinforcement learning to address these challenges in vehicle routing problems. The central motivation is that routing constraints, such as capacity limits and time-window penalties, are naturally imposed on groups of nodes and partial routes rather than on isolated pairwise edges. Therefore, a representation mechanism capable of preserving such high-order constraint semantics is needed. A key innovation of this work lies in the development of a constraint-oriented dynamic hyperedge reconstruction strategy within the designated encoder, which substantially enhances hypergraph representation learning. Additionally, the decoder leverages a double-pointer attention mechanism to iteratively generate solutions. The proposed model is trained using asynchronous parameter updates guided by hypergraph constraints and optimized through a dual loss function that includes both constraint loss and policy gradient loss. Experimental results on benchmark datasets demonstrate that this approach not only eliminates the need for complex heuristic operators but also achieves state-of-the-art (SOTA) solution quality.