原文传递
ADAPTATIONS OF THE A* ALGORITHM FOR DYNAMIC SHORTEST PATH PROBLEMS.
| 题名： | ADAPTATIONS OF THE A* ALGORITHM FOR DYNAMIC SHORTEST PATH PROBLEMS. |
| 作者： | Chabini-Ismail; Lan-Shan |
| 关键词： | Computer-algorithms; Routing-; Travel-time |
| 摘要： | 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. |
| 总页数： | ITS America. Meeting (10th : 2000 : Washington, D.C..). revolutionary thinking, real results : ITS 2000 : conference proceedings. 2000. pp28 |
| 报告类型： | 科技报告 |
相关文献
- BITWISE ALGORITHM FOR FASTEST PATHS IN TIME-DEPENDENT NETWORKS.
- BIT-STREAM REPRESENTATION OF TIME-DEPENDENT DATA : APPLICATIONS TO DATA COMMUNICATION AND PROCESSING.
- Discrete Dynamic Shortest Path Problems in Transportation Applications Complexity and Algorithms with Optimal Run Time
- Runtime Analysis of Benders Decomposition and Dual ILP Algorithms as Applied to Common Network Interdiction Problems.
- UNCOUPLED METHOD FOR EQUILIBRIUM-BASED LINEAR PATH FLOW ESTIMATOR FOR ORIGIN-DESTINATION TRIP MATRICES.
- SHORTEST PATH OF EMERGENCY VEHICLES UNDER UNCERTAIN URBAN TRAFFIC CONDITIONS.
检索历史
应用推荐
