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

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.