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

摘要

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 prob- lems. 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.