Please use this identifier to cite or link to this item:
Title: The multi-rule partial sequenced route query
Authors: Chen, H.
Ku, W.-S.
Sun, M.-T.
Zimmermann, R. 
Keywords: Advanced traveler information systems
Location-based services
Issue Date: 2008
Citation: Chen, H.,Ku, W.-S.,Sun, M.-T.,Zimmermann, R. (2008). The multi-rule partial sequenced route query. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems : 65-74. ScholarBank@NUS Repository.
Abstract: Trip planning search (TPS) represents an important class of queries in Geographic Information Systems (GIS). In many real-world applications, TPS requests are issued with a number of constraints. Unfortunately, most of these constrained TPS cannot be directly answered by any of the existing algorithms. By formulating each restriction into rules, we propose a novel form of route query, namely the multi-rule partial sequenced route (MRPSR) query. Our work provides a unified framework that also subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. In this paper, we first prove that MRPSR is NP-hard and then present three heuristic algorithms to search for near-optimal solutions for the MRPSR query. Our extensive simulations show that all of the proposed algorithms can answer the MRPSR query effectively and efficiently. Using both real and synthetic datasets, we investigate the performance of our algorithms with the metrics of the route distance and the response time in terms of the percentage of the constrained points of interest (POI) categories. Compared to the LORD-based brute-force solution, the response times of our algorithms are remarkably reduced while the resulting route length is only slightly longer than the shortest route. Copyright 2008 ACM.
Source Title: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
ISBN: 9781605583235
DOI: 10.1145/1463434.1463448
Appears in Collections:Staff Publications

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


checked on Nov 16, 2018

Page view(s)

checked on May 19, 2018

Google ScholarTM



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