Multi-Type Nearest Neighbor Queries Road Networks With Time Window Constraints

Date of Submission: 
September 14, 2009
Report Number: 
Report PDF: 
A multi-type nearest neighbor(MTNN) query finds the shortest tour for a given query point and different types of spatial features such that only one instance of each feature is visited during the tour. In a real life MTNN query a user normally needs an answer with specific start time and turn-by-turn route for specific period of time on road networks, which requires considerations of spatial and temporal features of the road network when designing algorithms. In this paper, we propose a label correcting algorithm that is based on a time aggregated multi-type graph, a special case of a time aggregated encoded path view. This algorithm gives the best start time, a turn-by-turn route and shortest path in terms of least travel time for a given query. Experimental results are provided to show the strength of our proposed algorithm and design decisions related to performance tuning.