This paper introduces a variable time discretization strategy for a time-dependent A* shortest path algorithm. The strategy is aimed at determining the optimal memory allocation for time-dependent travel times data in order to achieve a desirable compromise between accuracy and memory usage. The proposed strategy is based on the dispersion index of the travel times/costs over the entire analysis period, as a result, producing different intervals for each link. The links with travel times that have a higher variance and a lower mean will need to have a shorter time discretization length due to greater fluctuation in travel times. The proposed strategy is implemented in the time-dependent A* algorithm and tested with a numerical experiment on a Tucson, AZ, traffic network. The results show that with the same amount of computer memory usage, the proposed variable time discretization strategy achieves much higher accuracy than that of uniform time discretization.
Variable time discretization for a time-dependent shortest path algorithm
01.10.2011
709135 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
Taylor & Francis Verlag | 2014
|Reversibility of the time-dependent shortest path problem
Online Contents | 2002
|