Skip to content

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 (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:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the CVRP data.

Returns:

  • 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:

  • distance_matrix (ndarray) –

    Symmetric (n + 1) x (n + 1) matrix of node-to-node distances.

  • demands (list[float]) –

    Demand of each node, length n + 1 with demands[0] == 0.

  • n_vehicles (int) –

    Number of available vehicles.

  • vehicle_capacity (float) –

    Maximum total demand per vehicle.

  • node_names (list[int | str] | None, default: None ) –

    Identifiers for each node. Defaults to [0, 1, ..., n].

Returns:

  • CvrpData –

    The constructed data instance.

Raises:

  • 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:

  • coords (ndarray) –

    (n + 1) x 2 array of node coordinates; row 0 is the depot.

  • demands (list[float]) –

    Demand of each node, length n + 1 with demands[0] == 0.

  • n_vehicles (int) –

    Number of available vehicles.

  • vehicle_capacity (float) –

    Maximum total demand per vehicle.

Returns:

  • CvrpData –

    The constructed data instance with stored coordinates.

Raises:

  • 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:

  • n_customers (int, default: 4 ) –

    Number of customers (excluding the depot), by default 4.

  • n_vehicles (int, default: 2 ) –

    Number of available vehicles, by default 2.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

  • 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:

Returns:

  • str –

    String representation of the formulation.

formulate(data: CvrpData) -> Model staticmethod

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

Parameters:

  • data (CvrpData) –

    The problem instance containing distances, demands, capacity, and the number of vehicles.

Returns:

  • 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:

  • solution (Solution) –

    The solver solution containing variable assignments.

  • data (CvrpData) –

    The original problem data.

Returns:

  • CvrpSolution –

    Structured solution with routes, total distance, and validity.

Raises:

Solution

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

CvrpSolution

Bases: UcSolution

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

Attributes:

  • 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:

  • data (CvrpData | None, default: None ) –

    Problem data. Required so that node positions can be drawn.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Returns:

  • 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:

  • min_customers (int) –

    Minimum number of customers.

  • max_customers (int) –

    Maximum number of customers.

  • n_vehicles (int, default: 2 ) –

    Number of vehicles, by default 2.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

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:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • 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: