Improving the Accuracy and Efficiency of Online Calibration for Simulation-based Dynamic Traffic Assignment

Haizheng Zhang, Ravi Seshadri, A. Arun Prakash, Constantinos Antoniou, Francisco C. Pereira, Moshe E. Ben-AkivaTransportation 2021 · DOI · OpenReview

Abstract

Real-time traffic management relies on Simulation-based Dynamic Traffic Assignment (DTA) models, which require continuous online calibration to match real-world sensor data. Traditional methods, such as the Extended Kalman Filter (EKF), face significant hurdles: the "Lag Problem," where congestion delays the impact of demand on downstream sensors, and the "Curse of Dimensionality," which makes gradient calculations computationally prohibitive for large networks. This paper introduces a two-pronged strategy to overcome these challenges. By augmenting the state vector to account for temporal delays and utilizing graph-coloring algorithms to exploit spatial sparsity, the authors achieve a 13% improvement in accuracy and a nearly ten-fold reduction in computation time on the Singapore expressway network, demonstrating real-time feasibility for mega-cities.

Introduction

Managing urban traffic in real-time requires models that can accurately predict flow and density across complex networks. Simulation-based Dynamic Traffic Assignment (DTA) is the industry standard, but its effectiveness depends on "online calibration"—the continuous adjustment of parameters (e.g., origin-destination flows) based on live sensor data.

The standard approach, the Extended Kalman Filter (EKF), suffers from two primary limitations. First, it typically assumes a Markovian process where the current state only depends on the immediate past, failing to account for the 15-20 minute travel lags common in congested cities. Second, calculating the Jacobian matrix for thousands of parameters requires an impractical number of simulator runs, rendering real-time updates impossible for large-scale networks.

Methodology

Addressing the Lag Problem: State Augmentation

To resolve the disconnect between past demand and current observations, the authors propose a Constrained Extended Kalman Filter (CEKF) with state augmentation. Instead of estimating only the current 5-minute demand window, the filter estimates a window of past states simultaneously. This allows the model to retroactively update demand estimates as their effects reach downstream sensors over time.

Augmented state transition diagram where demand at time $t$ influences observations across multiple future time steps.

To maintain computational efficiency, the authors employ "staggered horizons," which allow for the reuse of previously calculated gradients, preventing the augmented state from exponentially increasing processing time.

Scaling to Mega-Cities: Graph-Coloring Efficiency

The second innovation addresses the computational bottleneck of gradient estimation. In a typical city, traffic demand in one region often has no impact on sensors in distant regions. This spatial independence creates a sparse Jacobian matrix.

Spatial independence in a traffic network: sensors $s1$ and $s2$ are affected only by their respective origins, illustrating the sparsity exploited for efficiency.

The authors represent these relationships as a graph and apply a greedy graph-coloring algorithm to group non-conflicting parameters. Parameters assigned the same "color" can be perturbed and simulated simultaneously in a single run. This "Partitioned Finite-Difference" approach collapses thousands of required simulations into a few hundred, drastically reducing the overhead of the traffic simulator.

Experimental Results

The proposed methods were validated using a synthetic toy network and the real-world Singapore Expressway Network, which consists of over 1,100 links and 4,100 origin-destination (OD) pairs.

  • Accuracy Boost: On the Singapore network, state augmentation (using a look-back window of three intervals, or CEKF-3) improved the Root Mean Squared Normalized error (RMSN) by approximately 13% compared to non-augmented models.
  • Massive Speedup: The graph-coloring approach reduced the number of required simulation runs from 4,121 to just 438. In practice, this dropped the total computation time per 5-minute interval from 29 minutes to 4.7 minutes, enabling true real-time deployment.

Conclusion

This research demonstrates that congestion-induced temporal lags and high-dimensional parameter spaces are not insurmountable barriers to real-time DTA. By exploiting the inherent memory and sparsity of traffic systems, the proposed CEKF framework provides a scalable solution for urban traffic management. Future work will explore the simultaneous calibration of supply parameters, such as road capacity and speed-density relationships, using these same efficiency-boosting techniques.

Summary updated

Abstract

Simulation-based Dynamic Traffic Assignment models have important applications in real-time traffic management and control. The efficacy of these systems rests on the ability to generate accurate estimates and predictions of traffic states, which necessitates online calibration. A widely used solution approach for online calibration is the Extended Kalman Filter (EKF), which -- although appealing in its flexibility to incorporate any class of parameters and measurements -- poses several challenges with regard to calibration accuracy and scalability, especially in congested situations for large-scale networks. This paper addresses these issues in turn so as to improve the accuracy and efficiency of EKF-based online calibration approaches for large and congested networks. First, the concept of state augmentation is revisited to handle violations of the Markovian assumption typically implicit in online applications of the EKF. Second, a method based on graph-coloring is proposed to operationalize the partitioned finite-difference approach that enhances scalability of the gradient computations. Several synthetic experiments and a real world case study demonstrate that application of the proposed approaches yields improvements in terms of both prediction accuracy and computational performance. The work has applications in real-world deployments of simulation-based dynamic traffic assignment systems.
BibTeX
@inproceedings{zhang2021improving,
  author = {Haizheng Zhang and Ravi Seshadri and A. Arun Prakash and Constantinos Antoniou and Francisco C. Pereira and Moshe E. Ben-Akiva},
  title = {{Improving the Accuracy and Efficiency of Online Calibration for Simulation-based Dynamic Traffic Assignment}},
  booktitle = {Transportation},
  year = {2021},
  doi = {10.1016/j.trc.2021.103195},
}
Figure