Application of discrete fourier transform to find reliable shortest paths

Xing Wu, Yu Nie*

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)82-91
Number of pages10
JournalTransportation Research Record
Issue number2263
DOIs
StatePublished - Dec 1 2011

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering

Fingerprint Dive into the research topics of 'Application of discrete fourier transform to find reliable shortest paths'. Together they form a unique fingerprint.

Cite this