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.


    Access

    Download

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Application of Discrete Fourier Transform to Find Reliable Shortest Paths


    Additional title:

    Transportation Research Record: Journal of the Transportation Research Board


    Contributors:
    Wu, Xing (author) / Nie, Yu (Marco) (author)


    Publication date :

    2011-01-01




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    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