Clustering aplicado al problema VRP con múltiples depósitos y ventanas de tiempo

Abstract

El Problema de Ruteo de Vehículos con Múltiples Depósitos y Ventanas de Tiempo (MDVRPTW por sus siglas en inglés) consiste básicamente en encontrar las rutas óptimas entre clientes y depósitos, teniendo en cuenta horarios de servicio, producción de cada cliente y capacidad máxima de cada depósito. Una forma de resolver el MDVRPTW consiste en dividir el problema en dos fases: la primera es asignar un subconjunto de los clientes a cada depósito y la segunda rutear, por separado, en cada uno de estos subconjuntos obtenidos. El objetivo de este estudio es enfocar la atención en la primera de estas fases, la fase de asignación, considerando la aplicación de una de las técnicas más conocidas de clustering, llamada clustering jerárquico. Para ello se han seleccionado dos algoritmos, uno de éstos consiste en un algoritmo clásico de clustering jerárquico llamado: AGLOMERACIaN y el otro es una adaptación del algoritmo ROCK. Para evaluar la aplicabilidad de estos algoritmos de clustering al MDVRPTW, se han comparado los resultados de un ruteo utilizando como algoritmos de asignación Aglomeración y Rock contra los resultados de un ruteo utilizando heurísticas de asignación. Tales heurísticas fueron desarrolladas en el Departamento de Investigación Operativa por Libertad Tansini, Daniel Giosa y Omar Viera específicamente para resolver el subproblema de la asignación. Los resultados obtenidos con estas comparaciones muestran que en el 87 por ciento de los casos se obtuvo menor costo total de ruteo usando clustering para la fase de asignación, aunque para los casos de prueba de gran tamaño los tiempos de ejecución favorecen a las heurísticas. Por lo tanto, para problemas de tamaño mediano y donde el tiempo de ejecución no es un factor crítico, es factible utilizar clustering como algoritmo de asignación previo al ruteo.