原文传递
Discrete Dynamic Shortest Path Problems in Transportation Applications Complexity and Algorithms with Optimal Run Time
| 题名： | Discrete Dynamic Shortest Path Problems in Transportation Applications Complexity and Algorithms with Optimal Run Time |
| 作者： | Chabini-I |
| 关键词： | Shortest path algorithms; Intelligent transportation systems; Algorithms; Real time control; Transportation system management; Discrete dynamic networks; Shortest paths; Optimal run time; Real time; Available |
| 摘要： | A solution is provided for what appears to be a 30-year-old problem dealing with the discovery of the most efficient algorithms possible to compute all-to-one shortest paths in discrete dynamic networks. This problem lies at the heart of efficient solution approaches to dynamic network models that arise in dynamic transportation systems, such as intelligent transportation systems (ITS) applications. The all-to-one dynamic shortest paths problem and the one-to-all fastest paths problem are studied. Early results are revisited and new properties are established. The complexity of these problems is established, and solution algorithms optimal for run time are developed. A new and simple solution algorithm is proposed for all-to-one, all departure time intervals, shortest paths problems. It is proved, theoretically, that the new solution algorithm has an optimal run time complexity that equals the complexity of the problem. Computer implementations and experimental evaluations of various solution algorithms support the theoretical findings and demonstrate the efficiency of the proposed solution algorithm. The findings should be of major benefit to research and development activities in the field of dynamic management, in particular real-time management, and to control of large-scale ITSs. |
| 总页数： | Transportation Research Record.1998. pp 170-175 (TABS: 5 Tab. REFS: 14 Ref.) |
| 报告类型： | 科技报告 |
相关文献
- DESIGN AND IMPLEMENTATION OF PARALLEL DYNAMIC SHORTEST PATH ALGORITHMS FOR INTELLIGENT TRANSPORTATION SYSTEMS APPLICATIONS.
- BIT-STREAM REPRESENTATION OF TIME-DEPENDENT DATA : APPLICATIONS TO DATA COMMUNICATION AND PROCESSING.
- A study on shortest path algorithm for route guidance in traffic network including left-turn restriction, U-turn and P-turn.
- IDENTIFYING MULTIPLE AND REASONABLE PATHS IN TRANSPORTATION NETWORKS: A HEURISTIC APPROACH.
- DBCENTRAI.IZBD Algorithms FOR THE MXNAOEHENT AND CCMJTROIi OF TRANSPORTATION SYSTEMS
- BITWISE ALGORITHM FOR FASTEST PATHS IN TIME-DEPENDENT NETWORKS.
检索历史
应用推荐
