Urban road network time varying K shortest path search method capable of considering turn delays

Abstract

The invention discloses an urban road network time varying K shortest path search algorithm capable of considering turn delays. The algorithm comprises the following steps that: on the basis of obtaining the intersection turn delays of continuous equal time intervals and a road section stroke time data sequence, combining with an extended network method to obtain time varying impedance between intersection boundary lines in a network; adopting an A* algorithm to search a shortest path and stroke time from an appointed starting point boundary line to an end point boundary line; and furthermore, circularly adopting a connecting line deletion method and the A* algorithm to delete the shortest path under parts of connecting line conditions until search for the appointed K time varying shortest path is finished. By use of the time varying K shortest path search algorithm provided by the invention, the influence on path search by the time variation and the intersection delay of the urban road network impendence is simultaneously considered, a globally optimal result can be obtained at a high calculation speed, and the algorithm exhibits good maneuverability.

Description

technical field [0001] The invention relates to the field of shortest path search in road traffic network, in particular to a time-varying K-shortest path search method in urban road network considering turning delay. Background technique [0002] The shortest path problem is one of the core problems in the field of network optimization, and it is of great significance for the realization of traffic allocation and path guidance. So far, a lot of research has been carried out on the shortest path search technology of road traffic network at home and abroad, and the improved Dijkstra algorithm and Floyd algorithm have been proposed continuously. With the maturity of heuristic search method technology, in recent years, intelligent algorithms represented by genetic algorithm, simulated annealing algorithm, ant colony algorithm, etc. have also been gradually applied to the shortest path search of road traffic network. However, many studies have given corresponding solution algor...

AI Technical Summary

Problems solved by technology

In fact, due to the dynamic nature of the traffic network, the travel time of road sections in different time periods is not completely consistent. Simplifying it to a fixed value for model solution is quite different from the actual situation, resulting in low accuracy of calculation results

Although some studies have considered the dynamics of the traffic network and constructed time-varying network shortest path algorithms, the turning delay at intersections has been ignored in the process of model building, or the turning delays in all directions have been considered equal as the node impedance of the intersection

Images