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.
Quantum computing to solve scenario-based stochastic time-dependent shortest path routing
V. V. DIXIT ET AL.
TRANSPORTATION LETTERS
Transportation Letters ; 16 , 8 ; 793-803
2024-09-13
11 pages
Article (Journal)
Electronic Resource
English
Reliable Shortest Path Problems in Stochastic Time-Dependent Networks
Online Contents | 2014
|Reliable Shortest Path Problems in Stochastic Time-Dependent Networks
Taylor & Francis Verlag | 2014
|How Shortest-Path Algorithms Solve Traffic Dynamics Problems
British Library Conference Proceedings | 2005
|Finding the Shortest Path in Stochastic Vehicle Routing: A Cardinality Minimization Approach
Online Contents | 2016
|