Cargando…

Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic

This article finds feasible solutions to the travelling salesman problem, obtaining the route with the shortest distance to visit n cities just once, returning to the starting city. The problem addressed is clustering the cities, then using the NEH heuristic, which provides an initial solution that...

Descripción completa

Detalles Bibliográficos
Autores principales: Anaya Fuentes, Gustavo Erick, Hernández Gress, Eva Selene, Seck Tuoh Mora, Juan Carlos, Medina Marín, Joselito
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6104944/
https://www.ncbi.nlm.nih.gov/pubmed/30133477
http://dx.doi.org/10.1371/journal.pone.0201868
_version_ 1783349573422415872
author Anaya Fuentes, Gustavo Erick
Hernández Gress, Eva Selene
Seck Tuoh Mora, Juan Carlos
Medina Marín, Joselito
author_facet Anaya Fuentes, Gustavo Erick
Hernández Gress, Eva Selene
Seck Tuoh Mora, Juan Carlos
Medina Marín, Joselito
author_sort Anaya Fuentes, Gustavo Erick
collection PubMed
description This article finds feasible solutions to the travelling salesman problem, obtaining the route with the shortest distance to visit n cities just once, returning to the starting city. The problem addressed is clustering the cities, then using the NEH heuristic, which provides an initial solution that is refined using a modification of the metaheuristic Multi-Restart Iterated Local Search MRSILS; finally, clusters are joined to end the route with the minimum distance to the travelling salesman problem. The contribution of this research is the use of the metaheuristic MRSILS, that in our knowledge had not been used to solve the travelling salesman problem using clusters. The main objective of this article is to demonstrate that the proposed algorithm is more efficient than Genetic Algorithms when clusters are used. To demonstrate the above, both algorithms are compared with some cases taken from the literature, also a comparison with the best-known results is done. In addition, statistical studies are made in the same conditions to demonstrate this fact. Our method obtains better results in all the 10 cases compared.
format Online
Article
Text
id pubmed-6104944
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-61049442018-09-15 Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic Anaya Fuentes, Gustavo Erick Hernández Gress, Eva Selene Seck Tuoh Mora, Juan Carlos Medina Marín, Joselito PLoS One Research Article This article finds feasible solutions to the travelling salesman problem, obtaining the route with the shortest distance to visit n cities just once, returning to the starting city. The problem addressed is clustering the cities, then using the NEH heuristic, which provides an initial solution that is refined using a modification of the metaheuristic Multi-Restart Iterated Local Search MRSILS; finally, clusters are joined to end the route with the minimum distance to the travelling salesman problem. The contribution of this research is the use of the metaheuristic MRSILS, that in our knowledge had not been used to solve the travelling salesman problem using clusters. The main objective of this article is to demonstrate that the proposed algorithm is more efficient than Genetic Algorithms when clusters are used. To demonstrate the above, both algorithms are compared with some cases taken from the literature, also a comparison with the best-known results is done. In addition, statistical studies are made in the same conditions to demonstrate this fact. Our method obtains better results in all the 10 cases compared. Public Library of Science 2018-08-22 /pmc/articles/PMC6104944/ /pubmed/30133477 http://dx.doi.org/10.1371/journal.pone.0201868 Text en © 2018 Fuentes et al http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Anaya Fuentes, Gustavo Erick
Hernández Gress, Eva Selene
Seck Tuoh Mora, Juan Carlos
Medina Marín, Joselito
Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title_full Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title_fullStr Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title_full_unstemmed Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title_short Solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
title_sort solution to travelling salesman problem by clusters and a modified multi-restart iterated local search metaheuristic
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6104944/
https://www.ncbi.nlm.nih.gov/pubmed/30133477
http://dx.doi.org/10.1371/journal.pone.0201868
work_keys_str_mv AT anayafuentesgustavoerick solutiontotravellingsalesmanproblembyclustersandamodifiedmultirestartiteratedlocalsearchmetaheuristic
AT hernandezgressevaselene solutiontotravellingsalesmanproblembyclustersandamodifiedmultirestartiteratedlocalsearchmetaheuristic
AT secktuohmorajuancarlos solutiontotravellingsalesmanproblembyclustersandamodifiedmultirestartiteratedlocalsearchmetaheuristic
AT medinamarinjoselito solutiontotravellingsalesmanproblembyclustersandamodifiedmultirestartiteratedlocalsearchmetaheuristic