首页> 美国政府科技报告 >Decentralized Algorithms for the Management and Control of TransportationSystems. An Approximate Shortest Path Algorithm for Hierarchical Networks
【24h】

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

机译:交通系统管理控制分散算法中图分类:O221万方期刊分类:Na大学学报(自然科学)分层网络的近似最短路径算法

获取原文

摘要

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.

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号