CVRPTask

The Capacitated Vehicle Routing Problem (CVRP) asks for a minimum-cost set of routes from a depot that visits every customer exactly once, such that the total demand on each route does not exceed vehicle capacity.

CVRPTask is a single-instance container. For batch I/O, generation, and parallel solving, use CVRPWrapper.

Problem data

Field	Shape / type
depots	(2,) or (3,) — depot coordinates (index 0 in coords).
points	(V, 2) or (V, 3) — customer coordinates.
coords	(V+1, 2) — [depot; points], built automatically.
demands	(V,) — customer demands (depot demand is 0).
capacity	float — vehicle capacity.
norm_demands	(V,) — demands / capacity.
cvrp_open	bool — if True, routes need not return to depot (OVRP).
sol / ref_sol	1D tour with 0 as depot separators, e.g. [0,3,5,0,2,1,0].

Solution encoding

Tours are stored as a single 1D array. Depot node index is 0; customer indices are 1 … V. Multiple routes are concatenated with 0 delimiters:

[0,  customer_a, customer_b, 0,  customer_c, 0]
     └── route 1 ──────────┘    └ route 2 ┘

Constraints checked by CVRPTask.check_constraints():

• Tour starts and ends at depot 0.

• Every customer 1…V appears exactly once.

• Per-route total demand ≤ capacity (with threshold tolerance).

Example 1 — Load from pickle

import pathlib
from ml4co_kit import CVRPTask

task = CVRPTask()
task.from_pickle(pathlib.Path(
    "test_dataset/routing/vrp/cvrp/task/cvrp50_uniform_task.pkl"
))

print(repr(task))
# CVRPTask(2fb389cdafdb4e79a94572f01edf0b95)
print(task.nodes_num, task.capacity)
# 50 40.0

cost = task.evaluate(task.ref_sol)
print(cost)
# 10.973381996154785

Example 2 — Build from raw arrays

import numpy as np
from ml4co_kit import CVRPTask

task = CVRPTask()
task.from_data(
    depots=np.array([0.0, 0.0], dtype=np.float32),
    points=np.array(
        [[1.0, 0.0], [0.0, 1.0], [1.0, 1.0]], dtype=np.float32
    ),
    demands=np.array([1.0, 1.0, 1.0], dtype=np.float32),
    capacity=2.0,
)
print(task.nodes_num)       # 3
print(task.norm_demands)    # [0.5 0.5 0.5]

# Two routes: {1,2} and {3}, capacity 2 each
sol = np.array([0, 1, 2, 0, 3, 0])
print(task.check_constraints(sol))  # True
print(task.evaluate(sol))           # 6.242641

# Single route with demand 3 > capacity 2
bad = np.array([0, 1, 2, 3, 0])
print(task.check_constraints(bad))  # False

Example 3 — VRPLIB I/O

import pathlib
from ml4co_kit import CVRPTask

task = CVRPTask()
task.from_vrplib(
    vrp_file_path=pathlib.Path(
        "test_dataset/routing/vrp/cvrp/vrplib/problem_1/X-n101-k25.vrp"
    ),
    sol_file_path=pathlib.Path(
        "test_dataset/routing/vrp/cvrp/vrplib/solution_1/X-n101-k25.sol"
    ),
    ref=True,
)
cost = task.evaluate(task.ref_sol)
print(cost)

Example 4 — Visualization

import pathlib
from ml4co_kit import CVRPTask

task = CVRPTask()
task.from_pickle(pathlib.Path(
    "test_dataset/routing/vrp/cvrp/task/cvrp50_uniform_task.pkl"
))
task.sol = task.ref_sol
task.render(
    save_path=pathlib.Path("docs/assets/cvrp_solution.png"),
    with_sol=True,
    figsize=(10, 10),
)

See also How to use ML4CO-Kit Case-03 for a full visualization walkthrough.

API reference

class ml4co_kit.task.routing.vrp.cvrp.CVRPTask(cvrp_open: bool = False, mixed_backhaul: bool = False, distance_type: ~ml4co_kit.task.routing.base.DISTANCE_TYPE = DISTANCE_TYPE.EUC_2D, round_type: ~ml4co_kit.task.routing.base.ROUND_TYPE = ROUND_TYPE.NO, precision: ~numpy.float32 | ~numpy.float64 = <class 'numpy.float32'>, threshold: float = 0.0001)

Bases: RoutingTaskBase

Single-instance CVRP task.

Parameters

cvrp_openbool, optional

If True, routes are open (OVRP): no return leg to the depot.

mixed_backhaulbool, optional

Reserved for backhaul variants (unused in plain CVRP).

distance_typeDISTANCE_TYPE, optional

Edge metric. Default EUC_2D.

round_typeROUND_TYPE, optional

Distance rounding rule. Default NO.

precisionnp.float32 or np.float64, optional

Coordinate / cost dtype.

thresholdfloat, optional

Numerical tolerance for constraint checking.

Notes

Solution format: 1D array with depot index 0 as route separators, e.g. [0, 3, 5, 0, 2, 1, 0] for two routes.

Examples

>>> import pathlib
>>> from ml4co_kit import CVRPTask
>>> task = CVRPTask()
>>> task.from_pickle(
...     pathlib.Path("test_dataset/routing/vrp/cvrp/task/cvrp50_uniform_task.pkl")
... )
>>> float(task.evaluate(task.ref_sol))
10.973...

check_constraints(sol: ndarray) → bool

Return True if sol is a feasible CVRP tour.

evaluate(sol: ndarray, check_constr: bool = True) → floating

Return total route length of sol.

Parameters

solnp.ndarray

Tour with depot index 0 as route separators.

check_constrbool, optional

Raise ValueError if constraints are violated.

Returns

np.floating

Sum of edge lengths (respects cvrp_open).

evaluate_w_gap(check_constr: bool = True) → Sequence[floating]

Compare sol and ref_sol and return the optimality gap (%).

Parameters

check_constrbool, optional

If True, validate solutions before evaluation.

Returns

tuple of (sol_cost, ref_cost, gap)

gap is None when ref_cost is near zero. For minimization, gap = (sol_cost - ref_cost) / ref_cost * 100.

from_data(depots: ndarray = None, points: ndarray = None, demands: ndarray = None, capacity: float = None, sol: ndarray = None, ref: bool = False, normalize: bool = False, name: str = None)

Populate the task from numpy arrays.

Parameters

depotsnp.ndarray, optional

Depot coordinates, shape (2,) or (3,).

pointsnp.ndarray, optional

Customer coordinates, shape (V, 2) or (V, 3).

demandsnp.ndarray, optional

Customer demands, shape (V,).

capacityfloat, optional

Vehicle capacity.

solnp.ndarray, optional

Tour encoding with 0 depot delimiters.

refbool, optional

If True, store sol in ref_sol instead of sol.

normalizebool, optional

Scale coordinates to [0, 1] (EUC_2D only).

namestr, optional

Instance name override.

from_pickle(file_path: Path)

Restore a task from a pickle file.

Parameters

file_pathpathlib.Path

Path to a .pkl file produced by to_pickle() or the toolkit.

from_vrplib(vrp_file_path: Path = None, sol_file_path: Path = None, ref: bool = False, normalize: bool = False)

Load CVRP data from a VRPLIB file.

get_data_md5() → str

Calculate MD5 hash of the task’s data content.

This method computes the MD5 hash based on the actual data content rather than the file content, which is useful for verifying data integrity when pickle files may have different object references.

Returns:

str: MD5 hash of the task’s data content

render(save_path: Path, with_sol: bool = True, figsize: tuple = (5, 5), node_color: str = 'darkblue', edge_color: str = 'darkblue', node_size: int = 50)

Save a matplotlib figure of the instance (and optional solution).

Parameters

save_pathpathlib.Path

Output image path (.png, etc.).

with_solbool, optional

Draw self.sol routes when True; instance only when False.

figsizetuple, optional

Figure size in inches.

node_color, edge_colorstr, optional

Plot colors (used when applicable).

node_sizeint, optional

Scatter marker size for customers.

to_pickle(file_path: Path)

Serialize this task to a pickle file.

Parameters

file_pathpathlib.Path

Output .pkl path (parent directories are created if needed).

to_vrplib(vrp_file_path: Path = None, sol_file_path: Path = None)

Save CVRP data to a VRPLIB file.