Implementation and Assessment of Resource-Efficient Algorithms for Metric TSP

The Travelling Salesman Problem (TSP) is a fundamental task in a class of combinatorial optimization problems which consists of finding a Hamiltonian circuit of minimal length. Solutions of the TSP are generally used for costs minimization tasks in logistics and manufacturing, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. A special case of the TSP is Metric TSP, where the triangle inequality holds. The objective of this article is to determine a group of Pareto optimal algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. In this paper, we consider only heuristic algorithms providing near optimal solutions in polynomial time, since the TSP is NP-hard. Classification of algorithms for Metric TSP is presented. Groups of feasible heuristic algorithms and their modifications are described. The data structure and the details of the research methodology are provided. Two real-life kinds of inputs are used for the experimental study: very large scale integration schemes and geographic coordinated of cities. Finally, results and prospective research are discussed. The paper contains 113 pages, 13 illustrations, 7 tables, 14 schemes, 67 bibliography items, 11 appendices. Keywords: travelling salesman problem, resource-efficient algorithm, heuristic algorithm, Metric TSP, computational experiment, NP-hard problem.