Michael N. Rice
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)nO(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.
- E. M. Arkin and R. Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics, 55(3):197--218, 1994. Google Scholar
Digital Library
- A. Behzad and M. Modarres. A new efficient transformation of generalized traveling salesman problem into traveling salesman problem. In Proc. of 15th ICSE, 2002.Google Scholar
- 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. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. G. Downey and M. R. Fellows. Parameterized Complexity (Monographs in Computer Science). Springer, November 1998.Google Scholar
- A. Dumitrescu and J. S. B. Mitchell. Approximation algorithms for TSP with neighborhoods in the plane. In SODA, pages 38--46, 2001. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- J. Flum and M. Grohe. Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series). Springer, March 2006. Google ScholarCross Ref
- 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. Google ScholarDigital Library
- J. Gudmundsson and C. Levcopoulos. A fast approximation algorithm for TSP with neighborhoods and red-blue separation. In COCOON, pages 473--482, 1999. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- A. L. Henry-Labordere. The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem. RIRO, B-2:43--49, 1969.Google Scholar
- 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.Google ScholarCross Ref
- G. Laporte and Y. Nobert. Generalized travelling salesman problem through n sets of nodes: An integer programming approach. INFOR, 21(1):61--75, 1983.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- I. Pohl. Bidirectional Heuristic Search in Path Problems. PhD thesis, Stanford University, 1969. Google ScholarDigital Library
- P. C. Pop, C. P. Sitar, I. Zelina, and I. Tascu. Exact algorithms for generalized combinatorial optimization problems. In COCOA, pages 154--162, 2007. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Exact graph search algorithms for generalized traveling salesman path problems. In SEA, pages 344--355, 2012. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Engineering generalized shortest path queries. In ICDE, pages 949--960, 2013. Google ScholarDigital Library
- S. Safra and O. Schwartz. On the complexity of approximating TSP with neighborhoods and related problems. In ESA, pages 446--458, 2003.Google ScholarCross Ref
- J. P. Saksena. Mathematical model of scheduling clients through welfare agencies. CORS Journal, 8:185--200, 1970.Google Scholar
- P. Slavik. The errand scheduling problem. Technical Report 97-2, Department of Computer Science, SUNY, Buffalo NY, March 1997.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
Index Terms
- Parameterized algorithms for generalized traveling salesman problems in road networks
Recommendations
Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
AbstractWe 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 CombinatoricsAbstractA polynomial Turing compression (PTC) for a parameterized problem L is a polynomial-time Turing machine that has access to an oracle for a problem 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