A variational inequality approach for inferring dynamic origin-destination travel demands

This dissertation tackles the problem of inferring time-varying travel demands from traffic measurements such as traffic counts and/or travel times. Also known as the estimation of dynamic origin-destination (O-D) matrices, its static counterpart has been extensively studied. This type of problem often leads to a bi-level structure where the upper level minimizes some distance measures, and the lower-level describes the user-equilibrium traffic behavior. This classical bi-level O-D estimation approach is, however, not suitable in the dynamic context because (1) dynamic equilibrium constraints are not differentiable, and (2) repeatedly solving the dynamic user optimal assignment problem (i.e., the lower problem) is difficult and computationally demanding in its own right.; We show that a one-level problem can be formulated by either decoupling or relaxing the user equilibrium conditions in the bi-level problem. The idea is first demonstrated through static O-D estimation problems in which the statistical properties of the resulting estimators are examined. We formulate the one-level dynamic O-D estimation problem (DODE) as a variational inequality (VI) problem due to the dependence of the dynamic assignment matrix on the underlying network traffic dynamics. The equivalence between the VI formulation and the DODE optimality conditions are proved, and the conditions under which a solution exists for the VI problem are established. To evaluate the implicit path cost mapping and path-link incidence relationship, a polymorphic dynamic network loading (PDNL) model is developed which integrates a variety of macroscopic traffic flow models and models. The prominent features of the PDNL model include flexibility, extendability, parallelizability and the capability of keeping track of individual vehicular quanta of arbitrary size. Various numerical algorithms, particularly those based on the notion of projection, are proposed to solve the formulated VI problem. In order to avoid path enumeration, a column generation scheme is employed on the space-time expanded network. Different time-dependent minimum-cost path algorithms are used to generate paths as required to solve the DODE problem optimally. Numerical results based on synthetic examples are provided which verify the proposed DODE formulation and its solution procedures.