A Multi-Phase Method for Euclidean Traveling Salesman Problems
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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n&...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-08-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/11/9/439 |
| _version_ | 1797491236479696896 |
|---|---|
| author | Víctor Hugo Pacheco-Valencia Nodari Vakhania Frank Ángel Hernández-Mira José Alberto Hernández-Aguilar |
| author_facet | Víctor Hugo Pacheco-Valencia Nodari Vakhania Frank Ángel Hernández-Mira José Alberto Hernández-Aguilar |
| author_sort | Víctor Hugo Pacheco-Valencia |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> 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 <i>k</i> 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. |
| first_indexed | 2024-03-10T00:44:34Z |
| format | Article |
| id | doaj.art-da7c03346b364744b38ee1a0ed9b816a |
| institution | Directory Open Access Journal |
| issn | 2075-1680 |
| language | English |
| last_indexed | 2024-03-10T00:44:34Z |
| publishDate | 2022-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Axioms |
| spelling | doaj.art-da7c03346b364744b38ee1a0ed9b816a2023-11-23T15:02:01ZengMDPI AGAxioms2075-16802022-08-0111943910.3390/axioms11090439A Multi-Phase Method for Euclidean Traveling Salesman ProblemsVíctor Hugo Pacheco-Valencia0Nodari Vakhania1Frank Ángel Hernández-Mira2José Alberto Hernández-Aguilar3Centro de Investigación en Ciencias UAEMor, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Col.Chamilpa, Cuernavaca 62209, MexicoCentro de Investigación en Ciencias UAEMor, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Col.Chamilpa, Cuernavaca 62209, MexicoFacultad de Matemáticas UAGro, Universidad Autónoma de Guerrero, Carlos E. Adame No. 54, Col.Garita, Acapulco 39650, MexicoFacultad de Contaduría, Administración e Informática UAEMor, Universidad Autónoma del Estado de Morelos, Av. Universidad 1001, Col.Chamilpa, Cuernavaca 62209, MexicoThe 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula> 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 <i>k</i> 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.https://www.mdpi.com/2075-1680/11/9/439traveling salesman problemheuristic algorithmtime complexityconvex hulltwo-dimensional Euclidean spaceoptimization |
| spellingShingle | Víctor Hugo Pacheco-Valencia Nodari Vakhania Frank Ángel Hernández-Mira José Alberto Hernández-Aguilar A Multi-Phase Method for Euclidean Traveling Salesman Problems Axioms traveling salesman problem heuristic algorithm time complexity convex hull two-dimensional Euclidean space optimization |
| title | A Multi-Phase Method for Euclidean Traveling Salesman Problems |
| title_full | A Multi-Phase Method for Euclidean Traveling Salesman Problems |
| title_fullStr | A Multi-Phase Method for Euclidean Traveling Salesman Problems |
| title_full_unstemmed | A Multi-Phase Method for Euclidean Traveling Salesman Problems |
| title_short | A Multi-Phase Method for Euclidean Traveling Salesman Problems |
| title_sort | multi phase method for euclidean traveling salesman problems |
| topic | traveling salesman problem heuristic algorithm time complexity convex hull two-dimensional Euclidean space optimization |
| url | https://www.mdpi.com/2075-1680/11/9/439 |
| work_keys_str_mv | AT victorhugopachecovalencia amultiphasemethodforeuclideantravelingsalesmanproblems AT nodarivakhania amultiphasemethodforeuclideantravelingsalesmanproblems AT frankangelhernandezmira amultiphasemethodforeuclideantravelingsalesmanproblems AT josealbertohernandezaguilar amultiphasemethodforeuclideantravelingsalesmanproblems AT victorhugopachecovalencia multiphasemethodforeuclideantravelingsalesmanproblems AT nodarivakhania multiphasemethodforeuclideantravelingsalesmanproblems AT frankangelhernandezmira multiphasemethodforeuclideantravelingsalesmanproblems AT josealbertohernandezaguilar multiphasemethodforeuclideantravelingsalesmanproblems |