Metaheuristic components

Operators

The routingblocks package provides a set of destroy and repair operators that remove and insert vertices into a solution, respectively.

Destroy operators

class routingblocks.operators.WorstRemovalOperator(instance: routingblocks.Instance, move_selector: routingblocks.operators.move_selectors.MoveSelector[routingblocks.RemovalMove])

Iteratively (one at a time) removes vertices according to the benefit yielded by removing them, i.e., the change in the solution’s cost with and without the vertex.

The operator uses a routingblocks.operators.MoveSelector[routingblocks.RemovalMove] to choose the next vertex to remove. This selector receives as argument a list of routingblocks.RemovalMove objects, each one representing a possible removal of a vertex from the solution, ordered by cost improvement.

This allows to customize the operator to different removal strategies, such as removing the vertex with the highest cost improvement, removing the vertex with the lowest cost improvement, or introducing randomness in the selection process.

Parameters:

instance (routingblocks.Instance) – The problem instance
move_selector (routingblocks.operators.MoveSelector[routingblocks.RemovalMove]) – The move selector used to choose the next vertex to remove

class routingblocks.operators.ClusterRemovalOperator(seed_selector: SeedSelector, cluster_member_selector: ClusterMemberSelector)

The ClusterRemovalOperator is a generic destroy operator that removes clusters of vertices from a solution. The operator first selects a seed vertex, and then selects a cluster of vertices around that seed. These two steps are repeated until the desired number of vertices has been selected or no seed vertices can be identified. The selected vertices are then removed from the solution. Note that seed vertices are not removed unless they are also selected by the cluster member selector.

The seed selection and cluster member selection are delegated to the routingblocks.operators.SeedSelector and routingblocks.operators.ClusterMemberSelector parameters, respectively. This allows to customize the operator for different use cases.

Parameters:

seed_selector (SeedSelector) – The seed selector
cluster_member_selector (ClusterMemberSelector) – The cluster member selector

class routingblocks.operators.StationVicinityRemovalOperator(instance: routingblocks.Instance, get_distance: Callable[[routingblocks.Vertex, routingblocks.Vertex], float], min_radius_factor: float, max_radius_factor: float, randgen: routingblocks.Randgen | None)

Station vicinity removal is a specialized cluster removal operator designed to reorder customer visits in the vicinity of replenishment stations. The operator defines the vicinity of a station by selecting a random radius based on a percentage of the maximum distance between vertices. It then randomly chooses a recharging station and removes the station along with vertices within the selected radius, repeating this process until the desired number of vertices are removed.

Parameters:

instance (routingblocks.Instance) – Instance the operator will be applied to
get_distance (Callable[[routingblocks.Vertex, routingblocks.Vertex], float]) – A function taking two vertices and returning the distance between them. The distance can be arbitrary, i.e., does not have to correspond to the evaluation function.
min_radius_factor (float) – Minimum of the interval the radius is picked from
max_radius_factor (float) – Maximum of the interval the radius is picked from
randgen (Optional[routingblocks.Randgen]) – Random number generator

class routingblocks.operators.RelatedRemovalOperator(relatedness_matrix: List[List[float]], move_selector: routingblocks.operators.move_selectors.MoveSelector[RelatedVertexRemovalMove], seed_selector: routingblocks.operators.move_selectors.MoveSelector[RelatedVertexRemovalMove], initial_seed_selector: routingblocks.operators.move_selectors.MoveSelector[routingblocks.Node], cluster_size: int = 1)

Removes related vertices from the solution. The operator first selects an initial seed vertex. Then, it selects the n most related vertices to the current seed vertex and adds them to the list of removed vertices. It then selects the next seed vertex from the list of removed vertices and repeats the process until the desired number of vertices has been selected. Finally, the operator removes the selected vertices from the solution.

The operator determines related vertices by using a relatedness matrix passed to the constructor. This matrix contains a number that measures the degree of the relatedness between each pair of vertices. The higher the number, the more related the vertices are.

(Initial) seed and related vertex selection is done using move selectors.

Parameters:

relatedness_matrix (List[List[float]]) – The relatedness matrix. See build_relatedness_matrix() for a way to build such a matrix.
move_selector (routingblocks.operators.move_selectors.MoveSelector[RelatedVertexRemovalMove]) – The move selector to use for selecting the vertex to remove. Receives a list of related vertices, ordered by the degree of relatedness in descending order.
seed_selector (routingblocks.operators.move_selectors.MoveSelector[RelatedVertexRemovalMove]) – The move selector to use for selecting the seed vertex.
initial_seed_selector (routingblocks.operators.move_selectors.MoveSelector[routingblocks.Node]) – The move selector to use for selecting the initial seed vertex.
cluster_size (int) – The number of related vertices to remove for each seed.

class routingblocks.operators.RelatedVertexRemovalMove

Variables:

vertex_id – The id of the corresponding vertex.
relatedness – The relatedness of the vertex to the seed vertex.
location – The location of the vertex in the solution.

vertex_id

relatedness

location

class routingblocks.operators.RouteRemovalOperator(rng: routingblocks.Random)

Removes random routes from the solution. May remove more than the requested number of vertices.

Parameters:: rng (routingblocks.Random) – The routingblocks.Random instance to use.

class routingblocks.operators.RandomRemovalOperator(random: Random)

Removes random vertices from the solution. Note that the same vertex may apppear several times, i.e., if two visits to the same vertex are removed.

Parameters:: random (Random) – The random number generator used.

Insertion operators

class routingblocks.operators.BestInsertionOperator(instance: routingblocks.Instance, move_selector: routingblocks.operators.move_selectors.MoveSelector[routingblocks.InsertionMove])

Iteratively (one at a time) inserts vertices according to the cost incurred from inserting them.

The operator uses a routingblocks.operators.MoveSelector[routingblocks.InsertionMove] to choose the next vertex to insert. This selector receives as argument a list of routingblocks.InsertionMove objects, each one representing a possible location at which the next vertex can be inserted, ordered by cost in descending order.

This allows to customize the operator to different insertion strategies, such as inserting the vertex at the location with the lowest cost, inserting the vertex at the location with the highest cost, or introducing randomness in the selection process.

Parameters:

instance (routingblocks.Instance) – The problem instance
move_selector (routingblocks.operators.move_selectors.MoveSelector[routingblocks.InsertionMove]) – The move selector used to choose the next insertion position

class routingblocks.operators.RandomInsertionOperator(random: Random)

Inserts vertices at random positions in the solution.

Parameters:: random (Random) – The routingblocks.Random instance to use.

Operator customization

Move Selectors

RoutingBlocks uses the concept of move selectors to customize destroy and repair operator behavior. These select a move from a sequence of possible moves. Their interface can often be implemented as a lambda function, but it is possible to implement stateful move selectors as well. The interface is as follows:

class routingblocks.operators.MoveSelector

A move selector selects a move from a sequence of moves.

__call__(moves: Iterable[T])

Selects a move from the sequence of moves.

Parameters:: moves (Iterable[T]) – The sequence of moves.
Returns:: The selected move.
Return type:: T

The following example illustrates two simple move selectors. The first one always selects the first move, the second one chooses a move at random:

# Selects the first move.
def my_first_move_selector(moves):
    return next(moves)

# Selects a move at random.
class my_random_move_selector:

    def __init__(self, random_generator):
        self.rng = random_generator

    def __call__(self, moves):
        return random.choice(list(moves))

RoutingBlocks provides a set of pre-defined move selectors:

routingblocks.operators.first_move_selector(moves: Iterable[T])

Selects the first move in the sequence.

Parameters:: moves (Iterable[T]) – The sequence of moves.
Returns:: The first move in the sequence.
Return type:: T

routingblocks.operators.last_move_selector(moves: Iterable[T])

Selects the last move in the sequence.

Parameters:: moves (Iterable[T]) – The sequence of moves.
Returns:: The last move in the sequence.
Return type:: T

routingblocks.operators.nth_move_selector_factory(n: int)

Creates a move selector which selects the nth move in the sequence.

Parameters:: n (int) – The index of the move to select.
Returns:: A move selector which selects the nth move in the sequence.
Return type:: MoveSelector[T]

routingblocks.operators.blink_selector_factory(blink_probability: float, randgen: routingblocks.Random)

Creates a move selector which selects the first move of the sequence with probability \((1-p)\), the second move with probability \((1-p)^2\), where \(p\) is the blink probability, and so on.

Parameters:

blink_probability (float) – The probability of blinking.
randgen (routingblocks.Random) – The random number generator.

Returns:

The configured move selector.

Return type:

MoveSelector[T]

routingblocks.operators.random_selector_factory(rangen: routingblocks.Random)

Creates a move selector which selects a random move from the sequence.

Parameters:: rangen (routingblocks.Random) – The random number generator.
Returns:: The configured move selector.

Other

class routingblocks.operators.SeedSelector

Selects a seed vertex from a solution.

__call__(evaluation: routingblocks.Evaluation, solution: routingblocks.Solution, already_selected_vertices: List[routingblocks.NodeLocation])

Parameters:

evaluation (routingblocks.Evaluation) – The evaluation to use
solution (routingblocks.Solution) – The solution to select from
already_selected_vertices (List[routingblocks.NodeLocation]) – A list of vertices that have already been selected, i.e., should not be included in the selection

Returns:

Return type:

routingblocks.NodeLocation

class routingblocks.operators.ClusterMemberSelector

Selects a cluster of vertices based on a seed vertex.

__call__(evaluation: routingblocks.Evaluation, solution: routingblocks.Solution, seed: routingblocks.NodeLocation)

Parameters:

evaluation (routingblocks.Evaluation) – The evaluation to use
solution (routingblocks.Solution) – The solution to select from
seed (routingblocks.NodeLocation) – The seed vertex

Returns:

Return type:

List[routingblocks.NodeLocation]

routingblocks.operators.build_relatedness_matrix(instance: routingblocks.Instance, relatedness_computer: Callable[[int, int], float])

Builds a relatedness matrix for the given instance and relatedness function.

Parameters:

instance (routingblocks.Instance) – The instance.
relatedness_computer (Callable[[int, int], float]) – A function that computes the relatedness between two vertices. Takes as input the ids of the two vertices and returns a number that measures the degree of relatedness.

Returns:

A matrix of relatedness values.

Return type:

List[List[float]]

Custom operators

Custom operators can be implemented by inheriting from the abstract base classes routingblocks.DestroyOperator and routingblocks.RepairOperator for destroy and repair operators, respectively. See here for an example. The interfaces are as follows:

class routingblocks.DestroyOperator

apply(evaluation: Evaluation, solution: Solution, number_of_vertices_to_remove: int)

Apply this operator to the given solution. The solution is modified in-place.

Parameters:

evaluation (Evaluation) – The evaluation function to use.
solution (Solution) – The solution to apply the operator to.
number_of_vertices_to_remove (int) – The number of vertices to remove from the solution.

Returns:

A list containing the IDs of the vertices that were removed from the solution.

Return type:

List[VertexID]

can_apply_to(solution: Solution)

Check if this operator can be applied to the given solution.

Parameters:: solution (Solution) – The solution to check.
Return type:: bool

name()

Get the name of this operator.

Return type:: str

class routingblocks.RepairOperator

apply(evaluation: Evaluation, solution: Solution, removed_vertex_ids: List[VertexID])

Apply this operator to the given solution. The solution is modified in-place.

Parameters:

evaluation (Evaluation) – The evaluation function to use.
solution (Solution) – The solution to apply the operator to.
removed_vertex_ids (List[VertexID]) – The IDs of the vertices that should be inserted into the solution.

Return type:

None

can_apply_to(solution: Solution)

Check if this operator can be applied to the given solution.

Parameters:: solution (Solution) – The solution to check.
Return type:: bool

name()

Get the name of this operator.

Return type:: str

Solvers

RoutingBlocks provides (A)LNS solvers that can be extended with arbitrary destroy and repair operators. The solvers manage operator selection, operator weights, and solution generation. We note that this solver can also be used to implement other perturbation-based algorithms. Their interfaces are as follows:

class routingblocks.LargeNeighborhood(randgen: routingblocks._routingblocks.Random)

LNS solver.

The solver uses a destroy and repair operator to iteratively generate new solutions. The destroy operator is used to remove a number of vertices from the solution, while the repair operator is used to re-insert the removed vertices into the solution.

Destroy and repair operators are selected uniformly from a pool of registered operators.

Parameters:: randgen (routingblocks._routingblocks.Random) – Random number generator.

add_destroy_operator(destroy_operator: routingblocks._routingblocks.DestroyOperator)

Register a new destroy operator. The weight of this operator is initialized to the average weight of all other destroy operators.

Parameters:: destroy_operator (routingblocks._routingblocks.DestroyOperator) – The operator to add.
Return type:: routingblocks._routingblocks.DestroyOperator

add_repair_operator(repair_operator: routingblocks._routingblocks.RepairOperator)

Register a new repair operator. The weight of this operator is initialized to the average weight of all other repair operators.

Parameters:: repair_operator (routingblocks._routingblocks.RepairOperator) – The operator to add.
Return type:: routingblocks._routingblocks.RepairOperator

generate(evaluation: routingblocks._routingblocks.Evaluation, solution: routingblocks._routingblocks.Solution, number_of_vertices_to_remove: int)

Generate a new solution by applying a destroy and repair operator selected randomly. Modifies the solution in-place.

Parameters:

evaluation (routingblocks._routingblocks.Evaluation) – The evaluation function to use.
solution (routingblocks._routingblocks.Solution) – The solution to generate a new solution from.
number_of_vertices_to_remove (int) – The number of vertices to remove from the solution.

Returns:

A tuple containing the destroy and repair operator used to generate the solution.

Return type:

Tuple[routingblocks._routingblocks.DestroyOperator, routingblocks._routingblocks.RepairOperator]

remove_destroy_operator(destroy_operator: routingblocks._routingblocks.DestroyOperator)

Remove a destroy operator.

Parameters:: destroy_operator (routingblocks._routingblocks.DestroyOperator) – The operator to remove.
Return type:: None

remove_repair_operator(repair_operator: routingblocks._routingblocks.RepairOperator)

Remove a repair operator.

Parameters:: repair_operator (routingblocks._routingblocks.RepairOperator) – The operator to remove.
Return type:: None

property destroy_operators

Get an iterator over all registered destroy operators.

Return type:: Iterator

property repair_operators

Get an iterator over all registered repair operators.

Return type:: Iterator

class routingblocks.AdaptiveLargeNeighborhood(randgen: Random, smoothing_factor: float)

ALNS solver. Initially, all operators are assigned equal weights of 1. The weights are then adapted based on the performance of the operators in the last period. Upon requesting an update, the weights are recalculated as follows:

\[w_{op, new} = \alpha \cdot \frac{s_{op}}{\max(1, n_{op})} + (1 - \alpha) \cdot w_{op, old}\]

Where

\(w_{op, new}\) is the updated weight of operator \(op\)
\(\alpha\) is the smoothing factor, which determines the importance of an operator’s historical performance
\(s_{op}\) is the sum of scores achieved by operator \(op\) in the last period
\(n_{op}\) is the total number of solutions generated using operator \(op\) in the last period
\(w_{op, old}\) is the old weight of operator \(op\)

Parameters:

randgen (Random) – Random number generator.
smoothing_factor (float) – Smoothing factor for the adaptive weights. Determines the importance of the historical

performance of the operators.

adapt_operator_weights()

Calculate the new weights for the operators based on their respective performance in the last period.

Return type:: None

add_destroy_operator(destroy_operator: DestroyOperator)

Register a new destroy operator. The weight of this operator is initialized to the average weight of all other destroy operators.

Parameters:: destroy_operator (DestroyOperator) – The operator to add.
Return type:: DestroyOperator

add_repair_operator(repair_operator: RepairOperator)

Register a new repair operator. The weight of this operator is initialized to the average weight of all other repair operators.

Parameters:: repair_operator (RepairOperator) – The operator to add.
Return type:: RepairOperator

collect_score(destroy_operator: DestroyOperator, repair_operator: RepairOperator, score: float)

Collect the score achieved by a solution generated by the given destroy and repair operators.

Parameters:

destroy_operator (DestroyOperator) – The destroy operator used to generate the solution.
repair_operator (RepairOperator) – The repair operator used to generate the solution.
score (float) – The score achieved by the solution.

Return type:

None

generate(evaluation: Evaluation, solution: Solution, number_of_vertices_to_remove: int)

Generate a new solution by applying a destroy and repair operator selected based the on the operator weights. Modifies the solution in-place.

Parameters:

evaluation (Evaluation) – The evaluation function to use.
solution (Solution) – The solution to generate a new solution from.
number_of_vertices_to_remove (int) – The number of vertices to remove from the solution.

Returns:

A tuple containing the destroy and repair operator used to generate the solution.

Return type:

Tuple[DestroyOperator, RepairOperator]

remove_destroy_operator(destroy_operator: DestroyOperator)

Remove a destroy operator.

Parameters:: destroy_operator (DestroyOperator) – The operator to remove.
Return type:: None

remove_repair_operator(repair_operator: RepairOperator)

Remove a repair operator.

Parameters:: repair_operator (RepairOperator) – The operator to remove.
Return type:: None

reset_operator_weights()

Reset the weights of all operators to 1.

Return type:: None

property destroy_operators

Get an iterator over all registered destroy operators.

Return type:: Iterator

property repair_operators

Get an iterator over all registered repair operators.

Return type:: Iterator