Heurística de Intercambio 2Opt Best Improvement_r y Nivel de Eficacia de las soluciones del Problema del Agente Viajero Simétrico
DOI:
https://doi.org/10.15381/rpcs.v5i1.25806Palabras clave:
Problema del Agente Viajero Simétrico, Intercambio 2Opt, Vecino más Cercano, MetaheurísticasResumen
En esta investigación se desarrolló un algoritmo híbrido denominado VMC_2OptBI_r, que a partir de la solución inicial construida bajo el pensamiento del Vecino más Cercano se buscó mejorar el criterio de búsqueda de soluciones aplicado por la Heurística de Intercambio 2Opt basada en una política de intercambio de nodos denominada Best Improvement (BI) e introduciendo un factor adicional “1+r” al criterio para realizar los intercambios 2Opt. El factor “1+r” permite modificar ligeramente la selección de nodos a intercambiar provocando así la exploración de nuevas soluciones. Para medir el nivel de eficacia del nuevo algoritmo se seleccionaron instancias del problema del agente viajero simétrico de TSPLIB, las cuales en primer lugar se compararon con sus versiones básicas: El Vecino más Cercano (VMC) y el VMC_2OptBI; luego se compararon con las soluciones de los algoritmos SCA_2Opt, SCA_2Opt_r, donde se comparó con las soluciones de cuatro metaheurísticas publicadas en artículos recientes (2019-2022). Los resultados mostraron que las soluciones obtenidas por el nuevo algoritmo VMC_2OptBI_r alcanzaron un nivel de eficacia de 100% con respecto al VMC, VMC_2OptBI, SCA_2Opt, un valor mayor al 81% con respecto al SCA_2Opt_r y un rango entre el 11% al 88% con respecto a las cuatro metaheurísticas revisadas para las instancias comparadas.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2023 David J. Astoquillca-Yaranga, Esther Berger-Vidal
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
LOS AUTORES RETIENEN SUS DERECHOS:
a. Los autores retienen sus derechos de marca y patente, y también sobre cualquier proceso o procedimiento descrito en el artículo.
b. Los autores retienen el derecho de compartir, copiar, distribuir, ejecutar y comunicar públicamente el artículo publicado en la Revista Peruana de Computación y Sistemas (por ejemplo, colocarlo en un repositorio institucional o publicarlo en un libro), con un reconocimiento de su publicación inicial en la Revista Peruana de Computación y Sistemas.
c. Los autores retienen el derecho a hacer una posterior publicación de su trabajo, de utilizar el artículo o cualquier parte de aquel (por ejemplo: una compilación de sus trabajos, notas para conferencias, tesis, o para un libro), siempre que indiquen la fuente de publicación (autores del trabajo, revista, volumen, número y fecha).
