Reliable shortest paths, in this paper, are paths that ensure a desired probability of arriving on time or earlier with the least time budget. Finding reliable shortest paths requires the evaluation of path travel time distributions through numerical convolution, which is a computationally intensive procedure. This paper develops several convolution methods based on the discrete Fourier transform (DFT) and compares them with a direct convolution method implemented with adaptive discretization. Two shortcomings in the conventional DFT-based convolution are recognized, namely, the incompatibility with dynamic programming and the computational inefficiency associated with support points that have negligible probability mass. Remedies are proposed to overcome these shortcomings. However, numerical experiments suggest that, even with these improvements, the DFT-based convolution methods are still not as computationally competitive as the direct convolution method, contrary to the promise of the theoretical complexity analysis.


    Zugriff

    Download

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Application of Discrete Fourier Transform to Find Reliable Shortest Paths


    Weitere Titelangaben:

    Transportation Research Record


    Beteiligte:
    Wu, Xing (Autor:in) / Nie, Yu (Marco) (Autor:in)


    Erscheinungsdatum :

    2011-01-01




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Finding Reliable Shortest Paths in Dynamic Stochastic Networks

    Wu, Xing | Transportation Research Record | 2013




    Finding the k reliable shortest paths under travel time uncertainty

    Chen, Bi Yu / Li, Qingquan / Lam, William H.K. | Elsevier | 2016