Solution representation

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

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

Parameters:

evaluation (Evaluation) –
instance (Instance) –
vertex_ids (List[int]) –

Return type:

Route

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

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.

__init__(self, evaluation: Evaluation, instance: Instance, number_of_routes: int)

Creates a new Solution object with the specified number of empty routes.

Parameters:

evaluation (Evaluation) – The evaluation object for cost and feasibility calculations.
instance (Instance) – The Instance object representing the problem instance.
number_of_routes (int) – The number of empty routes the solution should contain.

__init__(self, evaluation: Evaluation, instance: Instance, routes: List[Route])

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

__delitem__(route_index: int)

Removes the route at the specified index.

Parameters:: route_index (int) – The index of the route to remove.
Return type:: None

__getitem__(route_index: int)

Retrieves the route at the specified index.

Parameters:: route_index (int) – The index of the route to retrieve.
Returns:: The route at the specified index.
Return type:: Route

__iter__()

Returns an iterator over the routes in the solution.

Returns:: An iterator over the routes.
Return type:: Iterator

__len__()

Returns the number of routes in the solution.

Returns:: The number of routes in the solution.
Return type:: int

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

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