The relative performance of time-dependent shortest paths algorithms: A network expansion perspective

Yu Nie*, Xiaqjian Nie, H. M. Zhang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper studies three types of algorithms for computing all-to-one time-dependent shortest paths for all departure times on a discrete time dynamic network: the CLASSIC algorithms (direct extensions of static shortest path algorithms), the decreasing order of time (DOT) algorithm and the STEN algorithm based on an explicit network expansion. All algorithms are analyzed under the same type of compact space-time expansion networks, and implemented in a flexible and extendable framework using object-oriented programming (OOP) concepts. Two types of randomly generated networks similar to those found in real transportation systems are used for evaluating the relative performance of the studied algorithms. Our numerical results show a discrepancy between DOT's theoretical and practical computational efficiency, and STEN's computational tractability in applications involving large-size networks and demanding strict acyclicity.

Original languageEnglish (US)
Title of host publicationProceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportation Engineering
EditorsK.C. Sinha, T.F. Fwa, R.L. Cheu, D.-H. Lee
Pages66-71
Number of pages6
StatePublished - Dec 1 2004
EventProceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportaion Engineering - Beijing, China
Duration: May 26 2004May 28 2004

Other

OtherProceedings of the Eighth International Conference on Applications of Advanced Technologies in Transportaion Engineering
CountryChina
CityBeijing
Period5/26/045/28/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'The relative performance of time-dependent shortest paths algorithms: A network expansion perspective'. Together they form a unique fingerprint.

Cite this