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: dict[Activity, list[Activity]], perturbation_manager: PerturbationManager | None = None)[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: dict[Activity, list[Activity]]¶: Mapping from each client or pickup activity to the activities in its granular neighbourhood.
perturbation_manager: PerturbationManager | None = None¶: Perturbation manager that handles perturbation during each invocation. Uses a default perturbation manager if not provided.

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.
`unary_operators`	Returns the unary operators in use.

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: UnaryOperator | BinaryOperator)[source]¶

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

Parameters:

op: UnaryOperator | BinaryOperator¶: The operator to add to this local search object.

property neighbours : dict[Activity, list[Activity]]¶: Returns the granular neighbourhood currently used by the local search.

property unary_operators : list[UnaryOperator]¶: Returns the unary operators in use.

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 and shipments.

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(data: ProblemData, 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 and shipments.

Parameters:

data: ProblemData¶: Problem data instance.
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, num_neighbours: int = 50, symmetric_proximity: bool = True)¶

Configuration for calculating a granular neighbourhood.

Parameters:

weight_wait_time: float = 0.2¶: 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.
num_neighbours: int = 50¶: Number of activities in each granular neighbourhood. This parameter determines the size of the overall neighbourhood.
symmetric_proximity: bool = True¶: Whether to calculate a symmetric proximity matrix. This ensures edge \((i, j)\) is given the same weight as \((j, i)\).

Raises:

ValueError – When num_neighbours is not strictly positive.

Attributes

num_neighbours
symmetric_proximity
weight_wait_time

compute_neighbours(data: ProblemData, params: NeighbourhoodParams = NeighbourhoodParams()) → dict[Activity, list[Activity]][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 mapping from activities to neighbouring activities for each client and pickup activity.

Return type:

dict

Operators¶

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

from pyvrp.search import OPERATORS

class BinaryOperator¶

class UnaryOperator¶

class Relocate1(data: ProblemData)¶: The \(N\)-relocate operator evaluates relocating \(N\) consecutive nodes from \(U\)’s route, starting with \(U\), to after \(V\).

class Relocate2(data: ProblemData)¶: The \(N\)-relocate operator evaluates relocating \(N\) consecutive nodes from \(U\)’s route, starting with \(U\), to after \(V\).

class Relocate3(data: ProblemData)¶: The \(N\)-relocate operator evaluates relocating \(N\) consecutive nodes from \(U\)’s route, starting with \(U\), to after \(V\).

class Swap11(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class Swap21(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class Swap31(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class Swap22(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class Swap32(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class Swap33(data: ProblemData)¶: The \((N, M)\)-swap operator evaluates swapping \(N\) consecutive nodes from \(U\)’s route (starting with \(U\)) with \(M\) consecutive nodes from \(V\)’s route (starting with \(V\)).

class RelocateAlternative(data: ProblemData)¶: Evaluates replacing mutually exclusive group member \(U\) with another member of the same group and relocating the replacement after \(V\). Group members are evaluated in order until an improving move is found.

class RelocatePickup(data: ProblemData)¶: Evaluate relocating the pickup node \(U\) to the best position in its current route.

class RelocateDelivery(data: ProblemData)¶: Evaluates relocating the delivery node of the shipment represented by pickup node \(U\) to the first improving position in its current trip.

class RelocateShipment(data: ProblemData)¶: Evaluates relocating the shipment \(U\) after \(V\) in different routes. \(U\) is relocated directly after \(V\), and \(U\)’s delivery is inserted in the first improving place after \(U\).

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 RemoveAdjacentDepot(data: ProblemData)¶: Evaluates removing an adjacent reload depot of a node \(U\).

class RemoveOptionalClient(data: ProblemData)¶: Evaluates removing an optional client node \(U\).

class InsertOptionalClient(data: ProblemData)¶: Evaluates inserting an optional client node \(U\) after \(V\).

class ReplaceGroup(data: ProblemData)¶: Evaluates replacing the current mutually exclusive group member \(V\) with \(U\).

class ReplaceOptionalClient(data: ProblemData)¶: Evaluates replacing an optional client node \(V\) with \(U\).

class InsertOptionalShipment(data: ProblemData)¶: Evaluates inserting the optional shipment \(U\) after \(V\). The node \(U\) is placed directly after \(V\), the other node of the shipment pair is inserted in the first improving location of \(V\)’s route.

class RemoveOptionalShipment(data: ProblemData)¶: Evaluates removing the optional shipment \(U\).

class ReplaceOptionalShipment(data: ProblemData)¶: Evaluates replacing the optional shipment \(V\) with \(U\).

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.