Optimización basada en Mallas Variables: Caso de estudio Viajante de Comercio

Published in: Innovation in Engineering, Technology and Education for Competitiveness and Prosperity: Proceedings of the 12th Latin American and Caribbean Conference for Engineering and Technology
Date of Conference: July 21-24,2014
Location of Conference: Guayaquil,Ecuador
Authors: Byron Oviedo Bayas
Jorge Humberto Guanín Fajardo
Eduardo Díaz Ocampo
Amilkar Puris Cáceres
Refereed Paper: #259

Abstract:

A proposal is presented in this paper to implement the meta- heuristic Variable Mesh Optimization (VMO) at discrete Traveling Salesman Problem(TSP), where this model explores the search space from a population of solutions called mesh expands and contracts in order to find solutions of good quality. In this context the operator of expansion so as to be applicable in a discrete domain , making combinations between the solutions in order to obtain new nodes is changed. Another element that is changed is the operator of clearing , which is responsible for maintaining the diversity of the mesh in each interaction . A study of VMO model parameters using a set of TSP instances with different carcterísticas summarized in this paper, in addition, we can see that the purpose of this paper obtains competitive results when compared with others international reference algorithms mentioned in the statement of art.

Resumen:

En este trabajo se presenta una propuesta para aplicar la meta-heurística Optimización Basada en Mallas Variables (VMO) al problema discreto del Viajero Vendedor (TSP); este modelo explora el espacio de búsqueda a partir de una población de soluciones llamada malla que se expande y contrae con la finalidad de encontrar soluciones de buena calidad.En este contexto se modifica el operador de expansión de manera tal que sea aplicable en un dominio discreto, realizando combinaciones entre las soluciones a fin de obtener nuevos nodos. Otro de los elementos que se modifica es el operador de clearing, el cual se encarga de mantener la diversidad de la malla en cada interación. Se resume en este trabajo un estudio de parámetros del modelo VMO utilizando un conjunto de instancias de TSP con diferentes carcterísticas; además, se puede observar que la propuesta de este trabajo obtiene resultados competitivos al compararlos con otros algoritmos de referencia internacional mencionado en el estado del arte.