Source-linked AI summary
Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood
Thibaut Vidal
TL;DR
The paper addresses limited access to simple, efficient, open-source routing methods by introducing HGS-CVRP, an open-source hybrid genetic search specialized to the CVRP. It adds the SWAP* neighborhood and supporting exploration strategies to the HGS framework. The resulting method is reported as a leading metaheuristic in solution quality and convergence speed while remaining conceptually simple.
Problem
Many recent studies lack simple and efficient open-source routing methods, while reimplementation of sophisticated algorithms is difficult and time-consuming.
Method
The paper introduces HGS-CVRP, an open-source HGS implementation for the CVRP that adds SWAP* and incorporates methodological lessons from a decade of VRP research.
Results
HGS-CVRP stands as a leading metaheuristic in solution quality and convergence speed while remaining conceptually simple.
Takeaways & Limitations
SWAP* contributes substantially to search performance, especially late in local search when improving moves are harder to find.
Takeaways & Limitations
The authors note that HGS-CVRP could be improved with set-partitioning, decomposition, or ruin-and-recreate components, but deliberately retain a simple design.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces HGS-CVRP, an open-source hybrid genetic search specialized to the CVRP, addressing the difficulty of reproducing simple and efficient routing methods. It combines a concise design with SWAP* and reports strong solution quality and convergence performance.
- Recent routing research is hindered by the difficulty and time required to reproduce sophisticated heuristic solution methods.The paper emphasizes the need for methods that balance sophistication with simplicity and transparency.
- HGS-CVRP is an open-source, transparent, specialized, and concise implementation of hybrid genetic search for the canonical CVRP.The implementation retains core components while avoiding complexity from additional operators and hybridizations.
- The method combines crossover for diversification with efficient local search for solution improvement.
- SWAP* exchanges customers between routes and contributes improving moves that other neighborhoods may miss.Its moves can be explored in sub-quadratic time despite a Θ(n4) neighborhood, using pruning strategies.
- HGS-CVRP reaches the original HGS solution quality in a fraction of its computational time and largely outperforms other existing CVRP algorithms.
2 Hybrid Genetic Search for the CVRP
HGS-CVRP repeatedly generates and improves CVRP solutions through genetic recombination, local search, infeasible-solution exploration, and population management. Its CVRP specialization replaces pattern improvement with SWAP* while retaining structured diversity and feasibility control.
- The CVRP minimizes route distance while assigning every customer once to routes that respect vehicle capacity.
- HGS combines crossover-based diversification with neighborhood-based improvement in a population-based memetic search.
- Each iteration selects two parents, recombines them, improves the offspring through local search, and inserts the result into the appropriate population until termination.Termination typically uses a limit on consecutive iterations without improvement or a time limit.
- Recombination: Ordered crossover inherits a fragment from one parent and completes the permutation using the other, after which Split optimally reinserts route delimiters.Capacity constraints are therefore disregarded during crossover and handled by Split afterward.
- Neighborhood Search: HGS-CVRP excludes the original pattern-improvement phase and adds SWAP* to route improvement alongside Swap, Relocate, 2-Opt, and 2-Opt*.
- Population management: The algorithm maintains separate feasible and infeasible subpopulations, removes clones or low-fitness solutions, and adapts penalties toward a target feasible-solution ratio.Subpopulations are maintained between µ and µ+λ solutions, with survivor selection triggered at the maximum size.
3 The SWAP* Neighborhood
SWAP* exchanges customers between routes while allowing reinsertion at arbitrary positions, expanding beyond classical in-place Swap moves. The paper develops a theorem-based, filtered exploration that makes this larger neighborhood practical and demonstrates improvements on a CVRP instance.
- SWAP* exchanges two customers from different routes without insertion in place, allowing each customer to be inserted at any position in the other route.
- Theorem 1 reduces direct SWAP* evaluation from Θ(n^3) by limiting candidate insertion positions.
- A best SWAP* move places each exchanged customer either in the other customer’s original position or among that route’s three best pre-removal insertion positions.
- Algorithm 2 preprocesses the three best insertion positions for each customer, identifies the best move for each route pair, and applies the best move per route pair.
- Restricting evaluation to route pairs with intersecting depot-centered polar sectors reduces SWAP* effort to a level comparable to standard neighborhoods, using location information or alternative route-relatedness measures.
- On instance X-n101-k25, SWAP* improves a solution that is locally optimal under standard CVRP neighborhoods, reduces route intersections without capacity violations, and enables a subsequent Relocate improvement.
4 Open-Source Implementation
The open-source HGS-CVRP implementation organizes the algorithm into specialized classes and uses data structures designed for efficient solution manipulation and local search. Its parameters largely retain prior calibration, with nElite reduced to 4.
- The implementation is open source and organized into six main classes covering individuals, populations, genetics, splitting, local search, and supporting routines.
- Individual stores complete solutions with trip delimiters and giant tours, while Split recalculates delimiters after crossover.
- LocalSearch uses indexed arrays with O(1) access and predecessor-successor pointers to support preprocessing, move evaluation, and solution modification.
- Timestamped move records identify whether routes changed since evaluation, avoiding reinitialization when a route is modified.
- The implementation includes dedicated routines for polar-sector calculations and exposes algorithm parameters through Params, Commandline, and main.
- The parameters retain the original values calibrated by Vidal et al. (2012), except that nElite is lowered to 4.
5 Experimental Analyses
The experiments compare HGS-CVRP with the original HGS and other CVRP algorithms under controlled computational conditions. HGS-CVRP achieves strong final solution quality and convergence, while SWAP* contributes measurable improvements with bounded computational effort.
- Final solution quality: HGS-CVRP obtains an average gap of 0.11% at run completion and significantly higher solution quality than the other compared approaches.The comparison evaluates average solution values and percentage gaps from the best known solutions.
- Final solution quality: SWAP* roughly halves the remaining gap relative to HGS-2012, while HGS-CVRP finds 44 best-known solutions compared with 34 for HGS-2012.HGS-CVRP averages a 0.02% gap on the first 50 small and medium instances, which are solved to optimality or near-optimality.
- Convergence: HGS-CVRP outperforms HGS-2012 and the other algorithms throughout the search, and SWAP* positively affects performance even at early stages.SISR converges toward high-quality solutions only later, whereas HGS-CVRP leads from 1% to 100% of the time horizon.
- SWAP* analysis: SWAP* consumes no more than 32% of computational time and produces approximately 15% of solution improvements, including improvements at later local-search stages.Its effectiveness is attributed to move filtering and exploration strategies that limit the complexity of this larger neighborhood.
- SWAP* analysis: SWAP* is especially effective on shorter routes, where improving moves can correspond to pairs of individually improving but capacity-infeasible Relocate moves.The neighborhood finds a larger share of improvements with smaller proportional computational effort when routes contain fewer customers.
6 Conclusions
The paper releases a concise, state-of-the-art HGS-CVRP code base and introduces Swap*, while emphasizing efficient neighborhood search and methodological simplicity. Experiments support its solution quality and convergence speed, but the authors deliberately leave some possible enhancements unexplored.
- Contributions: The paper fulfills two goals: releasing a simple, state-of-the-art CVRP code base and introducing the Swap* neighborhood with efficient exploration strategies.The strategies permit search times similar to smaller neighborhoods such as Swap, Relocate, and 2-Opt*.
- Contributions: Swap* contributes substantially to search performance, particularly late in local search when improving moves become harder to find.The authors connect this contribution to the later stages of local searches.
- Implications: The authors recommend broader research on neighborhood-exploration complexity and argue that recent CVRP heuristic improvements mainly reflect more efficient, focused local searches.They distinguish these developments from new metaheuristic concepts.
- Implications: Systematic testing during HGS specialization retained only essential components, reinforcing simplification as part of experimental design and scientific reasoning.The authors present simplification as a way to understand each component's role.
- Limitations: The authors acknowledge that HGS-CVRP could improve through set partitioning, decomposition, or ruin-and-recreate mutation, but deferred these additions to preserve simplicity and interpretability.They frame heuristic design around identifying concepts that are both simple and effective and understanding each component.