Un algoritmo metaheurístico para la solución del problema de ruteo de vehículos con múltiples depósitos y flota heterogénea

Abstract

En este trabajo se presenta un algoritmo metaheurístico para resolver el problema de ruteo de vehículos con múltiples depósitos y flota heterogénea (MDHFVRP), la formulación matemática del problema se basa en un modelo de programación lineal entera mixta de cuatro índices propuesto en la literatura especializada. Para solucionar el problema MDHFVRP se utiliza una técnica de solución basada en un algoritmo genético de Chu-Beasley modificado. La metodología presenta un enfoque híbrido que permite generar una población inicial de buena calidad, para ello se utiliza como punto de inicio el procedimiento heurístico de \Lin-Kernighan-Helsgaun" (LKH), apoyado con la solución del modelo de programación lineal para el problema de la ruta m as corta. Dos métodos de recombinación que permiten obtener descendientes diversos son implementados y utilizados de forma conjunta. Adicionalmente, se presenta una etapa de mejoramiento utilizada como operador de mutación, donde seis estrategias de búsqueda local inter-rutas y dos estrategias de búsqueda local intra-rutas son utilizadas, de tal manera que cada descendiente sea mejorado en cada ciclo generacional tal que sea posible entrar a formar parte de la población. Para validar la metodología propuesta, se emplean instancias de prueba cuyo n umero de clientes varia entre 50 y 360. Las instancias han sido adaptadas y utilizadas en la literatura especializada como prueba de las metodologías existentes para el MDHFVRP.