Arc Interdiction Vehicle Routing Problem Using Quantum Annealing

The Vehicle Routing Problem (VRP) is a well-established NP-hard optimization problem that seeks to determine an efficient routing allocation for a fleet of vehicles over a graph, minimizing the total cost of traversal. Arc Interdiction adds another layer of complexity by introducing an adversary capable of disrupting some routes along the graph with the aim to increase the total cost. Given the complexity of VRP, solving large instances efficiently remains computationally intractable for classical algorithms. Quantum computers, with their ability to explore vast solution spaces in parallel, offer a promising avenue for accelerating optimization for such problems. This work formulates the bilevel optimization corresponding to Arc Interdiction VRP as a Quadratic Binary Unconstrained Optimization (QUBO), providing a novel approach to solving the problem using quantum hardware. Numerical experiments conducted using D-Wave’s Quantum Processing Units demonstrate the feasibility of the proposed formulation and provide insights into the performance of quantum annealing in handling interdiction scenarios.