Proceedings of ISP RAS


The Metric Travelling Salesman Problem: The Experiment on Pareto-optimal Algorithms

S.M. Avdoshin (HSE, Moscow, Russia)
E.N. Beresneva (HSE, Moscow, Russia)

Abstract

The Metric Travelling Salesman Problem is a subcase of the Travelling Salesman Problem (TSP), where the triangle inequality holds. It is a key problem in combinatorial optimization. Solutions of the Metric TSP are generally used for costs minimization tasks in logistics, manufacturing, genetics and other fields. Since this problem is NP-hard, heuristic algorithms providing near optimal solutions in polynomial time will be considered instead of the exact ones. The aim of this article is to experimentally find Pareto optimal heuristics for Metric TSP under criteria of error rate and run time efficiency. Two real-life kinds of inputs are intercompared - VLSI Data Sets based on very large scale integration schemes and National TSPs that use geographic coordinates of cities. This paper provides an overview and prior estimates of seventeen heuristic algorithms implemented in C++ and tested on both data sets. The details of the research methodology are provided, the computational scenario is presented. In the course of computational experiments, the comparative figures are obtained and on their basis multi-objective optimization is provided. Overall, the group of Pareto-optimal algorithms for different N consists of some of the MC, SC, NN, DENN, CI, GRD, CI + 2-Opt,  GRD + 2-Opt, CHR and LKH heuristics.

Keywords

metric travelling salesman problem, heuristic algorithms, Pareto-optimality

Edition

Proceedings of the Institute for System Programming, vol. 29, issue 4, 2017, pp. 123-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(4)-8

Full text of the paper in pdf Back to the contents of the volume