{"id":2339,"date":"2022-06-23T11:15:57","date_gmt":"2022-06-23T14:15:57","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2339"},"modified":"2022-08-09T09:36:11","modified_gmt":"2022-08-09T12:36:11","slug":"ruteo-de-vehiculos-con-optimizacion-de-costos-y-tripulacion-flexible","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/ruteo-de-vehiculos-con-optimizacion-de-costos-y-tripulacion-flexible\/","title":{"rendered":"Ruteo de veh\u00edculos con optimizaci\u00f3n de costos y tripulaci\u00f3n flexible"},"content":{"rendered":"

Investigadores del Grupo de Investigaci\u00f3n Operativa y Optimizaci\u00f3n Combinatoria del ICC trabajan en el desarrollo de algoritmos para optimizar las rutas, flotas y tripulaciones de una compa\u00f1\u00eda de transporte de larga distancia\u00a0 y, de ese modo, reducir los costos de entrega de las mercader\u00edas. El problema forma parte de una tesis de doctorado en curso.<\/b><\/p>\n

E<\/span>l ruteo de veh\u00edculos es uno de los temas habituales de la optimizaci\u00f3n combinatoria y la programaci\u00f3n lineal entera. La pregunta central que busca responder ser\u00eda: \u00bfCu\u00e1l es el conjunto \u00f3ptimo de rutas para una programaci\u00f3n de tripulaciones de veh\u00edculos que debe satisfacer las demandas de un conjunto dado de clientes? Se trata de una generalizaci\u00f3n del conocido problema del viajante de comercio, formulado hace unos 80 a\u00f1os en la comunidad cient\u00edfica, que a\u00fan no est\u00e1 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\u00f3n entre ciudades, etc.) se genera una infinidad de itinerarios posibles, volviendo muy compleja la b\u00fasqueda de una soluci\u00f3n a este problema.\u00a0\u00a0<\/span><\/p>\n

Cabe recalcar que determinar esta soluci\u00f3n \u00f3ptima es un problema <\/span>NP-Hard <\/span><\/i>(o NP-dif\u00edcil), por lo que se estima que solo existen aproximaciones a dicha soluci\u00f3n. Por este motivo, las soluciones m\u00e1s usuales para el ruteo de veh\u00edculos se basan en heur\u00edsticas (algoritmos de calidad que no aseguran encontrar la soluci\u00f3n \u00f3ptima pero que son eficientes en cuanto a tiempo).\u00a0 Estos problemas de complejidad te\u00f3rica involucran el dise\u00f1o de algoritmos, sin necesidad de ejecutarlos para saber cu\u00e1nto van a tardar, que ayudan a entender c\u00f3mo implementar partes cruciales de un programa complejo, para luego poder aplicarlo desde instancias m\u00e1s peque\u00f1as (recorridos con entregas a clientes) a instancias m\u00e1s grandes (una ciudad o varias).<\/span><\/p>\n

\"\"En este caso una compa\u00f1\u00eda de transporte de larga distancia quiere satisfacer un conjunto de solicitudes de recolecci\u00f3n y entrega de mercader\u00eda dentro de un horizonte de planificaci\u00f3n, respetando m\u00faltiples ventanas de tiempo, mediante el uso de una flota de camiones y un conjunto de conductores. El prop\u00f3sito de los investigadores es planificar de forma simult\u00e1nea las rutas de una flota de veh\u00edculos y la programaci\u00f3n de las tripulaciones. Estas tripulaciones pueden estar compuestas por uno o dos conductores y la correspondencia veh\u00edculo-tripulaci\u00f3n no es fija en el tiempo, teniendo cada conductor una programaci\u00f3n independiente. De este modo se permite una mayor flexibilidad de planificaci\u00f3n y un uso m\u00e1s eficiente de los veh\u00edculos (ya que podr\u00edan estar circulando constantemente). Pero en contrapartida, resulta necesaria una alta sincronizaci\u00f3n entre todas las rutas.<\/span><\/p>\n

El objetivo es desarrollar algoritmos de planificaci\u00f3n para optimizar los costos operativos desde tres aristas espec\u00edficas: 1) Entregar la mercader\u00eda lo antes posible (ya que cada d\u00eda de atraso respecto a la fecha pautada implica una penalidad); 2) Minimizar los kil\u00f3metros recorridos por los camiones en las diferentes rutas y 3) Minimizar el costo de los remises externos a la compa\u00f1\u00eda (despu\u00e9s de su descanso un conductor se traslada de una localidad a otra para subirse a un nuevo cami\u00f3n).<\/span><\/p>\n

\u201c<\/span>Nosotros tomamos este problema de la compa\u00f1\u00eda que nos cont\u00f3 una persona de la academia para un caso de distribuci\u00f3n de mercader\u00eda, 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\u00f3n y entrega<\/span><\/i>\u201d, explica <\/span>Paula Zabala<\/b>, investigadora del ICC e integrante del Grupo de Investigaci\u00f3n Operativa.<\/span><\/p>\n

Una de las dificultades a tener en cuenta para este caso, es que la mayor\u00eda de la bibliograf\u00eda disponible sobre log\u00edstica no considera que los conductores descansan, es decir, que los camiones est\u00e1n manejados por conductores que no pueden conducir las 24 horas seguidas y no tienen en cuenta las reglas laborales vigentes.<\/span><\/p>\n

\u201c<\/span>El aporte diferencial de nuestro trabajo es, por un lado, adaptar el programa a las reglas de la empresa, permitir que los veh\u00edculos no est\u00e9n asociados a los conductores sino que sean independientes. Por m\u00e1s que cada cami\u00f3n puede estar conducido por uno o dos tripulantes, las regulaciones consideran que debe descansar por lo menos 12 horas por cada per\u00edodo de 24 horas y un d\u00eda de franco por cada per\u00edodo de siete d\u00edas de trabajo. Cada conductor puede descender de un cami\u00f3n para descansar o viajar hacia otra ciudad en un conjunto determinado de ubicaciones. Y adem\u00e1s 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<\/span><\/i>\u201d, puntualiza la investigadora del ICC y doctora en ciencias de la computaci\u00f3n.<\/span><\/p>\n

Y aclara que al desarrollar los algoritmos de optimizaci\u00f3n con esas condiciones, se genera tambi\u00e9n una interdependencia entre las rutas: \u201c<\/span>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\u00f3metros recorridos sol\u00edan ser independientes de estos factores. Y las rutas se tienen que ir recorriendo al pasar de un cami\u00f3n al otro. Y si se llega a modificar la ruta de un cami\u00f3n, eso puede hacer que haya que modificar el resto de las rutas, por lo que el problema se vuelve mucho m\u00e1s complejo y hay m\u00e1s juego de combinaciones<\/span><\/i>\u201d.<\/span><\/p>\n

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

\u00bfC\u00f3mo fue el proceso de armar los algoritmos para este caso en particular? \u201c<\/span>Para resolver instancias en la pr\u00e1ctica, que es lo que podr\u00edamos ofrecerle a una compa\u00f1\u00eda de este tipo, desarrollamos algoritmos heur\u00edsticos para ver cu\u00e1l funciona mejor (al tener una soluci\u00f3n factible se va ajustando hasta bajar los costos lo m\u00e1s posible) y encontramos soluciones de alta calidad que ya est\u00e1n 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\u00f3n con las tripulaciones individuales y, en algunos casos, elimin\u00f3 este costo por completo<\/span><\/i>\u201d, afirma Zabala (ver los resultados publicados en el paper<\/span> \u201cA metaheuristic for crew scheduling in a pickup-and-delivery problem with time windows\u201d, 2021<\/span><\/a>).<\/span><\/p>\n

Al mismo tiempo, se est\u00e1n desarrollando algoritmos exactos basados en programaci\u00f3n lineal entera, que forman parte de la etapa final de la tesis de Lucci. “<\/span>Con los algoritmos exactos podemos correr instancias mucho m\u00e1s chicas que no necesariamente corren como un programa pero que nos servir\u00edan para testear y evaluar distintos escenarios, especialmente en optimizaci\u00f3n de costos. Por ejemplo si a la empresa le conviene invertir en m\u00e1s recursos tales como contratar m\u00e1s conductores o comprar m\u00e1s camiones. De ese modo, antes de tomar una decisi\u00f3n operativa, la empresa puede evaluarla para conocer de antemano qu\u00e9 rentabilidad tendr\u00eda al ir variando estos recursos<\/span><\/i>\u201d, complementa la directora del proyecto.\u00a0\u00a0<\/span><\/p>\n

Por \u00faltimo, una ventaja comparativa de los algoritmos desarrollados por el Grupo de Investigaci\u00f3n Operativa tiene que ver con la calidad de cada algoritmo, ya que no es r\u00edgido sino totalmente flexible a las reglas laborales del pa\u00eds o de la compa\u00f1\u00eda en cuesti\u00f3n. \u201c<\/span>Nuestros algoritmos tienen en cuenta cu\u00e1nto tiempo descansa el conductor, d\u00f3nde 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\u00edculos (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\u00f3n, permite una mayor flexibilidad de planificaci\u00f3n y un uso m\u00e1s eficiente de la flotas<\/span><\/i>\u201d, concluye Zabala.<\/span><\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"

Investigadores del Grupo de Investigaci\u00f3n Operativa y Optimizaci\u00f3n Combinatoria del ICC trabajan en el desarrollo de algoritmos para optimizar las rutas, flotas y tripulaciones de una compa\u00f1\u00eda de transporte de larga distancia y, de ese modo, reducir los costos de entrega de las mercader\u00edas. El problema forma parte de una tesis de doctorado en curso.<\/p>\n","protected":false},"author":9,"featured_media":2341,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[45,44,43],"class_list":["post-2339","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-noticias","tag-algoritmos","tag-investigacion-operativa","tag-optimizacion-combinatoria"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2339","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=2339"}],"version-history":[{"count":2,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2339\/revisions"}],"predecessor-version":[{"id":2343,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2339\/revisions\/2343"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2341"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}