Search

The pyvrp.search module contains classes and methods responsible for improving a newly created offspring solution. This happens just after pyvrp.crossover is performed by the GeneticAlgorithm.

class LocalSearch(data: ProblemData, rng: XorShift128, 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

`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.
`run`(solution, cost_evaluator, should_intensify)	This method uses the `search()` and `intensify()` methods to iteratively 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.

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_degrees: int = 0) → Solution

This method uses the intensifying route operators on this local search object to improve the given solution. To limit the computation demands of intensification, the overlap_tolerance_degrees 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_degrees: 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 from the depot are evaluted. 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.

Raises:

RuntimeError: When this method is called before registering route operators. Operators can be registered using add_route_operator().

run(solution: Solution, cost_evaluator: CostEvaluator, should_intensify: bool) → Solution

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

Parameters:

solution: The solution to improve through local search.
cost_evaluator: Cost evaluator to use.
should_intensify: Whether to apply intensify(). Intensification can provide much better solutions, but is computationally demanding. By default intensification is applied.

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.

Raises:

RuntimeError: When this method is called before registering node operators. Operators can be registered using add_node_operator().

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.

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. As a convenience, the pyvrp.search module makes all these operators available as NODE_OPERATORS:

from pyvrp.search import NODE_OPERATORS

class Exchange10(data: pyvrp._pyvrp.ProblemData)

class Exchange20(data: pyvrp._pyvrp.ProblemData)

class Exchange30(data: pyvrp._pyvrp.ProblemData)

class Exchange11(data: pyvrp._pyvrp.ProblemData)

class Exchange21(data: pyvrp._pyvrp.ProblemData)

class Exchange31(data: pyvrp._pyvrp.ProblemData)

class Exchange22(data: pyvrp._pyvrp.ProblemData)

class Exchange32(data: pyvrp._pyvrp.ProblemData)

class Exchange33(data: pyvrp._pyvrp.ProblemData)

class MoveTwoClientsReversed(data: pyvrp._pyvrp.ProblemData)

class TwoOpt(data: pyvrp._pyvrp.ProblemData)

Route operators

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

from pyvrp.search import ROUTE_OPERATORS

class RelocateStar(data: pyvrp._pyvrp.ProblemData)

class SwapStar(data: pyvrp._pyvrp.ProblemData)