Heuristic Exchange 2Opt Best Improvement_r and Level of Efficacy of the solutions of the Symmetric Travelling Salesman Problem
DOI:
https://doi.org/10.15381/rpcs.v5i1.25806Keywords:
Symmetric Travelling Salesman Problem, 2Opt Exchange, Nearest Neighbor, MetaheuristicsAbstract
In this research, a hybrid algorithm called VMC_2OptBI_r was developed, which improved the solution search criteria applied by the 2Opt Exchange Heuristic based on a node exchange policy called Best Improvement (BI) and introducing an additional factor "1+r" to perform the 2Opt exchanges. The "1+r" factor allows slightly modifying the selection of nodes to be exchanged, thus exploring new solutions. To measure the level of efficacy of the new algorithm, instances of the Symmetric Traveling Salesman Problem from TSPLIB were selected and compared with their basic versions: Nearest Neighbor (VMC) and VMC_2OptBI. Then, they were compared with the solutions of the SCA_2Opt and SCA_2Opt_r algorithms, where they were compared with the solutions of four metaheuristics published in recent articles (2019-2022). The results showed that the solutions obtained by the new VMC_2OptBI_r algorithm achieved an efficacy level of 100% compared to VMC, VMC_2OptBI, SCA_2Opt, a value higher than 81% compared to SCA_2Opt_r, and a range between 11% to 88% compared to the four reviewed metaheuristics for the compared instances.
Downloads
Published
Issue
Section
License
Copyright (c) 2023 David J. Astoquillca-Yaranga, Esther Berger-Vidal
This work is licensed under a Creative Commons Attribution 4.0 International License.
THE AUTHORS RETAIN THEIR RIGHTS:
(a) The authors retain their trademark and patent rights, and also over any process or procedure described in the article.
(b) The authors retain the right to share, copy, distribute, execute and publicly communicate the article published in the Revista Peruana de Computación y Sistemas (for example, place it in an institutional repository or publish it in a book), with acknowledgment of its initial publication in Revista Peruana de Computación y Sistemas.
(c) Authors retain the right to make a subsequent publication of their work, to use the article or any part of it (for example: a compilation of their work, lecture notes, thesis, or for a book), provided that they indicate the source. of publication (authors of the work, magazine, volume, number and date).
