dwave.optimization.generators.capacitated_vehicle_routing#
- capacitated_vehicle_routing(demand: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes], number_of_vehicles: int, vehicle_capacity: float, distances: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, locations_x: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, locations_y: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None, depot_x_y: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes] | None = None) Model [source]#
Generate a model encoding a capacitated vehicle routing problem.
The capacitated vehicle routing problem, CVRP, is to find the shortest possible routes for a fleet of vehicles delivering to multiple customer locations from a central depot. Vehicles have a specified delivery capacity, and on the routes to locations and then back to the depot, no vehicle is allowed to exceed its carrying capacity.
- Parameters:
demand – Customer demand, as an array-like. If
distances
is specified, the first element must be zero. Ifdistances
is not specified and the first element is zero,[locations_x[0], locations_y[0]]
must be the location of the depot. Elements other than the first must be positive numbers.number_of_vehicles – Number of available vehicles, as an integer.
vehicle_capacity – Maximum capacity for any vehicle. The total delivered demand by any vehicle on any route must not exceed this value.
distances – Distances between all the problem’s locations, as an array-like of positive numbers, including both customer sites and the depot. When specified, the first element of
demand
must be zero and specifyingX coordinates
orX coordinates
is not supportedlocations_x – X coordinates, as an array-like, of locations for customers, and optionally the depot. When specified, 2D Euclidean distances are calculated and specifying
distances
is not supported. If the first element represents the X coordinate of the depot, the first element ofdemand
must be zero.locations_y – Y coordinates, as an array-like, of locations for customers, and optionally the depot. When specified, 2D Euclidean distances are calculated and specifying
distances
is not supported. If the first element represents the Y coordinate of the depot, the first element ofdemand
must be zero.depot_x_y – Location of the depot, as an array-like of exactly two elements,
[X, Y]
. Required if the first element ofdemand
is nonzero anddistances
is not specified; not allowed otherwise.
- Returns:
A model encoding the CVRP problem.
Notes
The model uses a
disjoint_lists
class as the decision variable being optimized, with permutations of its sublist representing various itineraries for each vehicle.