ml4co_kit.task.routing.vrp.cvrp

Capacitated Vehicle Routing Problem (CVRP).

Find minimum-cost vehicle routes from a depot that serve all customers exactly once subject to vehicle capacity. CVRPTask holds one instance; use CVRPWrapper for batch operations.

Classes

CVRPTask(cvrp_open, mixed_backhaul, ...)

Single-instance CVRP task.

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

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_vrplib(vrp_file_path: Path = None, sol_file_path: Path = None, ref: bool = False, normalize: bool = False)

Load CVRP data from a VRPLIB file.

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_vrplib(vrp_file_path: Path = None, sol_file_path: Path = None)

Save CVRP data to a VRPLIB file.