Research On Continuous Path Planning In Dynamic Road Network

Intelligent transportation systems have emerged as a solution to the increasing transportation problems caused by the significant increase in the number of motor vehicles.Continuous path planning is an important part of these systems and aims to reduce traffic congestion,improve road utilization efficiency,and reduce traffic accidents by providing travelers with the optimal path in real time.However,current solutions have shortcomings in terms of inefficiency and insufficient accuracy due to high time complexity and the inability to update traffic conditions in a timely manner.This thesis aims to address these shortcomings through research on the continuous path planning problem in a dynamic road network,with a focus on improving computational efficiency and accuracy.The main research contents are as follows:(1)Firstly,this thesis discusses traditional path planning algorithms and their limitations in continuous path planning for dynamic road networks due to high time complexity.To reduce computation time,the thesis introduces an algorithm that limits the search area to an elliptical region and proposes a method to establish a reverse shortest path tree.The thesis also proposes three tree update strategies(SRS,DRS,TRS)to accelerate the update speed of the shortest path tree.Experiments on real datasets confirm the effectiveness of these algorithms in terms of computational efficiency and accuracy.(2)Next,this thesis introduces the concept of a safe region and incorporates it into continuous path planning.By mining historical traffic data,different roads are classified based on their importance level,and a historically graded safe region is proposed based on this classification.This safe region covers most of the highly important sections of the road network.Then,this paper elaborates on the path planning algorithms based on the historically graded safe region:the HGSRS algorithm and the HGSRS*algorithm.The main idea of the HGSRS algorithm is that if a path is within a safe region and its coverage of different important roads exceeds a given threshold,it will not be replanned.The HGSRS*algorithm adds the shortest path cache to speed up response queries based on this idea.This thesis demonstrates the efficiency and accuracy of the historically graded safe region and its algorithm through experimentation on a real dataset.(3)Finally,considering that the shortest path tree can only handle queries with different starting points and the same ending point when facing multiple queries,this article proposes a path planning algorithm based on path similarity.The algorithm first clusters queries with close starting points by calculating the path similarity,and then limits the search space of each cluster to an elliptical region,thereby improving the efficiency of path planning.Next,this article explains a method of using virtual nodes as the root node of the shortest path tree.This method achieves the purpose of responding to multiple queries by connecting a directed edge from the virtual root node to the endpoint of each query.Therefore,establishing a shortest path tree for each cluster can answer multiple queries at the same time,greatly improving computational efficiency.Through experiments on real datasets,this article verifies the effectiveness of the above algorithm in terms of computational efficiency and accuracy.