Decentralized Algorithms for the Management and Control of TransportationSystems. An Approximate Shortest Path Algorithm for Hierarchical Networks

摘要

When a person asks for travel directions to go from point O to point D, theadvice he gets is 'from O get on to highway H and travel till you reach exit E2; get off the highway and travel along streets S3, S4, etc. till you reach D'. The advice usually results in a path with a small number of turns and 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 shortests 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. The authors theoretically analyze the errors in path lengths, run times, run time improvement and optimal sizes of high and low level subnetworks for this model. The authors' 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 the authors test the algorithm performance on data from real traffic netoworks. The results of this testing indicate that singificant computation time savings can be achieved with only small errors in path length. The authors also propose two extensions to the above algorithm for finding the shortest paths for a large number of source-sink pairs.