01046140

Component

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.

01042056

07-1220

English

18p

2007

Transportation Research Board 86th Annual Meeting

CD-ROM

Figures (3) ; References (17) ; Tables (3)

Dynamic traffic assignment; Formulations; Graph theory; Traffic; Traffic congestion; Traffic flow

Cell transmission model; Graph-theoretic analysis; System optimal models; Theoretical models; User equilibrium

Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning

Transportation Research Board Annual Meeting 2007 Paper #07-1220

TRIS, TRB

Feb 8 2007 5:50PM