• Título: Un Algoritmo de Búsqueda Local Basado en Programación Lineal Entera Aplicado al Problema de Ruteo de Vehículos Multiperíodo.
• Directores: Juan José Miranda Bront y Agustín Montero.
• Jurado: Irene Loiseau y Federico Pousa.
• Abstract:

Los Problemas de Ruteo de Veh ́ıculos (VRP, por su sigla en ingl ́es) aparecen en la organización de las tareas de distribución de mercadería o personal, planificación de recorridos en robótica móvil o prestación de servicios a un conjunto de clientes mediante una flota de vehículos. Los vehículos realizan sus movimientos a través de una red partiendo de puntos fijos, llamados depósitos. Cada tramo entre dos clientes de esta red tiene asociado un costo y/o tiempo de viaje que puede depender de muchos factores, como por ejemplo del tipo de vehículo o del período durante el cual el tramo es recorrido. Este tipo de problemas es de gran relevancia en empresas de tama ̃no peque ̃no a grande, tanto en el sector público como privado. Estos problemas suelen ser NP-Hard y desde el punto de vista del modelado y resolución, las características de cada aplicación conllevan un desafío particular. Una excelente presentaci ́on sobre diferentes variantes de estos problemas puede verse en Toth & Vigo (2014).

Por cuestiones prácticas, en general el abordaje que se hace de los problemas de ruteo suele considerar las restricciones operativas de manera abstracta, en algunos casos simplificada. En muchas aplicaciones, la planificación suele limitarse a determinar cómo realizar la distribución diaria. Estos enfoques han producido significativas mejoras tanto en términos de costos como en la calidad del servicio. Sin embargo, debido a los avances obtenidos en términos algorítmicos y su consiguiente impacto en la práctica, actualmente la tendencia tanto en investigación como en desarrollo es a complejizar los problemas. Algunas variantes con creciente interés por parte de la comunidad científica consideran agrupar decisiones usualmente tomadas en etapas separadas (e.g., planificaci ́on de más de un dáa, combinación con asignación de tripulaciones) así como tambi ́en incorporar restricciones cada vez m ́as realistas (e.g., orden de la carga dentro del camión, balance respecto del eje central por cuestiones de seguridad). En esta dirección, recientemente se propuso en el marco del VeRoLog Solver Challenge 2017 (VSC2017) una variante proveniente de una aplicación real en la distribución de herramientas para la medición de calidad en la industria lechera. Partiendo de la demanda de clientes por determinado tipo de herramientas, el problema consiste en resolver de manera integrada la planificación de la utilización de las herramientas en un horizonte de tiempo, medido en días, y la distribución de las mismas incorporando la logística necesaria para el ruteo de las mismas en cada día.

El problema planteado presenta características similares al VRP con Ventanas de Tiempo (VRPTW), junto con características del clásico VRP con Pickup y Delivery (VRPPD) y VRP con capacidades (CVRP). Se tiene la posibilidad que una herramienta sea trasladada de un cliente que finaliza a otro que inicia, permitiendo reducir el número de herramientas totales necesarias a cambio de complejizar las operaciones. Instancias realistas de distintos tamaños son propouestas, llegando hasta 2500 clientes y un horizonte de tiempo de 75 días en las instancias de mayor tamaño.

En esta tesis se proponen algoritmos de búsqueda local, utilizando un modelo de reubicación basado en técnicas de programaci ́on lineal entera (PLE). Un ejemplo de este esquema para el caso de ruteo de vehículos en períodos simples puede verse en Montero et al. (2017). Se utiliza el paradigma de destrucción/reparación en donde un conjunto de nodos es removido de las rutas y reinsertado a través de la resolución del modelo. Los experimentos realizados muestran que el enfoque utilizado es capaz de mejorar las mejores soluciones obtenidas en la competencia. Además, dicho enfoque es capaz de ser extendido para ser utilizado en diversos contextos.