Milling the shortest path within a travel time constraint in road network environments

In recent years, a number of studies have been done on GPS (Global Positioning System) due to the wide applications. One important research issue is on the GPS navigation. In this paper, we propose a novel data mining algorithm named PA TE (Prediction-based Algorithm for Travel time Evaluation) that can efficiently predict the travel time of a navigation path and precisely recommends the navigation path to the users under a user-specified travel time constraint in road network environments. To our best knowledge, this is the first work on discovering the shortest navigation path within a travel time constraint. Furthermore, we propose a novel search structure named NPST (Navigation Path Search Tree) for efficiently finding the shortest navigation path that meets the user-specified travel time constraint Through a series of experiments, the proposed method was shown to have excellent performance under different system conditions.