?
Pareto-optimal Algorithms for Metric TSP: Experimental Research
The Travelling Salesman Problem (TSP) is a fundamental task in combinatorial optimization. A special case of the TSP is Metric TSP, where the triangle inequality holds. Solutions of the TSP are generally used for costs minimization, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. Since the TSP is NP-hard, heuristic algorithms providing near optimal solutions will be considered. The objective of this article is to find a group of Pareto optimal heuristic algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. Classification of algorithms for Metric TSP is presented. Feasible heuristic algorithms and their prior estimates are described. The data structure and the details of the research methodology are provided. Finally, results and prospective research are discussed.