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:
 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 userprovided 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()
andintensify()
methods to iteratively improve the given solution.Adds a node operator to this local search object.
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.
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.
 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()
andintensify()
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:

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

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:
 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:
 nb_granular¶
Number of other clients that are in each client’s granular neighbourhood. This parameter determines the size of the overall neighbourhood.
 Type:
 symmetric_proximity¶
Whether to calculate a symmetric proximity matrix. This ensures edge \((i, j)\) is given the same weight as \((j, i)\).
 Type:
 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:
 Raises:
ValueError – When
nb_granular
is nonpositive.

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:
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 2OPT* 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 reinsertions 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: Opensource implementation and SWAP* neighborhood. Comput. Oper. Res. 140. https://doi.org/10.1016/j.cor.2021.105643