research-article

Parameterized algorithms for generalized traveling salesman problems in road networks

Authors:

Michael N. Rice,

Vassilis J. TsotrasAuthors Info & Claims

SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Pages 114 - 123

https://doi.org/10.1145/2525314.2525342

Published: 05 November 2013 Publication History

Abstract

The Generalized Traveling Salesman (Path) Problem involves finding a minimum-cost tour (or path) through exactly one location from each of a set of generalized location categories (e.g., gas stations, coffee shops). This problem type has many practical applications in personal navigation and logistics. While NP-hard in general, this problem also admits fixed-parameter tractable (FPT) algorithms with run times of the form f(k)n^O(1) for some function f (independent of the problem size, n) with respect to the number of location categories, k (typically very small in practice). We present both exact and approximate FPT algorithms for this problem. Experimental results on the road network of North America (with over 50 million edges) show that we can optimally solve nationwide queries with up to 7 categories and millions of optional category locations in sub-second time. Our approximate solutions improve this even further down to millisecond query times, resulting in only negligible relative error with respect to optimality, on average.

References

[1]

E. M. Arkin and R. Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics, 55(3):197--218, 1994.

Digital Library

[2]

A. Behzad and M. Modarres. A new efficient transformation of generalized traveling salesman problem into traveling salesman problem. In Proc. of 15th ICSE, 2002.

[3]

V. Cacchiani, A. E. F. Muritiba, M. Negreiros, and P. Toth. A multistart heuristic for the equality generalized traveling salesman problem. Networks, 57(3):231--239, 2011.

Digital Library

[4]

E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.

Digital Library

[5]

V. Dimitrijevic and Z. Saric. An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs. Inf. Sci., 102(1-4):105--110, 1997.

Digital Library

[6]

R. G. Downey and M. R. Fellows. Parameterized Complexity (Monographs in Computer Science). Springer, November 1998.

[7]

A. Dumitrescu and J. S. B. Mitchell. Approximation algorithms for TSP with neighborhoods in the plane. In SODA, pages 38--46, 2001.

Digital Library

[8]

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

Digital Library

[9]

J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, March 2006.

[10]

R. Geisberger, P. Sanders, D. Schultes, and D. Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In WEA, pages 319--333, 2008.

Digital Library

[11]

J. Gudmundsson and C. Levcopoulos. A fast approximation algorithm for TSP with neighborhoods and red-blue separation. In COCOON, pages 473--482, 1999.

Digital Library

[12]

P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. In IEEE Transactions on System Science and Cybernetics, volume 4, 1968.

[13]

A. L. Henry-Labordere. The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem. RIRO, B-2:43--49, 1969.

[14]

G. Laporte, H. Mercure, and Y. Nobert. Generalized travelling salesman problem through n sets of nodes: The asymmetrical case. Discrete Applied Mathematics, 18(2):185--197, 1987.

[15]

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

[16]

F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In SSTD, pages 273--290, 2005.

Digital Library

[17]

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

Digital Library

[18]

C. S. Mata and J. S. B. Mitchell. Approximation algorithms for geometric tour and network design problems (extended abstract). In Symposium on Computational Geometry, pages 360--369, 1995.

Digital Library

[19]

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

[20]

I. Pohl. Bidirectional Heuristic Search in Path Problems. PhD thesis, Stanford University, 1969.

Digital Library

[21]

P. C. Pop, C. P. Sitar, I. Zelina, and I. Tascu. Exact algorithms for generalized combinatorial optimization problems. In COCOA, pages 154--162, 2007.

Digital Library

[22]

M. N. Rice and V. J. Tsotras. Exact graph search algorithms for generalized traveling salesman path problems. In SEA, pages 344--355, 2012.

Digital Library

[23]

M. N. Rice and V. J. Tsotras. Engineering generalized shortest path queries. In ICDE, pages 949--960, 2013.

Digital Library

[24]

S. Safra and O. Schwartz. On the complexity of approximating TSP with neighborhoods and related problems. In ESA, pages 446--458, 2003.

[25]

J. P. Saksena. Mathematical model of scheduling clients through welfare agencies. CORS Journal, 8:185--200, 1970.

[26]

P. Slavik. The errand scheduling problem. Technical Report 97-2, Department of Computer Science, SUNY, Buffalo NY, March 1997.

[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(1):38--53, 2006.

[28]

S. S. Srivastava, S. Kumar, R. C. Garg, and P. Sen. Generalized travelling salesman problem through n sets of nodes. CORS Journal, 7:97--101, 1969.

Cited By

Lyu YLee VNg JLim BLiu KChen C(2019)Flexi-Sharing: A Flexible and Personalized Taxi-Sharing SystemIEEE Transactions on Vehicular Technology10.1109/TVT.2019.2932869(1-1)Online publication date: 2019
https://doi.org/10.1109/TVT.2019.2932869
Kaffes VBelesiotis ASkoutas DSkiadopoulos SSacharidis DGamper JBöhlen M(2018)Finding shortest keyword covering routes in road networksProceedings of the 30th International Conference on Scientific and Statistical Database Management10.1145/3221269.3223038(1-12)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3221269.3223038
Cuchy MStolba MJakob M(2018)Benefits of Multi-Destination Travel Planning for Electric Vehicles2018 21st International Conference on Intelligent Transportation Systems (ITSC)10.1109/ITSC.2018.8569385(327-332)Online publication date: Nov-2018
https://doi.org/10.1109/ITSC.2018.8569385
Show More Cited By

Index Terms

Parameterized algorithms for generalized traveling salesman problems in road networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
Abstract
We consider the geometric version of the well-known Generalized Traveling Salesman Problem introduced in 2015 by Bhattacharya et al. that is called the Euclidean Generalized Traveling Salesman Problem in Grid Clusters (EGTSP-GC). They proved the ...
Polynomial Turing Compressions for Some Graph Problems Parameterized by Modular-Width
Computing and Combinatorics
Abstract
A polynomial Turing compression (PTC) for a parameterized problem L is a polynomial-time Turing machine that has access to an oracle for a problem $L^{'}$ such that a polynomial in the input parameter bounds each query. Meanwhile, a polynomial (many-...
Parameterized complexity of the k-arc Chinese Postman Problem

In the Mixed Chinese Postman Problem (MCPP), given an edge-weighted mixed graph G (G may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 2013

598 pages

ISBN:9781450325219

DOI:10.1145/2525314

General Chairs:
Craig Knoblock
University of Southern California
,
Markus Schneider
University of Florida
,
Program Chairs:
Peer Kröger
Ludwig-Maximilians-Universität München, Germany
,
John Krumm
Microsoft Research
,
Peter Widmayer
ETH Zürich, Switzerland

Copyright © 2013 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

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Information and Intelligent Systems

Conference

SIGSPATIAL'13

Sponsor:

SIGSPATIAL

SIGSPATIAL'13: 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 5 - 8, 2013

Florida, Orlando

Acceptance Rates

Overall Acceptance Rate 220 of 1,116 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
463
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lyu YLee VNg JLim BLiu KChen C(2019)Flexi-Sharing: A Flexible and Personalized Taxi-Sharing SystemIEEE Transactions on Vehicular Technology10.1109/TVT.2019.2932869(1-1)Online publication date: 2019
https://doi.org/10.1109/TVT.2019.2932869
Kaffes VBelesiotis ASkoutas DSkiadopoulos SSacharidis DGamper JBöhlen M(2018)Finding shortest keyword covering routes in road networksProceedings of the 30th International Conference on Scientific and Statistical Database Management10.1145/3221269.3223038(1-12)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3221269.3223038
Cuchy MStolba MJakob M(2018)Benefits of Multi-Destination Travel Planning for Electric Vehicles2018 21st International Conference on Intelligent Transportation Systems (ITSC)10.1109/ITSC.2018.8569385(327-332)Online publication date: Nov-2018
https://doi.org/10.1109/ITSC.2018.8569385
Liu HJin CYang BZhou A(2018)Finding Top-k Optimal Sequenced Routes2018 IEEE 34th International Conference on Data Engineering (ICDE)10.1109/ICDE.2018.00058(569-580)Online publication date: Apr-2018
https://doi.org/10.1109/ICDE.2018.00058
Cuchý MŠtolba MJakob M(2018)Integrated Route, Charging and Activity Planning for Whole Day Mobility with Electric VehiclesAgents and Artificial Intelligence10.1007/978-3-030-05453-3_13(274-289)Online publication date: 30-Dec-2018
https://doi.org/10.1007/978-3-030-05453-3_13
Hsueh YZimmermann R(2018)Trip Planning QueriesEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_80712(4229-4235)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_80712
Uddin RRice MRavishankar CTsotras V(2017)Assembly QueriesProceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3139958.3139993(1-10)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3139958.3139993
Li WCao JGuan JYiu MZhou S(2017)Efficient Retrieval of Bounded-Cost Informative RoutesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.272140829:10(2182-2196)Online publication date: 1-Oct-2017
https://doi.org/10.1109/TKDE.2017.2721408
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
Bolzoni PHelmer S(2017)Hybrid Best-First Greedy Search for Orienteering with Category ConstraintsAdvances in Spatial and Temporal Databases10.1007/978-3-319-64367-0_2(24-42)Online publication date: 22-Jul-2017
https://doi.org/10.1007/978-3-319-64367-0_2
Show More Cited By

View Options

Get Access

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