Published: 2009
Total Pages: 352
Get eBook
The cell transmission model (CTM) based single destination system optimal dynamic traffic assignment (SD-SO-DTA) model has wide applications. Although formulated as a linear programming (LP) model, embedded multi-period cell network representation yields an extremely large model for real-size networks. As a result, most of these models are not solvable using existent LP solvers. Solutions using LP techniques also involve holding vehicles, violating CTM flow dynamics. This doctoral research is aimed at developing innovative algorithms that overcome both computational efficiency and solution realism. We first prove that SD-SO-DTA is equivalent to the earliest arrival flow (EAF), and then develop efficient algorithms to solve EAF. Two variants of the algorithm are developed. For the case of time-varying parameters, we develop a network flow algorithm on a time-expanded network. The main challenge in this approach is to address the issue of having backward wave speed lower than forward wave speed. This situation leads to non-typical constraints involving coefficients with value of less than 1. Additionally, the proposed approach solves for optimal flows that exhibit non-vehicle-holding properties, which is a major breakthrough compared to all existing solution techniques for SD-SO-DTA. For the case of time-invariant network parameters, we reduce the SD-SO-DTA to a standard EAF problem on a dynamic network, which is constructed on the original roadway network without dividing it into cells. We prove that the EAF under a free flow condition is one of the optimal solutions, if cell properties follow a trapezoidal/triangular fundamental diagram. We use chain flows obtained on a static network to induce dynamic flows, an approach applicable to large-scale networks. Another contribution of this research is to provide a simple and practical algorithm solving the EAF with multiple sources. Most existing studies contain submodular function optimization as subroutines, and thus are not practical for real-life implementation. In this regard, we develop a practical and operational algorithm that avoids submodular function optimization. The main body of the given method is comprised of.