Modificaciones del algoritmo sacrificio cortoplacista adaptativo 2OPT_R para solucionar el problema del agente viajero simétrico: comparación del nivel de eficacia

Abstract

El presente trabajo se desarrolló, tomando en cuenta la escasa cantidad de investigaciones para el mejoramiento de una heurística considerada miope, como el algoritmo del Vecino más Cercano, observándose un mayor desarrollo de investigaciones enfocadas a las metaheurísticas. Razón por la cual, en esta investigación se buscó un diseño que logre mejorar el Nivel de Eficacia del algoritmo heurístico del Vecino más Cercano. Por ello, se tomó como base el enfoque del Sacrificio Cortoplacista Adaptativo, desarrollado por Pérez en 2011, cuya combinación con la heurística de mejoramiento 2Opt_r fue denominada por Pérez (2011) como SCA_2Opt_r. A partir de dicha heurística, se diseñaron las versiones Heavy y Soft en base a analogías con el análisis sistémico, logrando mostrar un Nivel de Eficacia de 100% para las versiones Heavy y entre el 31% al 85% según la versión Soft analizada, en comparación con el SCA_2Opt, SCA_2Opt_r. Posteriormente, se comparó con metaheurísticas de artículos internacionales consolidadas en la investigación de Pérez (2011), logrando alcanzar un Nivel de Eficacia competitivo, según la metaheurística a comparar.