Heuristic algorithms for route-search queries over geographical data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Heuristic algorithms for route-search queries over geographical data

Full text

Pdf (415 KB)

Source

Geographic Information Systems archive
Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems table of contents

Irvine, California

SESSION: Route finding and road networks table of contents

Article No. 11

Year of Publication: 2008

ISBN:978-1-60558-323-5

Authors

Yaron Kanza	Technion, Haifa, Israel
Eliyahu Safra	ESRI, Redlands, CA
Yehoshua Sagiv	Hebrew University, Jerusalem, Israel
Yerach Doytsher	Technion, Haifa, Israel

Sponsors

: Google
: Oak Ridge National Laboratory
: ESRI
Microsoft : Microsoft

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 16, Downloads (12 Months): 164, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1463434.1463449 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. D. Armstrong , D. S. Kung , P. Sinha , A. A. Zoltners, A computational study of a multiple-choice knapsack algorithm, ACM Transactions on Mathematical Software (TOMS), v.9 n.2, p.184-198, June 1983 [doi>10.1145/357456.357458]
	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.
	5	M. Dyer. An o(n) algorithm for the multiple-choice knapsack linear program. Mathematical Programming, 29:57--63, 1984.
	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.
	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	K. Sparck Jones , S. Walker , S. E. Robertson, A probabilistic model of information retrieval: development and comparative experiments, Information Processing and Management: an International Journal, v.36 n.6, p.779-808, Nov.06.2000 [doi>10.1016/S0306-4573(00)00015-7]
	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	Yao-Nan Lien , Eva Ma , Benjamin W. S. Wah, Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem, Information Sciences: an International Journal, v.74 n.1-2, p.177-189, Oct. 15, 1993 [doi>10.1016/0020-0255(93)90133-7]
	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.
	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	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	23	Hanan Samet , Jagan Sankaranarayanan , Houman Alborzi, Scalable network distance browsing in spatial databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376623]
	24	J. P. Saskena. Mathematical model for scheduling clients through welfare agencies. J. of the Canadian Operational Research Society, 8:185--200, 1970.
	25	Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases, Geoinformatica, v.7 n.3, p.255-273, September 2003 [doi>10.1023/A:1025153016110]
	26	P. Sinha and A. Zoltners. The multiple-choice knapsack problem. Operations Research, 27(3):503--515, 1979.
	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	Eitan Zemel, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, Information Processing Letters, v.18 n.3, p.123-128, March 1984 [doi>10.1016/0020-0190(84)90014-0]