Axioms (Aug 2022)

A Multi-Phase Method for Euclidean Traveling Salesman Problems

  • Víctor Hugo Pacheco-Valencia,
  • Nodari Vakhania,
  • Frank Ángel Hernández-Mira,
  • José Alberto Hernández-Aguilar

DOI
https://doi.org/10.3390/axioms11090439
Journal volume & issue
Vol. 11, no. 9
p. 439

Abstract

Read online

The Traveling Salesman Problem (TSP) aims to find the shortest tour for a salesman who starts and ends in the same city and visits the remaining n−1 cities exactly once. There are a number of common generalizations of the problem including the Multiple Traveling Salesman Problem (MTSP), where instead of one salesman, there are k salesmen and the same amount of individual tours are to be constructed. We consider the Euclidean version of the problem where the distances between the cities are calculated in two-dimensional Euclidean space. Both general the TSP and its Euclidean version are strongly NP-hard. Hence, approximation algorithms with a good practical behavior are of primary interest. We describe a general method for the solution of the Euclidean versions of the TSP (including MTSP) that yields approximation algorithms with a favorable practical behavior for large real-life instances. Our method creates special types of convex hulls, which serve as a basis for the constructions of our initial and intermediate partial solutions. Here, we overview three algorithms; one of them is for the bounded version of the MTSP. The proposed novel algorithm for the Euclidean TSP provides close-to-optimal solutions for some real-life instances.

Keywords