PyVRP’s algorithm

PyVRP provides a high-performance implementation of the iterated local search (ILS) algorithm for vehicle routing problems (VRPs). ILS is a single-trajectory algorithm that improves a solution by repeated applications of small perturbations and local improvement procedures. This approach effectively balances between exploration and exploitation of the search space.

Note

For a more thorough introduction to ILS for VRPs, we refer to the works of Lourenço et al. (2019) and Accorsi and Vigo (2021).

The algorithm begins with an initial solution which becomes the current and best solution. In each iteration, the algorithm perturbs the current solution just enough to escape from a local optimum, while preserving much of the solution’s structure. After perturbation, a local search procedure improves the solution to a new local optimum. An acceptance criterion then determines whether to adopt the new candidate solution as the current solution for the next iteration. This criterion typically accepts improvements, but occasionally also accepts worse solutions to escape local optima. If the candidate solution improves over the best solution found so far, it is also registered as the new best solution. The algorithm continues until a provided stopping criterion is met, at which point it returns the best solution found.

In pseudocode, ILS works as follows:

Input: an initial solution \(s_0\)
Output: the best-found solution \(s^\text{best}\)
Initialise \(s^\text{curr} \leftarrow s_0\) and \(s^\text{best} \leftarrow s_0\)
repeat until stopping criterion is met:
Perturb the current solution to generate \(s^\text{pert} = \text{Perturbation}(s^\text{curr})\)
Apply local search to obtain \(s^\text{cand} = \text{LocalSearch}(s^\text{pert})\)
if \(\text{AcceptanceCriterion}(s^\text{curr}, s^\text{cand})\):
\(s^\text{curr} \leftarrow s^\text{cand}\)
if \(s^\text{cand}\) has a better objective value than \(s^\text{best}\):
\(s^\text{best} \leftarrow s^\text{cand}\)
return \(s^\text{best}\)

Implementation

PyVRP provides a well-tested and high-quality implementation of ILS through the IteratedLocalSearch class, various stopping criteria in pyvrp.stop, and perturbation and local search procedures in pyvrp.search. All are implemented in Python, except for the perturbation and local search procedures, which are implemented in C++.