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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

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


    Weitere Titelangaben:

    V. V. DIXIT ET AL.
    TRANSPORTATION LETTERS


    Beteiligte:
    Dixit, Vinayak V. (Autor:in) / Niu, Chence (Autor:in) / Rey, David (Autor:in) / Waller, S. Travis (Autor:in) / Levin, Michael W. (Autor:in)

    Erschienen in:

    Transportation Letters ; 16 , 8 ; 793-803


    Erscheinungsdatum :

    13.09.2024


    Format / Umfang :

    11 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch






    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