A convex hull based algorithm for solving the Traveling Salesman Problem

Abstract

This paper introduces a new algorithm for solving the Traveling Salesman Problem, based on the convex hull. The proposed algorithm has two versions, in the first version, starting from the vertices farthest from the center, unselected vertices are successively added to the current tour and in the second version, starting from the vertices closest to the center, unselected vertices are successively added to the current tour. The proposed algorithm has been implemented in the Python programming language, and computational experiments have been conducted on library problems of varying dimensions. The obtained results are compared with well-known algorithms, demonstrating the efficiency of the proposed algorithm. The results of these experiments demonstrate the effectiveness and efficiency of the proposed algorithm.