Quantum Computing to Solve Scenario-Based Stochastic Time-Dependent Shortest Path Routing

Uncertainty is a fundamental property of networks which evolve continually due to varying demand and capacity. The characterization of the stochasticity with scenario-based approaches has emerged as a promising method to systematically incorporate variability. Under this paradigm, each scenario corresponds to a realization of the network state. Whilst efficient procedures exist to find optimal routes in deterministic and/or time-invariant environments, the same algorithms cannot always provide optimal solutions in stochastic and time-dependent networks. Furthermore, Stochastic Time Dependent Shortest Path (STDSP) problems are known NP-hard problems. Emerging Quantum Computing Methods are providing new ways to address these problems. The emergence of quantum annealing methods to solve Quadratic Unconstrained Binary Optimization (QUBO) problems has shown significant promise to provide computational speedup. The research provides a novel QUBO formulation for the STDSP problem, we also extend the formulation to the case of independent random link cost. 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 provide 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