Research On Dominate Route Queries Based On Road Network

With the rapid development of road networks and mobile communications,locatio-based services play an important role in people's lives.Route planning has always been a fundamental and important issue in location-based services and online map service applications.As the level of urbanization continues to increase and the scale of road networks continues to grow,the traditional route query algorithms cannot meet the data size requirements of the big data era due to its limitations due to the challenges of dealing with large complex road networks and time-dependent road networks.Therefore,it is necessary to design efficient algorithms to solve the route query problem in the road network.In this paper,there are two kinds of dominant route queries in road network:the dominant path query in static road network and the multi-constraint dominant route queries in time-dependent road network.At the same time,with the increase of users' personalized needs,users are no longer satisfied with the single path recommendation of the existing online map path planning.Therefore,the problem studied in this paper considers the two dimensions of path cost and node score to find the dominant route set that are not dominated by other routes.Firstly,this paper introduces the multi-preference sequential path Skyline query problem and its related definitions in static road networks.Analyze the limitations of the existing construction weighting Voronoi diagram algorithm in the preprocessing and query process.In order to improve the efficiency of the algorithm,an accurate algorithm based on process dominance is proposed in this thesis.The upper bound value of the route cost containing the path with the minimum preference cost is estimated to be used to prune the subsequent route,and the efficiency of searching the dominant route is improved according to the route dominance relationship and A*algorithm.At the same time,based on the effectiveness of the algorithm,an approximation algorithm is proposed.Based on the approximation algorithm of keyword node weight clustering,the keyword nodes are selected under different weighting values,and the distance estimation method by quadtree index is adopted.Using the clustering operation and selecting the nodes make up the route for constructing the final dominant route.In this thesis,the complexity of the proposed algorithm is analyzed,and the comparison experiments of three real road network datasets in OpenStreetMap under different parameters prove the efficiency and effectiveness of the proposed algorithm.Secondly,this thesis proposes a multi-constrained dominate route query in time-dependent road networks.The given time depends on the starting and destination vetexs in the road network,the time threshold,and the sequence of keyword categories that are sequentially passed,and the calculation starts from the starting vetex at a specific time and sequentially passes through a given category sequence(such as a gas station,a restaurant,a shopping mall,etc.).The set of routes to the destination vetex that are not subject to other routes in terms of time consumption and keyword target score.In order to solve the query problem,a basic accurate algorithm BSL algorithm is proposed.The breadth-first traversal strategy is used to search all feasible routes,and then the final dominant route set is determined by the dominance relationship.In order to improve the efficiency of query,the road network cost upper and lower bound pruning algorithm TDER algorithm is proposed to construct the time-dependent and lower bound graphs of time-dependent road network,and the search space is reduced by pre-calculation method and pruning strategy.At the same time,FTDR is inspired by the observation that people normally do not backward during their journey.Experiments were carried out using the Beijing Road Network dataset to verify the running time of the algorithm under different parameter settings and the number of return paths to prove its validity.