caa a22 4500 445331836 CHVBK 20180317142740.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s10707-010-0115-2 doi (NATIONALLICENCE)springer-10.1007/s10707-010-0115-2 The partial sequenced route query with traveling rules in road networks [Elektronische Daten] [Haiquan Chen, Wei-Shinn Ku, Min-Te Sun, Roger Zimmermann] 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. Springer Science+Business Media, LLC, 2010 Advanced traveler information systems nationallicence Path search nationallicence Query processing nationallicence Location-based services nationallicence Chen Haiquan Department of Computer Science and Software Engineering, Auburn University, 36849, Auburn, AL, USA aut Ku Wei-Shinn Department of Computer Science and Software Engineering, Auburn University, 36849, Auburn, AL, USA aut Sun Min-Te Department of Computer Science and Information Engineering, National Central University, 320, Taoyuan, Taiwan aut Zimmermann Roger Department of Computer Science, National University of Singapore, 117590, Singapore, Singapore aut GeoInformatica Springer US; http://www.springer-ny.com 15/3(2011-07-01), 541-569 1384-6175 15:3<541 2011 15 10707 https://doi.org/10.1007/s10707-010-0115-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10707-010-0115-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Chen Haiquan Department of Computer Science and Software Engineering, Auburn University, 36849, Auburn, AL, USA aut NATIONALLICENCE 700 1- Ku Wei-Shinn Department of Computer Science and Software Engineering, Auburn University, 36849, Auburn, AL, USA aut NATIONALLICENCE 700 1- Sun Min-Te Department of Computer Science and Information Engineering, National Central University, 320, Taoyuan, Taiwan aut NATIONALLICENCE 700 1- Zimmermann Roger Department of Computer Science, National University of Singapore, 117590, Singapore, Singapore aut NATIONALLICENCE 773 0- GeoInformatica Springer US; http://www.springer-ny.com 15/3(2011-07-01), 541-569 1384-6175 15:3<541 2011 15 10707 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer