ALGORITMO MEMÉTICO PARA RESOLVER EL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON CAPACIDAD LIMITADA (MEMETIC ALGORITHM FOR THE VEHICLE ROUTING PROBLEM)
ALGORITMO MEMÉTICO PARA RESOLVER EL PROBLEMA DE ENRUTAMIENTO DE VEHÍCULOS CON CAPACIDAD LIMITADA (MEMETIC ALGORITHM FOR THE VEHICLE ROUTING PROBLEM)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright statement
The authors exclusively assign to the Universidad EIA, with the power to assign to third parties, all the exploitation rights that derive from the works that are accepted for publication in the Revista EIA, as well as in any product derived from it and, in in particular, those of reproduction, distribution, public communication (including interactive making available) and transformation (including adaptation, modification and, where appropriate, translation), for all types of exploitation (by way of example and not limitation : in paper, electronic, online, computer or audiovisual format, as well as in any other format, even for promotional or advertising purposes and / or for the production of derivative products), for a worldwide territorial scope and for the entire duration of the rights provided for in the current published text of the Intellectual Property Law. This assignment will be made by the authors without the right to any type of remuneration or compensation.
Consequently, the author may not publish or disseminate the works that are selected for publication in the Revista EIA, neither totally nor partially, nor authorize their publication to third parties, without the prior express authorization, requested and granted in writing, from the Univeridad EIA.
Show authors biography
El diseño de rutas eficientes para vehículos que visitan un número importante de destinos es un factor crítico para la competitividad de muchas compañías. El diseño de dichas rutas se conoce como el problema de enrutamiento de vehículos. El enrutamiento de vehículos hace parte de una categoría de problemas conocida como NP-Difícil. Dado que el enrutamiento de vehículos es NP-Difícil, los diseños de rutas se hacen por medio de algoritmos de aproximación denominados metaheurísticos. El presente trabajo presenta un algoritmo memético que evoluciona utilizando un mecanismo inspirado en las mutaciones de los virus. Adicionalmente, el algoritmo utiliza la Búsqueda Tabú como mecanismo de intensificación. El algoritmo se evaluó 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.
Sumário: O desenho de rotas eficientes para veículos que visitam um número importante de destino é um fator crítico para a competitividade de muitas empresas. O desenho de estas rotas é conhecido como o problema de roteamento dos veículos. O roteamento dos veículos é parte duma categoria de problemas conhecida como NP-Difícil. Dado que o roteamento dos veículos é NP-Difícil, os desenhos de rotas fazem-se através de algoritmos de aproximação chamados meta-heurísticos. O presente trabalho apresenta um algoritmo memético que evolui utilizando um mecanismo inspirado das mutações dos vírus. Adicionalmente, o algoritmo utiliza a pesquisa tabu como mecanismo de intensificação. O algoritmo foi analisado utilizando um conjunto de reconhecidas instancias da literatura obtendo resultados altamente favorável.
Article visits 373 | PDF visits 213
