Research On Route Planning In Road Networks

With the increasing development of mobile internet in recent years,location-based services(LBS)are everywhere in our daily life.As a fundamental component in locationbased services,route/path planning provides routing services for our daily trip.However,different people has different routing requirements for different purposes,new route planning queries are called for to satisfy both personal and industry requirements.On the other hand,as the road network increases,classical route planning algorithms quite impractical in practice when applied to very large-scale,real-world road networks,we need to devise new routing algorithms to handle such large road networks.This dissertation proposes 3different and useful route planning queries based on different requirements,and devises efficient methods to solve these queries on large-scale,real-world road networks.Experimental results show that our methods are more effective and efficient than existing methods.The major contents and contributions of this dissertation are listed as follows.1.Popular route planning with travel cost estimation.With the increasing number of GPS-equipped vehicles,more and more trajectories are continuously generated,based on which some urban applications become feasible,such as route planning.In general,popular route that has been travelled frequently is a good choice,especially for people who are not familiar with the road networks.Moreover,an accurate estimation of the travel cost(such as travel time,fee and fuel)will benefit a wellscheduled trip plan.To this end,we study popular route planning with travel cost estimation based on trajectories.Specifically,given a source-destination pair and leaving time,we find the popular route from source to destination at the leaving and estimate its travel cost.Firstly,we propose a novel structure,called popular traverse graph,to summarize historical trajectories,where each node is a popular location,and each edge is a popular route between two locations.Subsequently,for each popular route in this graph,we use the minimum description length(MDL)principle to model the travel cost for each popular route at different time intervals,so that each time interval has a stable travel cost.Finally,based on the graph,for accurate travel cost estimation,we find the fastest popular route from source to destination at the leaving time in consideration of the optimal route concatenation which considers the dependencies between road segments.2.Finding top-k shortest paths with diversity.Classical top-k shortest paths problem(KSP)aims at finding the top-k shortest paths from given source and destination in a given graph,it plays an important role in many application domains,such as providing alternative paths for vehicle routing services.However,the returned k shortest paths may be highly similar,especially in large-scale road networks,i.e.,sharing significant amounts of edges,thus adversely affecting service qualities.In this dissertation,we formalize the K Shortest Paths with Diversity(KSPD)query that identifies top-k shortest paths from source to destination such that the paths are dissimilar with each other and the total length of the paths is minimized.We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that(1)it supports a wide variety of path similarity metrics which are widely adopted in the literature and(2)it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified.The core of the framework includes the use of two judiciously designed lower bounds,where one is dependent on and the other one is independent on the chosen path similarity metric,which effectively reduces the search space and significantly improves efficiency.3.Finding top-k optimal sequenced routes.Shortest sequenced route represents the constrained shortest route that visits at least one vertex from each of a set of specified vertex categories(e.g.,restaurants,shopping malls in road networks)in a specified order.This problem has many practical applications in different domains,such as route planing.However,the shortest sequenced route with the minimum total cost may not meet different personal preferences in some cases.Hence,the top-k shortest sequenced routes are called for,in which the most satisfying route can be selected according to his/her preferences.In this dissertation,we study finding the top-k optimal sequenced routes on general graphs.To efficiently find the top-k optimal sequenced routes,we propose two algorithms Pruning KOSR and Star KOSR.In Pruning KOSR,we define a dominance relationship between two partially-explored routes.The partially-explored routes that can be dominated by other partially-explored routes are postponed being extended,which leads to a smaller searching space and thus improves efficiency.In Star KOSR,we further improve the efficiency by extending routes in an A*manner.With the help of a judiciously designed heuristic estimation that works for general graphs,the cost of partially explored routes to the destination can be estimated such that the qualified complete routes can be found early.In addition,we demonstrate the high extensibility of the proposed algorithms by incorporating Hop Labeling,an effective label indexing technique for shortest path queries,to further improve efficiency.Furthermore,when k = 1,Star KOSR also outperforms the state-of-the-art method for the optimal sequenced route queries.In summary,this dissertation proposes 3 different route planning queries based on different scenarios,and devices specific solutions for these queries.Experiments on synthetic and real-world network datasets show the effectiveness and efficiency of proposed methods.Firstly,we propose popular route planning and travel cost estimation,these are basic routing services in our daily life.Then,for personal requirements,we consider top-k paths in routing and propose queries on top-k shortest paths with diversity and top-k optimal sequenced routes based on path diversity and different POIs,respectively.In future work,we plan to further extend our works to improve the efficiency and consider new route planning queries in terms of different scenarios and requirements.