A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem

Abstract

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.

References in corpus (9)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing of the Traveling Salesman Problem
• Adiabatic Quantum Simulation of Quantum Chemistry
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Application of Quantum Annealing to Nurse Scheduling Problem
• Quantum Annealing Implementation of Job-Shop Scheduling
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Consistency of the Adiabatic Theorem

Cited by in corpus (1)

• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem