Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10707-010-0115-2
Title: The partial sequenced route query with traveling rules in road networks
Authors: Chen, H.
Ku, W.-S.
Sun, M.-T.
Zimmermann, R. 
Keywords: Advanced traveler information systems
Location-based services
Path search
Query processing
Issue Date: 2011
Citation: Chen, H., Ku, W.-S., Sun, M.-T., Zimmermann, R. (2011). The partial sequenced route query with traveling rules in road networks. GeoInformatica 15 (3) : 541-569. ScholarBank@NUS Repository. https://doi.org/10.1007/s10707-010-0115-2
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. © 2010 Springer Science+Business Media, LLC.
Source Title: GeoInformatica
URI: http://scholarbank.nus.edu.sg/handle/10635/39789
ISSN: 13846175
DOI: 10.1007/s10707-010-0115-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

21
checked on Aug 17, 2018

WEB OF SCIENCETM
Citations

11
checked on Jun 27, 2018

Page view(s)

58
checked on May 12, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.