Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones

Resumen Técnico: Enrutamiento de Camión-Dron basado en Lockers con Consideraciones Integradas de Recogidas, Entregas y Zonas de No Vuelo (LTDRP-PDNF)

Definición del Problema
Este artículo aborda el Problema de Enrutamiento de Camión-Dron basado en Lockers con Consideraciones Integradas de Recogidas, Entregas y Zonas de No Vuelo (LTDRP-PDNF). Este problema modela un sistema de logística de última milla donde una flota de camiones, cada uno equipado con un dron, parte de un depósito central para dar servicio a estaciones de entrega y lockers inteligentes. A diferencia de los modelos tradicionales, el LTDRP-PDNF integra varias restricciones complejas del mundo real:

• Operaciones Duales: Los lockers sirven tanto como almacenamiento temporal para la recogida de clientes como nodos automatizados para el despegue, aterrizaje, transferencia de paquetes y reemplazo de batería de los drones.
• Multi-producto y Recogida/Entrega Simultánea: Los lockers tienen demandas de múltiples tipos de productos con pesos distintos, lo que requiere operaciones simultáneas de entrega y recogida (logística inversa).
• Energía Dependiente de la Carga: El consumo de energía del dron se modela explícitamente como una función del peso de la carga útil.
• Espacio Aéreo Restringido: Los drones deben navegar alrededor de zonas de no vuelo (por ejemplo, aeropuertos, bases militares), lo que requiere cálculos de desvíos basados en representaciones de espacio aéreo restringido hexagonales.
• Sincronización: El sistema requiere la coordinación entre las rutas de los camiones, las asignaciones de servicio de los drones y el reabastecimiento de baterías (en los camiones o en los lockers) para asegurar la viabilidad operativa.

El objetivo es minimizar el costo operativo total, que comprende los costos de transporte y los costos de uso de los vehículos, cumpliendo al mismo tiempo con las restricciones de capacidad, batería y espacio.

Metodología
Para resolver este problema computacionalmente desafiante de tipo NP-duro, los autores formulan el proceso de construcción de rutas secuenciales como un Proceso de Decisión de Markov (MDP) y proponen una heurística neuronal basada en Aprendizaje por Refuerzo Profundo (DRL) de dos etapas.

1. Etapa I: Enrutamiento Solo de Camión (CVRP):

   • Los autores resuelven primero un Problema de Enrutamiento de Vehículos Capacitados (CVRP) para establecer la estructura principal del enrutamiento del camión.
   • Arquitectura: Se emplea una red neuronal de codificador-decodificador. El codificador utiliza un mecanismo de atención de múltiples cabezales para mapear las coordenadas de los nodos y las demandas en representaciones latentes. El decodificador utiliza una Unidad Recurrente Recíproca Bidireccional (Bi-GRU) para capturar el contexto de enrutamiento secuencial (tanto hacia adelante como hacia atrás) para la selección de nodos.
   • Entrenamiento: La política se entrena utilizando el algoritmo REINFORCE con una línea base para minimizar los costos de la ruta. Se aplica una búsqueda local 2-opt ligera post-generación para refinar las soluciones.

2. Etapa II: Enrutamiento Coordinado Camión-Dron (LTDRP-PDNF):

   • Estrategia de Transferencia: Para abordar la complejidad del problema completo, los autores emplean una estrategia de aprendizaje por transferencia; los parámetros de la red neuronal aprendidos en la Etapa I (dominio fuente: CVRP) se transfieren al dominio objetivo (LTDRP-PDNF) para generar las rutas de los camiones, reduciendo significativamente el tiempo de entrenamiento.
   • Asignación de Despacho Híbrido: Se utiliza una heurística personalizada, MBP-ILS (Máxima Batería y Carga Útil - Búsqueda Local Mejorada), para construir las rutas de los drones basadas en las rutas de los camiones generadas.
     • MBP: Un algoritmo voraz basado en la distancia asigna los lockers a los camiones y construye las rutas iniciales de los drones mientras aplica estrictamente las restricciones de carga útil y batería. Si se viola una restricción, el dron regresa al camión más cercano para el reab abastecimiento.
     • ILS: Una búsqueda local mejorada (usando intercambios 2-opt) optimiza las rutas de los drones para reducir la distancia de viaje y evitar las zonas de no vuelo, priorizando puntos de encuentro de bajo costo.

Contribuciones Clave

• Formulación de Problema Novedosa: El artículo introduce el LTDRP-PDNF, un modelo integral que considera simultáneamente demandas de múltiples productos, recogida/entrega simultánea, consumo de energía dependiente de la carga, desvíos por zonas de no vuelo y cambio de batería asistido por lockers.
• Heurística Neuronal de Dos Etapas: El desarrollo de un marco de DRL que aprovecha el aprendizaje por transferencia desde un modelo CVRP para resolver el más complejo LTDRP-PDNF, junto con una heurística híbrida para el despacho de drones.
• Formulación de MDP: Una formulación de MDP rigurosa que captura la coordinación asíncrona entre camiones y drones, incluyendo las transiciones de estado para los niveles de batería, la carga útil y la evasión de zonas de no vuelo.

Resultados Experimentales
Se realizaron extensos experimentos numéricos en instancias de diversas escalas (20, 50 y 100 nodos) y se compararon contra solucionadores exactos (Gurobi), metaheurísticas (ALNS, PSO) y bases de comparación neuronales (AM).

• Calidad de la Solución: El método propuesto superó consistentemente a las bases de comparación. Para instancias de CVRP, logró resultados casi óptimos (por ejemplo, una brecha del 0.66% para 20 nodos) y los mejores valores de objetivo para instancias más grandes donde Gurobi no pudo encontrar soluciones dentro del límite de tiempo. Para LTDRP-PDNF, logró los mejores valores de objetivo para N=50 y N=100, superando a la base de comparación basada en atención (AM) por márgenes significativos (por ejemplo, brechas de 2.24% y 3.34% respectivamente).
• Eficiencia Computacional: El método demostró una velocidad excepcional, resolviendo instancias en segundos (por ejemplo, 0.09s para CVCVRP-100, 14.79s para LTDRP-PDNF-100), mientras que Gurobi no pudo encontrar soluciones factibles para instancias más grandes dentro de 3600 segundos, y las metaheurísticas requirieron tiempos de ejecución significativamente mayores.
• Generalización: El método exhibió fuertes capacidades de generalización, manteniendo un rendimiento superior en instancias de tamaño cruzado (30, 60, 110 nodos) que no fueron vistas durante el entrenamiento.
• Análisis de Sensibilidad: Los resultados indicaron que tanto la carga útil del dron como la capacidad de la batería impactan significativamente los costos totales, observándose rendimientos decrecientes después de ciertos umbrales.

Significancia y Reivindicaciones
El artículo afirma que el marco propuesto ofrece una solución efectiva y escalable para sistemas de entrega de camión-dron basados en lockers bajo complejas restricciones operativas. Al integrar DRL con aprendizaje por transferencia y heurísticas híbridas, el método supera los cuellos de botella computacionales de los métodos exactos y las limitaciones de adaptabilidad de las heurísticas tradicionales. Los autores sostienen que su enfoque proporciona una representación realista de los desafíos logísticos del mundo real, ofreciendo una vía viable para el despliegue de redes de entrega asistidas por drones en entornos con espacio aéreo restringido y patrones de demanda complejos. El estudio destaca que equilibrar la configuración del vehículo (carga útil/batería) con la planificación operativa es crucial para la eficiencia de costos en tales sistemas.