Routing Algorithms for Dynamic, Intelligent Transportation Networks
MetadataShow full item record
The main objective of this research study is to analyze the effectiveness of time-dependent shortest path (TDSP) algorithms and k-shortest path (k-SP) algorithms as a practical routing tool in such intelligent transportation networks. Similar algorithms have been used to solve routing problems in computer networks. The similarities and differences between computer and ITS road networks are studied. An exhaustive review of TDSP and k-SP algorithms was conducted to classify and determine the best algorithms and implementation procedures available in the literature. A new (heuristic) algorithm (TD-kSP) that calculates multiple optimal paths for dynamic networks is proposed and developed. A complete object-oriented computer program in C++ was written using specialized network representations, node-renumbering schemes and efficient path processing data structures (classes) to implement this algorithm. A software environment where such optimization algorithms can be applied in practice was then developed using object-oriented design methodology. Extensive statistical and regression analysis tests for various random network sizes, densities and other parameters were conducted to determine the computational efficiency of the algorithm. Finally, the algorithm was incorporated within the GIS-based Wide-Area Incident Management Software System (WAIMSS) developed at the Center for Transportation Research, Virginia Tech. The results of these tests are used to obtain the empirical time-complexity of the algorithm. Results indicate that the performance of this algorithm is comparable to the best TDSP algorithms available in the literature, and strongly encourages its possible application in real-time applications.
Complete testing of the algorithm requires the use of real-time link flow data. While the use of randomly generated data and delay functions in this study may not significantly affect its computational performance, other measures of effectiveness as a routing tool remains untested. This can be verified only if the algorithm itself becomes a part of the user-behavior feedback loop. A closed loop traffic simulation/ system-dynamics study would be required to perform this task. On the other hand, an open-loop simulation would suffice for vehicle scheduling/dispatching problems.
- Masters Theses