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: Journal of the Transportation Research Board


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


    Erscheinungsdatum :

    01.01.2011




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Finding Reliable Shortest Paths in Dynamic Stochastic Networks

    Wu, Xing | Transportation Research Record | 2013




    On Universal Shortest Paths

    Turner, L. / Hamacher, H.W. / Gesellschaft fur Operations Research | British Library Conference Proceedings | 2011