A Dantzig-Wolfe Decomposition-Based Heuristic for Off-line Capacity Calibration of Dynamic Traffic Assignment

Dung Ying Lin, Varunraj Valsaraj, S. Travis Waller

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


One of the critical elements in considering any real-time traffic management strategy requires assessing network traffic dynamics. Traffic is inherently dynamic, since it features congestion patterns that evolve over time and queues that form and dissipate over a planning horizon. Dynamic traffic assignment (DTA) is therefore gaining wider acceptance among agencies and practitioners as a more realistic representation of traffic phenomena than static traffic assignment. Though it is imperative to calibrate the DTA model such that it can accurately reproduce field observations and avoid erroneous flow predictions when evaluating traffic management strategies, DTA calibration is an onerous task due to the large number of variables that can be modified and the intensive computational resources required. To compliment other research on behavioral and trip table issues, this work focuses on DTA capacity calibration and presents an efficient Dantzig-Wolfe decomposition-based heuristic that decomposes the problem into a restricted master problem and a series of pricing problems. The restricted master problem is a capacity manipulation problem, which can be solved by a linear programming solver. The pricing problem is the user optimal DTA which can be optimally solved by an existing combinatorial algorithm. In addition, the proposed set of dual variable approximation techniques is one of a very limited number of approaches that can be used to estimate network-wide dual information in facilitating algorithmic designs while maintaining scalability. Two networks of various sizes are empirically tested to demonstrate the efficiency and efficacy of the proposed heuristic. Based on the results, the proposed heuristic can calibrate the network capacity and match the counts within a 1% optimality gap.

Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalComputer-Aided Civil and Infrastructure Engineering
Issue number1
Publication statusPublished - 2011 Jan

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Computational Theory and Mathematics


Dive into the research topics of 'A Dantzig-Wolfe Decomposition-Based Heuristic for Off-line Capacity Calibration of Dynamic Traffic Assignment'. Together they form a unique fingerprint.

Cite this