# Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood

arXiv: https://arxiv.org/abs/2012.10384 · HTML: https://mlsanity.com/paper/2012.10384/

## Key facts

- Cited by 125 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2020.

## Built on by (most cited first, 30 of 125)

- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization](https://mlsanity.com/paper/2301.03313/) (2023)
- [Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt](https://mlsanity.com/paper/2310.18264/) (2023)
- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts](https://mlsanity.com/paper/2405.01029/) (2024)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy](https://mlsanity.com/paper/2308.14104/) (2023)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [PyVRP: a high-performance VRP solver package](https://mlsanity.com/paper/2403.13795/) (2023)
- [INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer](https://mlsanity.com/paper/2402.02317/) (2024)
- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [Guidelines for the Computational Testing of Machine Learning approaches to Vehicle Routing Problems](https://mlsanity.com/paper/2109.13983/) (2021)
- [Distance-aware Attention Reshaping: Enhance Generalization of Neural Solver for Large-scale Vehicle Routing Problems](https://mlsanity.com/paper/2401.06979/) (2024)
- [Neural Deconstruction Search for Vehicle Routing Problems](https://mlsanity.com/paper/2501.03715/) (2025)
- [Destroy and Repair Using Hyper Graphs for Routing](https://mlsanity.com/paper/2502.16170/) (2025)
- [Learning to Reduce Search Space for Generalizable Neural Routing Solver](https://mlsanity.com/paper/2503.03137/) (2025)
- [ARS: Automatic Routing Solver with Large Language Models](https://mlsanity.com/paper/2502.15359/) (2025)
- [MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver](https://mlsanity.com/paper/2506.02935/) (2025)

## Abstract (arXiv)

The vehicle routing problem is one of the most studied combinatorial optimization topics, due to its practical importance and methodological interest. Yet, despite extensive methodological progress, many recent studies are hampered by the limited access to simple and efficient open-source solution methods. Given the sophistication of current algorithms, reimplementation is becoming a difficult and time-consuming exercise that requires extensive care for details to be truly successful. Against this background, we use the opportunity of this short paper to introduce a simple -- open-source -- implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research. In particular, it includes an additional neighborhood called SWAP* which consists in exchanging two customers between different routes without an insertion in place. As highlighted in our study, an efficient exploration of SWAP* moves significantly contributes to the performance of local searches. Moreover, as observed in experimental comparisons with other recent approaches on the classical instances of Uchoa et al. (2017), HGS still stands as a leading metaheuristic regarding solution quality, convergence speed, and conceptual simplicity.