Traffic congestion has been cited as the most conspicuous problem in traffic management. It has far-reaching economic,social and political effects. Intelligent Transportation Systems (ITS) research and development programs have been assigned the task of developing sophisticated techniques and counter-measures to reduce traffic congestion to manageable levels, and also achieve these objectives using area-wide traffic management methods. During times of traffic congestion, the traffic network in a transient, time-dynamic state, and resembles a dynamic network. In addition, in the context of ITS, the network can accurately detect such transient behavior using traffic sensors, and several other information gathering devices. In conjunction with Operations Research techniques, the time-varying traffic flows can be routed through the network in an optimal manner, based on the feedback from these information sources. Dynamic Traffic Assignment (DTA) methods have been proposed to perform this task. An important step in DTA is the calculation of user-optimal, system-optimal, and multiple optimal routes for assigning traffic. One would also require the calculation of user-optimal paths for vehicle scheduling and dispatching problems.

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.