Optimización para entregas de mercadería en la última milla

Desde el ICC se desarrolla un proyecto que utiliza algoritmos de optimización para mejorar la planificación de las entregas directas de mercadería al cliente, en la etapa final de la cadena de distribución de los productos. El proyecto prevé soluciones para reducir costos en áreas tradicionales de logística y transporte pero resulta muy relevante para fenómenos actuales tales como el comercio electrónico.
Actualmente el Instituto UBA-CONICET de Ciencias de la Computación cuenta con un grupo de Investigación Operativa y Optimización Combinatoria. En este grupo se busca desarrollar técnicas algorítmicas, modelos y metodologías de cómputo que puedan ofrecer una solución concreta a problemas reales de optimización.

Uno de esos problemas tiene que ver con el ruteo de vehículos, particularmente con la distribución y entrega de mercadería, en especial en lo que se llama la “última milla”, que es la etapa final de la cadena de distribución del producto al cliente. Pero en este caso los investigadores agregan un factor de complejidad enorme: la congestión de tránsito. En especial, porque el tiempo de recorrido de los vehículos varía significativamente de acuerdo al horario y a la ruta elegida en ese horario del día.

“Dentro del área de la algoritmia, uno de los enfoques consiste en diseñar algoritmos sin necesidad de ejecutarlos para saber cuánto van a tardar. Son problemas de complejidad teórica que nos ayudan a pensar cómo implementar partes cruciales de un programa complejo, compuestos de muchos algoritmos, para hacer más eficiente el cómputo y que consuma menos recursos”, detalla Francisco Soulignac, investigador recientemente incorporado al ICC y doctor en ciencias de la computación. Para el especialista en algoritmia, este tipo de abordaje del problema permite estimar cuánto tarda efectivamente un algoritmo en resolver un problema y aplicarlo en instancias más pequeñas, en este caso de ruteo de vehículos en un determinado recorrido con varios clientes, para poder escalarlo a instancias más grandes, por ejemplo una ciudad o varias.

Sin embargo, no se trata de un fenómeno completamente nuevo. Hace unos 80 años científicos buscaron estudiar el problema del Viajante de Comercio: un comerciante quiere recorrer varias ciudades del país para vender su mercadería y necesita construir un itinerario que pase por cada una de las ciudades una sola vez, y que termine en el mismo lugar inicial, pero con la particularidad de que sea el camino más barato.

“El viajante de comercio es nuestra base teórica para pensar el delivery de paquetes con un único vehículo.  En el problema general de ruteo, distintos vehículos deben visitar varios clientes al mismo tiempo, con recorridos distintos. Esto implica determinar el costo del envío del producto desde que sale del depósito hasta que llega al cliente final y conocer el tiempo real de recorrido”, precisa Soulignac. Y enfatiza que como en muchos casos el cliente ya no va a comprar más al negocio, “existe una fuerte expectativa de que el producto sea entregado en la puerta de su domicilio, just in time”, algo que es propio de lo que está sucediendo con las empresas de comercio electrónico, que ahora también tienen su división de logística.

Dado que se trata de un problema de enorme complejidad, que apuesta su resolución mucho más allá del tradicional problema del viajante de comercio, para teorizar el algoritmo los investigadores trabajan sobre diferentes factores.

¿Cómo reducir, entonces, el costo del envío y optimizar la distribución? Una de las variables claves es la ventana de tiempo de la entrega, “cuando uno asigna una ventana de tiempo, podríamos fijar nosotros esa restricción horaria en que se entregará a algunos clientes, de algún modo estaríamos modelando esa realidad y eso puede ayudar a reducir la complejidad”, puntualiza el investigador del ICC. No obstante, desde el punto de vista de quién hace la entrega -la empresa repartidora- siempre es necesario reducir los costos de envío y tener en cuenta cuál es el mejor recorrido. Para ello se intenta optimizar el envío de los paquetes considerando la congestión de tránsito en las grandes ciudades. “Nuestro algoritmo incorpora como factor no sólo el tiempo de viaje de los vehículos, sino cómo afecta el tiempo de recorrido de acuerdo a cada viaje en particular y de la restricción horaria por parte del cliente o usuario, ya que si no se entrega en determina horario operativamente se puede perder una entrega”, complementa Soulignac.

El grupo de Investigación Operativa posee diferentes formas de estudiar la congestión y desarrollar soluciones algorítmicas concretas planificando los recorridos. La primera alternativa es la planificación táctica, donde de acuerdo a la información histórica de tráfico de una ciudad, se planifican los viajes de determinados días -a partir de mañana- durante una semana y se tienen en cuenta las ventanas de atención de los clientes. Mientras que la segunda alternativa consiste en planificar en tiempo real, donde el investigador se enfrenta a las contingencias de la ciudad (atascos, cortes de tránsito, accidentes, etc.) y debe resolver cuál es el mejor recorrido del vehículo. Este problema suele requerir una técnica más heurística. “No siempre buscamos la solución óptima, sino una solución que funcione, que esté cerca del óptimo a medida que vamos incorporando más cantidad de clientes”, aclara el doctor en ciencias de la computación.

Por último, Soulignac subraya que de acuerdo a los algoritmos que están diseñando -que recurren a técnicas de grafos- observan que ante la congestión de tránsito conviene tener ventanas de atención cada vez más pequeñas. Más allá de esto, aclara que aún el abordaje es teórico, un prototipo de algoritmo con instancias sintéticas que todavía no posee datos reales de viajes. “Nuestro próximo desafío es tomar datos de congestión del tráfico que sean reales, obtener esos datos para procesarlos y convertir nuestra solución en una herramienta, un prototipo que incluso pueda utilizarse en la web. Tenemos resultados prometedores pero queremos verlos funcionar en la práctica”, concluye.

Francisco Soulignac

Cabe recalcar que el proyecto de investigación obtuvo el Premio Google LARA 2019, lo cual le permite contar con financiamiento durante un año. Este proyecto lleva el nombre “Problemas de enrutamiento bajo congestión: algoritmos, implementaciones eficientes y datos reales”, y es desarrollado por Francisco Soulignac y Gonzalo Lera-Romero (otro investigador del instituto) con la colaboración de Juan José Miranda Bront (investigador de la Universidad Di Tella).

Publicaciones destacadas:

https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21937

http://www.optimization-online.org/DB_HTML/2020/01/7558.html