{"id":2587,"date":"2024-03-04T11:53:01","date_gmt":"2024-03-04T14:53:01","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=2587"},"modified":"2024-06-14T13:51:47","modified_gmt":"2024-06-14T16:51:47","slug":"desafios-del-viajante-de-comercio-con-un-dron","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/desafios-del-viajante-de-comercio-con-un-dron\/","title":{"rendered":"Desaf\u00edos del viajante de comercio con un dron"},"content":{"rendered":"

Investigadores argentinos publicaron un trabajo cient\u00edfico que aporta mejoras claves a un algoritmo orientado a resolver un problema de log\u00edstica muy demandado en la actualidad: sincronizar a un cami\u00f3n con un dron para entregar mercader\u00eda a todos los clientes de una misma ruta, teniendo en cuenta las restricciones b\u00e1sicas de cada veh\u00edculo y minimizando el tiempo que demoran ambos veh\u00edculos en atender a los clientes y volver al dep\u00f3sito. Los autores del paper son Francisco Soulignac (Investigador del ICC y Profesor del DC), Gonzalo Lera Romero (Ingeniero de Investigaci\u00f3n en ASAPP y Doctorando del DC) y Marcos Blufstein (Graduado del DC e Ingeniero de Software en Microsoft).<\/b><\/p>\n

El problema del viajante de comercio es uno de los m\u00e1s tradicionales dentro de la optimizaci\u00f3n combinatoria, no obstante a\u00fan no est\u00e1 del todo resuelto. Un comerciante quiere recorrer varias ciudades del pa\u00eds para vender su mercader\u00eda 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\u00e1s barato. Siempre puede ir de una ciudad hacia otra, en cualquier direcci\u00f3n, 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\u00f3n entre ciudades, etc.) se genera una infinidad de itinerarios posibles, volviendo muy compleja la b\u00fasqueda de una soluci\u00f3n a este problema.<\/p>\n

Determinar una soluci\u00f3n \u00f3ptima es un problema\u00a0NP-Hard\u00a0<\/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).<\/p>\n

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\u00edmite de lo que ser\u00eda posible resolver hoy en d\u00eda. El paper, publicado en\u00a0INFORMS Journal on Computing<\/i>, se titula \u201cDecremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone<\/i><\/b><\/a>\u201d y tiene como autores a los investigadores argentinos\u00a0Francisco Soulignac<\/b>,\u00a0Gonzalo Lera Romero<\/b>\u00a0y\u00a0Marcos Blufstein<\/b>. Este trabajo resulta una continuaci\u00f3n de la\u00a0Tesis de Licenciatura en Ciencias de la Computaci\u00f3n de Blufstein<\/a>, que form\u00f3 parte del\u00a0Programa de Iniciaci\u00f3n a la Investigaci\u00f3n en Computaci\u00f3n<\/a>, programa que llevan adelante conjuntamente el DC e ICC y est\u00e1 destinado a estudiantes avanzados de la carrera.<\/p>\n

Uso de drones como delivery y el problema del viajante de comercio<\/b><\/p>\n

Desde hace casi una d\u00e9cada, la empresa Amazon viene\u00a0anunciando<\/a>\u00a0que revolucionar\u00eda la log\u00edstica tradicional de entrega de paquetes a domicilio, implementando el uso de drones como veh\u00edculos de delivery (de hecho ya es una realidad en varias ciudades de Estados Unidos, con su programa \u201cPrime Air\u201d, dise\u00f1ado para que cada viaje dure como m\u00e1ximo 30 minutos y muy pronto se utilizar\u00e1 tambi\u00e9n en Europa).<\/p>\n

Ante esta situaci\u00f3n, diversos grupos de investigadores vienen estudiando la aplicabilidad de los drones en los problemas de ruteo de veh\u00edculos, desde una perspectiva computacional. Por ejemplo, un cl\u00e1sico abordaje es el Algoritmo de Branch and Price para este problema, propuesto por Roberti and Ruthmair en el trabajo \u201cExact Methods for the Traveling Salesman Problem with Drone<\/a>\u201d (2021).<\/p>\n

\u00bfQu\u00e9 particularidades tiene \u201cel problema del viajante de comercio con un dron\u201d? Para entenderlo de forma sencilla, un cami\u00f3n y un dron se mueven en simult\u00e1neo para visitar a todos los clientes de un conjunto una \u00fanica vez, ya sea \u00fanicamente por el cami\u00f3n, \u00fanicamente por el dron, o por ambos veh\u00edculos al mismo tiempo. El dron tiene una capacidad limitada; solo puede llevar de a un paquete a la vez, despu\u00e9s de lo cual debe regresar al cami\u00f3n para buscar otro paquete. Por otro lado, el dron tiene la ventaja de poder evitar la red de tr\u00e1fico, lo que le permite moverse de un cliente a otro en l\u00ednea recta. Una ventaja adicional es que el cami\u00f3n puede transportar al dron en su bodega, como si fuera un paquete m\u00e1s, y activarlo en alg\u00fan punto de la ruta cuando sea necesario.<\/p>\n

\u201cEn nuestro caso el problema fue una especie de excusa, ya que nuestra idea fue estudiar c\u00f3mo resolver m\u00e1s eficientemente este tipo de problemas NP-completos, con el condimento adicional de sincronizar dos veh\u00edculos de entrega de mercader\u00eda para que trabajen juntos. Actualmente hay muchos trabajos sobre c\u00f3mo podr\u00eda funcionar este sistema y qu\u00e9 ventajas tendr\u00eda, pero los resultados computacionales que muestran llegaban a resolver instancias peque\u00f1as, con muy pocos clientes<\/i>\u201d, puntualiza\u00a0Francisco Soulignac<\/b>, autor del paper e investigador en el Instituto de Ciencias de la Computaci\u00f3n (ICC UBA-CONICET<\/a>).<\/p>\n

El investigador aclara que las instancias que se encuentran tanto en la bibliograf\u00eda actual como en el trabajo publicado por este grupo del ICC\/DC, son instancias sint\u00e9ticas: esto significa que no son basadas en datos reales (de hecho el acceso a estos datos suele estar limitado por las empresas de log\u00edstica y comercio electr\u00f3nico), sino que sirven como instancias iniciales para empezar a entender el problema, donde los clientes y el dep\u00f3sito de mercader\u00edas est\u00e1n distribuidos de manera aleatoria con una distribuci\u00f3n uniforme. \u201cNuestro objetivo era comparar los algoritmos basados en programaci\u00f3n din\u00e1mica que dise\u00f1amos para este problema particular, con los algoritmos existentes en otros trabajos. No era ponernos a evaluar efectivamente c\u00f3mo funcionar\u00eda un sistema as\u00ed en la vida real porque no tenemos acceso a esos datos<\/i>\u201d, aclara Soulignac. De ese modo la resoluci\u00f3n computacional con el redise\u00f1o del algoritmo apunt\u00f3 a escalar una soluci\u00f3n exacta de 39 a 99 clientes.<\/p>\n

Una nueva soluci\u00f3n computacional (Branch and Price + DSSR)<\/b><\/p>\n

El algoritmo desde donde parti\u00f3 la soluci\u00f3n \u2013y en el que se bas\u00f3 la Tesis de Licenciatura de Blufstein- se denomina \u201cBranch and Price\u201d, que se centra en el problema de la sincronizaci\u00f3n y t\u00e9cnicamente se explora el \u00e1rbol de alternativas y en cada nodo se resuelve varios problemas de programaci\u00f3n din\u00e1mica.<\/p>\n

\u201cPor un lado nosotros mejoramos ese algoritmo de programaci\u00f3n din\u00e1mica, proponiendo una b\u00fasqueda bidireccional (algo que ya existe en la literatura actual para otros problemas y que no es tan sencillo cuando hay dos veh\u00edculos) y la mayor contribuci\u00f3n fueron nuevas \u2018reglas de dominaci\u00f3n\u2019 para mejorar la resoluci\u00f3n exacta de ese problema interno, descartando la cantidad de estados o posibilidades para evaluar<\/i>\u201d, plantea Soulignac. Al mismo tiempo, explica que la tesis de Blufstein fue una avance bastante importante que permiti\u00f3 resolver instancias de cada vez m\u00e1s clientes (hasta llegar a los 39 clientes), teniendo en cuenta que la complejidad de estos problemas crece exponencialmente.<\/p>\n

\"\"<\/p>\n

\u201cPero al quedarnos instancias pendientes de resolver y no poder escalar m\u00e1s el problema, en esta nueva publicaci\u00f3n cient\u00edfica reemplazamos este algoritmo por una t\u00e9cnica que se llama \u2018Decremental State-Space Relaxation\u201d (DSSR)\u2019, que consiste en comenzar a resolver un problema de manera m\u00e1s relajada, mientras se eliminan posibilidades o aristas (en este caso son rutas que el cami\u00f3n o el dron no pueden tomar) e ir forzando el problema cada vez m\u00e1s, hasta resolver el problema en forma exacta sobre una red con pocas aristas\u201d<\/em>, describe el investigador del ICC y profesor del DC.<\/p>\n

En este punto, Soulignac comenta que sincronizar dos veh\u00edculos 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\u00e1sicas de carga y de velocidad de cada veh\u00edculo. Es decir, no tomaron en cuenta la duraci\u00f3n de la bater\u00eda del dron, si tiene un rango limitado o no, si tiene que quedarse esperando al otro veh\u00edculo, etc.<\/p>\n

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\u00f3n se puede adaptar a m\u00e1s situaciones. \u201cImplementamos distintas variantes con varias restricciones y nuestro algoritmo sigui\u00f3 funcionando razonablemente bien a pesar de que no nos centramos en ese problema. Sigui\u00f3 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<\/em>\u201d, afirma el investigador.<\/p>\n

\n
\"\"

Dr. Francisco Soulignac<\/p><\/div><\/p>\n

\n<\/div>\n

Por \u00faltimo, Soulignac reflexiona acerca de que ser\u00eda relevante evaluar si esta nueva soluci\u00f3n se puede explotar en alg\u00fan otro tipo de problema de optimizaci\u00f3n combinatoria, \u201cel tiempo nos dir\u00e1 si la soluci\u00f3n fue una casualidad o si verdaderamente se puede explotar en m\u00e1s situaciones de optimizaci\u00f3n. Claramente el problema de la sincronizaci\u00f3n fue nuestro problema particular y creo que lo resolvimos de manera eficiente<\/em>\u201d, concluye.<\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"

Investigadores argentinos publicaron un trabajo cient\u00edfico que aporta mejoras claves a un algoritmo orientado a sincronizar a un cami\u00f3n con un dron para entregar mercader\u00eda a todos los clientes de una misma ruta. Los autores del paper son Francisco Soulignac (Investigador del ICC y Profesor del DC), Gonzalo Lera Romero (Ingeniero de Investigaci\u00f3n en ASAPP y Doctorando del DC) y Marcos Blufstein (Graduado del DC e Ingeniero de Software en Microsoft).<\/p>\n","protected":false},"author":9,"featured_media":2590,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[45,44,43],"class_list":["post-2587","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\/2587","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=2587"}],"version-history":[{"count":2,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2587\/revisions"}],"predecessor-version":[{"id":2592,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/2587\/revisions\/2592"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/2590"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=2587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=2587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=2587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}