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.


    Access

    Download


    Export, share and cite



    Title :

    Quantum computing to solve scenario-based stochastic time-dependent shortest path routing


    Additional title:

    V. V. DIXIT ET AL.
    TRANSPORTATION LETTERS


    Contributors:

    Published in:

    Transportation Letters ; 16 , 8 ; 793-803


    Publication date :

    2024-09-13


    Size :

    11 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English






    Reliable Shortest Path Problems in Stochastic Time-Dependent Networks

    Chen, Bi Yu / Lam, William H. K. / Sumalee, Agachai et al. | Taylor & Francis Verlag | 2014


    How Shortest-Path Algorithms Solve Traffic Dynamics Problems

    National Research Council (U.S.) | British Library Conference Proceedings | 2005