A Primal-Dual Algorithm for Link Dependent Origin Destination Matrix Estimation

Gabriel Michau, Nelly Pustelnik, Pierre Borgnat, Patrice Abry, Alfredo Nantes, Ashish Bhaskar, Edward Chung

TL;DR

This paper introduces a novel "Link-Dependent Origin-Destination Matrix" (LODM) to represent traffic flow, which inherently incorporates traffic assignment. They propose a primal-dual optimization algorithm to estimate this LODM using traffic counts and probe trajectory data, outperforming traditional methods.

What Problem Does This Paper Address?

Estimating Origin-Destination (OD) matrices, which describe traffic demand between origins and destinations, is crucial for transportation engineering. Traditional methods often rely on complex multi-step models and primarily use traffic counts. However, these methods struggle with the inherent ill-posedness of the problem and the difficulty of accurately modeling traffic assignment. This paper addresses this by proposing a more integrated approach that directly estimates link-dependent flows and leverages new data sources like probe trajectories.

Methods

The core contribution is the introduction of the Link-Dependent Origin-Destination Matrix (LODM), denoted as $Q$, which represents the flow on each link for each OD pair. This is a departure from traditional OD matrices that only represent demand. The estimation of $Q$ is framed as a convex optimization problem with five objective function terms:

  • Traffic Count Data Fidelity ($f_{TC}$): Ensures consistency with observed traffic counts on links.
  • Poisson Bluetooth Sampling Data Fidelity ($f_P$): Models the probabilistic nature of probe trajectory data, assuming a Poisson distribution for sampled vehicle counts.
  • Definition Domain Constraint ($f_C$): Enforces that the estimated flow of Bluetooth-enabled vehicles does not exceed the total traffic flow.
  • Kirchhoff's Law ($f_K$): Enforces traffic conservation at intersections for each OD pair.
  • Total Variation ($f_{TV}$): Encourages similarity in routes for users with similar origins/destinations, acting as a spatial regularization.

A primal-dual proximal algorithm is developed to minimize this objective function, which is particularly suited for problems combining differentiable and non-differentiable functions with linear operators.

Datasets

The paper uses simulated data for its experiments. A simplified road network with 50 nodes was created, and traffic was simulated for $10^5$ users. This simulated data includes:

  • Ground truth LODM ($Q^*$)
  • Link traffic counts ($q$)
  • Sampled probe trajectories ($B$)

The simulation parameters were chosen to be consistent with real-world networks and traffic patterns.

Key Insights and Ideas

  • LODM as a unified representation: The LODM elegantly combines OD demand and traffic assignment, simplifying the estimation problem by removing the need for a separate assignment model.
  • Leveraging probe trajectory data: The paper demonstrates the significant value of probe trajectory data (like from Bluetooth devices) in improving OD matrix estimation, especially when combined with traffic counts.
  • Primal-dual algorithm for non-smooth objectives: The choice of a primal-dual proximal algorithm is crucial for handling the non-differentiable terms in the objective function, making the optimization tractable.
  • Importance of regularization: The Total Variation term, while computationally more expensive, provides a slight improvement, suggesting its utility in capturing spatial correlations and handling unobserved flows.
  • Trade-offs in objective function weights: The results highlight that the optimal choice of weights ($\gamma$) for each objective function term depends on the desired outcome (e.g., minimizing RMSE vs. EMD) and the reliability of the input data (e.g., noise in traffic counts).

Key Results

  • The proposed primal-dual algorithm for LODM estimation outperforms naive estimation methods (e.g., using only Bluetooth data or traffic counts) in terms of both RMSE and EMD metrics.
  • When comparing different combinations of objective functions, including the Poisson sampling fidelity term ($f_P$) along with either traffic counts ($f_{TC}$) or Kirchhoff's law ($f_K$) and Total Variation ($f_{TV}$) yielded the best results.
  • Even with a reduced number of users (simulating shorter time periods), the method still provided significant improvements over naive estimates, showing robustness.
  • The paper shows that the choice of weights for different objective functions leads to different trade-offs, with higher $\gamma_{TC}$ favoring consistency with traffic counts and higher $\gamma_K$ favoring adherence to Kirchhoff's law.

Limitations and Future Work

  • Computational Cost: The primal-dual algorithm, especially with the Total Variation term, can be computationally intensive, requiring several hours for convergence on a Core i7 laptop for the simulated network.
  • Role of Total Variation: The paper notes that the TV term's contribution is subtle and its computational cost might outweigh its benefits in some scenarios.
  • Future Work: The authors suggest several avenues for future research:
  • Incorporating traffic turn fractions at intersections as an additional term.
  • Developing online algorithms for real-time estimation.
  • Implementing time dependencies to capture evolving traffic patterns.
  • Exploring alternative methods like Kalman filters or incorporating additional sensor data.

Summary updated

Abstract

Origin-Destination Matrix (ODM) estimation is a classical problem in transport engineering aiming to recover flows from every Origin to every Destination from measured traffic counts and a priori model information. In addition to traffic counts, the present contribution takes advantage of probe trajectories, whose capture is made possible by new measurement technologies. It extends the concept of ODM to that of Link dependent ODM (LODM), keeping the information about the flow distribution on links and containing inherently the ODM assignment. Further, an original formulation of LODM estimation, from traffic counts and probe trajectories is presented as an optimisation problem, where the functional to be minimized consists of five convex functions, each modelling a constraint or property of the transport problem: consistency with traffic counts, consistency with sampled probe trajectories, consistency with traffic conservation (Kirchhoff's law), similarity of flows having close origins and destinations, positivity of traffic flows. A primal-dual algorithm is devised to minimize the designed functional, as the corresponding objective functions are not necessarily differentiable. A case study, on a simulated network and traffic, validates the feasibility of the procedure and details its benefits for the estimation of an LODM matching real-network constraints and observations.
BibTeX
@article{michau2017primal,
  author = {Gabriel Michau and Nelly Pustelnik and Pierre Borgnat and Patrice Abry and Alfredo Nantes and Ashish Bhaskar and Edward Chung},
  title = {{A Primal-Dual Algorithm for Link Dependent Origin Destination Matrix Estimation}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2017},
  doi = {10.1109/tsipn.2016.2623094},
}

Loading related content...

Figure