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. If distances 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 specifying X coordinates or X coordinates is not supported

  • locations_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 of demand 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 of demand 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 of demand is nonzero and distances 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.