Link-Based System Optimum Dynamic Traffic Assignment Problems in General Networks

Most current system optimum dynamic traffic assignment (SO-DTA) models do not contain first-in-first-out (FIFO) constraints and are limited to single-destination network applications. In this study, we introduce the link transmission model (LTM) for the development of SO-DTA models either with or without FIFO constraints for general network applications. The proposed SO-DTA models include the LTM and can lead to a linear programming (LP) formulation if the FIFO constraints are not explicitly captured. The vehicle holding problem can be addressed by adding a penalty term to the objective function. We also formulate FIFO constraints in terms of the relationship between link cumulative inflows and outflows and the link entry time. Optimization models that integrate the proposed FIFO constraints into the proposed LP formulations for SO-DTA problems without FIFO constraints are also developed to formulate SO-DTA problems with FIFO constraints. Based on the properties of the proposed optimization problems, branch-and-bound algorithms are developed to solve SO-DTA problems with FIFO constraints. Two methods are developed to identify FIFO violations in feasible flow patterns and to design a branching scheme for the proposed branch-and-bound algorithms. Finally, numerical examples are set up to demonstrate the properties of the proposed models and the performance of the algorithms.