A NEW ALGORITHM FOR SHORTEST PATHS IN DISCRETE DYNAMIC NETWORKS

In this paper we study two shortest paths problems in discrete dynamic networks: the one-to-all for one departure time interval, and the all-to-one for all departure time intervals. Early results are revisited. New properties of these problems are established and exploited in developing solution algorithms. A new and simple solution algorithm for the all-to-one fastest paths problem for all departure time intervals is proposed. It is proved, analytically, that the new solution algorithm has an optimal running time complexity that equals the complexity of the problem. Computer implementations and experimental evaluations of four solution algorithms support analytical results and demonstrate the efficiency of the proposed algorithm. We expect our findings to be of major benefit to research and development activities in the field of dynamic management of large-scale transportation systems.

Language

  • English

Media Info

  • Features: References; Tables;
  • Pagination: p. 537-542

Subject/Index Terms

Filing Info

  • Accession Number: 00767527
  • Record Type: Publication
  • ISBN: 0080429319
  • Report/Paper Numbers: Volume 2
  • Files: TRIS
  • Created Date: Aug 10 1999 12:00AM