Search methods¶

The pyvrp.search module contains classes and search methods responsible for improving a newly created offspring solution. This happens just after pyvrp.crossover is performed by the GeneticAlgorithm. 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)

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

__call__(solution: Solution, cost_evaluator: CostEvaluator) → 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.

Returns:

The improved solution.

Return type:

Solution

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

Local search method. This search method explores a granular neighbourhood in a very efficient manner using user-provided node and route 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.

Methods

__call__(solution, cost_evaluator)	This method uses the search() and intensify() methods to iteratively improve the given solution.
add_node_operator(op)	Adds a node operator to this local search object.
add_route_operator(op)	Adds a route operator to this local search object.
intensify(solution, cost_evaluator[, ...])	This method uses the intensifying route operators on this local search object to improve the given solution.
neighbours()	Returns the granular neighbourhood currently used by the local search.
search(solution, cost_evaluator)	This method uses the node operators on this local search object to improve the given solution.
set_neighbours(neighbours)	Convenience method to replace the current granular neighbourhood used by the local search object.

add_node_operator(op: NodeOperator)[source]¶

Adds a node operator to this local search object. The node operator will be used by search() to improve a solution.

Parameters:

op: NodeOperator¶

The node operator to add to this local search object.

add_route_operator(op: RouteOperator)[source]¶

Adds a route operator to this local search object. The route operator will be used by intensify() to improve a solution using more expensive route operators.

Parameters:

op: RouteOperator¶

The route operator to add to this local search object.

set_neighbours(neighbours: list[list[int]])[source]¶

Convenience method to replace the current granular neighbourhood used by the local search object.

Parameters:

neighbours: list[list[int]]¶

A new granular neighbourhood.

neighbours() → list[list[int]][source]¶

Returns the granular neighbourhood currently used by the local search.

__call__(solution: Solution, cost_evaluator: CostEvaluator) → Solution[source]¶

This method uses the search() and intensify() methods to iteratively improve the given solution. First, search() is applied. Thereafter, intensify() is applied. This repeats until no further improvements are found. Finally, the improved solution is returned.

Parameters:

solution: Solution¶

The solution to improve through local search.

cost_evaluator: CostEvaluator¶

Cost evaluator to use.

Returns:

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

Return type:

Solution

intensify(solution: Solution, cost_evaluator: CostEvaluator, overlap_tolerance: float = 0.05) → Solution[source]¶

This method uses the intensifying route operators on this local search object to improve the given solution. To limit the computational demands of intensification, the overlap_tolerance argument can be used to limit the number of route pairs that are evaluated.

Parameters:

solution: Solution¶

The solution to improve.

cost_evaluator: CostEvaluator¶

Cost evaluator to use.

overlap_tolerance: float = 0.05¶

This method evaluates improving moves between route pairs. To limit computational efforts, by default not all route pairs are considered: only those route pairs that share some overlap when considering their center’s angle to the center of all clients. This parameter controls the amount of overlap needed before two routes are evaluated.

Returns:

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

Return type:

Solution

search(solution: Solution, cost_evaluator: CostEvaluator) → Solution[source]¶

This method uses the node operators on this local search object to improve the given solution.

Parameters:

solution: Solution¶

The solution to improve.

cost_evaluator: CostEvaluator¶

Cost evaluator to use.

Returns:

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

Return type:

Solution

class NeighbourhoodParams(weight_wait_time: float = 0.2, weight_time_warp: float = 1.0, nb_granular: int = 40, 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

nb_granular¶

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 nb_granular 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

Node operators¶

Instances of these operators can be added to the LocalSearch object via the add_node_operator() method. Each node operator inherits from NodeOperator. As a convenience, the pyvrp.search module makes all these operators available as NODE_OPERATORS:

from pyvrp.search import NODE_OPERATORS

class NodeOperator¶

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

Route operators¶

Instances of these operators can be added to the LocalSearch object via the add_route_operator() method. Each route operator inherits from RouteOperator. As a convenience, the pyvrp.search module makes all these operators available as ROUTE_OPERATORS:

from pyvrp.search import ROUTE_OPERATORS

class RouteOperator¶

class SwapRoutes(data: ProblemData)¶

This operator evaluates exchanging the visits of two routes \(U\) and \(V\).

class SwapStar(data: ProblemData)¶

Explores the SWAP* neighbourhood of [1]. The SWAP* neighbourhood explores free form re-insertions of clients \(U\) and \(V\) in the given routes (so the clients are exchanged between routes, but they are not necessarily inserted in the place of the other exchanged client).

References

[1]

Thibaut Vidal. 2022. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140. https://doi.org/10.1016/j.cor.2021.105643