Upload resources

Upload your works to SEDICI to increase its visibility and improve its impact

 

Show simple item record

dc.date.accessioned 2022-09-06T16:57:46Z
dc.date.available 2022-09-06T16:57:46Z
dc.date.issued 2021
dc.identifier.uri http://sedici.unlp.edu.ar/handle/10915/141649
dc.description.abstract En la última década surgieron distintos problemas de ruteo en los que una flota de camiones y drones se agrupan para realizar envíos al consumidor en problemas de logística de última milla. La idea es aprovechar las ventajas de ambos tipos de vehículos: los camiones transportan una gran cantidad de mercadería aunque se mueven lentamente por la red de tráfico; los drones se desplazan velozmente por moverse fuera de la red de tráfico, aunque tienen menor capacidad y autonomía. En este contexto, los problemas más simples consisten en la generación de una única ruta en la que un camión y un drone se unen para atender a un conjunto de clientes. En el problema de viajante de comercio con un drone (TSP-D) el camión parte de un depósito llevando un drone en su interior. Cada vez que el camión visita un cliente v, puede optar por lanzar el drone con un único paquete para visitar un cliente w que no va a ser visitado por el camión. Luego, el camión y el drone continúan sus rutas por separado. Una vez que el drone atiende a w, el mismo viaja a la ubicación de otro cliente z / r donde se encuentra con el camión nuevamente para continuar con la ruta en forma conjunta. El objetivo es minimizar el tiempo que demoran el camión y el drone en atender a todos los clientes y volver al depósito, sin tener en cuenta los tiempos de servicio, carga del drone o sincronización entre ambos vehículos. Recientemente Roberti y Ruthmair (Exact methods for the traveling salesman problem with drone. Transp. Sci., 55(2): 315-335, 2021) propusieron un algoritmo de programación dinámica, basado en un esquema de labeling, para resolver TSP-D. Embebiendo una versión relajada del mismo dentro de un algoritmo de tipo branch- cut-and-price pudieron resolver todas las instancias (de prueba) con 19 clientes, la mayoría con 29 clientes y algunas con 39 clientes. En esta charla mostramos nuevas reglas de dominación para mejorar la eficiencia del algoritmo de labeling. Asimismo, estudiamos distintas opciones para la relajación del algoritmo que permiten mejorar las cotas inferiores al resolver cada nodo del árbol de branching. El nuevo algoritmo resuelve varias de las instancias (de prueba) previamente no resueltas en la misma cantidad de tiempo. es
dc.format.extent 19-19 es
dc.language es es
dc.subject Drone es
dc.subject Ruteo es
dc.subject Camiones es
dc.title Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone es
dc.type Objeto de conferencia es
sedici.identifier.uri http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-06.pdf es
sedici.identifier.issn 2618-3277 es
sedici.creator.person Blufstein, Marcos es
sedici.creator.person Lera-Romero, Gonzalo es
sedici.creator.person Miranda-Bront, Juan José es
sedici.creator.person Soulignac, Francisco J. es
sedici.subject.materias Ciencias Informáticas es
sedici.description.fulltext true es
mods.originInfo.place Sociedad Argentina de Informática e Investigación Operativa es
sedici.subtype Resumen es
sedici.rights.license Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0)
sedici.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/
sedici.date.exposure 2021-10
sedici.relation.event IV Simposio Argentino de Informática Industrial e Investigación Operativa (SIIIO 2021) - JAIIO 50 (Modalidad virtual) es
sedici.description.peerReview peer-review es


Download Files

This item appears in the following Collection(s)

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Except where otherwise noted, this item's license is described as Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0)