原文传递
A Computational Study of Routing Algorithms for Realistic
Transportation Networks
| 题名： | A Computational Study of Routing Algorithms for Realistic Transportation Networks |
| 作者： | Rudiger R, Jacob, TSASA Kai "NMI" Nagel, TSASA Madhav V. Marathe, CIC-3 |
| 关键词： | Experimental Analysis, Transportation Planning, Algorithms, Network Design, Shortest Paths Algorithms. |
| 摘要： | We carry out an experimental analysis of a number of shortest path (routing) algorithms investigated in the context of the TRANSIMS (Transportation ANalysis and SIMulation System) project. The main focus of the paper is to study how various heuristic and exact solutions, associated data structures affected the computational performance of the software developed especially for realistic transportation networks. For this purpose we have used Dallas Ft-Worth road network with very hi^ degree of resolution. The following general results are obtained. 1. We discuss and experimentally analyze various one-one shortest path algorithms. These include classical exact algorithms studied in the literature as well as heuristic solutions that are designed to take into account the geometric structure of the input instances. 2. We describe a number of extensions to the basic shortest path algorithm. These extensions were primarily motivated by practical problems arising in TRANSIMS and ITS (Intelligent Transportation Systems) related technologies. Extensions discussed include — (i) Time dependent networks, (ii) multi-modal networks, (iii) networks with public transportation and associated schedules. Computational results are provided to empirically compare the efficiency of various algorithms. Our studies indicate that a modified Dijkstra’s algorithm is computationally fast and an excellent candidate for use in various transportation planning applications as well as ITS related technologies. |
| 报告类型： | 科技报告 |
相关文献
- A computational study of routing algorithms for realistic transportation networks
- Enabling Congestion Avoidance and Reduction in the Michigan-Ohio Transportation Network to Improve Supply Chain Efficiency: Freight ATIS. Progress Report, October 1, 2007.
- Enabling Congestion Avoidance and Reduction in the Michigan-Ohio Transportation Network to Improve Supply Chain Efficiency: Freight ATIS. Final Report, October 2010.
- HEURISTIC ALGORITHMS FOR SOLVING HAZARDOUS MATERIALS LOGISTICAL PROBLEMS.
- Reliable Routing in Transit Networks.
- Development of analytic intermodal freight networks for use within a GIS
检索历史
应用推荐
