Abstract
Finding the shortest paths in road networks has been studied for years. However, from the perspective of a user, finding the shortest path from a start location to a destination is only a basic requirement. Other demands may also be involved, such as asking for dining or mailing on the way to the destination. In this paper, we consider a novel problem of finding the shortest path which satisfies the user requirement represented as a set of points of interest such as a shopping center or a restaurant. Three main approaches are proposed to deal with this problem. The first two basic approaches answer the queries without and with a destination by using the BFS and DFS based algorithms, respectively. Moreover, we design some pruning strategies for reducing the search space of the paths and then propose another advanced approach. The experiment results show that the advanced approach has great performance in terms of executing time.