Uso de optimización de mallas variables para el "viajante de comercio" / Use of Variable Meshes Optimization for the "Traveler of Commerce" / Uso da Otimização de Malhas Variáveis para o "Viajante do Comércio"

RESUMEN

Resumen Introducción:. 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 Objetivo 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 interacción. Metodología: Se resume en este trabajo un estudio de parámetros del modelo VMO utilizando un conjunto de instancias de TSP con diferentes caracterí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. El trabajo está estructurado de la siguiente manera En el apartado 1 se describe los aspectos fundamentales de problema de estudio TSP. Seguidamente en el segundo se explica el funcionamiento general de VMO, en el tercero se define cada uno de los operadores de expansión y contracción para el problema de estudio. Posteriormente en el apartado cuarto se realiza un estudio de parámetros de la propuesta y un análisis comparativo experimental con los resultados obtenidos con otros algoritmos mencionado en el estado del arte. Conclusiones: Se aplicaron otros operadores de generación de nuevos nodos en el proceso de expansión, donde se realiza una combinación de soluciones de manera que cumpla con las restricciones impuestas por el problema.

ABSTRACT

Abstract Introduction: This paper presents a proposal to apply the meta-heuristic Optimization Based on Variable Meshes (VMO) to the discreet problem of the Traveler Seller (TSP); This model explores the search space to Objective from a population of solutions called mesh that expands and contracts in order to find good quality solutions. In this context, the expansion operator is modified in such a way that it is applicable in a discrete domain, making combinations among the solutions in order to obtain new nodes. Another element that is modified is the clearing operator, which is responsible for maintaining the diversity of the mesh in each interaction. Methodology: A study of VMO model parameters is summarized in this paper, using a set of TSP instances with different characteristics; In addition, it can be observed that the proposal of this work obtains competitive results when compared with other international reference algorithms mentioned in the state of the art. The work is structured as follows Section 1 describes the fundamental aspects of the TSP study problem. Then, in the second, the general functioning of VMO is explained, in the third one, each of the expansion and contraction operators is defined for the study problem. Later in the fourth section a study of the parameters of the proposal and an experimental comparative analysis with the results obtained with other algorithms mentioned in the state of the art is made. Conclusions: Other operators of generation of new nodes were applied in the expansion process, where a combination of solutions is made in order to comply with the restrictions imposed by the problem.

RESUMO

Resumo Introdução: Este artigo apresenta uma proposta para aplicar a Otimização meta-heurística Baseada em Malhas Variáveis (VMO) ao problema discreto do Vendedor Vendedor (TSP); Esse modelo explora o espaço de pesquisa para o Objective a partir de uma população de soluções chamada malha que se expande e se contrai para encontrar soluções de boa qualidade. Neste contexto, o operador de expansão é modificado de tal maneira que é aplicável em um domínio discreto, fazendo combinações entre as soluções para obter novos nós. Outro elemento que é modificado é o operador de limpeza, que é responsável por manter a diversidade da malha em cada interação. Metodologia: Um estudo dos parâmetros do modelo VMO é resumido neste artigo, usando um conjunto de instâncias do TSP com diferentes características; Além disso, pode-se observar que a proposta deste trabalho obtém resultados competitivos quando comparados com outros algoritmos de referência internacionais mencionados no estado da arte. O trabalho está estruturado da seguinte forma a seção 1 descreve os aspectos fundamentais do problema do estudo TSP. Então, no segundo, o funcionamento geral do VMO é explicado, no terceiro, cada operador de expansão e contração é definido para o problema do estudo. Posteriormente na quarta seção é feito um estudo dos parâmetros da proposta e uma análise comparativa experimental com os resultados obtidos com outros algoritmos mencionados no estado da arte. Conclusões: Outros operadores de geração de novos nós foram aplicados no processo de expansão, onde uma combinação de soluções é feita a fim de cumprir as restrições impostas pelo problema.