DECENTRALIZED ALGORITHMS FOR THE MANAGEMENT AND CONTROL OF TRANSPORTATION SYSTEMS

When a person asks for travel directions to go from point O to point D, the advice he often gets is "from O get on the highway H and travel 'til you reach exit E2; get off the highway and travel along streets S3, S4, etc. 'til you reach D". This advice usually results in a path with a small number of turns which is easy to follow. The reason is the person giving this advice recognizes that traffic networks contain highways, expressways, freeways which span longer distances and are faster than street roads and minor arterials. Since a major portion of the travel is done on faster arcs, the total travel time may also be close to optimum. As described above, traffic networks exhibit a hierarchical behavior in their arc set. Computer and communication networks also exhibit such behavior. Based on the ideas in the above advice, the authors develop a single source to single sink shortest path algorithm which operates on a two-level hierarchical network. By solving the shortest path problem mainly on the high level subnetwork, this algorithm may achieve significant computation time savings when compared to optimal shortest path algorithms. But this algorithm may give non-optimal paths. To study this trade off, the authors formulate a simple mathematical model of hierarchical networks. They theoretically analyze the errors in path lengths, run times, run time improvements and optimal sizes of high and low level subnetworks for this model. Their study indicates that if the cost of arcs in the high level subnetwork is at most half the cost of arcs in the low level subnetwork, then the Hierarchical Algorithm is optimal for all source-sink pairs in the model. Further they test the algorithm performance on data from real traffic networks. The results of this testing indicate that significant computation time savings can be achieved with only small errors in path length. They also propose two extensions to the above algorithm for finding the shortest paths for a large number of source-sink pairs.

• Supplemental Notes:
  • Supported by a grant from the US Department of Transportation, University Transportation Centers Program
• Corporate Authors:

  Massachusetts Institute of Technology

  Department of Civil Engineering, 77 Massachusetts Avenue
  Cambridge, MA  United States  02139
• Authors:
  • Chabini, I
• Publication Date: 2000-6-29

Language

• English

Media Info

• Features: Figures; References;
• Pagination: 33 p.

Subject/Index Terms

• TRT Terms: Algorithms; Intelligent transportation systems; Mathematical models; Networks; Origin and destination; Traffic; Travel behavior
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Society; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00797093
• Record Type: Publication
• Report/Paper Numbers: Final Report
• Files: TRIS
• Created Date: Aug 6 2000 12:00AM