A Variable Time-discretization Strategies-based, Time-dependent Shortest Path Algorithm for Dynamic Traffic Assignment

摘要

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 procedureby solving for the current optimal auxiliary solution (shortest path). Common types of TDSPalgorithms require temporal discretization of linkode time/cost data, and the discretizationcould affect the solution quality of TDSP and of the overall SBDTA as well. This paperintroduces two variable time-discretization strategies applicable to TDSP algorithms. Thestrategies are aimed at determining the optimal time-discretization for time-dependentlinksodes travel time data. The first proposed strategy produces a specific discretizationinterval for each link. The second proposed strategy generates time-varying intervals for thesame link over the analysis period. The proposed strategies are implemented in a link-basedtime-dependent A* algorithm and tested with two numerical experiments on two traffic networks.The results show that, with the same amount of computer memory usage, the proposed variabletime-discretization strategies achieve considerably higher accuracy than that of uniform timediscretization. Further, this study incorporates the modified TDSP into a SBDTA model. Anumerical analysis on two separate networks evaluates the sensitivity and properties of SBDTAoutputs with respect to the time-discretization strategy of TDSP. The analysis shows that theenhanced SBDTA model uses less memory, achieving better convergence at moderatecomputational tradeoff.