Source-linked AI summary
Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem
André Hottung, Kevin Tierney
TL;DR
Purely learned routing heuristics have improved but remain behind state-of-the-art optimization methods. The paper introduces NLNS, which embeds an attention-based learned repair mechanism in large neighborhood search, and evaluates it on CVRP and SDVRP. NLNS surpasses existing machine-learning approaches, outperforms handcrafted LNS, and approaches state-of-the-art optimization performance.
Problem
Purely machine-learning routing approaches still underperform state-of-the-art optimization methods, motivating methods that narrow this performance gap.
Method
NLNS integrates reinforcement-learning-trained, attention-based neural repair heuristics into a large neighborhood search framework for vehicle routing.
Results
NLNS surpasses existing machine-learning approaches, significantly outperforms handcrafted LNS, and comes close to or matches state-of-the-art optimization approaches on CVRP and SDVRP.
Takeaways & Limitations
Guided search enables learned heuristics to achieve performance close to established optimization methods across the evaluated CVRP and SDVRP instances.
Abstract
from arXiv · showhide
Learning how to automatically solve optimization problems has the potential to provide the next big leap in optimization technology. The performance of automatically learned heuristics on routing problems has been steadily improving in recent years, but approaches based purely on machine learning are still outperformed by state-of-the-art optimization methods. To close this performance gap, we propose a novel large neighborhood search (LNS) framework for vehicle routing that integrates learned heuristics for generating new solutions. The learning mechanism is based on a deep neural network with an attention mechanism and has been especially designed to be integrated into an LNS search setting. We evaluate our approach on the capacitated vehicle routing problem (CVRP) and the split delivery vehicle routing problem (SDVRP). On CVRP instances with up to 297 customers, our approach significantly outperforms an LNS that uses only handcrafted heuristics and a well-known heuristic from the literature. Furthermore, we show for the CVRP and the SDVRP that our approach surpasses the performance of existing machine learning approaches and comes close to the performance of state-of-the-art optimization approaches.
1 INTRODUCTION
Learned heuristics have made progress in optimization and routing, but purely machine-learning approaches still trail state-of-the-art optimization. NLNS addresses this gap by embedding learned repair heuristics in large neighborhood search and evaluates the approach on CVRP and SDVRP.
- Machine-learning heuristics can automate optimization, but many problems remain difficult and learned routing methods still underperform state-of-the-art optimization.
- NLNS integrates learned heuristics into a large neighborhood search metaheuristic that repairs incomplete solutions and guides exploration of the solution space.
- NLNS is evaluated on capacitated and split-delivery vehicle routing instances against handcrafted, machine-learning, and optimization approaches.
- The neural repair mechanism uses an attention-based model trained with policy-gradient reinforcement learning, while simple destroy procedures can apply across routing problems.
- NLNS significantly outperforms handcrafted LNS and existing machine-learning approaches, while coming close to or matching state-of-the-art optimization performance.
2 RELATED WORK
Related work applies neural architectures, reinforcement learning, supervised learning, and search procedures to routing and broader optimization. NLNS differs by learning repair heuristics within LNS while aiming to reduce reliance on domain-specific knowledge.
- Pointer networks and newer neural architectures made variable-length routing representations more tractable for machine-learning methods.
- Existing VRP models use attention and recurrent decoders to construct CVRP and SDVRP solutions, often combined with actor-critic reinforcement learning and beam search.
- Graph attention networks have been trained with policy-gradient reinforcement learning to generate solutions for multiple routing problems.
- Unlike a supervised LNS approach using complex domain-specific features, NLNS automates heuristic generation without requiring deep problem or optimization knowledge.
- Other approaches learn components such as algorithm selection, search-parameter adjustment, or low-level heuristic application within hyper-heuristics.
3 NEURAL LARGE NEIGHBORHOOD SEARCH
NLNS extends large neighborhood search by using reinforcement-learned repair heuristics within GPU-oriented parallel search. It destroys solutions with simple operators, represents incomplete tours as neural inputs, and uses an attention-based policy to reconnect them feasibly.
- NLNS overview: NLNS automates repair-operator design with reinforcement learning while supporting batch and parallel single-instance search on GPUs.It extends LNS rather than replacing its destroy-and-repair structure.
- NLNS overview: LNS generates neighboring solutions by destroying parts of a solution, repairing the incomplete result, and applying an acceptance criterion.The destroy step can remove tours or other solution components, while repair restores feasibility.
- 3.1 Destroy operators: NLNS uses simple point-based and tour-based destroy procedures that remove customers or nearby tours selected around a random point.The destruction degree specifies the percentage of customers removed.
- 3.2 Learning to repair solutions: Repair is modeled as sequential reinforcement learning, connecting incomplete tours to other incomplete tours or the depot until all tours are complete and capacity-feasible.The model acts over discrete time steps on the incomplete solution.
- 3.2 Learning to repair solutions: The model encodes incomplete-tour ends and the depot as four-dimensional inputs containing coordinates, fulfilled demand, and tour-status information.Inputs are generated differently for multi-customer tours, single-node tours, and the depot, with selected values rescaled to [0, 1].
- 3.2.1 Model Architecture: At each repair step, an attention mechanism computes input relevance and a context vector, which combines with a reference-tour embedding to produce action probabilities.The network applies identical embeddings to inputs and uses a feed-forward transformation to produce the decision representation.
4 COMPUTATIONAL RESULTS
The experiments evaluate NLNS against machine-learning, handcrafted-LNS, and state-of-the-art optimization baselines on CVRP and SDVRP. NLNS consistently improves over handcrafted or purely learned search, matching or approaching strong optimization methods depending on the setting.
- 4.1 Batch Search: NLNS batch search is compared with AM and RL-BS on CVRP and SDVRP instances containing 20, 50, and 100 customers.The evaluation uses four learned repair operators for each problem class, corresponding to destroy operators with different procedures and destruction degrees.
- 4.2.1 Capacitated Vehicle Routing Problem: NLNS is evaluated against UHGS, LKH3, and an LNS using a handcrafted repair operator on grouped CVRP instances.The dataset contains 17 groups of 20 instances, with instances within each group sampled from the same distribution.
- 4.2.1 Capacitated Vehicle Routing Problem: UHGS performs best on every CVRP instance group, while its gaps to NLNS and LKH3 range from 0.08% to 3.38%.The reported comparison uses average costs and runtimes over three runs per instance, without reporting gaps to optimality.
- 4.2.1 Capacitated Vehicle Routing Problem: NLNS significantly outperforms the handcrafted-repair LNS on all CVRP instances, with gaps between 0.89% and 12.14% to UHGS.The authors state that designing a competing repair operator is complex and requires substantial effort and problem understanding.
- 4.2.1 Capacitated Vehicle Routing Problem: NLNS and LKH3 show similar CVRP performance, with NLNS finding lower-cost solutions on 11 of 17 instance groups.The paper characterizes this as the first learned heuristic to achieve performance parity with LKH3.
- 4.2.2 Split Delivery Vehicle Routing Problem: On eight SDVRP instances, SplitILS is better with 75 customers, whereas NLNS outperforms it on larger instances with 100 customers.NLNS uses two sets of learned repair operators trained on 100-customer instances, even when repairing some 75-customer instances.
5 CONCLUSION
The paper presents NLNS, which learns repair operators within a guided LNS framework for vehicle routing. Across CVRP and SDVRP evaluations, it outperforms handcrafted and purely machine-learning alternatives, approaches strong optimization methods, and surpasses SplitILS on larger SDVRP instances.
- 5 CONCLUSION: NLNS extends LNS by learning repair operators for VRP instances and using them in guided heuristic search.The framework combines learned components with high-level search rather than relying only on simple machine-learning search strategies.
- 5 CONCLUSION: NLNS's learned repair components outperform a handcrafted heuristic from the literature, and its search guidance improves over machine-learning approaches with trivial search strategies.The conclusion attributes this pattern to combining learned models with high-level search guidance.
- 5 CONCLUSION: For sequential CVRP solving, NLNS performs similarly to LKH3 but is outperformed by the population-based UHGS approach.This conclusion concerns the single-instance search setting.