Quantum computing to solve scenario-based stochastic time-dependent shortest path routing
Vinayak Dixit, Chence Niu, David Rey, S. Travis Waller, Michael W. Levin
Abstract
Networks are inherently uncertain and require scenario-based approaches to handle variability. In stochastic and time-dependent networks, optimal solutions cannot always be found using deterministic algorithms. Furthermore, Stochastic Time Dependent Shortest Path problems are known to be NP-hard. Emerging Quantum Computing Methods are providing new ways to address these problems. In this paper, the STDSP problem is formulated as a Quadratic Constrained Binary Optimization Problem. We show that in the case of independent link costs, the size of the problem increases exponentially. Finally, we find that using the quantum solver provides a linear computational experience with respect to the size of the problem. The proposed solution has implications for stochastic networks across different contexts including communications, traffic, industrial operations, electricity, water, broader supply chains, and epidemiology.