The partial sequenced route query with traveling rules in road networks |
| |
Authors: | Haiquan Chen Wei-Shinn Ku Min-Te Sun Roger Zimmermann |
| |
Affiliation: | (1) Department of Computer Science and Software Engineering, Auburn University, Auburn, AL 36849, USA;(2) Department of Computer Science and Information Engineering, National Central University, Taoyuan, 320, Taiwan;(3) Department of Computer Science, National University of Singapore, Singapore, 117590, Singapore |
| |
Abstract: | In modern geographic information systems, route search represents an important class of queries. In route search related applications,
users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling
rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule
partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR
query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route
(OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI)
with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP-hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend
all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance
of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively
and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution,
the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly
longer than the shortest route. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|