PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Estimation of Dynamic Origin-Destination Matrices Using Reinforcement Learning with Link-Flow Propagation Guidance

Donggyu Min, Dong-Kyu Kim

arXiv:2608.30317v1cs.LGcs.AI

TL;DR

Online DODE must estimate current OD demand from partial observations and propagated network states while handling stochastic, delayed DNL and varying target trajectories. LFPG-RL adds rollout-based, OD-specific propagation guidance to PPO actor updates, and achieved the best reported case-study performance against evaluated methods. Its scope is bounded because LFPG is rollout-conditioned rather than a counterfactual DNL derivative, especially under severe congestion.

  • Problem

    Online DODE requires efficient estimation under delayed, stochastic DNL, while scalar rewards provide limited OD-component guidance across varying target trajectories.

  • Method

    LFPG-RL extracts rollout-specific OD-to-link propagation and combines it with link-flow residuals to shape PPO advantages for online DODE.

  • Results

    LFPG-RL reduced RMSE by 92.1% and MAPE by 96.4% versus PPO with the same actor-critic architecture, and reduced RMSE by 62.3% and MAPE by 45.7% versus the strongest baseline.

  • Takeaways & Limitations

    Completed DNL rollouts provide structural information beyond scalar rewards, and training from rollout-conditioned propagation patterns can be more robust than using propagation as an online search direction.

  • Takeaways & Limitations

    Under severe congestion, route-choice shifts, queues, and spillback may make rollout-recorded propagation less representative of an OD component’s local effect.

Abstract

from arXiv · show

Online dynamic origin-destination (OD) matrix estimation (DODE) calibrates time-dependent OD demand to reproduce observed link-flow trajectories. In online, OD demand should be estimated from current observations and propagated network states while subsequent observations and stochastic dynamic network loading (DNL) outcomes remain uncertain. Recently, reinforcement learning (RL) has emerged as a promising alternative, reducing computational burden by replacing iterative algorithms while being applicable to stochastic environments. However, because the policy is trained offline and deployed online, it must handle varying target link-flow trajectories; since each target trajectory defines the link-flow error used in the reward, the same OD demand vector can require different adjustments, making conventional scalar feedback ambiguous. To address this gap, this study proposes LFPG-RL, which integrates link-flow propagation guidance (LFPG) into proximal policy optimization (PPO). LFPG combines link-flow error sensitivities with the contribution of each OD-time demand component to simulated link flows, transforming aggregate mismatch into OD-specific advantage shaping for PPO actor updates. At deployment, the policy requires only a single forward pass. LFPG-RL is developed and evaluated on 250 weekday trajectories of 15-min link-flow data from a Melbourne arterial network modeled by a link transmission model with stochastic route choice. On held-out trajectories, LFPG-RL achieved an RMSE of 4.69, MAPE of 20.15%, and Pearson correlation of 0.995. These results support the contention that our method is a more efficient and accurate online OD demand calibration method compared to existing ones.

1 Introduction

Online DODE must estimate current OD demand under nonlinear, delayed, stochastic network effects and tight decision intervals. LFPG-RL addresses scalar-feedback ambiguity by using rollout-derived propagation information to shape PPO updates for online deployment.

  • Dynamic OD estimation calibrates time-dependent demand so simulated link flows reproduce observed trajectories.
  • Online DODE is constrained by nonlinear, time-delayed, stochastic DNL and the inability to revise committed demand within the current interval.
  • RL shifts computation offline by mapping observed link flows and propagated network state to current OD demand through one deployment-time forward pass.
  • Varying target trajectories create a generalization challenge because the same OD vector can produce different error patterns and similar scalar rewards can hide distinct patterns.
  • LFPG relates OD-time demand contributions from DNL rollouts to link-flow errors, converting aggregate mismatch into component-level guidance.
  • LFPG-RL adds LFPG-derived shaping to PPO actor updates while retaining the GAE-based global term.

2 Related Works

Related work addresses online DODE through filtering, optimization, dimensionality reduction, and RL, but computational cost and policy generalization remain central challenges. LFPG-RL responds to the limited attribution provided by scalar policy-gradient feedback.

  • Online DODE determines current demand from available observations and carried-over network state before future observations arrive.
  • PCA, EKF, LETKF, SPSA, metamodels, assignment-free formulations, Bayesian optimization, and hybrid models target scalability or evaluation efficiency.
  • Filtering-based methods recursively update demand, whereas optimization-based methods repeatedly estimate demand and evaluate traffic-assignment outcomes.
  • Optimization-based approaches still require iterative processes under limited computational budgets, while surrogate methods may suffer model-plant mismatch.
  • RL can shift computational burden to pre-deployment training and estimate OD demand through a policy forward pass.
  • Pretrained policies must generalize across target trajectories, but scalar advantages do not preserve residual patterns or attribute them to individual OD components.
  • Propagation-aware studies motivate LFPG because standard policy-gradient methods do not exploit structural information contained in completed DNL rollouts.

3.1 Key Concept

LFPG-RL uses completed DNL rollouts to guide policy learning beyond scalar rewards. The policy acts on the current state, while rollout propagation and residuals generate OD-specific PPO shaping signals during training.

  • At each decision step, the policy receives the current state and produces the current OD demand vector.
  • The DNL model propagates selected demand into simulated link flows, and completed rollouts provide information for extracting LFPG signals during PPO training.

3.2 Problem Statement

Online DODE is formulated as sequential selection of OD demand vectors using current observations and propagated network state. The DNL process supplies delayed, stochastic transitions and simulated link-flow errors for the objective and PPO formulation.

  • The estimator selects each current OD demand vector from information available at that step, without using future target observations.
  • After an action is selected, DNL advances one step and returns full network-link states used to form observed-link simulated flows.
  • Because DNL is dynamic and time-delayed, the simulated flow depends on the committed action history rather than only the current action.
  • The objective compares observed and simulated link-flow vectors while accounting for simulator, route-choice, and estimator randomness.
  • Stacking sequentially selected demand vectors produces the dynamic OD matrix, with each action fixed once selected and not revisable later.
  • The sequential estimator is represented as a finite-horizon MDP with state, action, transition, reward, initial-state, and horizon components.
  • The transition kernel is induced by DNL and route-choice randomness, conditioned on the sampled target trajectory.
  • The reward is negative normalized link-flow error, so cumulative reward maximization corresponds to minimizing cumulative observed-simulated mismatch.

3.3 Policy Optimization with Link-Flow Propagation Guidance

LFPG extracts rollout-specific OD-time contributions to link flows and combines them with mismatch sensitivities to create OD-specific guidance. This guidance shapes PPO actor updates while preserving the global advantage signal.

  • Propagation extraction: Each completed DNL rollout records how every OD-time demand group contributes to downstream network links across future time steps.The resulting propagation tensor is rollout-specific and reflects realized congestion, prior demands, and stochastic route-choice outcomes.
  • Propagation extraction: The propagation tensor decomposes simulated network-link flows into contributions from OD-time groups, after which H maps them into observed-link flows.This decomposition distinguishes component contributions from aggregate mismatch.
  • LFPG construction: Unlike scalar reward feedback, LFPG preserves information about which OD components contribute to downstream link-flow errors.Scalar rewards evaluate the aggregate mismatch but do not identify the responsible OD dimensions.
  • LFPG construction: LFPG combines propagated contributions with signed link-flow error sensitivities to indicate each OD-time component’s association with future errors and suggested adjustment direction.The sensitivity is zero for network links excluded from observation, and the LFPG magnitude is volume-weighted rather than counterfactual.
  • Policy optimization: LFPG is computed from the same completed rollout without additional DNL evaluations and is used only during training to improve OD-specific policy updates.At deployment, the policy selects actions from the current state through a single learned-policy forward pass.
  • Policy optimization: The actor objective retains normalized global PPO advantages and adds normalized, clipped LFPG shaping based on propagation direction and sampled-action residuals.PPO clipping is applied separately to the global advantage and LFPG shaping components.

3.4 Experimental Settings

The experiments use a stochastic LTM-based DNL model of a Melbourne arterial network and weekday SCATS link-flow trajectories. Evaluation targets reproduction of observed flows rather than recovery of uniquely identified OD demand.

  • Dynamic network loading model: The DNL model uses a discrete-time link transmission model representing queue formation, spillback, and time-delayed demand propagation.The estimation interval is 15 minutes, while the internal DNL simulation runs at one-minute resolution.
  • Target network and data: The Melbourne case study contains 31 OD centroids and 78 directed links, producing 930 OD components per action vector.The network uses primary arterial links and SCATS detectors mapped to corresponding directed links.
  • Target network and data: The dataset includes 250 weekday trajectories, split into 220 training days and 30 held-out test days.Each episode covers 04:00–10:00 in 24 decision steps of 15 minutes.
  • Target network and data: Ground-truth OD matrices are unavailable and are not used, so evaluation measures reproduction of observed link-flow trajectories rather than true OD recovery or identifiability.Estimated OD matrices are interpreted as calibrated simulator inputs rather than uniquely identified travel demand.
  • Experimental comparisons: LFPG-RL is compared with PPO using the same architecture, LFPG-GD, W-SPSA, and sequential-filtering baselines under a common action space.The comparisons isolate the effect of LFPG, test LFPG with gradient descent, and compare against non-RL online methods.

4 Results

LFPG-RL outperformed PPO and other baselines in reproducing held-out link-flow trajectories, while LFPG-GD was the strongest non-policy baseline. The results also indicate that propagation guidance is most effective when learned through a generalized policy.

  • LFPG-RL steadily improved during training while PPO remained in a low-performance regime, indicating that propagation guidance supplied a useful learning signal beyond scalar reward feedback.The two policies shared the same architecture and training configuration except for LFPG advantage shaping.
  • LFPG-RL achieved RMSE 4.69, MAPE 20.15%, and Pearson r = 0.995, compared with PPO’s RMSE 59.64, MAPE 562.66%, and Pearson r = −0.041.Relative to PPO, LFPG-RL reduced RMSE by 92.1% and MAPE by 96.4%.
  • LFPG-RL produced the tightest concentration of simulated-versus-target link flows around the exact-reproduction diagonal.All methods operated under a 15-minute per-step computation time budget matching the data update interval.
  • LFPG-RL improved on LFPG-GD, reducing RMSE by 62.3% and MAPE by 45.7%.LFPG-GD remained the strongest baseline, with RMSE 12.47, MAPE 37.13%, and Pearson r = 0.965.
  • LFPG-RL had the smallest and most compact stepwise RMSE distribution, with mean 4.25 and median 4.45 vehicles per 15-minute interval.LFPG-GD’s mean and median stepwise RMSE were 10.32 and 10.04, respectively, with a wider upper tail.
  • LFPG-RL had the lowest mean stepwise MAPE at 21.65% and the strongest time-wise alignment, with median rt = 0.988.LFPG-GD’s corresponding mean stepwise MAPE was 37.86%, and its median rt was 0.925.
  • LFPG-RL showed a relatively uniform low-error heatmap pattern, averaging capacity-normalized absolute error 0.0131 with 0 of 648 cells exceeding 0.05.LFPG-GD averaged 0.0248 and had 96 cells exceeding 0.05, with stronger localized error bands later in the horizon.

5 Conclusion

LFPG-RL addresses policy-generalization and scalar-reward limitations in online DODE by using DNL rollout propagation information to shape PPO updates at the OD-component level. Evaluations on a Melbourne arterial network show improved accuracy and stability, while limitations remain under saturated regimes and without OD priors.

  • LFPG-RL extracts link-flow propagation information from completed DNL rollouts and uses it to shape PPO actor updates at the OD-component level.This addresses the limited guidance provided by aggregate scalar link-flow mismatch.
  • LFPG-RL reduced RMSE by 92.1% and MAPE by 96.4% versus PPO with the same actor-critic architecture, and by 62.3% and 45.7% versus the strongest baseline.The evaluation used field link-flow observations from a Melbourne arterial network with an LTM-based DNL model and stochastic route choice.
  • Stepwise and spatiotemporal analyses found LFPG-RL more stable across decision steps and less prone to localized errors.
  • Completed DNL rollouts provide structural information beyond scalar rewards, and rollout-conditioned propagation patterns can make stochastic RL more robust than local LFPG-GD search under delayed, stochastic DNL.
  • Under severe congestion, route-choice shifts, queues, and spillback may make recorded propagation less representative of local OD-component effects.The current formulation also uses link-flow observations without OD matrix priors.
Loading 2608.30317v1…