Research On Dynamic Shortest Route Choice Algorithm Based On Online Map Speed Data

Urban dynamic traffic guidance is one of the most effective measures to ease traffic congestion.Travelers can choose the appropriate travel route and travel time to avoid the unnecessary delay of traveling according to the guiding information.The core of dynamic route guidance is dynamic shortest route choice.In the previous research,road network speed data in some areas is insufficient due to the limitation of regional economic development,which leads to a difference between route planning results and the actual ones.In addition,the time-varying state of road traffic is not fully considered in the process of dynamic shortest route choice.To solve the above problems,a GCN-LSTM-BP short-term traffic speed prediction model was constructed on the basis of online map speed data;subsequently,the shortest route choice algorithm is studied for urban dynamic travel time based on the speed prediction information.Firstly,the methods to get the required data for the thesis research are explained.Considering limitations of getting large-scale road network speed data by traditional data collection methods,the traditional speed data are replaced by the online map speed data in this paper.The latitude and longitude coordinates of each intersection in the road network in the online map are obtained by calling APIs provided by online map service platforms such as Baidu,AMAP,etc.According to the latitude and longitude coordinates of adjacent intersections,the mileage and travel time of the road sections in different periods are crawled in batches;the travel speed of road section is calculated;and the collection of road network speed data is achieved.Secondly,a short-term traffic speed prediction model for road sections is constructed based on the acquired online map speed data.From the spatial-temporal correlation of road traffic speed,a spatial dependence mining model of road traffic speed is constructed on the basis of GCN network;a time dependence mining model of road traffic speed is constructed based on LSTM network;and the processed Baidu map road speed data and AMAP road speed data are fused to construct a road short-term traffic speed prediction model based on the GCN-LSTM-BP network to realize road speed prediction.The experimental results show the prediction model proposed in this paper considering the spatial-temporal characteristics has a better prediction effect than that of the model considering the temporal characteristics of speed only.Finally,the shortest route choice model for urban dynamic travel time is constructed based on the speed prediction information,and the Dijkstra algorithm is improved to solve the model.The traditional Dijkstra algorithm is easy to include redundant nodes in the search area when calculating the shortest route between the origin-destination,increasing the time complexity of the algorithm.hence,a Dijkstra algorithm considering the limitation of time-varying rectangular area was proposed in this paper.According to the relationship between the length of shortest travel time route and the Euclidean distance between starting and ending points at different times,the search area of Dijkstra algorithm is limited to improve the Dijkstra algorithm,reduce the search time and advance the efficiency of the algorithm.According to the actual road network and the predicted speed of the road network,the traditional Dijkstra algorithm and the improved Dijkstra algorithm are used to select the dynamic shortest route of the travel time for a certain number of OD pairs in the road network,which further validates the effectiveness and reliability of the algorithm.