Abstract
How to efficiently find the fastest path between two given positions is an important topic in road networks. However, previous works can’t help users to choose the path that must across certain kinds of intermediate positions by considering heterogeneous travel costs. For example, the user may need a parking lot on the way to the restaurant, and both of the driving time and walk time are concerned. In addition, the traffic conditions often vary as time goes by. A chosen departure time for the travel can significantly reduce the related travel costs. These real requirements motivate us to study the issue of fast paths recommendation, which list all the advantageous intermediate positions and the corresponding paths for the user to select. In this paper, we propose a novel approach to solve this problem by applying the extended skyline techniques on all possible time sub-intervals for the final answers. For better performance, two bounds in road networks, i.e., the travel time lower bound and the travel time lower bound in time interval are introduced. We use the travel time lower bound to prune useless intermediate nodes by using a maximal speed in road network to restrict the search space. Then, the travel time lower bound in time interval is adopted to reduce computation of the fast paths for intermediate nodes by using a lower maximal speed in a time interval to diminish the search time. A series of experiments are performed to demonstrate that the proposed approaches based on the two bounds are more effective and efficient than the straightforward method for the fast paths recommendation.