Formulaciones de PLE para un abordaje simultáneo en un problema de ruteo de vehículos con cambios de tripulación

LUCCI, MAURO; SEVERÍN, DANIEL; PAULA ZABALA

Simposio; SIIIO 2021 - Simposio Argentino de Informática Industrial e Investigación Operativa; 2021

Sociedad Argentina de Informática

Una compañía dedicada a la distribución de café dispone de una flota homogénea de camiones y de una planta de conductores que deben ser organizados para cumplir con un conjunto de solicitudes de recolección-y-entrega de mercadería con ventanas de tiempo. El objetivo es encontrar una asignación optima para estos recursos que minimice los costos operativos, sujeto a una serie de restricciones operativas y laborales. Las tripulaciones pueden estar conformadas por uno o dos conductores y cada uno de ellos puede ser relevado durante el recorrido. Adicionalmente, los conductores pueden utilizar transportes externos a la compañía, por un costo adicional que se desea minimizar. Es frecuente en la literatura la aplicación de un abordaje secuencial para resolver este tipo de problemas. Una primera etapa involucra rutear los camiones, ignorando las restricciones de los conductores, y sobre las rutas previamente construidas se asignan las tripulaciones en una segunda etapa. Esto resulta en dos subproblemas mas fáciles de resolver, pero sin garantía de optimalidad global ni de factibilidad (la segunda etapa podrá resultar infactible a partir de las rutas determinadas en la primera). Por el contrario, un abordaje simultaneo ha sido mucho menos estudiado en la literatura. Este ultimo supone un gran desafío desde un punto de vista computacional, dado que emergen complejas restricciones de sincronización entre los recursos. Partiendo de modelos matemáticos basados en teoría de grafos, se presentaran dos formulaciones de PLE compactas para el problema en estudio, siguiendo un abordaje simultaneo. Mediante experiencias computacionales, las formulaciones serán comparadas sobre diversas instancias de prueba resueltas con un solver específico, a n de determinar cual de ellas resulta mas competitiva para futuros desarrollos.