Keywords and Stops Aware Optimal Routes on Road Networks

Recently, the keyword-aware routing problem has been increasingly studied, which is to return the optimal route from the starting point s to the destination t, satisfying all the user-specified keyword requirements. Most existing solutions focus only on the travel cost (distance or time) of the route and do not take into account the number of stops required to meet the keyword service. However, parking more often can degrade the user experience, as finding a parking space in a city is difficult and time-consuming. In this paper, we study the Keywords and Stops aware Optimal Routes (KSOR) problem, which finds a set of non-dominated routes with minimum distance and minimum number of stops. It is non-trivial to search such routes because the newly added Point of Interest (POI) may reduce the stops when expanding the road network, which poses challenges for pruning the partial routes. To avoid this dilemma, we first utilize a spatial index to find the potential POIs around the shortest path from s to t. To efficiently combine these POIs for generating valid routes, we propose two route generation methods. The light enumeration method prune the range of enumerated route combinations by the calculated lower and upper bounds of the stops. And the weighted calculation method generates routes by calculating the optimal combination of POIs under different weights of distance and stops. Extensive experiments conducted on real road networks show that the proposed methods are more efficient.