Aplicación de técnicas de clusterización como inicializadores y la metaheurística ILS, al Problema de Ruteo Vehículos con Múltiples Depósitos (MDVRP)

En este Proyecto de Grado se propone una metodología híbrida que combina las técnicas aglomerativas de Clusterización para generar soluciones iniciales con un algoritmo de búsqueda local iterada, iterated location search (ILS) para resolver el problema de ruteo de vehículos considerando múltiples depósitos (MDVRP). El MDVRP es clasificado como NP duro, en el que se atiende a un conjunto de clientes con una demanda determinada. La función objetivo del problema consiste en minimizar el total de la distancia recorrida por las rutas, teniendo en cuenta que todos los clientes deben ser atendidos cumpliendo restricciones de capacidad de depósitos y vehículos. En la etapa de inicialización se proponen algoritmos heurísticos basados en métodos de clusterización y cuyo objetivo es identificar una estructura inicial, para ser usadas como soluciones de inicio en el proceso de optimización. Las respuestas identificadas son de excelente calidad y para obtenerlas se requiere de bajos tiempos de cómputo. En la etapa de optimización se utiliza el algoritmo ILS el cual es implementado con base en conceptos de intensificación y diversificación y para esto se usa operadores de tipo inter e intra ruta. Además, y con el fin de permitir que el procedimiento viaje entre las regiones infactibles, son aceptadas sobrecargas en vehículos, depósitos y excesos en la longitud de las rutas. Estas violaciones de los limites, denominadas infactibilidades, son llevadas en cuenta en la función objetivo como penalidades.