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
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
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).
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).