A relaxation approach for estimating origin-destination trip tables

Yu Marco Nie, H. M. Zhang

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


The problem of estimating origin-destination travel demands from partial observations of traffic conditions has often been formulated as a network design problem (NDP) with a bi-level structure. The upper level problem in such a formulation minimizes a distance metric between measured and estimated traffic conditions, and the lower level enforces user-equilibrium traffic conditions in the network. Since bi-level problems are usually challenging to solve numerically, especially for large-scale networks, we proposed, in an earlier effort (Nie et al., Transp Res, 39B:497-518, 2005), a decoupling scheme that transforms the O-D estimation problem into a single-level optimization problem. In this paper, a novel formulation is proposed to relax the user equilibrium conditions while taking users' route choice behavior into account. This relaxation approach allows the development of efficient solution procedures that can handle large-scale problems, and makes the integration of other inputs, such as path travel times and historical O-Ds rather straightforward. An algorithm based on column generation is devised to solve the relaxed formulation and its convergence is proved. Using a benchmark example, we compare the estimation results obtained from bi-level, decoupled and relaxed formulations, and conduct various sensitivity analysis. A large example is also provided to illustrate the efficiency of the relaxation method.

Original languageEnglish (US)
Pages (from-to)147-172
Number of pages26
JournalNetworks and Spatial Economics
Issue number1
StatePublished - Feb 2010


  • Bi-level program
  • Column generation
  • Relaxation
  • Static O-D estimation problem

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'A relaxation approach for estimating origin-destination trip tables'. Together they form a unique fingerprint.

Cite this