Efficient algorithms for the cell based single destination system optimal dynamic traffic assignment problem

摘要: The cell transmission model (CTM) based single destination system optimal dynamic traffic assignment (SD-SO-DTA) has wide applications. Although formulated as a linear programming (LP) model, embedded multi-period network representation yields an extremely large for real-size networks. As result, most of these models are not solvable using existent LP solvers. Solutions 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 SD-SO-DTA equivalent to the earliest arrival (EAF), then develop efficient solve EAF. Two variants algorithm developed. For case time-varying parameters, we on time-expanded network. main challenge in this approach address issue having backward wave speed lower than forward speed. This situation leads non-typical constraints involving coefficients with value less 1. Additionally, proposed solves flows exhibit non-vehicle-holding properties, which major breakthrough compared all existing SD-SO-DTA. For time-invariant reduce standard EAF problem network, constructed original roadway without dividing it into cells. under free condition one solutions, if properties follow trapezoidal/triangular fundamental diagram. use chain obtained static induce flows, applicable large-scale Another contribution provide simple practical solving multiple sources. Most studies contain submodular function optimization subroutines, thus real-life implementation. In regard, operational avoids optimization. body given method comprised |S+| iterations s – t computations, where number Numerical results show our multi-source parameters optimum.