Multi-Type Nearest Neighbor Queries Road Networks With Time Window Constraints
2009-09-14
Title
Multi-Type Nearest Neighbor Queries Road Networks With Time Window Constraints
Authors
Published Date
2009-09-14
Publisher
Type
Report
Abstract
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Ma, Xiaobin; Shekhar, Shashi; Xiong, Hui. (2009). Multi-Type Nearest Neighbor Queries Road Networks With Time Window Constraints. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215811.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.