Full text

Turn on search term navigation

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

Abstract

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 n1 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.

Details

Title
A Multi-Phase Method for Euclidean Traveling Salesman Problems
Author
Pacheco-Valencia, Víctor Hugo 1   VIAFID ORCID Logo  ; Nodari Vakhania 1   VIAFID ORCID Logo  ; Hernández-Mira, Frank Ángel 2   VIAFID ORCID Logo  ; Hernández-Aguilar, José Alberto 3   VIAFID ORCID Logo 

 Centro de Investigación en Ciencias UAEMor, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Col.Chamilpa, Cuernavaca 62209, Mexico 
 Facultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Carlos E. Adame No. 54, Col.Garita, Acapulco 39650, Mexico 
 Facultad de Contaduría, Administración e Informática UAEMor, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Col.Chamilpa, Cuernavaca 62209, Mexico 
First page
439
Publication year
2022
Publication date
2022
Publisher
MDPI AG
e-ISSN
20751680
Source type
Scholarly Journal
Language of publication
English
ProQuest document ID
2716486681
Copyright
© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.