ADAPTATIONS OF THE A* ALGORITHM FOR DYNAMIC SHORTEST PATH PROBLEMS

In this paper the authors present adaptations of the A* algorithm for computing shortest paths between an origin node and a destination node in dynamic networks for one or multiple departure times. They give some properties of dynamic networks on which the dynamic adaptations of the A* algorithm are based. They develop efficient lower bounds on minimum travel times that exploit these properties. These lower bounds are then exploited to design efficient adaptations of the A* algorithm to solve instances of the one-to-one dynamic shortest path problem. The adapted algorithms are implemented and their computational performance is experimentally evaluated and tested. Using randomly generated networks, the authors show that the computer implementations of these adaptations can lead to a saving ratio of 11, in terms of number of nodes selected, and a saving ratio of 5 in terms of computation times for a network with 3000 nodes 10000 links and 100 time intervals. It is also shown that the savings increase with the network size

• Supplemental Notes:
  • Publication Date: 2000 ITS America, Washington DC
• Corporate Authors:

  ITS America

  1100 17th Street, NW, 12th Floor
  Washington, DC  United States  20036
• Authors:
  • Chabini, Ismail
  • Lan, Shan
• Conference:
  • ITS America 10th Annual Meeting and Exposition: Revolutionary Thinking, Real Results
  • Location: Washington DC, United States
  • Date: 2000-5-1 to 2000-5-4
• Publication Date: 2000

Language

• English

Media Info

• Pagination: 28 p.

Subject/Index Terms

• TRT Terms: Computer algorithms; Routing; Travel time

Filing Info

• Accession Number: 00793459
• Record Type: Publication
• Source Agency: UC Berkeley Transportation Library
• Files: PATH
• Created Date: Jun 13 2000 12:00AM