A computationally efficient methodology to characterize travel time reliability using the fast Fourier transform

In this paper we present a novel methodology to assess travel time reliability in a transportation network, when the source of uncertainty is given by random road capacities. Specifically, we present a method based on the theory of Fourier transforms to numerically approximate the probability density function of the system-wide travel time. Except for noted pathological cases, any common continuous or discrete probability distribution can be used to model capacity uncertainty. Theoretical bounds on the approximation errors are formally derived, both for general distributions as well as for the specific instance of normally distributed capacities. These bounds provide valuable insights into the structure of the approximation errors and suggest ways to reduce them. From a practical point of view, we propose a procedure based on successively refining the computational grid in order to guarantee accurate approximations. The proposed methodology takes advantage of the established computational efficiency of the fast Fourier transform. In a numerical case study, we demonstrate that the results of the methodology are consistent with intuition. (C) 2010 Elsevier Ltd. All rights reserved.