Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone

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...

Descripción completa

Detalles Bibliográficos
Autores principales: Blufstein, Marcos, Lera-Romero, Gonzalo, Miranda-Bront, Juan José, Soulignac, Francisco J.
Formato: Objeto de conferencia Resumen
Lenguaje:Español
Publicado: 2021
Materias:
Ciencias Informáticas
Drone
Ruteo
Camiones
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/141649
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-06.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-141649
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Drone
Ruteo
Camiones
spellingShingle Ciencias Informáticas
Drone
Ruteo
Camiones
Blufstein, Marcos
Lera-Romero, Gonzalo
Miranda-Bront, Juan José
Soulignac, Francisco J.
Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
topic_facet Ciencias Informáticas
Drone
Ruteo
Camiones
description 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.
format Objeto de conferencia
Resumen
author Blufstein, Marcos
Lera-Romero, Gonzalo
Miranda-Bront, Juan José
Soulignac, Francisco J.
author_facet Blufstein, Marcos
Lera-Romero, Gonzalo
Miranda-Bront, Juan José
Soulignac, Francisco J.
author_sort Blufstein, Marcos
title Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
title_short Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
title_full Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
title_fullStr Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
title_full_unstemmed Mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
title_sort mejoras a un algoritmo de programación dinámica para el problema del viajante de comercio con un drone
publishDate 2021
url http://sedici.unlp.edu.ar/handle/10915/141649
http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-06.pdf
work_keys_str_mv AT blufsteinmarcos mejorasaunalgoritmodeprogramaciondinamicaparaelproblemadelviajantedecomercioconundrone
AT leraromerogonzalo mejorasaunalgoritmodeprogramaciondinamicaparaelproblemadelviajantedecomercioconundrone
AT mirandabrontjuanjose mejorasaunalgoritmodeprogramaciondinamicaparaelproblemadelviajantedecomercioconundrone
AT soulignacfranciscoj mejorasaunalgoritmodeprogramaciondinamicaparaelproblemadelviajantedecomercioconundrone
bdutipo_str Repositorios
_version_ 1764820459505844227

Ejemplares similares