.. _example_nl_cvrp:
===============
Vehicle Routing
===============
This example demonstrates the use of a `Leap `_
hybrid solver on a :ref:`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 :ref:`example_nl_tsp` example; for information
on formulating problems as nonlinear models, see the
:ref:`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
====================
.. include:: hybrid_solver_service.rst
:start-after: example-requirements-start-marker
:end-before: example-requirements-end-marker
Solution Steps
==============
.. include:: hybrid_solver_service.rst
:start-after: example-steps-start-marker
:end-before: example-steps-end-marker
This example formulates this problem as a :ref:`nonlinear model `
and uses the :class:`~dwave.system.samplers.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
:math:`(15, 38)`.
This example uses one of Ocean software's model generators to instantiate a
:class:`~dwave.optimization.model.Model` class for a CVRP.
The :class:`~dwave.optimization.model.Model` class encodes all the information
(:term:`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
:class:`~dwave.optimization.generators.capacitated_vehicle_routing`
generator.
Solve the Problem by Sampling
=============================
D-Wave's quantum cloud service provides cloud-based
:std:doc:`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 :doc:`dwave-system `
:class:`~dwave.system.samplers.LeapHybridNLSampler` class enables you to
easily incorporate Leap's hybrid nonlinear-model solvers into your application:
>>> from dwave.system import LeapHybridNLSampler
>>> sampler = LeapHybridNLSampler() # doctest: +SKIP
Check the minimum required solution time estimated for the model. You can choose
to set your own :ref:`time_limit `, which
can be higher or lower:
Check the minimum required solution time estimated for the model. You can choose
to set your own :ref:`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)) # doctest: +SKIP
5
Submit the model to the selected solver.
>>> results = sampler.sample(
... model,
... time_limit=10) # doctest: +SKIP
You can check information such as timing in the returned results:
>>> print(results.result().timing['charge_time']) # doctest: +SKIP
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() # doctest: +SKIP
>>> route1, route2 = route.iter_successors() # doctest: +SKIP
>>> 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(model.iter_constraints())}") # doctest: +SKIP
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
:ref:`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)]) # doctest: +SKIP
>>> results = sampler.sample(model) # doctest: +SKIP
Saving Results
--------------
You can save the states of a model to a file.
>>> import shutil
>>> with open("model_states", 'wb') as f: # doctest: +SKIP
... shutil.copyfileobj(model.states.to_file(), f)