A variable time-discretization strategies-based, time-dependent shortest path algorithm for dynamic traffic assignment

Ye Tian, Yi Chang Chiu

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Within the simulation-based dynamic traffic assignment (SBDTA) model, the time-dependent shortest path (TDSP) algorithm plays a crucial role in the path-set update procedure by solving for the current optimal auxiliary solution (shortest path). Common types of TDSP algorithms require temporal discretization of link/node time/cost data, and the discretization could affect the solution quality of TDSP and of the overall SBDTA as well. This article introduces two variable time-discretization strategies applicable to TDSP algorithms. The strategies are aimed at determining the optimal time discretization for timedependent links/nodes travel time data. The first proposed strategy produces a specific discretization interval for each link. The second proposed strategy generates time-varying intervals for the same link over the analysis period. The proposed strategies are implemented in a link-based time-dependent A∗ algorithm in a SBDTA model DynusT and tested with two numerical experiments on two traffic networks. The results show that the proposed discretization methods achieve the research goal—to flexibly and scalably balance the memory usage and run time for SBDTA without degrading the convergence. This property is rather important when dealing with a large real-world network with a long analysis period.

Original languageEnglish (US)
Pages (from-to)339-351
Number of pages13
JournalJournal of Intelligent Transportation Systems: Technology, Planning, and Operations
Issue number4
StatePublished - Oct 1 2014
Externally publishedYes


  • Link-varying discretization
  • Simulation-based dynamic traffic assignment
  • Time-dependent shortest path
  • Time-varying discretization
  • Variable time discretization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Information Systems
  • Automotive Engineering
  • Aerospace Engineering
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'A variable time-discretization strategies-based, time-dependent shortest path algorithm for dynamic traffic assignment'. Together they form a unique fingerprint.

Cite this