Problem instance

Problem instance classes represent the problem to be solved. They model the underlying graph and store problem-specific data. The following classes are available:

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

__init__(self, depot: Vertex, stations: List[Vertex], customers: List[Vertex], arcs: List[List[Arc]], fleet_size: int) → None

Initialize an Instance with a depot, lists of stations and customers, a list of arcs, and a fleet size.

Parameters:

depot (Vertex) – The depot vertex
stations (List[Vertex]) – A list of station vertices
customers (List[Vertex]) – A list of customer vertices
arcs (List[List[Arc]]]) – A matrix of Arc objects representing the connections between vertices
fleet_size (int) – The number of vehicles in the fleet

__init__(self, vertices: List[Vertex], arcs: List[List[Arc]]) → None

Initialize an Instance with a list of vertices and a list of arcs. Sets the fleet size to the number of customers. Expects vertices to be in the order depot, stations, customers.

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

__init__(self, vertices: List[Vertex], arcs: List[List[Arc]], fleet_size: int) → None

Initialize an Instance with a list of vertices, a list of arcs, and a fleet size. Expects vertices to be in the order depot, stations, customers.

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]

__len__()

Retrieves the number of vertices in the instance.

Returns:: The number of vertices.
Return type:: int

__iter__()

Retrieves an iterator over the vertices in the instance.

Returns:: An iterator over the 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

The instance builder is a utility class that can be used to create instances. It takes care of ordering, ensures unique vertex IDs, and validates consistency. The following example illustrates it’s usage:

from routingblocks import InstanceBuilder, Vertex, Arc

class MyVertexData:
    pass

class MyArcData:
    pass

# Default factories use the constructors of Vertex and Arc. Use custom factories to create Vertex/Arc representations.
# optimized for specific problem settings (e.g., `create_adtpw_vertex` and `create_adtpw_arc` for ADTPW)
builder = InstanceBuilder()
builder.fleet_size = 3

builder.add_depot("D", MyVertexData())

builder.add_customer("C1", MyVertexData())
builder.add_customer("C2", MyVertexData())

builder.add_station("S1", MyVertexData())

for i, j in product(["D", "S1", "C1", "C2"], ["D", "S1", "C1", "C2"]):
    builder.add_arc(i, j, MyArcData())

instance = builder.build()

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.

vertex_factory(id: VertexID, str_id: str, is_depot: bool, is_station: bool, data: T) → Vertex

Function signature for a vertex_factory. Creates a new vertex using the given parameters.

Parameters:

id – Unique ID of the vertex
str_id – Name of the vertex
is_depot – Whether the vertex is a depot
is_station – Whether the vertex is a station
data – User-defined data to be stored in the vertex

Returns:

A new Vertex object

arc_factory(data: T) → Arc

Function signature for a arc_factory. Creates a new arc with the given data.

Parameters:: data – User-defined data to be stored in the arc
Returns:: A new Arc object