Vehicle Routing#

This example demonstrates the use of a Leap hybrid solver on a nonlinear-model. It explains how to estimate the minimum time the solver requires for the model, check that solutions meet the model’s constraints, set initial states, and more. For a simpler example usage of the solver, start with the Traveling Salesperson example; for information on formulating problems as nonlinear models, see the dwave-optimization package.

The goal of the well-known 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.

Example Requirements#

The code in this example requires that your development environment have Ocean software and be configured to access SAPI, as described in the Initial Set Up section.

Solution Steps#

Section Workflow Steps: Formulation and Sampling describes the problem-solving workflow as consisting of two main steps: (1) Formulate the problem as an objective function in a supported model and (2) Solve your model with a D-Wave solver.

This example formulates this problem as a nonlinear model and uses the LeapHybridNLSampler to find good solutions.

Formulate the Problem#

First, define customer demand and locations. A standard format for signaling the location of the depot, used by libraries such as CVRPLIB, is to set the demand of the first location as zero.

>>> demand = [0, 34, 12, 65, 10, 43, 27, 55, 61, 22]
>>> sites = [(15, 38), (23, -19), (44, 62), (3, 12), (-56, -21), (-53, 2),
...          (33, 63), (14, -33), (42, 41), (13, -62)]

Here there are ten locations, with the depot being located at coordinates \((15, 38)\).

This example uses one of Ocean software’s model generators to instantiate a Model class for a CVRP. The Model class encodes all the information (objective function, constraints, constants, and decision variables) relevant to your models.

>>> from dwave.optimization.generators import capacitated_vehicle_routing
>>> model = capacitated_vehicle_routing(
...     demand=demand,
...     number_of_vehicles=2,
...     vehicle_capacity=200,
...     locations_x=[x for x,y in sites],
...     locations_y=[y for x,y in sites])

For detailed information on how the CVRP is modelled, see the documentation for the capacitated_vehicle_routing generator.

Solve the Problem by Sampling#

D-Wave’s quantum cloud service provides cloud-based hybrid solvers you can submit quadratic and nonlinear models to. These solvers, which implement state-of-the-art classical algorithms together with intelligent allocation of the quantum processing unit (QPU) to parts of the problem where it benefits most, are designed to accommodate even very large problems. Leap’s solvers can relieve you of the burden of any current and future development and optimization of hybrid algorithms that best solve your problem.

Ocean software’s dwave-system LeapHybridNLSampler class enables you to easily incorporate Leap’s hybrid nonlinear-model solvers into your application:

>>> from dwave.system import LeapHybridNLSampler
>>> sampler = LeapHybridNLSampler()                  

Check the minimum required solution time estimated for the model. You can choose to set your own time_limit, which can be higher or lower:

Higher than the estimated time: allows the solver time to possibly find better solutions.
Lower than the estimated time: tries finding solutions quickly. Leap’s hybrid solvers are not guaranteed to complete processing in under the estimated time limit, and you may be charged up to the estimated minimum required time.

>>> print(sampler.estimated_min_time_limit(model))      
5

Submit the model to the selected solver.

>>> results = sampler.sample(
...     model,
...     time_limit=10)          

You can check information such as timing in the returned results:

>>> print(results.result().timing['charge_time'])       
10000000

You can iterate through the returned samples. The code below shows up to three solutions, printing the value of the objective function, the itinerary for the fleet’s two vehicles, and whether the solution meets the model’s constraints on maximum capacity.

>>> num_samples = model.states.size()
>>> route, = model.iter_decisions()                     
>>> route1, route2 = route.iter_successors()            
>>> for i in range(min(3, num_samples)):
...     print(f"Objective value {int(model.objective.state(i))} for \n" \
...     f"\t Route 1: {route1.state(i)} \t Route 2: {route2.state(i)} \n" \
...     f"\t Feasible: {all(sym.state(i) for sym in model.iter_constraints())}")   
Objective value 484 for
         Route 1: [4. 3. 7. 1. 5.]       Route 2: [4. 3. 7. 1. 5.]
         Feasible: True
Objective value 423 for
         Route 1: [0. 6. 8. 3. 4.]       Route 2: [0. 6. 8. 3. 4.]
         Feasible: True
Objective value 423 for
         Route 1: [2. 7. 1. 5.]          Route 2: [2. 7. 1. 5.]
         Feasible: True

Providing an Initial State#

For some problems you might have estimates or guesses of solutions, and by providing to the solver, as part of your problem submission, such assignments of decision variables as an initial state of the model, you may accelerate the solution.

Leap’s hybrid nonlinear-model solver supports accepting an initial state as part of the submitted model.

As explained in the documentation for the dwave-optimization package, you can set states—assign values to decision variables—in your model. The code below sets state 0 to one of the routes found above and resubmits the model to the solver with a shorter runtime (the default runtime).

>>> model.states.resize(1)
>>> route.set_state(0, [route1.state(0), route2.state(0)])   
>>> results = sampler.sample(model)     

Saving Results#

You can save the states of a model to a file.

>>> import shutil
>>> with open("model_states", 'wb') as f:                    
...     shutil.copyfileobj(model.states.to_file(), f)