A Time-Dependent Dijkstra’s Algorithm for the Shortest Path Considering Periodic Queuing Delays at Signalized Intersections

In urban road networks, queuing delays at signalized intersections often account for over half of the total travel time. The complexity of traffic signals and vehicle queuing makes traditional shortest path algorithms insufficient for real-time optimal path finding. This study proposes a Time-Dependent Dijkstra’s algorithm to address these challenges. The network topology is redesigned to model vehicle turning behaviors accurately. A periodic queuing delay parameter matrix for signalized intersections is introduced, storing traffic flow and signal phase parameters. Additionally, a time-varying weight matrix tracks the vehicle’s position in the signal cycle upon intersection arrival. Using cumulative curve theory, a periodic queuing-delay model is constructed to capture delays for vehicles arriving at different times. The algorithm updates the network weight matrix in real-time based on vehicle arrival times at intersections, enabling FIFO-consistent time-dependent shortest path computation for a given departure time. Numerical and SUMO simulations on a real-world road network in Suzhou Industrial Park (comprising 15 signalized intersections and 22 road segments) demonstrate the algorithm’s effectiveness. Results show a 25.36% reduction in travel time compared to the traditional Dijkstra’s Algorithm and a 10.46% reduction compared to an algorithm considering only signalized intersection waiting time when departure times vary. The results highlight the impact of periodic queuing delays, with the algorithm reducing travel time and improving path planning.