Search¶

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)¶

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.

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

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

Data object describing the problem to be solved.

rng

Random number generator.

neighbours

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.
get_neighbours()	Returns the granular neighbourhood currently used by the local search.
intensify(solution, cost_evaluator[, ...])	This method uses the intensifying route operators on this local search object to improve the given solution.
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)¶

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

Parameters:¶

op

The node operator to add to this local search object.

add_route_operator(op: RouteOperator)¶

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

The route operator to add to this local search object.

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

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

Parameters:¶

neighbours

A new granular neighbourhood.

get_neighbours() → list[list[int]]¶

Returns the granular neighbourhood currently used by the local search.

Returns:¶

list

The current granular neighbourhood.

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

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

The solution to improve.

cost_evaluator

Cost evaluator to use.

overlap_tolerance

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

Solution

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

search(solution: Solution, cost_evaluator: CostEvaluator) → Solution¶

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

Parameters:¶

solution

The solution to improve.

cost_evaluator

Cost evaluator to use.

Returns:¶

Solution

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

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)¶

Configuration for calculating a granular neighbourhood.

Raises:¶

ValueError

When nb_granular is non-positive.

Attributes:¶

weight_wait_time

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.

weight_time_warp

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.

nb_granular

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

symmetric_proximity

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

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.

compute_neighbours(data: ProblemData, params: NeighbourhoodParams = NeighbourhoodParams(weight_wait_time=0.2, weight_time_warp=1.0, nb_granular=40, symmetric_proximity=True, symmetric_neighbours=False)) → list[list[int]]¶

Computes neighbours defining the neighbourhood for a problem instance.

Parameters:¶

data

ProblemData for which to compute the neighbourhood.

params

NeighbourhoodParams that define how the neighbourhood is computed.

Returns:¶

list

A list of list of integers representing the neighbours for each client. The first element represents the depot and is an empty 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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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¶

The \((N, M)\)-exchange operators exhange \(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 MoveTwoClientsReversed¶

class TwoOpt¶

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 RelocateStar¶

class SwapStar¶

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). Our implementation of the SWAP* neighbourhood follows Algorithm 2 of [1] fairly closely.

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