System optimal dynamic traffic assignment: A graph-theoretic approach and its engineering application

The system optimal dynamic traffic assignment (SO-DTA) problem determines the time-dependent traffic flow pattern that minimizes the total system cost in a road network. This problem is of great importance for benchmarking and designing diverse congestion alleviation strategies. Despite its great importance, SO-DTA for large-scale general networks remains one of the most challenging problems in transportation research. Solutions with conventional optimization methods are often problematic, due to the high dimensionality and non-convexity of the formulations.This dissertation focuses on the SO-DTA problem with a single destination (S-SO-DTA), which is the building block for solving the general SO-DTA problem. Using a graph-theoretic approach, we reveal the intrinsic connection between the S-SO-DTA problem and the minimum cost flow (MCF) problem in graph theory. It is demonstrated that non-convexity and high-dimensionality, the two major obstacles for solving the S-SO-DTA problem, can be decoupled and tackled separately by relaxation and transformation techniques. The entire decoupling process uncovers a series of interesting and insightful properties, which give birth to a two-stage innovative solution procedure for the S-SO-DTA problem. The first stage solves a special minimum cost flow problem by an augmented network simplex method, while the second stage transforms an optimal traffic flow pattern of the minimum cost flow problem to an optimal traffic flow pattern of the S-SO-DTA problem by applying a pseudo dynamic network loading procedure. By exploiting specialties of network structure, this two-stage procedure is capable of efficiently obtaining global optimal solutions for large-scale S-SO-DTA problems. An extended version of the S-SO-DTA problem, the S-SO-DTA problem with departure time choice, is also discussed. It is shown that most of the graph-theoretic properties as well as the solution procedure can be easily extended with minor modifications.Finally, this thesis work also investigates the potential applications of the S-SO-DTA results in a variety of operational contexts, including emergency evacuation, access control in monocentric networks, and dynamic congestion pricing. Guidelines for designing efficient dynamic traffic management measures are provided.