PyVRP: a high-performance VRP solver package

1. Introduction

• PyVRP implements hybrid genetic search for VRPs in Python, with performance-critical algorithm parts in C++ and other components customizable in Python.The package presents the HGS implementation as one example of a larger family of VRP algorithms that can use its building blocks.Source: §1 · pp. 1–2
• Users can solve VRP instances or customize HGS components, while advanced users can build and install PyVRP from source to support additional variants.The paper names population management, crossover strategies, granular neighbourhoods, and local-search operator selection as customizable aspects.Source: §1 · p. 2
• The MIT-licensed package aims to provide an easy-to-use, extensible solver with state-of-the-art results, serving practitioners and researchers seeking a starting point or strong baseline.The library is accompanied by unit tests, online documentation, and examples.Source: §1 · p. 2
• Earlier versions ranked first in the DIMACS VRPTW challenge and static EURO meets NeurIPS 2022 competition; the redesigned PyVRP still yields excellent performance on public benchmarks.The package was simplified and redesigned after the challenge-winning versions.Source: §1 · p. 3

2. Problem description

• PyVRP supports CVRP and VRPTW and minimizes distance rather than the number of vehicles; fleet minimization can be built on top by repeatedly removing vehicles until feasibility fails.The solver is designed to handle instances with up to several thousand customers.Source: §2 · p. 3

2.1. CVRP

• In CVRP, a fixed fleet serves every customer from a common depot and returns there, minimizing distance while keeping each vehicle’s total demand within capacity.Customers have nonnegative demands, and distances between locations are denoted d_ij.Source: §2.1 · p. 4

2.2. VRPTW

• VRPTW adds service times and customer time windows to CVRP: service may start no earlier than the earliest arrival time and vehicles cannot arrive after the latest time.Vehicles may wait when they arrive early; travel durations can differ from distances, as in practical settings.Source: §2.2 · p. 4

2.3. Conventions

• PyVRP uses integer distances and durations by default, with helpers to scale and round or truncate benchmark data; double precision is available but slower in initial experiments.The conventions support different benchmark rounding rules, including one-decimal precision used in the DIMACS VRPTW challenge.Source: §2.3 · p. 4

PyVRP

• PyVRP’s goal is an easy-to-use, open-source state-of-the-art solver; the authors distinguish it by a combination of scope, performance, flexibility, and ease of use.The paper presents PyVRP as a useful addition to the related-project landscape.Source: §3 · pp. 4, 6

HGS-CVRP

• HGS-CVRP (Vidal 2022) is a state-of-the-art C++ solver specialised for CVRP; its Python interface PyHygese requires a compiler toolchain and C++ source edits for customisation beyond parameters.Source: §3 · p. 5

LKH-3

• LKH-3 (Helsgaun 2017) supports many VRP variants by transforming them into symmetric TSPs, but customisation requires C-source edits and its license is academic and non-commercial.The paper also notes uncertainty about whether community contributions are welcomed.Source: §3 · p. 5

VROOM

• VROOM (Coupey et al. 2023) is an open-source solver aimed at good solutions to real-life VRPs and integrates with open-source routing software.Source: §3 · p. 5

OR-Tools

• OR-Tools (Perron and Furnon 2022) is a documented, multi-language optimisation toolkit using constraint programming for many routing problems, but its performance is described as far from state of the art.Source: §3 · p. 5

VRPSolver

• VRPSolver (Pessoa et al. 2020) is an exact state-of-the-art solver that can prove optimality on modest instances, but does not scale beyond a few hundred customers.Its most powerful components are limited to academic use by its license.Source: §3 · p. 5

“A VRP Solver”

• “A VRP Solver” (Builuk 2023) supports many variants and has a user manual, but its functional-endpoint documentation and benchmark performance are unclear.Source: §3 · p. 6

4. Technical implementation

• PyVRP implements a variant of HGS comprising a genetic algorithm, a population, and a local-search improvement method.The paper directs readers to its documentation for a fuller overview of classes, functions, and helper methods.Source: §4 · p. 6

4.1. Overview of HGS

• HGS combines genetic search with local search, maintaining feasible and infeasible solutions and improving offspring before survivor selection balances population quality and diversity.Time-window and capacity violations are penalised as soft constraints; penalty weights are adjusted to target a percentage of feasible local-search outcomes.Source: §4.1 · p. 6

4.2. Genetic algorithm

• The Python genetic algorithm selects two parents, crosses them to create offspring, applies local search, and adds the improved solution to the population.A feasible offspring that beats the current best becomes the new best; the returned result includes that solution and runtime statistics.Source: §4.2 · p. 7

4.3. Local search

• Profiling suggests local search accounts for 80–90% of runtime in PyVRP, motivating its C++ implementation; it applies moves yielding direct objective improvement immediately and repeats until none remain.Source: §4.3 · p. 7

4.3.1. Node operators

• Node operators evaluate customer-pair moves in a default granular neighbourhood of size k, reducing neighbourhood size from O(n^2) to O(kn).Users can customise or replace the neighbourhood; operators include (N,M)-exchange and 2-OPT.Source: §4.3 · p. 7, §4.3.1 · p. 8

4.3.2. Route operators

• Route operators consider moves between route pairs; RELOCATE* finds the best (1,0)-exchange, while SWAP* allows swapped customers to be inserted at different locations.The implementation adds time-window support, caching, and early stopping for known-bad moves.Source: §4.3.2 · pp. 8–9

4.4. Population management

• Population management uses feasible and infeasible sub-populations, with biased fitness balancing objective quality and diversity; users may supply their own diversity measure.The default diversity measure is a directed variant of broken pairs distance.Source: §4.4 · p. 9

5. The PyVRP package

• Automated workflows build the package for Linux, Windows, and Mac OS, enabling installation from the Python package index without compiling C++ extensions.The repository includes source code, tests, documentation, and examples.Source: §5 · p. 9

5.1. Package structure

• The package separates modeling, genetic-algorithm, crossover, diversity, search, stopping, and plotting tools into accessible Python namespaces.It also includes a reader for benchmark instances in various formats.Source: §5.1 · pp. 9–10

5.2. Example use

• Users can define a CVRP through the Model interface, solve it, and inspect or plot the returned solution and run statistics.A second example assembles local search, population, crossover, and stopping components to solve a VRPTW instance, allowing users to inspect and customize the HGS implementation.Source: §5.2 · p. 11

5.3. Extending PyVRP

• Extending PyVRP may require data-structure changes for hard constraints, cost-evaluation changes for soft constraints, and updated move-cost deltas.New data attributes may need to enter the instance and solution representations; caching cost-delta evaluations can help maintain efficiency, especially for time-related costs.Source: §5.3 · p. 13

6. Experiments

• The experiments compare against best known solutions and literature results, adjusting time limits for CPU differences using PassMark scores.CVRP instances were run with ten seeds and average total distance reported; VRPTW results also average ten seeds, with two-hour limits for 1000-customer instances.Source: §6 · p. 13, §6.1 · p. 13, §6.2 · pp. 14–15

6.1. CVRP

• On solved instances, PyVRP’s CVRP mean gap was 0.22% and gap of the mean 0.27%, versus HGS-2012’s 0.21% and 0.28% and HGS-CVRP’s 0.11% and 0.16%, respectively.Source: §6.1 · p. 14

6.2. VRPTW

• 0.40% mean gap and 0.46% gap of the mean: PyVRP’s VRPTW results are slightly higher than HGS-DIMACS’s 0.32% and 0.37%.Table 2 summarizes results on 1000-customer Homberger and Gehring instances.Source: §6.2 · p. 15, Table 2 · p. 15
• During extended runs on the complete Homberger and Gehring instances, PyVRP managed to improve 27 of the 300 best known solutions.The authors state that PyVRP’s simplified implementation would have placed second in the DIMACS VRPTW competition.Source: §6.2 · p. 15

7. Conclusion

• PyVRP is an open-source Python package for solving VRPTW, and numerical experiments show excellent performance on that variant.Its implementation can be extended with new solution techniques and VRP variants.Source: §7 · p. 15
• The authors hope PyVRP helps researchers and practitioners build on the state of the art in VRP solving.Source: §7 · p. 15

Appendix A: Parameter settings

• The experiments’ parameter settings are listed in Table 3.Source: Appendix A · p. 16

• The complete CVRP benchmark results are presented in Table 4.Source: Appendix B · p. 16

• Table 5 presents the complete VRPTW benchmark results for 1000-customer Homberger and Gehring instances.Source: Appendix C · p. 16, Table 5 · p. 21
• Table 5 continues in the appendix with further results for the same 1000-customer Homberger and Gehring instances.Source: Table 5 · p. 22