Existing heuristic algorithms for solving traveling salesman problem, such as Nearest Neighbor, 2-Opt, 3-Opt, Lin-Kernighan and LKH have been investigated in this work. Mentioned algorithms have been compared in terms of calculation time and quality of found solution. Decomposition approach, based on using common edges in multiple solutions, has been proposed.
1. R. Matai, S.P. Singh, M.L. Mittal, “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches ”, Jaipur, India, 2010, 2. 2. R. Bosch and A. Herman, “Continuous line drawings via the traveling salesman problem,” Operations Research Letters 3 (2004) 302-303, 3. Р. Базилевич, Р. Кутельмах // Комп'ютерні науки та інформаційні технології [Текст] : [зб. наук. пр.] / відп. ред. Ю. М. Рашкевич. - Л. : Видавництво Національного університету "Львівська політехніка", 2009. - 279 c. : іл. - (Вісник / Національний університет "Львівська політехніка" ; № 650). - С. 235-244, 4.E. Nood and J. Been, An Efficient Transformation of the Generalized Travaling Salesman Problem, October 1991, 5. D.S. Johnson and L.A. McGeoch, “The Traveling Salesman Problem: A Case Study in Local Optimization”, November 20, 1995., 6. Christian Nilsson , Heuristics for the Traveling Salesman Problem, Linkoping Univercity, 7. Keld Helsgaun , General k-opt submoves for the Lin–Kernighan TSP veling heuristic Keld Helsgaun, 1 July 2009, 8. Chris Walsaw, A multilevel lin-kernigan-helsgaun algorithm for the treveling salesman problem, 9. D.Applegate, W.Cook, A.Rohe, Chained Lin-Kernigan for large traveling salesman problems, Algorithms and Optimization Departament, AT&T Labs-Research 10.Verhoeven, M.G.A. & Aarts, E.H.L. A parallel Lin-Kernighan algorithm for the traveling salesman problem, 1994.