  Quantum annealing (QA) is a quantum computing algorithm that works on the
principle of Adiabatic Quantum Computation (AQC), and it has shown significant
computational advantages in solving combinatorial optimization problems such as
vehicle routing problems (VRP) when compared to classical algorithms. This
paper presents a QA approach for solving a variant VRP known as multi-depot
capacitated vehicle routing problem (MDCVRP). This is an NP-hard optimization
problem with real-world applications in the fields of transportation,
logistics, and supply chain management. We consider heterogeneous depots and
vehicles with different capacities. Given a set of heterogeneous depots, the
number of vehicles in each depot, heterogeneous depot/vehicle capacities, and a
set of spatially distributed customer locations, the MDCVRP attempts to
identify routes of various vehicles satisfying the capacity constraints such as
that all the customers are served. We model MDCVRP as a quadratic unconstrained
binary optimization (QUBO) problem, which minimizes the overall distance
traveled by all the vehicles across all depots given the capacity constraints.
Furthermore, we formulate a QUBO model for dynamic version of MDCVRP known as
D-MDCVRP, which involves dynamic rerouting of vehicles to real-time customer
requests. We discuss the problem complexity and a solution approach to solving
MDCVRP and D-MDCVRP on quantum annealing hardware from D-Wave.
