Search methods¶

The pyvrp.search module contains classes and search methods responsible for modifying or improving solutions. PyVRP currently provides a LocalSearch method.

All search methods implement the SearchMethod protocol.

class SearchMethod(*args, **kwargs)[source]¶

Protocol that search methods must implement.

Methods

__call__(solution, cost_evaluator[, exhaustive])

Search around the given solution, and returns a new solution that is hopefully better.

__call__(solution: Solution, cost_evaluator: CostEvaluator, exhaustive: bool = False) → Solution[source]¶

Search around the given solution, and returns a new solution that is hopefully better.

Parameters:

solution: Solution¶

The solution to improve.

cost_evaluator: CostEvaluator¶

Cost evaluator to use when evaluating improvements.

exhaustive: bool = False¶

Whether to explicitly require a complete search, rather than allow the search method to perform a limited search. Default False, that is, the search method gets to decide for itself what to do.

Returns:

The improved solution.

Return type:

Solution

class LocalSearch(data: ProblemData, rng: RandomNumberGenerator, neighbours: list[list[int]], perturbation_manager: PerturbationManager = PerturbationManager())[source]¶

Local search method. This search method explores a granular neighbourhood in a very efficient manner using user-provided operators. This quickly results in much improved solutions.

Parameters:

data: ProblemData¶

Data object describing the problem to be solved.

rng: RandomNumberGenerator¶

Random number generator.

neighbours: list[list[int]]¶

List of lists that defines the local search neighbourhood.

perturbation_manager: PerturbationManager = PerturbationManager()¶

Perturbation manager that handles perturbation during each invocation.

Attributes

binary_operators	Returns the binary operators in use.
neighbours	Returns the granular neighbourhood currently used by the local search.
statistics	Returns search statistics about the most recently improved solution.

Methods

__call__(solution, cost_evaluator[, exhaustive])	This method improves the given solution through a (default non-exhaustive) local search.
add_operator(op)	Adds an operator to this local search object.

add_operator(op: BinaryOperator)[source]¶

Adds an operator to this local search object. The operator will be used to improve a solution.

Parameters:

op: BinaryOperator¶

The operator to add to this local search object.

property neighbours : list[list[int]]¶

Returns the granular neighbourhood currently used by the local search.

property binary_operators : list[BinaryOperator]¶

Returns the binary operators in use.

property statistics : LocalSearchStatistics¶

Returns search statistics about the most recently improved solution.

__call__(solution: Solution, cost_evaluator: CostEvaluator, exhaustive: bool = False) → Solution[source]¶

This method improves the given solution through a (default non-exhaustive) local search.

Parameters:

solution: Solution¶

The solution to improve through local search.

cost_evaluator: CostEvaluator¶

Cost evaluator to use.

exhaustive: bool = False¶

Performs an exhaustive, complete search if set. Otherwise does only a limited search over perturbed clients (default).

Returns:

The improved solution. This is not the same object as the solution that was passed in.

Return type:

Solution

class LocalSearchStatistics¶

Simple data structure that tracks statistics about the number of local search moves applied to the most recently improved solution.

num_moves¶

Number of evaluated operator moves.

num_improving¶

Number of evaluated moves that led to an objective improvement.

num_updates¶

Total number of changes to the solution. This always includes the number of evaluated improving moves, but also e.g. insertion of required but missing clients.

Attributes

num_improving
num_moves
num_updates

class PerturbationParams(min_perturbations: int = 1, max_perturbations: int = 25)¶

Perturbation parameters.

Parameters:

min_perturbations: int = 1¶

Minimum number of perturbations to apply. Must not be negative.

max_perturbations: int = 25¶

Maximum number of perturbations to apply.

Attributes

max_perturbations
min_perturbations

class PerturbationManager(params: PerturbationParams)¶

Handles perturbation during the search. In each iteration, it applies num_perturbations() perturbations that strengthen (resp., weaken) randomly selected neighbourhoods by inserting (removing) clients.

Parameters:

params: PerturbationParams¶

Perturbation parameters for this manager.

Methods

num_perturbations(self)	Number of perturbations to apply.
shuffle(self, rng)	Draws and sets a new random number of perturbations to apply.

num_perturbations(self) → int¶

Number of perturbations to apply.

shuffle(self, rng: RandomNumberGenerator) → None¶

Draws and sets a new random number of perturbations to apply.

class NeighbourhoodParams(weight_wait_time: float = 0.2, weight_time_warp: float = 1.0, num_neighbours: int = 50, symmetric_proximity: bool = True, symmetric_neighbours: bool = False)[source]¶

Configuration for calculating a granular neighbourhood.

weight_wait_time¶

Penalty weight given to the minimum wait time aspect of the proximity calculation. A large wait time indicates the clients are far apart in duration/time.

Type:

float

weight_time_warp¶

Penalty weight given to the minimum time warp aspect of the proximity calculation. A large time warp indicates the clients are far apart in duration/time.

Type:

float

num_neighbours¶

Number of other clients that are in each client’s granular neighbourhood. This parameter determines the size of the overall neighbourhood.

Type:

int

symmetric_proximity¶

Whether to calculate a symmetric proximity matrix. This ensures edge \((i, j)\) is given the same weight as \((j, i)\).

Type:

bool

symmetric_neighbours¶

Whether to symmetrise the neighbourhood structure. This ensures that when edge \((i, j)\) is in, then so is \((j, i)\). Note that this is not the same as symmetric_proximity.

Type:

bool

Raises:

ValueError – When num_neighbours is non-positive.

compute_neighbours(data: ProblemData, params: NeighbourhoodParams = NeighbourhoodParams()) → list[list[int]][source]¶

Computes neighbours defining the neighbourhood for a problem instance.

Parameters:

data: ProblemData¶

ProblemData for which to compute the neighbourhood.

params: NeighbourhoodParams = NeighbourhoodParams()¶

NeighbourhoodParams that define how the neighbourhood is computed.

Returns:

A list of list of integers representing the neighbours for each client. The first lists in the lower indices are associated with the depots and are all empty.

Return type:

list

Operators¶

Instances of these operators can be added to the LocalSearch object via the add_operator() method. Each operator inherits from BinaryOperator. As a convenience, the pyvrp.search module makes most relevant operators available as OPERATORS:

from pyvrp.search import OPERATORS

class BinaryOperator¶

class Exchange10(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange20(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange30(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange11(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange21(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange31(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange22(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange32(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class Exchange33(data: ProblemData)¶

The \((N, M)\)-exchange operators exchange \(N\) consecutive clients from \(U\)’s route (starting at \(U\)) with \(M\) consecutive clients from \(V\)’s route (starting at \(V\)). This includes the RELOCATE and SWAP operators as special cases.

The \((N, M)\)-exchange class uses C++ templates for different \(N\) and \(M\) to efficiently evaluate these moves.

class RelocateWithDepot(data: ProblemData)¶

Tests if inserting a reload depot while relocating \(U\) after \(V\) results in an improving move. Concretely, this operator implements the second and third insertion scheme of Francois et al. [1].

References

[1]

Francois, V., Y. Arda, and Y. Crama (2019). Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows. Transportation Science, 53(6): 1706 - 1730. https://doi.org/10.1287/trsc.2019.0909.

class SwapTails(data: ProblemData)¶

Given two nodes \(U\) and \(V\), tests whether replacing the arc of \(U\) to its successor \(n(U)\) and \(V\) to \(n(V)\) by \(U \rightarrow n(V)\) and \(V \rightarrow n(U)\) is an improving move.

Note

This operator is also known as 2-OPT* in the VRP literature.