A brief introduction to ILS¶

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.

The ILS algorithm works as follows.

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:

PyVRP provides well-tested and high-quality implementations of the ILS algorithm, stopping criteria, acceptance criteria and various perturbation and local search procedures.