A heuristic method for the travelling salesman problem

Issue title: Special Section: Collective intelligence in information systems

Guest editors: Ngoc Thanh Nguyen, Edward Szczerbicki, Bogdan Trawiński and Van Du Nguyen

Article type: Research Article

Authors: Mazur, Zygmunt^{a; *} | Pec, Janusz^b

Affiliations: [a] Wroclaw University of Science and Technology, Faculty of Computer Science and Management | [b] Central Statistical Office of Poland, Warsaw

Correspondence: [*] Corresponding author. Zygmunt Mazur, Wroclaw University of Science and Technology, Faculty of Computer Science and Management. E-mail: zygmunt.mazur@pwr.edu.pl.

Abstract: In this paper we describe a heuristic procedure for solving the travelling salesman problem in the symmetric case without using the triangle inequality cij ≤ cik + ckj. A complete proof of the correctness of the algorithm and example of the presentation how the method works are given. There is estimated computational complexity, which is at most O(m2), where m is a number of the edges of the complete graph with n vertices -Kn. There is shown also, it is possible obtain the following bound that HEURISTICSOLUTIONOPTIMALSOLUTION<3 , if some specific inequality considering weights (costs) of edges is satisfied.

Keywords: Symmetric travelling salesman problem (STSP), assignment problem, hamiltonian circuit, simple graph, simple circuit, complete graph K_n , list L_i , heuristics

DOI: 10.3233/JIFS-179347

Journal: Journal of Intelligent & Fuzzy Systems, vol. 37, no. 6, pp. 7383-7388, 2019