Portal de Periódicos da CAPES

ALGORITMO MEMÉTICO PARA RESOLVER EL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON CAPACIDAD LIMITADA (MEMETIC ALGORITHM FOR THE VEHICLE ROUTING PROBLEM)

2014; EIA University; Volume: 10; Issue: 20 Linguagem: Espanhol

10.24050/reia.v10i20.510

2463-0950

Juan R. Jaramillo,

Quality and Supply Management

El diseno de rutas eficientes para vehiculos que visitan un numero importante de destinos es un factor critico para la competitividad de muchas companias. El diseno de dichas rutas se conoce como el problema de enrutamiento de vehiculos. El enrutamiento de vehiculos hace parte de una categoria de problemas conocida como NP-Dificil. Dado que el enrutamiento de vehiculos es NP-Dificil, los disenos de rutas se hacen por medio de algoritmos de aproximacion denominados metaheuristicos. El presente trabajo presenta un algoritmo memetico que evoluciona utilizando un mecanismo inspirado en las mutaciones de los virus. Adicionalmente, el algoritmo utiliza la Busqueda Tabu como mecanismo de intensificacion. El algoritmo se evaluo utilizando un conjunto de reconocidas instancias de la literatura obteniendo resultados altamente favorables. Abstract: Solving the Capacitated Vehicle Routing Problem is critical for the success of many companies. The Capacitated Vehicle Routing Problem belongs to the family of NP-Hard problems. Consequently, the development of Meta-heuristics is critical for its solution. This work presents a Memetic Algorithm inspired on virus mutation mechanisms. In addition, the algorithm uses Tabu Search for intensification purposes. The algorithm was evaluated using a well know set of instances from the literature. The results indicate that the algorithm performed well. Sumario: O desenho de rotas eficientes para veiculos que visitam um numero importante de destino e um fator critico para a competitividade de muitas empresas. O desenho de estas rotas e conhecido como o problema de roteamento dos veiculos. O roteamento dos veiculos e parte duma categoria de problemas conhecida como NP-Dificil. Dado que o roteamento dos veiculos e NP-Dificil, os desenhos de rotas fazem-se atraves de algoritmos de aproximacao chamados meta-heuristicos. O presente trabalho apresenta um algoritmo memetico que evolui utilizando um mecanismo inspirado das mutacoes dos virus. Adicionalmente, o algoritmo utiliza a pesquisa tabu como mecanismo de intensificacao. O algoritmo foi analisado utilizando um conjunto de reconhecidas instancias da literatura obtendo resultados altamente favoravel.