Desafíos del viajante de comercio con un dron

Investigadores argentinos publicaron un trabajo científico que aporta mejoras claves a un algoritmo orientado a resolver un problema de logística muy demandado en la actualidad: sincronizar a un camión con un dron para entregar mercadería a todos los clientes de una misma ruta, teniendo en cuenta las restricciones básicas de cada vehículo y minimizando el tiempo que demoran ambos vehículos en atender a los clientes y volver al depósito. Los autores del paper son Francisco Soulignac (Investigador del ICC y Profesor del DC), Gonzalo Lera Romero (Ingeniero de Investigación en ASAPP y Doctorando del DC) y Marcos Blufstein (Graduado del DC e Ingeniero de Software en Microsoft).

El problema del viajante de comercio es uno de los más tradicionales dentro de la optimización combinatoria, no obstante aún no está del todo resuelto. 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. Siempre puede ir de una ciudad hacia otra, en cualquier dirección, y conoce la distancia que hay entre cualquier par de ciudades y el costo de recorrerla. 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.

Determinar una 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).

No obstante, recientemente investigadores locales publicaron un trabajo de referencia que propone nuevas estrategias para resolver este problema NP-Hard en forma exacta, corriendo el límite de lo que sería posible resolver hoy en día. El paper, publicado en INFORMS Journal on Computing, se titula “Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone” y tiene como autores a los investigadores argentinos Francisco Soulignac, Gonzalo Lera Romero y Marcos Blufstein. Este trabajo resulta una continuación de la Tesis de Licenciatura en Ciencias de la Computación de Blufstein, que formó parte del Programa de Iniciación a la Investigación en Computación, programa que llevan adelante conjuntamente el DC e ICC y está destinado a estudiantes avanzados de la carrera.

Uso de drones como delivery y el problema del viajante de comercio

Desde hace casi una década, la empresa Amazon viene anunciando que revolucionaría la logística tradicional de entrega de paquetes a domicilio, implementando el uso de drones como vehículos de delivery (de hecho ya es una realidad en varias ciudades de Estados Unidos, con su programa “Prime Air”, diseñado para que cada viaje dure como máximo 30 minutos y muy pronto se utilizará también en Europa).

Ante esta situación, diversos grupos de investigadores vienen estudiando la aplicabilidad de los drones en los problemas de ruteo de vehículos, desde una perspectiva computacional. Por ejemplo, un clásico abordaje es el Algoritmo de Branch and Price para este problema, propuesto por Roberti and Ruthmair en el trabajo “Exact Methods for the Traveling Salesman Problem with Drone” (2021).

¿Qué particularidades tiene “el problema del viajante de comercio con un dron”? Para entenderlo de forma sencilla, un camión y un dron se mueven en simultáneo para visitar a todos los clientes de un conjunto una única vez, ya sea únicamente por el camión, únicamente por el dron, o por ambos vehículos al mismo tiempo. El dron tiene una capacidad limitada; solo puede llevar de a un paquete a la vez, después de lo cual debe regresar al camión para buscar otro paquete. Por otro lado, el dron tiene la ventaja de poder evitar la red de tráfico, lo que le permite moverse de un cliente a otro en línea recta. Una ventaja adicional es que el camión puede transportar al dron en su bodega, como si fuera un paquete más, y activarlo en algún punto de la ruta cuando sea necesario.

“En nuestro caso el problema fue una especie de excusa, ya que nuestra idea fue estudiar cómo resolver más eficientemente este tipo de problemas NP-completos, con el condimento adicional de sincronizar dos vehículos de entrega de mercadería para que trabajen juntos. Actualmente hay muchos trabajos sobre cómo podría funcionar este sistema y qué ventajas tendría, pero los resultados computacionales que muestran llegaban a resolver instancias pequeñas, con muy pocos clientes”, puntualiza Francisco Soulignac, autor del paper e investigador en el Instituto de Ciencias de la Computación (ICC UBA-CONICET).

El investigador aclara que las instancias que se encuentran tanto en la bibliografía actual como en el trabajo publicado por este grupo del ICC/DC, son instancias sintéticas: esto significa que no son basadas en datos reales (de hecho el acceso a estos datos suele estar limitado por las empresas de logística y comercio electrónico), sino que sirven como instancias iniciales para empezar a entender el problema, donde los clientes y el depósito de mercaderías están distribuidos de manera aleatoria con una distribución uniforme. “Nuestro objetivo era comparar los algoritmos basados en programación dinámica que diseñamos para este problema particular, con los algoritmos existentes en otros trabajos. No era ponernos a evaluar efectivamente cómo funcionaría un sistema así en la vida real porque no tenemos acceso a esos datos”, aclara Soulignac. De ese modo la resolución computacional con el rediseño del algoritmo apuntó a escalar una solución exacta de 39 a 99 clientes.

Una nueva solución computacional (Branch and Price + DSSR)

El algoritmo desde donde partió la solución –y en el que se basó la Tesis de Licenciatura de Blufstein- se denomina “Branch and Price”, que se centra en el problema de la sincronización y técnicamente se explora el árbol de alternativas y en cada nodo se resuelve varios problemas de programación dinámica.

“Por un lado nosotros mejoramos ese algoritmo de programación dinámica, proponiendo una búsqueda bidireccional (algo que ya existe en la literatura actual para otros problemas y que no es tan sencillo cuando hay dos vehículos) y la mayor contribución fueron nuevas ‘reglas de dominación’ para mejorar la resolución exacta de ese problema interno, descartando la cantidad de estados o posibilidades para evaluar”, plantea Soulignac. Al mismo tiempo, explica que la tesis de Blufstein fue una avance bastante importante que permitió resolver instancias de cada vez más clientes (hasta llegar a los 39 clientes), teniendo en cuenta que la complejidad de estos problemas crece exponencialmente.

“Pero al quedarnos instancias pendientes de resolver y no poder escalar más el problema, en esta nueva publicación científica reemplazamos este algoritmo por una técnica que se llama ‘Decremental State-Space Relaxation” (DSSR)’, que consiste en comenzar a resolver un problema de manera más relajada, mientras se eliminan posibilidades o aristas (en este caso son rutas que el camión o el dron no pueden tomar) e ir forzando el problema cada vez más, hasta resolver el problema en forma exacta sobre una red con pocas aristas”, describe el investigador del ICC y profesor del DC.

En este punto, Soulignac comenta que sincronizar dos vehículos resulta muy complejo en el contexto del viajante de comercio y para resolverlo tomaron inicialmente la variante del problema en donde enfrentan la menor cantidad de restricciones posibles, las limitaciones básicas de carga y de velocidad de cada vehículo. Es decir, no tomaron en cuenta la duración de la batería del dron, si tiene un rango limitado o no, si tiene que quedarse esperando al otro vehículo, etc.

Teniendo en cuenta que la cantidad de clientes que abordaron puede llegar a 99 y la aleatoriedad que puede existir entre los mismos, los investigadores se preguntaron si esta resolución se puede adaptar a más situaciones. “Implementamos distintas variantes con varias restricciones y nuestro algoritmo siguió funcionando razonablemente bien a pesar de que no nos centramos en ese problema. Siguió resistiendo, los resultados fueron razonables aceptando que el dron tenga un rango limitado de viaje o que no se pueda quedar estacionado esperando, o que haya un tiempo de servicio limitado para enviarlo, las cuales son las restricciones habituales”, afirma el investigador.

Dr. Francisco Soulignac

Por último, Soulignac reflexiona acerca de que sería relevante evaluar si esta nueva solución se puede explotar en algún otro tipo de problema de optimización combinatoria, “el tiempo nos dirá si la solución fue una casualidad o si verdaderamente se puede explotar en más situaciones de optimización. Claramente el problema de la sincronización fue nuestro problema particular y creo que lo resolvimos de manera eficiente”, concluye.