Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Neural solvers have achieved impressive progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint-handling schemes via feasibility masking or implicit feasibility awareness can be inefficient or inapplicable for hard constraints. In this paper, we present Construct-and-Refine (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning-based feasibility refinement. Unlike prior construction-search hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework that guides the construction module to generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction-improvement-shared representation, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints to showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers. Our code, pre-trained models, and datasets are available at: https://github.com/jieyibi/CaR-constraint . Introduction Vehicle Routing Problems (VRPs) often involve complex real-world constraints (Wu et al., 2023) . Classic VRP solvers, such as LKH-3 (Helsgaun, 2017) and OR-Tools (Furnon & Perron, 2024), have relied on heuristics carefully designed by human experts to handle these constraints and approximate near-optimal solutions. Recently, Neural Combinatorial Optimization (NCO) methods (Bengio et al., 2021) have offered a different path: they automate solver design with deep learning and exploit GPUbatched inference for high efficiency while ensuring solution quality (Kwon et al., 2020) . However, recent work has primarily targeted simple variants, leaving their potential on hard-constrained VRPs underexplored. In those more complex settings, where hand-crafted heuristics often leave certain research gaps, reinforcement learning (RL)-based methods may offer a promising alternative by learning to navigate constraints directly from data. This makes effective constraint handling a key challenge in advancing the broader applicability of NCO to real-world VRPs. Most RL-based NCO solvers handle constraints via two schemes: feasibility masking and implicit feasibility awareness. Feasibility masking enforces constraints by excluding invalid actions in the Markov Decision Process (MDP). While effective for simple MDPs, it becomes intractable in complex cases where computing mask itself is NP-hard, e.g., with complex local search operators in neural improvement solvers (Ma et al., 2023) , or with interdependent constraints in neural construction Work done during the author's internship at MIT.