Capacitated Vehicle Routing (CVRP) API Reference

Data

Data model for Capacitated Vehicle Routing (CVRP) use case.

`CvrpData`

Bases: UcData

Data for the Capacitated Vehicle Routing Problem (CVRP) use case.

The CVRP asks for a set of vehicle routes, each starting and ending at a single depot (node 0), that together visit every customer exactly once while never exceeding the per-vehicle capacity. The objective is to minimise the total travelled distance.

Attributes:

Name	Type	Description
`name`	`Literal['vehicle_routing_problem']`	Constant identifier for this data type.
`distance_matrix`	`SymMatrix`	Symmetric `(n + 1) x (n + 1)` matrix of distances between all nodes, where node `0` is the depot and nodes `1, ..., n` are customers. `distance_matrix[i, j]` is the distance from node `i` to node `j`.
`demands`	`NumPyArray`	1D array of length `n + 1` with the demand of each node. The depot demand `demands[0]` is always `0`.
`n_vehicles`	`int`	Number of available vehicles (routes leaving the depot).
`vehicle_capacity`	`float`	Maximum total demand a single vehicle can carry.
`node_names`	`list[int \| str]`	Identifiers for each node; `node_names[0]` is the depot. The order matches the rows/columns of `distance_matrix`.
`coordinates`	`(NumPyArray \| None, optional)`	Optional `(n + 1) x 2` array of 2D coordinates used for plotting and for computing Euclidean distances. `None` if no coordinates are available.

Examples:

Create a depot with two customers from a distance matrix:

>>> data = CvrpData.from_distance_matrix(
...     distance_matrix=np.array(
...         [[0, 2, 3], [2, 0, 4], [3, 4, 0]],
...     ),
...     demands=[0.0, 1.0, 1.0],
...     n_vehicles=1,
...     vehicle_capacity=2.0,
... )

`plot(*, ax: Axes | None = None) -> Axes`

Plot the CVRP node layout.

The depot is highlighted in a distinct colour. When coordinates are available the nodes are placed at their given positions; otherwise a spring layout is computed automatically.

Parameters:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

`to_string() -> str`

Return a string describing the CVRP data.

Returns:

Type	Description
`str`	String representation of the data.

`from_distance_matrix(distance_matrix: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float, node_names: list[int | str] | None = None) -> CvrpData` `staticmethod`

Create CvrpData from a distance matrix.

Parameters:

Name	Type	Description	Default
`distance_matrix`	`ndarray`	Symmetric `(n + 1) x (n + 1)` matrix of node-to-node distances.	required
`demands`	`list[float]`	Demand of each node, length `n + 1` with `demands[0] == 0`.	required
`n_vehicles`	`int`	Number of available vehicles.	required
`vehicle_capacity`	`float`	Maximum total demand per vehicle.	required
`node_names`	`list[int \| str] \| None`	Identifiers for each node. Defaults to `[0, 1, ..., n]`.	`None`

Returns:

Type	Description
`CvrpData`	The constructed data instance.

Raises:

Type	Description
`ValueError`	If the shapes of `demands`/`node_names` do not match the matrix, or if the depot demand is non-zero.

`from_coordinates(coords: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float) -> CvrpData` `staticmethod`

Create CvrpData from 2D coordinates using Euclidean distances.

Parameters:

Name	Type	Description	Default
`coords`	`ndarray`	`(n + 1) x 2` array of node coordinates; row `0` is the depot.	required
`demands`	`list[float]`	Demand of each node, length `n + 1` with `demands[0] == 0`.	required
`n_vehicles`	`int`	Number of available vehicles.	required
`vehicle_capacity`	`float`	Maximum total demand per vehicle.	required

Returns:

Type	Description
`CvrpData`	The constructed data instance with stored coordinates.

Raises:

Type	Description
`ValueError`	If `demands` length does not match the number of coordinates or if the depot demand is non-zero.

`generate_random(n_customers: int = 4, n_vehicles: int = 2, seed: int | None = None) -> CvrpData` `staticmethod`

Generate a random CVRP instance on the unit square.

Customer coordinates are sampled uniformly, demands are small random integers, and the vehicle capacity is set so that the fleet can serve the total demand.

Parameters:

Name	Type	Description	Default
`n_customers`	`int`	Number of customers (excluding the depot), by default `4`.	`4`
`n_vehicles`	`int`	Number of available vehicles, by default `2`.	`2`
`seed`	`int \| None`	Random seed for reproducibility, by default `None`.	`None`

Returns:

Type	Description
`CvrpData`	A randomly generated data instance.

Examples:

>>> data = CvrpData.generate_random(n_customers=4, seed=42)

Formulation

Formulation for Capacitated Vehicle Routing (CVRP) use case.

`CvrpFormulation`

Bases: UcFormulation[CvrpData, CvrpSolution]

Constraint-based MTZ formulation for the Capacitated Vehicle Routing Problem.

Mathematical Formulation

Given:
    - n: number of customers, indexed ``1, ..., n`` (node ``0`` is the depot)
    - Q: vehicle capacity
    - K: number of vehicles
    - d[i, j]: distance from node i to node j
    - demand_i: demand of customer i (demand_0 = 0)

Decision Variables:
    - x[i, j] in {0, 1} for all i != j over nodes 0, ..., n:
        1 if a vehicle travels directly from node i to node j.
    - u[i] integer for customers i = 1, ..., n with
        demand_i <= u[i] <= Q:
        cumulative load on the vehicle just after visiting customer i
        (Miller-Tucker-Zemlin load/order variable).

Objective:
    minimize sum_{i != j} d[i, j] * x[i, j]

Constraints:
    1. Customer in-degree: for each customer i >= 1:
           sum_{j != i} x[j, i] == 1
    2. Customer out-degree: for each customer i >= 1:
           sum_{j != i} x[i, j] == 1
    3. Depot out-degree: sum_{j >= 1} x[0, j] == K
    4. Depot in-degree:  sum_{j >= 1} x[j, 0] == K
    5. MTZ capacity/subtour elimination: for customers i != j (i, j >= 1):
           u[i] - u[j] + Q * x[i, j] <= Q - demand_j

References

Wikipedia: https://en.wikipedia.org/wiki/Vehicle_routing_problem

`to_string(data: CvrpData) -> str` `staticmethod`

Return a string describing the formulation.

Parameters:

Name	Type	Description	Default
`data`	`CvrpData`	The problem data.	required

Returns:

Type	Description
`str`	String representation of the formulation.

`formulate(data: CvrpData) -> Model` `staticmethod`

Formulate the CVRP as a mixed-integer program using the MTZ model.

Parameters:

Name	Type	Description	Default
`data`	`CvrpData`	The problem instance containing distances, demands, capacity, and the number of vehicles.	required

Returns:

Type	Description
`Model`	A Luna Model ready to be solved.

`interpret(solution: Solution, data: CvrpData) -> CvrpSolution` `staticmethod`

Interpret the solver result into a structured CVRP solution.

Routes are reconstructed by following the active arcs x[i, j] == 1 out of the depot until the depot is reached again.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution containing variable assignments.	required
`data`	`CvrpData`	The original problem data.	required

Returns:

Type	Description
`CvrpSolution`	Structured solution with routes, total distance, and validity.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find any solution.

Solution

Solution model for Capacitated Vehicle Routing (CVRP) use case.

`CvrpSolution`

Bases: UcSolution

Solution for the Capacitated Vehicle Routing (CVRP) use case.

Attributes:

Name	Type	Description
`name`	`Literal['vehicle_routing_problem']`	Constant identifier for this solution type.
`routes`	`list[list[int \| str]]`	One list of node names per vehicle route. Each route starts and ends at the depot node name.
`total_distance`	`float`	Total distance travelled across all routes.
`is_valid`	`bool`	`True` when every customer is visited exactly once and no route exceeds the vehicle capacity.

`plot(data: CvrpData | None = None, *, ax: Axes | None = None) -> Axes`

Plot the CVRP solution routes.

Each route is drawn in a distinct colour as directed (arrowed) edges. When data carries coordinates the nodes are placed at their given positions; otherwise a spring layout is computed automatically.

Parameters:

Name	Type	Description	Default
`data`	`CvrpData \| None`	Problem data. Required so that node positions can be drawn.	`None`
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

Raises:

Type	Description
`ValueError`	If data is `None`.

`to_string() -> str`

Return a string describing the solution.

Returns:

Type	Description
`str`	String representation of the solution.

Instance

Instance model for Capacitated Vehicle Routing (CVRP) use case.

`CvrpInstance`

Bases: UcInstance[CvrpData, CvrpFormulation, CvrpSolution]

Instance combining data and formulation for Capacitated Vehicle Routing.

Collection

Collection of Capacitated Vehicle Routing (CVRP) instances.

`CvrpCollection`

Bases: UcInstanceCollection[CvrpInstance]

Collection of Capacitated Vehicle Routing instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

`from_random(min_customers: int, max_customers: int, n_vehicles: int = 2, num_instances: int = 1, *, seed: int | None = None) -> CvrpCollection` `classmethod`

Generate random CVRP instances.

Parameters:

Name	Type	Description	Default
`min_customers`	`int`	Minimum number of customers.	required
`max_customers`	`int`	Maximum number of customers.	required
`n_vehicles`	`int`	Number of vehicles, by default 2.	`2`
`num_instances`	`int`	Number of instances per size, by default 1.	`1`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`CvrpCollection`	Collection containing generated instances.

Examples:

>>> collection = CvrpCollection.from_random(
...     min_customers=3,
...     max_customers=4,
...     num_instances=2,
...     seed=42,
... )

`filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]`

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

Name	Type	Description	Default
`max_runtime`	`float`	SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.	`3600`
`quiet`	`bool`	Suppress the SCIP solver output.	`True`

Returns:

Type	Description
`list[bool]`	Feasibility mask over the instances as they were before filtering, in that order: `True` where the instance was kept, `False` where it was removed.

Raises:

Type	Description
`ValueError`	If `max_runtime` is not positive.

Capacitated Vehicle Routing (CVRP) API Reference

Data

CvrpData

plot(*, ax: Axes | None = None) -> Axes

to_string() -> str

from_distance_matrix(distance_matrix: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float, node_names: list[int | str] | None = None) -> CvrpData staticmethod

from_coordinates(coords: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float) -> CvrpData staticmethod

generate_random(n_customers: int = 4, n_vehicles: int = 2, seed: int | None = None) -> CvrpData staticmethod

Formulation

CvrpFormulation

to_string(data: CvrpData) -> str staticmethod

formulate(data: CvrpData) -> Model staticmethod

interpret(solution: Solution, data: CvrpData) -> CvrpSolution staticmethod

Solution

CvrpSolution

plot(data: CvrpData | None = None, *, ax: Axes | None = None) -> Axes

to_string() -> str

Instance

CvrpInstance

Collection

CvrpCollection

from_random(min_customers: int, max_customers: int, n_vehicles: int = 2, num_instances: int = 1, *, seed: int | None = None) -> CvrpCollection classmethod

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

`CvrpData`

`plot(*, ax: Axes | None = None) -> Axes`

`to_string() -> str`

`from_distance_matrix(distance_matrix: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float, node_names: list[int | str] | None = None) -> CvrpData` `staticmethod`

`from_coordinates(coords: np.ndarray, demands: list[float], n_vehicles: int, vehicle_capacity: float) -> CvrpData` `staticmethod`

`generate_random(n_customers: int = 4, n_vehicles: int = 2, seed: int | None = None) -> CvrpData` `staticmethod`

`CvrpFormulation`

`to_string(data: CvrpData) -> str` `staticmethod`

`formulate(data: CvrpData) -> Model` `staticmethod`

`interpret(solution: Solution, data: CvrpData) -> CvrpSolution` `staticmethod`

`CvrpSolution`

`plot(data: CvrpData | None = None, *, ax: Axes | None = None) -> Axes`

`to_string() -> str`

`CvrpInstance`

`CvrpCollection`

`from_random(min_customers: int, max_customers: int, n_vehicles: int = 2, num_instances: int = 1, *, seed: int | None = None) -> CvrpCollection` `classmethod`

`filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]`