UC Berkeley

The research presented in this dissertation aims to develop computationally tractable models and algorithms for the reliable and efficient utilization of capacity restricted transportation networks via route selection and demand redistribution, motivated by the fact that traffic congestion in road networks is a major problem in urban communities. Three related topics are considered, 1) route planning with reliability guarantees, 2) system optimal dynamic traffic assignment, and 3) controlling user equilibrium departure times.

Route planning can in many practical settings require finding a route that is both fast and reliable. However, in most operational settings, only deterministic shortest paths are considered, and even when the link travel-times are known to be stochastic the common approach is to simply minimize the expected travel-time. This approach does not account for the variance of the travel-time and gives no reliability guarantees. In many cases, travelers have hard deadlines or are willing to sacrifice some extra travel-time for increased travel-time reliability, such as in commercial routing applications where delivery guarantees need to be met and perishables need to be delivered on time. The research presented in this dissertation develops fast computation techniques for the reliable routing problem known as the stochastic on-time arrival (SOTA) problem, which provides a routing strategy that maximizes the probability of arriving at the destination within a fixed time budget.

Selfish user optimal routing strategies can, however, lead to very inefficient traffic equilibria in congested traffic networks. This "Price of Anarchy" can be mitigated using system optimal coordinated routing algorithms. The dissertation considers the system optimal dynamic traffic assignment problem when only a subset of the network agents can be centrally coordinated. A road traffic dynamics model is developed based on the Lighthill-Williams-Richards partial differential equation and a corresponding multi-commodity junction solver. Full Lagrangian paths are assumed to be known for the controllable agents, while only the aggregate split ratios are required for the non-controllable (selfish) agents. The resulting non-linear optimal control problem is solved efficiently using the discrete adjoint method.

Spill-back from under-capacitated off-ramps is one of the major causes of congestion during the morning commute. This spill-back induces a capacity drop on the freeway, which then creates a bottleneck for the mainline traffic that is passing by the off-ramp. Therefore, influencing the flow distribution of the vehicles that exit the freeway at the off-ramp can improve the throughput of freeway vehicles that pass this junction. The dissertation studies the generalized morning commute problem where vehicles exiting the freeway at the under-capacitated off-ramp have a fixed desired arrival time and a corresponding equilibrium departure time schedule, and presents strategies to manipulated this equilibrium to maximize throughput on the freeway via incentives or tolls.