logo móvil
Contáctanos

Un estudio de rendimiento del impacto de diferentes métodos de perturbación en la eficiencia de GVNS para resolver TSP

Autores: Papalitsas, Christos; Karakostas, Panayiotis; Andronikos, Theodore

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

Acceso abierto

Artículo científico
2019

Un estudio de rendimiento del impacto de diferentes métodos de perturbación en la eficiencia de GVNS para resolver TSP


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Sistemas

Palabras clave

Método de perturbación inspirado en la mecánica cuántica
Método de agitación
Procedimientos de agitación de papel
Algoritmo GVNS
Metaheurístico

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 20

Citaciones: Sin citaciones


Descripción
El propósito de este documento es evaluar cómo tres procedimientos de agitación afectan el rendimiento de un algoritmo GVNS metaheurístico. El primer procedimiento de agitación es conocido en la literatura como método de agitación intensificada. El segundo es un método de perturbación inspirado en la mecánica cuántica, y el tercero es un método de mezcla. Los esquemas GVNS se evalúan utilizando una estrategia de búsqueda para Mejora Primera y Mejor y un límite de tiempo de uno y dos minutos. Los esquemas GVNS formados se aplicaron en instancias de referencia del Problema del Viajante de Comercio (sTSP, nTSP) de la conocida TSPLib. Para examinar la ventaja potencial de alguno de los tres esquemas metaheurísticos, se realizó un extenso análisis estadístico sobre los resultados reportados. Los datos experimentales muestran que para instancias de aTSP, los dos primeros métodos tienen un rendimiento equivalente y, en cualquier caso, mucho mejor que el enfoque de mezcla. Además, el primer método tiene un mejor rendimiento que los otros dos al usar la estrategia de Mejora Primera, mientras que el segundo método da resultados bastante similares al tercero. Sin embargo, no se observaron desviaciones significativas al usar diferentes métodos de perturbación para instancias de TSP Simétrico (sTSP, nTSP).

Otros recursos que podrían interesarte

Temas Virtualpro