Rating-aware Route Planning In Road Network

With the development of mobile web and geo-positioning technologies, Location-Based Services(LBS) have been widely studied and applied in people’s daily life.As we know, experts at home and abroad have achieved lots of goals concerning route planning, however, there still exist some shortages. Further researches are needed to meet people’ s incessantly emerging, complex and diverse needs.Now, a big challenge arises in route planning because of the increasing data in road network. The existing methods are not good at solving a NP-Complete problem. Besides,taking into consideration the rating requirements of POI( point of interest), it will become more complicated and consume too much time, as a result, it does not well benefit users.The thesis processes data of road network according to the characteristics of POI. Our works concludes the following major aspects:(1) we have analyzed the exiting work about the shortest path algorithm and query methods over road networks. By comparing advantages and disadvantage of algorithms, we mainly use A* and bi-direction dijkstra algorithms to process the problem.(2) we introduce two method about dealing with large road network: 1.we utilize basic candidate selection to reduce query space in order to improve the e?ciency; 2.we firstly cluster the nodes in the network to speed up our work.(3) We propose a new problem called rating-aware route planning in route network.Before and after spatial query optimization, we propose several algorithms to solve the problem.(4) we carry out empirical experiments on semi-real data to evaluate the solutions of route planning based on ranking. we compare the result of several solutions to select the best one.In this thesis, we have a research on route planning algorithm based on rating and its applications. It turns out that this algorithm possesses an important practical significance:it not only extends the practicality of route planning algorithm but also can serve as reference to related researches.