research-article

Heuristic algorithms for route-search queries over geographical data

Authors:

Yehoshua Sagiv,

Yerach DoytsherAuthors Info & Claims

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Article No.: 11, Pages 1 - 10

https://doi.org/10.1145/1463434.1463449

Published: 05 November 2008 Publication History

Abstract

In a geographical route search, given search terms, the goal is to find an effective route that (1) starts at a given location, (2) ends at a given location, and (3) travels via geographical entities that are relevant to the given terms. A route is effective if it does not exceed a given distance limit whereas the ranking scores of the visited entities, with respect to the search terms, are maximal. This paper introduces route-search queries, suggests three semantics for such queries and deals with the problem of efficiently answering queries under the different semantics. Since the problem of answering route-search queries is a generalization of the traveling salesman problem, it is unlikely to have an efficient solution, i.e., there is no polynomial-time algorithm that solves the problem (unless P=NP). Hence, in this work we consider heuristics for the problem. Methods for effectively computing routes are presented. The methods are compared analytically and experimentally. For these methods, experiments on both synthetic and real-world data illustrate their efficiency and their effectiveness in computing a route that satisfies the constraints of a route-search query.

References

[1]

R. Armstrong, D. Kung, P. Sinha, and A. Zoltners. A computational study of a multiple-choice knapsack algorithm. ACM Transactions on Mathematical Software, 9:184--198, 1983.

Digital Library

[2]

I. Chao, B. Golden, and E. Wasil. A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3):475--489, 1996.

[3]

I. Chao, B. Golden, and E. Wasil. The team orienteering problem. European Journal of Operational Research, 88:464--474, 1996.

[4]

A. G. Chentsov and L. N. Korotayeva. The dynamic programming method in the generalized traveling salesman problem. Mathematical and Computer Modeling, 25(1):93--105, 1997.

Digital Library

[5]

M. Dyer. An o(n) algorithm for the multiple-choice knapsack linear program. Mathematical Programming, 29:57--63, 1984.

Digital Library

[6]

M. Dyer, N. Kayal, and J. Walker. A branch and bound algorithm for solving the multiple choice knapsack problem. IJCAM, 11:231--249, 1984.

[7]

M. Fischetti, J. J. Salazar-González, and P. Toth. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45(3):378--394, 1997.

Digital Library

[8]

B. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34:307--318, 1987.

[9]

B. Golden, Q. Wang, and L. Liu. A multifaceted heuristic for the orienteering problem. Naval Research Logistics, 35:359--366, 1988.

[10]

A. Henry-Labordere. The record balancing problem - a dynamic programming solution of a generalized traveling salesman problem. Revue Francaise D Informatique DeRecherche Operationnelle, 2:43--49, 1969.

[11]

S. Jones, S. Walker, and S. Robertson. A probabilistic model of information retrieval: Development and comparative experiments (parts 1 and 2). Information Processing and Management, 36(6):779--840, 2000.

Digital Library

[12]

P. Keller. Algorithms to solve the orienteering problem: A comparison. European Journal of Operational Research, 41:224--231, 1989.

[13]

G. Laporte, A. Asef-Vaziri, and C. Sriskandarajah. Some applications of the generalized traveling salesman problem. Journal of the Operational Research Society, 47(12):1461--1467, 1996.

[14]

G. Laporte, H. Mercure, and Y. Nobert. Finding the shortest hamiltonian circuit through n clusters: A lagrangian approach. Congressus Numerantium, 48:277--290, 1985.

[15]

G. Laporte and Y. Nobert. Generalized traveling salesman problem through n-sets of nodes - an integer programming approach. INFOR, 21(1):61--75, 1983.

[16]

A. Leifer and M. Rosenwein. Strong linear programming relaxations for the orienteering problem. European Journal of Operational Research, 73:517--523, 1994.

[17]

Y. Lien, E. Ma, and B. W. S. Wah. Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem. Information Sciences, 74(1--2):177--189, 1993.

Digital Library

[18]

C. E. Noon and J. C. Bean. A lagrangian based approach for the asymmetric generalized traveling salesman problem. Operations Research, 39(4):623--632, 1991.

Digital Library

[19]

D. Pisinger. A minimal algorithm for the multiple-choice knapsack problem. European Journal of Operational Research, 83(2):394--410, 1995.

[20]

R. Ramesh, Y. Yoon, and M. Karwan. An optimal algorithm for the orienteering tour problem. ORSA Journal on Computing, 4(2):155--165, 1992.

[21]

S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at trec-3. In Proc. of the Text REtrieval Conference (TREC-3), pages 109--126, Gaithersburg, USA, 1994.

[22]

G. Salton and M. McGill. Introduction to modern information retrieval. McGraw-Hill, 1983.

Digital Library

[23]

H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In ACM SIGMOD, pages 43--54, 2008.

Digital Library

[24]

J. P. Saskena. Mathematical model for scheduling clients through welfare agencies. J. of the Canadian Operational Research Society, 8:185--200, 1970.

[25]

C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica, 7(3):255--273, 2003.

Digital Library

[26]

P. Sinha and A. Zoltners. The multiple-choice knapsack problem. Operations Research, 27(3):503--515, 1979.

Digital Library

[27]

L. V. Snyder and M. S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational research, 174:38--53, 2006.

[28]

S. S. Srivastava, S. Kumar, R. C. Garg, and P. Sen. Generalized traveling salesman problem through n sets of nodes. Journal of the Canadian Operational Research Society, 7:97--101, 1969.

[29]

T. Tsiligirides. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9):797--809, 1984.

[30]

E. Zemel. An o(n) algorithm for the linear multiple choice knapsack problem and related problems. Information Processing Letters, 18:123--128, 1984.

Digital Library

Cited By

Israr AAli ZAlkhammash EJussila J(2022)Optimization Methods Applied to Motion Planning of Unmanned Aerial Vehicles: A ReviewDrones10.3390/drones60501266:5(126)Online publication date: 13-May-2022
https://doi.org/10.3390/drones6050126
Chen ZChen LCong GJensen C(2021)Location- and keyword-based querying of geo-textual data: a surveyThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00661-w30:4(603-640)Online publication date: 30-Mar-2021
https://dl.acm.org/doi/10.1007/s00778-021-00661-w
Feng ZLiu TLi HLu HShou LXu J(2020)Indoor Top-k Keyword-aware Routing Query2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00109(1213-1224)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00109
Show More Cited By

Index Terms

Heuristic algorithms for route-search queries over geographical data
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Spatial-temporal systems

Recommendations

An interactive approach to route search
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

In a probabilistic route search, there is a start location, a target location, and search queries Q₁, ..., Q_n. Each Q_i has an answer set A_i consisting of geo-spatial objects and their probabilities. The probability of an object o ∈ A_i specifies the ...
Interactive route search in the presence of order constraints

A route search is an enhancement of an ordinary geographic search. Instead of merely returning a set of entities, the result is a route that goes via entities that are relevant to the search. The input to the problem consists of several search queries, ...
Detecting dominant locations from search queries
SIGIR '05: Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval

Accurately and effectively detecting the locations where search queries are truly about has huge potential impact on increasing search relevance. In this paper, we define a search query's dominant location (QDL) and propose a solution to correctly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

November 2008

559 pages

ISBN:9781605583235

DOI:10.1145/1463434

Program Chairs:
Walid G. Aref
Purdue University
,
Mohamed F. Mokbel
University of Minnesota
,
Markus Schneider
University of Florida

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ESRI
Google Inc.
Oak Ridge National Laboratory
Microsoft: Microsoft
SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GIS '08

Sponsor:

Microsoft
SIGSPATIAL

GIS '08: 16th International Symposium on Advances in Geographic Information Systems

November 5 - 7, 2008

California, Irvine

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
435
Total Downloads

Downloads (Last 12 months)13
Downloads (Last 6 weeks)5

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Israr AAli ZAlkhammash EJussila J(2022)Optimization Methods Applied to Motion Planning of Unmanned Aerial Vehicles: A ReviewDrones10.3390/drones60501266:5(126)Online publication date: 13-May-2022
https://doi.org/10.3390/drones6050126
Chen ZChen LCong GJensen C(2021)Location- and keyword-based querying of geo-textual data: a surveyThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-021-00661-w30:4(603-640)Online publication date: 30-Mar-2021
https://dl.acm.org/doi/10.1007/s00778-021-00661-w
Feng ZLiu TLi HLu HShou LXu J(2020)Indoor Top-k Keyword-aware Routing Query2020 IEEE 36th International Conference on Data Engineering (ICDE)10.1109/ICDE48307.2020.00109(1213-1224)Online publication date: Apr-2020
https://doi.org/10.1109/ICDE48307.2020.00109
Vijaya Babu KYalawar MMaddela P(2020)An Clue-Based Route Search on Road Networks Using Keywords and Spatial RelationsICCCE 202010.1007/978-981-15-7961-5_28(287-297)Online publication date: 12-Oct-2020
https://doi.org/10.1007/978-981-15-7961-5_28
Yang YLi SSun KDi X(2020)Design of Route Search Algorithm Based on Station Map Information and Depth-First-SearchProceedings of the 4th International Conference on Electrical and Information Technologies for Rail Transportation (EITRT) 201910.1007/978-981-15-2914-6_9(79-86)Online publication date: 2-Apr-2020
https://doi.org/10.1007/978-981-15-2914-6_9
Zheng BSu HHua WZheng KZhou XLi G(2017)Efficient Clue-Based Route Search on Road NetworksIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.270384829:9(1846-1859)Online publication date: 1-Sep-2017
https://doi.org/10.1109/TKDE.2017.2703848
Bolzoni PPersia FHelmer S(2017)Itinerary Planning with Category Constraints Using a Probabilistic ApproachDatabase and Expert Systems Applications10.1007/978-3-319-64471-4_29(363-377)Online publication date: 2-Aug-2017
https://doi.org/10.1007/978-3-319-64471-4_29
Fan LBonomi LShahabi CXiong L(2017)Multi-user Itinerary Planning for Optimal Group PreferenceAdvances in Spatial and Temporal Databases10.1007/978-3-319-64367-0_1(3-23)Online publication date: 22-Jul-2017
https://doi.org/10.1007/978-3-319-64367-0_1
Johnson TKanza YLakshmanan LShkapenyuk VArora ARoy SMehta S(2016)NepalProceedings of the 1st ACM SIGMOD Workshop on Network Data Analytics10.1145/2980523.2980530(1-8)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1145/2980523.2980530
Kanza YSamet HAli MHuang YGertz MRenz MSankaranarayanan J(2015)An online marketplace for geosocial dataProceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2820783.2820881(1-4)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2820783.2820881
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents