Investigadores del Grupo de Investigación Operativa y Optimización Combinatoria del ICC trabajan en el desarrollo de algoritmos para optimizar las rutas, flotas y tripulaciones de una compañía de transporte de larga distancia  y, de ese modo, reducir los costos de entrega de las mercaderías. El problema forma parte de una tesis de doctorado en curso.

El ruteo de vehículos es uno de los temas habituales de la optimización combinatoria y la programación lineal entera. La pregunta central que busca responder sería: ¿Cuál es el conjunto óptimo de rutas para una programación de tripulaciones de vehículos que debe satisfacer las demandas de un conjunto dado de clientes? Se trata de una generalización del conocido problema del viajante de comercio, formulado hace unos 80 años en la comunidad científica, que aún no está resuelto en la algoritmia. Claramente a medida que se incrementa la cantidad de ciudades y las restricciones para ir de una a otra (horarios, distancias, costos, conexión entre ciudades, etc.) se genera una infinidad de itinerarios posibles, volviendo muy compleja la búsqueda de una solución a este problema.

Cabe recalcar que determinar esta solución óptima es un problema NP-Hard (o NP-difícil), por lo que se estima que solo existen aproximaciones a dicha solución. Por este motivo, las soluciones más usuales para el ruteo de vehículos se basan en heurísticas (algoritmos de calidad que no aseguran encontrar la solución óptima pero que son eficientes en cuanto a tiempo).  Estos problemas de complejidad teórica involucran el diseño de algoritmos, sin necesidad de ejecutarlos para saber cuánto van a tardar, que ayudan a entender cómo implementar partes cruciales de un programa complejo, para luego poder aplicarlo desde instancias más pequeñas (recorridos con entregas a clientes) a instancias más grandes (una ciudad o varias).

En este caso una compañía de transporte de larga distancia quiere satisfacer un conjunto de solicitudes de recolección y entrega de mercadería dentro de un horizonte de planificación, respetando múltiples ventanas de tiempo, mediante el uso de una flota de camiones y un conjunto de conductores. El propósito de los investigadores es planificar de forma simultánea las rutas de una flota de vehículos y la programación de las tripulaciones. Estas tripulaciones pueden estar compuestas por uno o dos conductores y la correspondencia vehículo-tripulación no es fija en el tiempo, teniendo cada conductor una programación independiente. De este modo se permite una mayor flexibilidad de planificación y un uso más eficiente de los vehículos (ya que podrían estar circulando constantemente). Pero en contrapartida, resulta necesaria una alta sincronización entre todas las rutas.

El objetivo es desarrollar algoritmos de planificación para optimizar los costos operativos desde tres aristas específicas: 1) Entregar la mercadería lo antes posible (ya que cada día de atraso respecto a la fecha pautada implica una penalidad); 2) Minimizar los kilómetros recorridos por los camiones en las diferentes rutas y 3) Minimizar el costo de los remises externos a la compañía (después de su descanso un conductor se traslada de una localidad a otra para subirse a un nuevo camión).

“Nosotros tomamos este problema de la compañía que nos contó una persona de la academia para un caso de distribución de mercadería, trazamos un mapa de las rutas y lo aplicamos a 15 ciudades de la Argentina para generar instancias sobre esas ciudades, a partir de 3.000 solicitudes mensuales de recolección y entrega”, explica Paula Zabala, investigadora del ICC e integrante del Grupo de Investigación Operativa.

Una de las dificultades a tener en cuenta para este caso, es que la mayoría de la bibliografía disponible sobre logística no considera que los conductores descansan, es decir, que los camiones están manejados por conductores que no pueden conducir las 24 horas seguidas y no tienen en cuenta las reglas laborales vigentes.

“El aporte diferencial de nuestro trabajo es, por un lado, adaptar el programa a las reglas de la empresa, permitir que los vehículos no estén asociados a los conductores sino que sean independientes. Por más que cada camión puede estar conducido por uno o dos tripulantes, las regulaciones consideran que debe descansar por lo menos 12 horas por cada período de 24 horas y un día de franco por cada período de siete días de trabajo. Cada conductor puede descender de un camión para descansar o viajar hacia otra ciudad en un conjunto determinado de ubicaciones. Y además los conductores pueden viajar entre localidades en remises, con un costo adicional para la empresa. Por otro lado, al permitir este relevo de conductores, no hay duplas fijas de conductores sino que son independientes de un conductor a otro. Eso aumenta la productividad pero complejiza el problema”, puntualiza la investigadora del ICC y doctora en ciencias de la computación.

Y aclara que al desarrollar los algoritmos de optimización con esas condiciones, se genera también una interdependencia entre las rutas: “si bien las rutas que conectan las ciudades son independientes de la flota de camiones y conductores, son rutas que se tienen que sincronizar de alguna manera en cuanto a tiempo y espacio, ya que los kilómetros recorridos solían ser independientes de estos factores. Y las rutas se tienen que ir recorriendo al pasar de un camión al otro. Y si se llega a modificar la ruta de un camión, eso puede hacer que haya que modificar el resto de las rutas, por lo que el problema se vuelve mucho más complejo y hay más juego de combinaciones”.

El desarrollo de las posibles soluciones para este problema confluyó en la tesis del estudiante de doctorado Mauro Lucci, la cual comenzó en 2019 y se encuentra en la etapa final de su elaboración, dirigida por Paula Zabala (ICC UBA-CONICET) y co-dirigida por Daniel Severin (Universidad Nacional de Rosario, UNR). Se trata de un modelo teórico de alto valor agregado para aplicar en cualquier caso similar de logística y transporte.

¿Cómo fue el proceso de armar los algoritmos para este caso en particular? “Para resolver instancias en la práctica, que es lo que podríamos ofrecerle a una compañía de este tipo, desarrollamos algoritmos heurísticos para ver cuál funciona mejor (al tener una solución factible se va ajustando hasta bajar los costos lo más posible) y encontramos soluciones de alta calidad que ya están publicadas. Incluso descubrimos que la posibilidad de llevar un conductor adicional redujo el costo de los traslados externos en 2,25 veces en promedio en comparación con las tripulaciones individuales y, en algunos casos, eliminó este costo por completo”, afirma Zabala (ver los resultados publicados en el paper “A metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows”, 2021).

Al mismo tiempo, se están desarrollando algoritmos exactos basados en programación lineal entera, que forman parte de la etapa final de la tesis de Lucci. «Con los algoritmos exactos podemos correr instancias mucho más chicas que no necesariamente corren como un programa pero que nos servirían para testear y evaluar distintos escenarios, especialmente en optimización de costos. Por ejemplo si a la empresa le conviene invertir en más recursos tales como contratar más conductores o comprar más camiones. De ese modo, antes de tomar una decisión operativa, la empresa puede evaluarla para conocer de antemano qué rentabilidad tendría al ir variando estos recursos”, complementa la directora del proyecto.

Por último, una ventaja comparativa de los algoritmos desarrollados por el Grupo de Investigación Operativa tiene que ver con la calidad de cada algoritmo, ya que no es rígido sino totalmente flexible a las reglas laborales del país o de la compañía en cuestión. “Nuestros algoritmos tienen en cuenta cuánto tiempo descansa el conductor, dónde debe descansar (en este caso siempre en una localidad y no al costado de la ruta), las distancias entre paradas, los relevos entre conductores e incluso la velocidad de los vehículos (90 kms promedio) o tipo de terreno de las rutas (asfalto), ya que todos son factores que en definitiva influyen en el tiempo final de los recorridos. Aunque esto requiere una alta sincronización, permite una mayor flexibilidad de planificación y un uso más eficiente de la flotas”, concluye Zabala.