Solving the Dial-a-Ride Problem with Time Windows Using Quantum Annealing and Quantum-Guided Cluster Algorithms

The Dial-a-Ride Problem (DARP) is a variant of the NP-hard vehicle routing problem with significant practical relevance in modern transportation systems. In this work, we introduce a novel Quadratic Unconstrained Binary Optimization formulation of the DARP that explicitly incorporates routing and time window constraints without requiring continuous variables, thereby making it compatible with quantum optimization approaches. We employ quantum annealing on D-Wave hardware to solve the resulting instances. As the hardware alone cannot identify the ground states for instances with 196 qubits, we enhance the obtained solutions using the Quantum-Guided Cluster Algorithm, a post-processing heuristic that leverages two-point correlations between sampled states. Our numerical results demonstrate that the proposed hybrid quantum-classical framework yields close-to-optimal solutions quickly for instances of up to 14 requests.