Routingblocks class index

class routingblocks.ADPTWVertexData(x: float, y: float, demand: float, earliest_time_of_arrival: float, latest_time_of_arrival: float, service_time: float)

Data stored on vertices in an ADPTW problem setting.

Parameters:

  • x (float) – The x coordinate of the vertex.

  • y (float) – The y coordinate of the vertex.

  • demand (float) – The demand of the vertex. 0 for station and depot vertices.

  • earliest_time_of_arrival (float) – The earliest time at which service at the vertex can begin.

  • latest_time_of_arrival (float) – The latest time at which service at the vertex can begin.

  • service_time (float) – The time needed to serve the vertex.

class routingblocks.ADPTWArcData(distance: float, travel_time: float, consumption: float)

Data stored on arcs in an ADPTW problem setting.

Parameters:

  • distance (float) – The distance between the two vertices connected by the arc.

  • travel_time (float) – The time it takes to travel between the two vertices connected by the arc.

  • consumption (float) – The time required to replenish the resource consumed when traveling between the two vertices connected by the arc.

routingblocks.create_adptw_vertex(vertex_id: int, str_id: str, is_facility: bool, is_depot: bool, data: ADPTWVertexData)

Creates a vertex for an ADPTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created vertex is not accessible from python. Doing so will likely result in a crash.

Parameters:

  • vertex_id (int) – The unique identifier of the vertex.

  • str_id (str) – A human-readable string identifier for the vertex.

  • is_facility (bool) – Whether the vertex is a replenishment facility.

  • is_depot (bool) – Whether the vertex is a depot.

  • data (ADPTWVertexData) – The data to associate with this vertex.

Returns:

Return type:

Vertex

routingblocks.create_adptw_arc(data: ADPTWArcData)

Creates an arc for an ADPTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created arc is not accessible from python. Doing so will likely result in a crash.

Parameters:

data (ADPTWArcData) – The data to associate with this vertex

Returns:

Return type:

Arc

class routingblocks.ADPTWEvaluation(vehicle_resource_capacity: float, vehicle_storage_capacity: float)

Evaluation for ADPTW problems. Works only with arcs and vertices created using create_adptw_arc and create_adptw_vertex. Uses a set of penalty factors to penalize infeasible solutions.

Variables:

  • overload_penalty_factor – The penalty factor for overloading the vehicle.

  • resource_penalty_factor – The penalty factor for consuming more resources than carried the vehicle.

  • time_shift_penalty_factor – The penalty factor for time shifts.

Parameters:

  • vehicle_resource_capacity (float) – The vehicle’s battery capacity expressed in units of time, that is, the time it takes to fully replenish the resource of an empty vehicle.

  • vehicle_storage_capacity (float) – The vehicle’s storage capacity. Determines how much demand can be served in a single route.

overload_penalty_factor
resource_penalty_factor
time_shift_penalty_factor
class routingblocks.ADPTWFacilityPlacementOptimizer(instance: Instance, resource_capacity_time: float)

ADPTW-specific detour insertion algorithm. Inserts visits to replenishment facilities at optimal locations into a route.

Parameters:

  • instance (Instance) – The instance.

  • resource_capacity_time (float) – The vehicle’s resource capacity expressed in units of time, that is, the time it takes to fully replenish the resource of an empty vehicle.

optimize(route_vertex_ids: List[VertexID])

Optimizes the route by inserting visits to replenishment facilities at optimal locations. :param route_vertex_ids: The vertex ids of the route to optimize. :return: The optimized route as a list of vertex ids.

Parameters:

route_vertex_ids (List[VertexID]) –

Return type:

List[VertexID]

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

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

class routingblocks.Arc(data: Any)

A simple arc object that represents a connection between two vertices in a graph. The arc stores additional data transparent to the RoutingBlocks package. This data can be used to store additional information about the arc, such as distances, durations, or any other attributes relevant to the problem being modeled.

Parameters:

data (Any) – Additional data associated with the arc.

property data

Retrieves the arc data.

Returns:

The data associated with the arc.

Return type:

Any

class routingblocks.Evaluation

The evaluation class implements problem-specific cost and move evaluation functions. It’s design bases on the concepts introduced in Vidal et al. [VCGP14]. Note that this class is an interface: it’s not meant to be instantiated or used directly. Please use the concrete implementations of this interface and helper functions instead.

compute_cost(label: AnyForwardLabel)

Computes the cost of a given label.

Parameters:

label (AnyForwardLabel) – The label

Returns:

The cost of the label

Return type:

float

evaluate(instance: Instance, segments: List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]])

Evaluates the cost of the route given by concatenating the passed route sub-sequences. Each sub-sequences is guaranteed to have valid forward and backward labels.

Corresponds to EVALN in Vidal et al. [VCGP14].

Parameters:

  • instance (Instance) – The instance

  • segments (List[List[Tuple[Vertex, AnyForwardLabel, AnyBackwardLabel]]]) – A list of route sub-sequences, each given as a list of tuples of (vertex, forward label, backward label)

Returns:

The cost of the route

Return type:

float

create_backward_label(vertex: Vertex)

Creates and initializes a backward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:

vertex (Vertex) – The vertex representing singleton route [vertex]

Returns:

The initialized backward label

Return type:

AnyBackwardLabel

create_forward_label(vertex: Vertex)

Creates and initializes a forward label for the given vertex.

Corresponds to INIT in Vidal et al. [VCGP14].

Parameters:

vertex (Vertex) – The vertex representing singleton route [vertex]

Returns:

The initialized backward label

Return type:

AnyBackwardLabel

get_cost_components(label: AnyForwardLabel)

Returns the cost components of a given label.

Parameters:

label (AnyForwardLabel) – The label

Returns:

The cost components of the label

Return type:

List[float]

is_feasible(label: AnyForwardLabel)

Checks whether a given label is feasible.

Parameters:

label (AnyForwardLabel) – The label

Returns:

True if the label is feasible, False otherwise

Return type:

bool

propagate_forward(pred_label: AnyForwardLabel, pred_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the forward label of pred_vertex to the vertex.

Corresponds to FORW([..., pred_vertex]⊕[vertex]) in Vidal et al. [VCGP14].

Parameters:

  • pred_label (AnyForwardLabel) – The forward label of the predecessor vertex

  • pred_vertex (Vertex) – The predecessor vertex

  • vertex (Vertex) – The vertex

  • arc (Arc) – The arc connecting pred_vertex and vertex

Returns:

The propagated forward label

Return type:

AnyForwardLabel

propagate_backward(succ_label: AnyBackwardLabel, succ_vertex: Vertex, vertex: Vertex, arc: Arc)

Extends the partial route represented by the backward label of succ_vertex to the vertex.

Corresponds to BACK([vertex]⊕[succ_vertex, ...]) in Vidal et al. [VCGP14].

Parameters:

  • succ_label (AnyBackwardLabel) – The backward label of the successor vertex

  • succ_vertex (Vertex) – The successor vertex

  • vertex (Vertex) – The vertex

  • arc (Arc) – The arc connecting succ_vertex to vertex. Note that this corresponds to the reverse arc of the forward direction.

Returns:

The propagated backward label

Return type:

AnyBackwardLabel

class routingblocks.PyEvaluation

The PyEvaluation class implements the evaluation interface in pure Python. It’s meant to be used as a base class for custom python-based evaluation classes.

class routingblocks.PyConcatenationBasedEvaluation

The evaluation class implements problem-specific cost and move evaluation functions. It’s design bases on the concepts introduced in Vidal et al. [VCGP14]. Note that this class is an interface: it’s not meant to be instantiated or used directly. Please use the concrete implementations of this interface and helper functions instead.

concatenate(fwd: AnyForwardLabel, bwd: AnyBackwardLabel, vertex: Vertex)

Specialization of the general evaluation member of PyEvaluation for cases where two route subsequences can be concatenated efficiently. Classes who extend this class do not need to implement PyEvaluation.evaluate.

The concatenation function works as follows: Assume that we have two route subsequences [v_1, ..., v_n] and [v_{n+1}, ..., v_m]. The specialized evaluation function first propagates v_n to v_{n+1}, and the calls concatenate(fwd_{n+1}, bwd_{n+1}, v_{n+1}) where fwd_{n+1} is the forward label of v_{n+1} and bwd_{n+1} is the backward label of v_{n+1}.

If the specialized evaluation function is called with several route sub-sequences [..., v_n], [v_n+1, ... v_{n+m}], [v_{n+m+1}, ...] then the first sequence is extended to v_{n+m} and the operation reduces to the first case: concatenate(fwd_{n+m+1}, bwd_{n+m+1}, v_{n+m+1}) where fwd_{n+m+1} is the forward label of v_{n+m+1} and bwd_{n+m+1} is the backward label of v_{n+m+1}.

Parameters:

  • fwd (AnyForwardLabel) – The forward label representing the route sub-sequence [v_1, ..., v_n, v_{n+1}]

  • bwd (AnyBackwardLabel) – The backward label representing the route sub-sequence [v_{n+1}, ..., v_m]

  • vertex (Vertex) – The vertex v_{n+1}

Returns:

The cost of the route [v_1, ..., v_n, v_{n+1}, ..., v_m]

Return type:

float

routingblocks.evaluate_insertion(evaluation: Evaluation, instance: Instance, route: Route, after_position: int, vertex_id: VertexID)

Evaluates inserting a node into a route after the specified position.

Parameters:

  • evaluation – The evaluation function

  • instance – The instance

  • route – The route

  • after_position – The position after which the vertex is inserted

  • node – The node to insert

Returns:

The cost of the route with the vertex inserted

Return type:

float

routingblocks.evaluate_splice(evaluation: Evaluation, instance: Instance, route: Route, forward_segment_end_pos: int, backward_segment_begin_pos: int)

Evaluates splicing two sub-sequences of a route together. The first sub-seuence ends (non-inclusive) at forward_segment_end_pos and the second sub-sequence starts (including) at backward_segment_begin_pos.

Example: Let route = [D, C1, C2, C3, C4, C5, C6, D] and forward_segment_end_pos = 2 and backward_segment_begin_pos = 5. Then the sub-sequences are [D, C1] and [C5, C6, D]. The splice operation thus evaluates the cost of the route [D, C1, C5, C6, D].

Parameters:

  • evaluation (Evaluation) – The evaluation function

  • instance (Instance) – The instance

  • route (Route) – The route

  • forward_segment_end_pos (int) – The end position of the first sub-sequence (non-inclusive)

  • backward_segment_begin_pos (int) – The start position of the second sub-sequence

Returns:

The cost of the spliced route

Return type:

float

class routingblocks.Propagator

The Propagator class implements problem-specific ordering, dominance, and propagation functions. It’s design bases on the concepts introduced in Irnich [Irn08]. Note that this class is an interface: it’s not meant to be instantiated or used directly. Please use the concrete implementations of this interface instead.

cheaper_than(label: Any, other_label: Any)

Checks whether the label is cheaper than the other label, i.e., has lower cost.

Parameters:

  • label (Any) – The (potentially) cheaper label.

  • other_label (Any) – The (potentially) more expensive label.

Returns:

True if the label is cheaper than the other label, False otherwise.

Return type:

bool

create_root_label()

Creates the initial label for the dynamic programming algorithm. Represents the state at the source node, i.e. the depot node. :return: The initial label.

Return type:

Any

dominates(label: Any, other_label: Any)

Checks whether the label dominates the other label.

Parameters:

  • label (Any) – The (potentially) dominating label.

  • other_label (Any) – The (potentially) dominated label.

Returns:

Return type:

bool

extract_path(label: Any)

Extracts the path represented by label, converting it to a list of vertex IDs.

Parameters:

label (Any) – The label that represents the path.

Returns:

The list of vertex IDs visited on the path.

Return type:

List[VertexID]

is_final_label(label: Any)

Checks whether the label is the final label, i.e. whether it represents a depot-depot path. :param label: The label to check. :return: True if the label is final, False otherwise.

Parameters:

label (Any) –

Return type:

bool

order_before(label: Any, other_label: Any)

Whether the label should be ordered before the other label. This is used to determine the order in which labels are stored in the set of settled labels, which is important for dominance checks: the checks considers only labels that would be ordered before the label being checked.

Parameters:

  • label (Any) – The (potentially) earlier label.

  • other_label (Any) – The (potentially) later label.

Returns:

True if the label should be ordered before the other label, False otherwise.

Return type:

bool

prepare(route_vertex_ids: List[VertexID])

Prepare the propagator before running the algorithm on the route represented by the given vertex IDs. :param route_vertex_ids: The vertex IDs of the route.

Parameters:

route_vertex_ids (List[VertexID]) –

Return type:

None

propagate(label: Any, origin_vertex: Vertex, target_vertex: Vertex, arc: Arc)

Propagates the label to the target vertex, using the given arc. This creates a new label that represents the state at the target vertex. Return None if the resulting path would be infeasible.

Parameters:

  • label (Any) – The label to propagate.

  • origin_vertex (Vertex) – The origin vertex of the arc.

  • target_vertex (Vertex) – The target vertex of the arc.

  • arc (Arc) – The arc to propagate the label along.

Returns:

The propagated label, or None if the resulting path would be infeasible.

Return type:

Optional[Any]

class routingblocks.FacilityPlacementOptimizer(instance: Instance, propagator: Propagator)

Algorithm that inserts visits to replenishment facilities at optimal locations into a route.

Parameters:

  • instance (Instance) – The instance.

  • propagator (Propagator) – The propagator to use.

optimize(route_vertex_ids: List[VertexID])

Inserts visits to replenishment facilities at optimal locations into the route represented by the given vertex IDs.

Parameters:

route_vertex_ids (List[VertexID]) – The vertex IDs of the route.

Returns:

The vertex IDs of the optimized route.

Return type:

List[VertexID]

class routingblocks.InsertionMove(vertex_id: VertexID, after_node_location: NodeLocation, delta_cost: float)
Parameters:

  • vertex_id (VertexID) – The vertex to be inserted.

  • after_node – The node after which the vertex should be inserted.

  • delta_cost (float) – The change in cost incurred from inserting the vertex at the specified position.

  • after_node_location (NodeLocation) –

vertex_id
after_node
delta_cost
class routingblocks.InsertionCache(instance: Instance)
Parameters:

instance (Instance) –

clear()
Return type:

None

get_best_insertions_for_vertex(vertex_id: VertexID)
Parameters:

vertex_id (VertexID) –

Return type:

List[InsertionMove]

invalidate_route(route: Route, route_index: int)
Parameters:

  • route (Route) –

  • route_index (int) –

Return type:

None

rebuild(evaluation: Evaluation, solution: Solution, vertex_ids: List[VertexID])
Parameters:
Return type:

None

stop_tracking(vertex_id: VertexID)
Parameters:

vertex_id (VertexID) –

Return type:

None

tracks_vertex(vertex_id: VertexID)
Parameters:

vertex_id (VertexID) –

Return type:

bool

property moves_in_order
Return type:

List[InsertionMove]

property tracked_vertices
Return type:

List[VertexID]

class routingblocks.Instance(depot: Vertex, stations: List[Vertex], customers: List[Vertex], arcs: List[List[Arc]], fleet_size: int)

Represents an instance of a vehicle routing problem. The instance contains a collection of vertices (depot, stations, and customers), a matrix of arcs connecting the vertices, and a fleet size representing the number of vehicles available. Provides convenient methods to access and iterate through the various types of vertices.

Note

It is recommend to use the InstanceBuilder to create instances.

Parameters:

  • vertices (List[Vertex]) – A list of vertices in the order depot, stations, customers

  • arcs (List[List[Arc]]) – A list of lists of Arc objects representing the connections between vertices

  • fleet_size (int) – The number of vehicles in the fleet

property fleet_size

Retrieves the number of vehicles available.

Returns:

The fleet size.

Return type:

int

property number_of_customers

Retrieves the number of customers.

Returns:

The number of customers.

Return type:

int

property number_of_stations

Retrieves the number of stations.

Returns:

The number of stations.

Return type:

int

property number_of_vertices

Retrieves the number of vertices.

Returns:

The number of vertices.

Return type:

int

property depot

Retrieves the depot vertex.

Returns:

The depot vertex.

Return type:

Vertex

property vertices

Retrieves an iterator over the instance’s vertices.

Returns:

An iterator over the instance’s vertices.

Return type:

Iterator[Vertex]

property stations

Retrieves an iterator over the station vertices.

Returns:

An iterator over the station vertices.

Return type:

Iterator[Vertex]

property customers

Retrieves an iterator over the customer vertices.

Returns:

An iterator over the customer vertices.

Return type:

Iterator[Vertex]

get_vertex(id: int)

Retrieves a vertex by its ID.

Parameters:

id (int) – The ID of the desired vertex.

Returns:

The vertex with the specified ID.

Return type:

Vertex

get_customer(customer_index: int)

Retrieves the n-th customer vertex.

Parameters:

customer_index (int) – The index of the desired customer vertex.

Returns:

The customer vertex at the specified index.

Return type:

Vertex

get_station(station_index: int)

Retrieves the n-th station vertex.

Parameters:

station_index (int) – The index of the desired station vertex.

Returns:

The station vertex at the specified index.

Return type:

Vertex

get_arc(source_vertex_id: int, target_vertex_id: int)

Retrieves the arc connecting two vertices, specified by their IDs.

Parameters:

  • source_vertex_id (int) – The ID of the source vertex.

  • target_vertex_id (int) – The ID of the target vertex.

Returns:

The arc connecting the source and target vertices.

Return type:

Arc

class routingblocks.ArcSet(number_of_vertices: int)
Parameters:

number_of_vertices (int) –

forbid_arc(origin_vertex_id: VertexID, target_vertex_id: VertexID)
Parameters:

  • origin_vertex_id (VertexID) –

  • target_vertex_id (VertexID) –

Return type:

None

include_arc(origin_vertex_id: VertexID, target_vertex_id: VertexID)
Parameters:

  • origin_vertex_id (VertexID) –

  • target_vertex_id (VertexID) –

Return type:

None

includes_arc(origin_vertex_id: VertexID, target_vertex_id: VertexID)
Parameters:

  • origin_vertex_id (VertexID) –

  • target_vertex_id (VertexID) –

Return type:

bool

class routingblocks.GeneratorArc(solution: Solution, origin_route_index: int, origin_node_position: int, target_route_index: int, target_node_position: int)
property origin_node
Return type:

Node

property origin_route
Return type:

Route

property target_node
Return type:

Node

property target_route
Return type:

Route

class routingblocks.Move

Interface for implementing custom moves.

apply(instance: Instance, solution: Solution)

Applies the move to the solution.

Parameters:

  • instance (Instance) – The instance.

  • solution (Solution) – The solution to be improved.

Returns:

Return type:

None

get_cost_delta(evaluation: Evaluation, instance: Instance, solution: Solution)

Returns the cost delta of the move according to the passed evaluation function.

Parameters:

  • evaluation (Evaluation) – The evaluation function to use.

  • instance (Instance) – The instance.

  • solution (Solution) – The solution.

Returns:

Return type:

float

class routingblocks.LocalSearchOperator

Interface for implementing custom local search operators.

finalize_search()

Called after the search for improving moves has been completed.

Return type:

None

find_next_improving_move(evaluation: Evaluation, solution: Solution, last_evaluated_move: Move | None)

Finds the next improving move. Returns None if no improving move is found. To avoid looping forever, this method should pick up the search where it left off, i.e., at last_evaluated_move.

Parameters:

  • evaluation (Evaluation) – The evaluation function to use.

  • solution (Solution) – The solution to be improved.

  • last_evaluated_move (Optional[Move]) – The last move that was evaluated. Note that this corresponds to the last Move this operator returned. None if no move has been evaluated yet.

Returns:

The next improving move. None if no improving move is found.

Return type:

Optional[Move]

prepare_search(solution: Solution)

Called before the search for improving moves is started.

Parameters:

solution (Solution) – The solution to be improved.

Return type:

None

class routingblocks.PivotingRule

Interface for implementing custom pivoting rules.

select_move(solution: Solution)

Return the move to be applied to the solution.Returns none if no move is found.

Parameters:

solution (Solution) – The solution to be improved.

Returns:

The move to be applied to the solution.

Return type:

Optional[Move]

continue_search(found_improving_move: Move, delta_cost: float, solution: Solution)

Determine if the search should continue or terminate.

Parameters:

  • found_improving_move (Move) – The move found to be improving.

  • delta_cost (float) – The(exact) cost difference between the current solution and the solution after applying the move.

  • solution (Solution) – The solution the move should be applied to.

Returns:

True if the search should continue, False otherwise.

Return type:

bool

class routingblocks.BestImprovementPivotingRule

The best improvement pivoting rule selects the best improving move found during the search for improving moves. It never terminates the search prematurely.

class routingblocks.KBestImprovementPivotingRule(k: int)

The k - best improvement pivoting rule selects best out of the first k improving moves found during the search for improving moves. It terminates the search as soon as the k - th improving move is found.

Parameters:

k (int) – The number of improving moves to consider.

class routingblocks.FirstImprovementPivotingRule

The first improvement pivoting rule selects the first improving move found during the search for improving moves. It terminates the search as soon as the first improving move is found.

class routingblocks.LocalSearch(instance: Instance, evaluation: Evaluation, exact_evaluation: Evaluation | None, pivoting_rule: PivotingRule)

This class implements a customizable local search algorithm.

Parameters:
optimize(solution: Solution, operators: List[LocalSearchOperator])

Searches the neighborhood of the solution for improving moves and applies them until no further improvement is possible. The neighborhood is defined by the passed operators. Modifies the passed solution in-place.

Parameters:

  • solution (Solution) – The solution to be improved.

  • operators (List[LocalSearchOperator]) – The operators to use for searching the neighborhood.

Returns:

Return type:

None

class routingblocks.QuadraticNeighborhoodIterator
iter_neighborhood()
Return type:

Iterator

class routingblocks.NIFTWVertexData(x: float, y: float, demand: float, earliest_time_of_arrival: float, latest_time_of_arrival: float, service_time: float)

Data stored on vertices in an NIFTW problem setting.

Parameters:

  • x (float) – The x coordinate of the vertex.

  • y (float) – The y coordinate of the vertex.

  • demand (float) – The demand of the vertex. 0 for station and depot vertices.

  • earliest_time_of_arrival (float) – The earliest time at which service at the vertex can begin.

  • latest_time_of_arrival (float) – The latest time at which service at the vertex can begin.

  • service_time (float) – The time needed to serve the vertex.

class routingblocks.NIFTWArcData(distance: float, travel_time: float, consumption: float)

Data stored on arcs in an NIFTW problem setting.

Parameters:

  • distance (float) – The distance between the two vertices connected by the arc.

  • travel_time (float) – The time it takes to travel between the two vertices connected by the arc.

  • consumption (float) – The time required to recharge the resources consumed when traveling between the two vertices connected by the arc.

routingblocks.create_niftw_vertex(vertex_id: int, str_id: str, is_station: bool, is_depot: bool, data: NIFTWVertexData)

Creates a vertex for an NIFTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created vertex is not accessible from python. Doing so will likely result in a crash.

Parameters:

  • vertex_id (int) – The unique identifier of the vertex.

  • str_id (str) – A human-readable string identifier for the vertex.

  • is_station (bool) – Whether the vertex is a station.

  • is_depot (bool) – Whether the vertex is a depot.

  • data (NIFTWVertexData) – The data to associate with this vertex.

Returns:

Return type:

Vertex

routingblocks.create_niftw_arc(data: NIFTWArcData)

Creates an arc for an NIFTW problem setting. Stores :param data directly as a native C++ object.

Warning

The data member of the created arc is not accessible from python. Doing so will likely result in a crash.

Parameters:

data (NIFTWArcData) – The data to associate with this vertex

Returns:

Return type:

Arc

class routingblocks.NIFTWEvaluation(vehicle_resource_capacity: float, vehicle_storage_capacity: float, replenishment_time: float)

Evaluation for NIFTW problems. Works only with arcs and vertices created using create_niftw_arc and create_niftw_vertex. Uses a set of penalty factors to penalize infeasible solutions.

Variables:

  • overload_penalty_factor – The penalty factor for overloading the vehicle.

  • resource_penalty_factor – The penalty factor for consuming more resources than carried by the vehicle.

  • time_shift_penalty_factor – The penalty factor for time shifts.

Parameters:

  • vehicle_resource_capacity (float) – The vehicle’s battery capacity expressed in units of time, that is, the time it takes to fully recharge an empty battery.

  • vehicle_storage_capacity (float) – The vehicle’s storage capacity. Determines how much demand can be served in a single route.

  • replenishment_time (float) – The time penalty incurred to replenish all the resources carried by the vehicle.

overload_penalty_factor
resource_penalty_factor
time_shift_penalty_factor
class routingblocks.NIFTWFacilityPlacementOptimizer(instance: Instance, battery_capacity_time: float, replenishment_time: float)

NIFTW-specific detour insertion algorithm. Inserts visits to replenishment facilities at optimal locations into a route.

Parameters:

  • instance (Instance) – The instance to optimize.

  • battery_capacity_time (float) – The vehicle’s resource capacity expressed in units of time, that is, the time it takes to fully recharge an empty battery.

  • replenishment_time (float) – The time penalty incurred to replenish all the resources carried by the vehicle.

optimize(route_vertex_ids: List[VertexID])

Optimizes the route by inserting visits to replenishment facilities at optimal locations. :param route_vertex_ids: The vertex ids of the route to optimize. :return: The optimized route as a list of vertex ids.

Parameters:

route_vertex_ids (List[VertexID]) –

Return type:

List[VertexID]

class routingblocks.Node(vertex: Vertex, fwd_label: AnyForwardLabel, bwd_label: AnyBackwardLabel)

A node represents a visit to a vertex. It carries forward and backward labels that are used for cost calculation, constraint checking, and efficient move evaluation. The data itself is opaque to the node class, and is only used by the evaluation object.

Parameters:

  • vertex (Vertex) – The associated Vertex object.

  • fwd_label (AnyForwardLabel) – The forward label for the node.

  • bwd_label (AnyBackwardLabel) – The backward label for the node.

cost(evaluation: Evaluation)

Computes the cost according to the forward label carried by the node using the given evaluation. See the documentation of the evaluation object for more information.

Parameters:

evaluation (Evaluation) – The evaluation object for computing costs.

Returns:

The cost.

Return type:

float

cost_components(evaluation: Evaluation)

Computes the individual cost components according to the forward label carried by the node using the given evaluation. See the documentation of the evaluation object for more information.

Parameters:

evaluation (Evaluation) – The evaluation object for computing cost components.

Returns:

A list of cost components.

Return type:

List[float]

feasible(evaluation: Evaluation)

Determines if the node is feasible based on the given evaluation. See the documentation of the evaluation object for more information.

Parameters:

evaluation (Evaluation) – The evaluation object for checking feasibility.

Returns:

True if the node is feasible, False otherwise.

Return type:

bool

update_backward(evaluation: Evaluation, predecessor: Node, arc: Arc)

Updates the backward label of the node based on the given evaluation, predecessor node, and arc. See the documentation of the evaluation object for more information.

Parameters:

  • evaluation (Evaluation) – The evaluation object for updating the backward label.

  • predecessor (Node) – The predecessor node in the solution space.

  • arc (Arc) – The arc connecting the predecessor node to the current node.

Return type:

None

update_forward(evaluation: Evaluation, successor: Node, arc: Arc)

Updates the forward label of the node based on the given evaluation, successor node, and arc. See the documentation of the evaluation object for more information.

Parameters:

  • evaluation (Evaluation) – The evaluation object for updating the forward label.

  • successor (Node) – The successor node in the solution space.

  • arc (Arc) – The arc connecting the current node to the successor node.

Return type:

None

property backward_label

Retrieves the backward label of the node.

Returns:

The backward label.

Return type:

AnyBackwardLabel

property forward_label

Retrieves the forward label of the node.

Returns:

The forward label.

Return type:

AnyForwardLabel

property vertex

Retrieves the vertex represented by this node.

Returns:

The associated Vertex object.

Return type:

Vertex

property vertex_id

Shorthand to retrieve the unique id of the node’s vertex.

Returns:

The unique identifier of the associated vertex.

Return type:

int

property vertex_strid

Shorthand to retrieve the name of the node’s vertex.

Returns:

The name of the associated vertex.

Return type:

str

class routingblocks.NodeLocation(route: int, position: int)

A class representing the location of a node within a solution. Stores the route index and the position of the node within that route.

Parameters:

  • route (int) – The index of the route in which the node is located.

  • position (int) – The position of the node within the route.

route
position
class routingblocks.Random

Initializes a new instance of the Random class with a provided seed.

The seed is a number used to initialize the underlying pseudo-random number generator.

Parameters:

seed (int) – The seed value for the random number generator. Providing the same seed will generate the same sequence of random numbers.

randint(min: int, max: int)

Returns a random integer from the specified range [min, max], including both endpoints.

Parameters:

  • min (int) – The lower bound of the range.

  • max (int) – The upper bound of the range.

Returns:

A random integer value from the specified range [min, max].

Return type:

int

uniform(min: float, max: float)

Returns a random floating-point number between the specified min and max values, including min and potentially up to max.

Parameters:

  • min (float) – The lower bound of the range.

  • max (float) – The upper bound of the range.

Returns:

A random floating-point number within the specified range [min, max).

Return type:

float

class routingblocks.RemovalMove(vertex_id: VertexID, node_location: NodeLocation, delta_cost: float)
Parameters:

  • vertex_id (VertexID) – The vertex ID of the node to be removed.

  • node_location (NodeLocation) – The location of the node to be removed.

  • delta_cost (float) – The change in cost of the solution if the node is removed.

vertex_id
node_location
delta_cost
class routingblocks.RemovalCache(instance: Instance)
Parameters:

instance (Instance) –

clear()
Return type:

None

invalidate_route(route: Route, route_index: int)
Parameters:

  • route (Route) –

  • route_index (int) –

Return type:

None

rebuild(evaluation: Evaluation, solution: Solution)
Parameters:
Return type:

None

property moves_in_order
Return type:

List[RemovalMove]

class routingblocks.Route(evaluation: Evaluation, instance: Instance)

Routes represent a sequence of visits to vertices, represented by Node objects. A route starts and ends at the depot. The route class ensures that the information stored in each node’s label is consistent with the forward and backward sequences.

Example:

Route [D, a, b, c, d, e, D], where capital D represents a visit to the depot. Then the route class ensures that the forward labels stored on node ‘c’ represent the sequence [D, a, b, c], that is, are calculated by propagating the forward label at D across arcs (D, a), (a, b), (b, c). Similarly, the backward labels stored on node ‘c’ represent the sequence [c, d, e, D].

Routes behave like lists of nodes, that is, they can e.g. be indexed and iterated over.

Routes carry a globally unique modification timestamp which can be used to efficiently test two routes for equality: On each modification of the route, the modification timestamp is incremented, while copying a route preserves it’s timestamp. Hence, two routes with the same modification timestamp are guaranteed to be equal, although the converse does not necessarily apply.

The route constructor creates an empty route, that is, a route that contains only start and end depots. Refer to create_route for a method to create a route from a sequence of vertex ids.

Parameters:

  • evaluation (Evaluation) – The Evaluation object used for cost and feasibility calculations.

  • instance (Instance) – The Instance object representing the problem instance.

property cost

Calculates the route’s cost.

Returns:

The cost of the route.

Return type:

float

property cost_components

Calculates the route’s cost components.

Returns:

A list of cost components .

Return type:

List[float]

property depot

Retrieves the depot node of the route.

Returns:

The start depot node.

Return type:

Node

property empty

Determines if the route is empty.

Returns:

True if the route is empty, False otherwise.

Return type:

bool

property end_depot

Retrieves the end depot node of the route.

Returns:

The end depot node.

Return type:

Node

property feasible

Determines if the route is feasible.

Returns:

True if the route is feasible, False otherwise.

Return type:

bool

property modification_timestamp

Retrieves the modification timestamp of the route.

Returns:

The modification timestamp.

Return type:

int

exchange_segments(segment_begin_position: int, segment_end_position: int, other_segment_begin_position: int, other_segment_end_position: int, other_route: Route)

Exchanges the segment [segment_begin_position, segment_end_position) of this route with the segment [other_segment_begin_position, other_segment_end_position) of the other route. The swapped segments do not include the respective segment end nodes. This method if well defined even if other_route is this route as long as the segments do not overlap.

Parameters:

  • segment_begin_position (int) – The start position of the segment in this route.

  • segment_end_position (int) – The end position of the segment in this route. Not included.

  • other_segment_begin_position (int) – The start position of the segment in the other route.

  • other_segment_end_position (int) – The end position of the segment in the other route. Not included.

  • other_route (Route) – The other route to exchange segments with.

Return type:

None

insert_segment_after(position: int, node_segment: List[Node])

Inserts a sequence of nodes after the given position in the route.

Parameters:

  • position (int) – The position after which to insert the segment.

  • node_segment (List[Node]) – The sequence of nodes to insert.

Returns:

The new position after the insertion.

Return type:

int

insert_vertices_after(vertices: Iterable[Tuple[VertexID, int]])

Inserts a batch of vertices at the given positions. This method is more efficient than calling insert_segment_after multiple times.

Parameters:

vertices (Iterable) – The iterable containing tuples of vertices with the positions to insert after.

Return type:

None

remove_segment(begin_position: int, end_position: int)

Removes a segment of nodes from the route. Example:

route = routingblocks.create_route(evaluation, instance, [D, C1, C2, C3, D])
new_position_of_end_position = route.remove_segment(1, 3)
print(route) # [D, C3, D]
print(new_position_of_end_position) # 1
Parameters:

  • begin_position (int) – The start position of the segment to remove.

  • end_position (int) – The end position of the segment to remove. Not inclusive.

Returns:

The new position of end_position after removal.

Return type:

int

remove_vertices(vertex_positions: List[int])

Removes vertices at the specified positions from the route.

Parameters:

vertex_positions (List[int]) – The list of vertex positions to remove.

Return type:

None

update()

Updates the route, recalculating the forward and backward labels, costs, and feasibility.

Return type:

None

copy()

Creates a copy of the route. Copies Node objects and labels, but not the underlying Vertex and Instance objects.

Returns:

A deep copy of the route.

Return type:

Route

routingblocks.create_route(evaluation: Evaluation, instance: Instance, vertex_ids: List[int])
Parameters:
Return type:

Route

class routingblocks.Solution(evaluation: Evaluation, instance: Instance, number_of_routes: int)

The Solution class represents a solution to a VRP problem. It maintains a list of Route objects, providing methods for cost calculation, feasibility checking, route manipulation, and finding vertices. Solution objects behave like lists of routes, so you can iterate over them, index them, and get their length:

solution = Solution(evaluation, instance, 5)

for route in solution:
    print(route)

print(solution[0])

print(len(solution))

del solution[0]

Note that any operations that add routes implicitly copy the route objects. For example:

solution = Solution(evaluation, instance, 0)
route = create_route(evaluation, instance, [D, C1, D])
solution.add_route(route)

route.insert_vertex_after(1, C2)
print(route) # [D, C1, C2, D]
print(solution.routes[0]) # [D, C1, D]

Creates a new Solution object with the specified list of routes.

Parameters:

  • evaluation (Evaluation) – The evaluation object for cost and feasibility calculations.

  • instance (Instance) – The Instance object representing the problem instance.

  • routes (List[Route]) – The list of routes to include in the solution.

add_route(route: Route | None = None)

Adds a new route to the solution. If no route is provided, an empty route will be added.

Parameters:

route (Optional[Route]) – The route to add to the solution (optional).

Return type:

None

exchange_segment(first_route: Route, first_route_begin_position: int, first_route_end_position: int, second_route: Route, second_route_begin_position: int, second_route_end_position: int)

Exchanges segments between two routes using their indices.

Parameters:

  • first_route_index (int) – The index of the first route in the exchange operation.

  • first_route_begin_position (int) – The start position of the segment in the first route.

  • first_route_end_position (int) – The end position of the segment in the first route.

  • second_route_index (int) – The index of the second route in the exchange operation.

  • second_route_begin_position (int) – The start position of the segment in the second route.

  • second_route_end_position (int) – The end position of the segment in the second route.

find(vertex_id: int)

Finds the locations of a vertex in the solution.

Parameters:

vertex_id (int) – The vertex ID to search for.

Returns:

A list of NodeLocation objects representing the locations of the vertex in the solution.

Return type:

List[NodeLocation]

insert_vertex_after(after_location: NodeLocation, vertex_id: int)

Inserts a vertex after the specified location.

Parameters:

  • after_location (NodeLocation) – The location after which to insert the vertex.

  • vertex_id (int) – The vertex ID to insert.

Returns:

The position of the newly inserted vertex.

Return type:

int

insert_vertices_after(vertex_ids_and_positions: Iterable[Tuple[VertexID, NodeLocation]])

Inserts multiple vertices at the specified locations.

Parameters:

  • vertex_ids_and_positions (Iterable[Tuple[VertexID, NodeLocation]]) – An iterable of tuples containing the vertex ID and the location after which to insert the vertex.

  • vertex_ids_and_positions –

Return type:

None

lookup(location: NodeLocation)

Retrieves the node at the specified location.

Parameters:

location (NodeLocation) – The location of the node to retrieve.

Returns:

The node at the specified location.

Return type:

Node

remove_route(route: Route)

Removes the specified route from the solution.

Parameters:

route (Route) – The route to remove from the solution.

Return type:

None

remove_vertex(location: NodeLocation)

Removes the vertex at the specified location.

Parameters:

location (NodeLocation) – The location of the vertex to remove.

Return type:

None

remove_vertices(locations: List[NodeLocation])

Removes multiple vertices at the specified locations. This is more efficient than calling remove_vertex() multiple times.

Parameters:

locations (List[NodeLocation]) – A list of locations of the vertices to remove.

Return type:

None

copy()

Creates a copy of the solution. This copies routes and nodes.

Returns:

A copy of the solution.

Return type:

Solution

property cost

Gets the total cost of the solution, i.e., the sum of costs of all routes.

Returns:

The total cost of the solution.

Return type:

float

property cost_components

Gets the cost components of the solution, i.e., the sum of costs components of all routes.

Returns:

A list of cost components for the solution.

Return type:

List[float]

property feasible

Determines if the solution is feasible.

Returns:

True if the solution is feasible, False otherwise.

Return type:

bool

property insertion_points

Gets all possible insertion points in the solution. That is, for each route r, positions [0, len(r) - 2].

Returns:

A list of NodeLocation objects representing the insertion points in the solution.

Return type:

List[NodeLocation]

property non_depot_nodes

Gets the non-depot nodes in the solution. Useful for removing nodes from the solution.

Returns:

A list of NodeLocation objects representing the non-depot nodes in the solution.

Return type:

List[NodeLocation]

property number_of_insertion_points

Gets the number of insertion points in the solution.

Returns:

The number of insertion points in the solution.

Return type:

int

property number_of_non_depot_nodes

Gets the number of non-depot nodes in the solution.

Returns:

The number of non-depot nodes in the solution.

Return type:

int

property routes

Returns an iterator over the routes in the solution.

Returns:

An iterator over the routes.

Return type:

Iterator

routingblocks.AnyForwardLabel
routingblocks.AnyBackwardLabel
routingblocks.VertexID
class routingblocks.Vertex(vertex_id: int, str_id: str, is_station: bool, is_depot: bool, data: Any)

A simple vertex object that represents a location vehicles can visit. Vertices can be stations, depots or customers. Each vertex has a unique id and a human-readable string identifier. The vertex also stores additional data transparent to the RoutingBlocks package. This data can be used to store additional information about the vertex, such as time windows, demand, prizes, or any other attribute that is relevant to the problem.

Parameters:

  • vertex_id (int) – The unique identifier of the vertex.

  • str_id (str) – A human-readable string identifier for the vertex.

  • is_station (bool) – Whether the vertex is a station.

  • is_depot (bool) – Whether the vertex is a depot.

  • data (Any) – Additional data associated with the vertex.

vertex_id
str_id
is_station
is_depot
property is_customer

Determines if the vertex is a customer.

Returns:

True if the vertex is a customer, False otherwise.

Return type:

bool

property data

Retrieves the vertex data.

Returns:

The data associated with the vertex.

Return type:

Any

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

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

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:
name()
Return type:

str

can_apply_to(_solution: routingblocks.Solution)
Parameters:

_solution (routingblocks.Solution) –

Return type:

bool

apply(evaluation: routingblocks.Evaluation, _solution: routingblocks.Solution, number_of_removed_vertices: int)
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • _solution (routingblocks.Solution) –

  • number_of_removed_vertices (int) –

Return type:

List[int]

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:
apply(evaluation: routingblocks.Evaluation, solution: routingblocks.Solution, vertex_ids: Iterable[int])
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • solution (routingblocks.Solution) –

  • vertex_ids (Iterable[int]) –

Return type:

None

name()
Return type:

str

can_apply_to(solution: routingblocks.Solution)
Parameters:

solution (routingblocks.Solution) –

Return type:

bool

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.

can_apply_to(_solution: routingblocks.Solution)
Parameters:

_solution (routingblocks.Solution) –

Return type:

bool

apply(evaluation: routingblocks.Evaluation, _solution: routingblocks.Solution, number_of_removed_vertices: int)
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • _solution (routingblocks.Solution) –

  • number_of_removed_vertices (int) –

Return type:

List[int]

name()
Return type:

str

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:
can_apply_to(_solution: routingblocks.Solution)
Parameters:

_solution (routingblocks.Solution) –

Return type:

bool

apply(evaluation: routingblocks.Evaluation, solution: routingblocks.Solution, number_of_removed_vertices: int)
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • solution (routingblocks.Solution) –

  • number_of_removed_vertices (int) –

Return type:

List[int]

name()
Return type:

str

class routingblocks.operators.DistanceBasedClusterMemberSelector(vertices: List[routingblocks.Vertex], get_distance: Callable[[routingblocks.Vertex, routingblocks.Vertex], float], min_radius_factor: float = 1.0, max_radius_factor: float = 1.0, randgen: routingblocks.Randgen | None = None)

Clusters vertices according to their distance to the seed vertex.

Parameters:

  • vertices (List[routingblocks.Vertex]) – The vertices in the instance

  • get_distance (Callable[[routingblocks.Vertex, routingblocks.Vertex], float]) – A distance function that takes two vertices and returns their distance to each other

  • min_radius_factor (float) – The minimum radius of the cluster as a factor of the maximum distance between any two vertices

  • max_radius_factor (float) – The maximum radius of the cluster as a factor of the maximum distance between any two vertices

  • randgen (Optional[routingblocks.Randgen]) – A random number generator

class DistanceListItem(vertex: routingblocks.Vertex, distance: float)
Parameters:
class routingblocks.operators.ClusterMemberSelector

Selects a cluster of vertices based on a seed vertex.

class routingblocks.operators.SeedSelector

Selects a seed vertex from a solution.

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

can_apply_to(solution: routingblocks.Solution)

Station vicinity removal can be applied to any solution that contains at least one station.

Parameters:

solution (routingblocks.Solution) –

Return type:

bool

name()
Return type:

str

apply(evaluation: routingblocks.Evaluation, solution: routingblocks.Solution, number_of_removed_vertices: int)
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • solution (routingblocks.Solution) –

  • number_of_removed_vertices (int) –

Return type:

List[int]

class routingblocks.operators.StationSeedSelector(stations: List[routingblocks.Vertex], randgen: routingblocks.Randgen | None = None)
Parameters:
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.

can_apply_to(_solution: routingblocks.Solution)
Parameters:

_solution (routingblocks.Solution) –

Return type:

bool

apply(evaluation: routingblocks.Evaluation, _solution: routingblocks.Solution, number_of_removed_vertices: int)
Parameters:

  • evaluation (routingblocks.Evaluation) –

  • _solution (routingblocks.Solution) –

  • number_of_removed_vertices (int) –

Return type:

List[int]

name()
Return type:

str

class routingblocks.operators.MoveSelector

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

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

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.

class routingblocks.operators.RandomInsertionOperator(random: Random)

Inserts vertices at random positions in the solution.

Parameters:

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

class routingblocks.utility.InstanceBuilder(create_vertex: vertex_factory | None = None, create_arc: arc_factory | None = None)

A class for building an instance of a vehicle routing problem. The builder provides methods to add vertices (depot, customers, and stations) and arcs with their associated data. Once all the necessary data has been added, the builder can create an instance of the problem.

Initializes a new InstanceBuilder object.

Parameters:

  • create_vertex (Optional[vertex_factory]) – A factory function for creating vertex objects. Defaults to the constructor of the Vertex class.

  • create_arc (Optional[arc_factory]) – A factory function for creating arc objects. Defaults to the constructor of the Arc class.

set_depot(str_id: str, vertex_data)

Sets the depot for the instance.

Parameters:

  • str_id (str) – The string identifier for the depot.

  • vertex_data – Additional data associated with the depot vertex.

add_customer(str_id: str, vertex_data)

Adds a customer to the instance.

Parameters:

  • str_id (str) – The string identifier for the customer.

  • vertex_data – Additional data associated with the customer vertex.

add_station(str_id: str, vertex_data)

Adds a station to the instance.

Parameters:

  • str_id (str) – The string identifier for the station.

  • vertex_data – Additional data associated with the station vertex.

add_arc(i: str, j: str, arc_data)

Adds an arc between two vertices.

Parameters:

  • i (str) – The string identifier for the source vertex.

  • j (str) – The string identifier for the target vertex.

  • arc_data – Additional data associated with the arc.

property number_of_vertices

Retrieves the number of vertices in the instance.

Returns:

The number of vertices.

Return type:

int

reset()

Resets the InstanceBuilder, clearing all stored data.

build()

Constructs an Instance object based on the vertices and arcs added to the InstanceBuilder. Uses vertex_factory and arc_factory to create the vertices and arcs.

Returns:

A new Instance object.

Return type:

Instance

Raises:

  • ValueError – If the InstanceBuilder does not have a depot or at least one customer.

  • ValueError – If not all arcs are defined between vertices.