• Título: Algoritmo GRASP para Problemas de Ruteo de Vehículos con Clientes Agrupados.
• Directora: Irene Loiseau.
• Jurado: Javier Marenco, Paula Zabala.
• Resumen:

El problema básico de ruteo de vehículos (VRP) consiste en determinar
un conjunto de rutas para que una flota de vehículos atienda a un
conjunto de clientes a un costo mínimo. El objetivo de esta tesis fue
proponer soluciones para una variante del VRP llamada problema de ruteo
de vehículos por clusters con restricciones de capacidad (CluVRP SCC por
sus siglas en inglés). En este caso los clientes están agrupados en
clusters, y todos los clientes de cada cluster deben ser visitados por
un mismo vehículo antes de pasar a otro cluster. Como en la mayoría de
los problemas de ruteo, acá el objetivo es minimizar los costos de
transporte. Este problema ha sido poco abordado y los trabajos que
encontramos son muy recientes. Tiene varias aplicaciones reales como por
ejemplo en un problema de entregas de productos organizados en
containers o en el traslado de pasajeros que quieren ser transportados
en grupo. Como la mayoría de los problemas de ruteo que aparecen en la
práctica pertenece a la clase NP-Hard.

También se trabajó en una variante, el problema de ruteo de vehículos
por clusters con restricciones débiles
(CluVRP WCC por sus siglas en inglés). En este caso todos los clientes
de un cluster deben ser visitados por el mismo vehículo, pero a
diferencia de CluVRP SCC, los clientes pueden no ser visitados en forma
consecutiva dentro de un mismo cluster, si no que, un vehículo puede
salir y reingresar a un cluster varias veces.

Se implementó un nuevo algoritmo basado en la metaheurística GRASP
(Greedy Randomized Adaptive Search Procedures) que obtuvo buenos
resultados comparados con los que encontramos en la literatura.