An Exact Graph Structure for Dynamic Traffic Assignment: Formulation, Properties, and Computational Experience
Georgios Kalafatas, Srinivas Peeta · Transportation Research Board 86th Annual MeetingTransportation Research Board · 2007
The objective of this paper is to present an exact graph structure for dynamic traffic assignment (DTA), thereby providing a clear theoretical bridge between dynamic traffic assignment and graph theory. An exact graph-based formulation (GBF) with origins in the cell transmission model (CTM) is presented for the single destination DTA problem. The “cell” concept is formalized and projected in graph theoretic terms, leading to the graph theoretic cell transmission model (GTCTM). The fundamental difference with the CTM and existing DTA formulations (linear, minimum cost flow sub-structure) is in the modeling of backward propagating traffic waves, which is extensively discussed. The system optimal (SO) and the user equilibrium (UE) traffic assignment objectives are modeled on the same graph structure with modified weights. Properties of the corresponding graph are recognized: (i) the GBF is acyclic, and (ii) every edge-disjoint path is also a node-disjoint path. The existence of a solution and the property of uniqueness are analyzed using the GTCTM basis. Experimental results indicate significant benefits in computational time; it is the direct outcome of reducing the complexity of a linear formulation to minimum cost flow.