Abstract
We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem. John Wiley & Sons, Chichester (1985)
Cheeseman, P., Kanefsky, B., Taylor, W.: Where the really hard problems are. In: Proceedings of IJCAI 1991 (1991)
Beck, J., Prosser, P., Selensky, E.: Vehicle routing and job shop scheduling: What’s the difference? In: Proc. of the 13th International Conference on Automated Planning & Scheduling (2003)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic phase transitions. Nature 400, 133–137 (1999)
Hayes, B.: Can’t get no satisfaction. American Scientist 85, 108–112 (1997)
Hogg, T.: Refining the phase transition in combinatorial search. Artificial Intelligence 81, 127–154 (1996)
Culberson, J., Gent, I.: Well out of reach: why hard problems are hard. Technical report, APES Research Group (1999)
van Hemert, J.: Evolving binary constraint satisfaction problem instances that are difficult to solve. In: Proceedings of the IEEE 2003 Congress on Evolutionary Computation, pp. 1267–1273. IEEE Press, Los Alamitos (2003)
Kratica, J., Ljubić, I., Tošic, D.: A genetic algorithm for the index selection problem. In: Raidl, G.R., Cagnoni, S., Cardalda, J.J.R., Corne, D.W., Gottlieb, J., Guillot, A., Hart, E., Johnson, C.G., Marchiori, E., Meyer, J.-A., Middendorf, M. (eds.) EvoIASP 2003, EvoWorkshops 2003, EvoSTIM 2003, EvoROB/EvoRobot 2003, EvoCOP 2003, EvoBIO 2003, and EvoMUSART 2003. LNCS, vol. 2611, pp. 280–290. Springer, Heidelberg (2003)
Lin, S., Kernighan, B.: An effective heuristic algorithm for the traveling salesman problem. Operations Research 21, 498–516 (1973)
Applegate, D., Cook, W., Rohe, A.: Chained lin-kernighan for large travelling salesman problems (2000), http://www.citeseer.com/applegate99chained.html
Papadimitriou, C.: The complexity of the Lin-Kernighan heuristic for the traveling salesman problem. SIAM Journal of Computing 21, 450–465 (1992)
Johnson, D., McGeoch, L.: The traveling salesman problem: a case study. In: Aarts, E., Lenstra, J. (eds.) Local Search in Combinatorial Optimization, pp. 215–310. John Wiley & Sons, Inc, Chichester (1997)
Neto, D.: Efficient Cluster Compensation for Lin-Kernighan Heuristics. PhD thesis, Computer Science, University of Toronto (1999)
van Hemert, J., Urquhart, N.: Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 151–160. Springer, Heidelberg (2004)
Applegate, D., Bixby, R., Chvátal, V., Cook, W.: Finding tours in the TSP. Technical Report 99885, Research Institute for Discrete Mathematics, Universität Bonn (1999)
Applegate, D., Cook, W., Dash, S., Mevenkamp, M.: Qsopt linear programming solver (2004), http://www.isye.gatech.edu/~wcook/qsopt/
Sander, J., Ester, M., Kriegel, H.P., Xu, X.: Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications. Data Min. Knowl. Discov. 2, 169–194 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Hemert, J.I. (2005). Property Analysis of Symmetric Travelling Salesman Problem Instances Acquired Through Evolution. In: Raidl, G.R., Gottlieb, J. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2005. Lecture Notes in Computer Science, vol 3448. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31996-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-31996-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25337-2
Online ISBN: 978-3-540-31996-2
eBook Packages: Computer ScienceComputer Science (R0)