×

Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem. (English) Zbl 1208.90148

Summary: The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems.
In this paper, we discuss possible adaptations of TSP heuristics for the generalized traveling salesman problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then, we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics.
It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Balas, E.; Saltzman, M.J., An algorithm for the three-index assignment problem, Operations research, 39, 150-161, (1991) · Zbl 0743.90079
[2] Ben-Arieh, D.; Gutin, G.; Penn, M.; Yeo, A.; Zverovitch, A., Transformations of generalized ATSP into ATSP, Operations research letters, 31, 357-365, (2003) · Zbl 1033.90097
[3] Bontoux, B.; Artigues, C.; Feillet, D., A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem, Computers & operations research, 37, 1844-1852, (2010) · Zbl 1188.90263
[4] Chandra, B., Karloff, H., Tovey, C., 1994. New results on the old k-opt algorithm for the TSP. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 150-159. · Zbl 0867.90113
[5] Fischetti, M.; Salazar González, J.J.; Toth, P., The symmetric generalized traveling salesman polytope, Networks, 26, 113-123, (1995) · Zbl 0856.90116
[6] Fischetti, M.; Salazar González, J.J.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations research, 45, 378-394, (1997) · Zbl 0893.90164
[7] Gutin, G.; Karapetyan, D., A memetic algorithm for the generalized traveling salesman problem, Natural computing, 9, 47-60, (2010) · Zbl 1206.90144
[8] Gutin, G., Karapetyan, D., Krasnogor, N., 2008. A memetic algorithm for the generalized asymmetric traveling salesman problem. In: Nature Inspired Cooperative Strategies for Optimization (NICSO 2007), pp. 199-210.
[9] Helsgaun, K., An effective implementation of the lin – kernighan traveling salesman heuristic, European journal of operational research, 126, 106-130, (2000) · Zbl 0969.90073
[10] Helsgaun, K., General k-opt submoves for the lin – kernighan TSP heuristic, Mathematics and statistics, 1, 119-163, (2009) · Zbl 1180.90269
[11] Hu, B., Raidl, G.R., 2008. Effective neighborhood structures for the generalized traveling salesman problem, In: Proceedings of EvoCOP 2008, pp. 36-47.
[12] Huang, H., Yang, X., Hao, Z., Wu, C., Liang, Y., Zhao, X., 2005. Hybrid chromosome genetic algorithm for generalized traveling salesman problems. In: Proceedings of ICNC 2005, pp. 137-140.
[13] Johnson, D.S.; McGeoch, L.A., Experimental analysis of heuristics for the STSP, (), 369-444 · Zbl 1113.90356
[14] Karapetyan, D., Gutin, G., in press. Local search heuristics for the multidimensional assignment problem. Journal of Heuristics (A preliminary version is published in Lecture Notes in Computer Science, vol. 5420, 2009, pp. 100-115). doi:10.1007/s10732-010-9133-3. · Zbl 1194.68209
[15] Laporte, G.; Asef-Vaziri, A.; Sriskandarajah, C., Some applications of the generalized travelling salesman problem, The journal of the operational research society, 47, 1461-1467, (1996) · Zbl 0873.90104
[16] Laporte, G.; Semet, F., Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem, Infor, 37, 114-120, (1999)
[17] Lin, S.; Kernighan, B.W., An effective heuristic algorithm for the traveling-salesman problem, Operations research, 21, 498-516, (1973) · Zbl 0256.90038
[18] Noon, C.E., 1988. The Generalized Traveling Salesman Problem. Ph.D. thesis. University of Michigan.
[19] Noon, C.E.; Bean, J.C., A Lagrangian based approach for the asymmetric generalized traveling salesman problem, Operations research, 39, 623-632, (1991) · Zbl 0741.90086
[20] Noon, C.E.; Bean, J.C., An efficient transformation of the generalized traveling salesman problem, Infor, 31, 39-44, (1993) · Zbl 0774.90085
[21] Pintea, C.; Pop, P.; Chira, C., The generalized traveling salesman problem solved with ant algorithms, Journal of universal computer science, 13, 1065-1075, (2007)
[22] Pop, P.C., New integer programming formulations of the generalized traveling salesman problem, American journal of applied sciences, 4, 932-937, (2007)
[23] Pop, P.C.; Kern, W.; Still, G., A new relaxation method for the generalized minimum spanning tree problem, European journal of operational research, 170, 900-908, (2006) · Zbl 1091.90068
[24] Rego, C.; Glover, F., Local search and metaheuristics, (), 309-368 · Zbl 1113.90370
[25] Reinelt, G., TSPLIB - a traveling salesman problem library, ORSA journal on computing, 3, 376-384, (1991) · Zbl 0775.90293
[26] Renaud, J.; Boctor, F.F., An efficient composite heuristic for the symmetric generalized traveling salesman problem, European journal of operational research, 108, 571-584, (1998) · Zbl 0944.90068
[27] Silberholz, J., Golden, B.L., 2007. The generalized traveling salesman problem: A new genetic algorithm approach. In: Extending the Horizons: Advances in Computing Optimization, and Decision Technologies. Springer, pp. 165-181. · Zbl 1278.90346
[28] Snyder, L.; Daskin, M., A random-key genetic algorithm for the generalized traveling salesman problem, European journal of operational research, 174, 38-53, (2006) · Zbl 1116.90091
[29] Tasgetiren, M., Suganthan, P.N., Pan, Q.Q., 2007. A discrete particle swarm optimization algorithm for the generalized traveling salesman problem. In: Proceedings of GECCO 2007, pp. 158-167.
[30] Tasgetiren, M.F.; Suganthan, P.; Pan, Q.K., An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem, Applied mathematics and computation, 215, 3356-3368, (2010) · Zbl 1183.65071
[31] Yang, J.; Shi, X.; Marchese, M.; Liang, Y., An ant colony optimization method for generalized tsp problem, Progress in natural science, 18, 1417-1422, (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.