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

Resumo Técnico: Roteamento de Caminhão-Drone Baseado em Armários com Considerações Integradas de Coletas, Entregas e Zonas de Não Voo (LTDRP-PDNF)

Definição do Problema
Este artigo aborda o Problema de Roteamento de Caminhão-Drone Baseado em Armários com Considerações Integradas de Coletas, Entregas e Zonas de Não Voo (LTDRP-PDNF). Este problema modela um sistema de logística de última milha onde uma frota de caminhões, cada um equipado com um drone, parte de um depósito central para atender estações de entrega e armários inteligentes (smart lockers). Diferente dos modelos tradicionais, o LTDRP-PDNF integra diversas restrições complexas do mundo real:

• Operações Duplas: Os armários servem tanto como armazenamento temporário para coletas de clientes quanto como nós automatizados para decolagem, pouso, transferência de encomendas e substituição de bateria por drones.
• Multi-Produto e Coleta/Entrega Simultânea: Os armários possuem demandas para múltiplos tipos de produtos com pesos distintos, exigindo operações simultâneas de entrega e coleta (logística reversa).
• Energia Dependente da Carga: O consumo de energia do drone é explicitamente modelado como uma função do peso da carga útil.
• Espaço Aéreo Restrito: Os drones devem navegar ao redor de zonas de não voo (ex: aeroportos, bases militares), o que exige cálculos de desvio baseados em representações de espaço aéreo restrito hexagonais.
• Sincronização: O sistema requer coordenação entre rotas de caminhões, atribuições de serviço de drones e reposição de bateria (em caminhões ou armários) para garantir a viabilidade operacional.

O objetivo é minimizar o custo operacional total, compreendendo custos de transporte e custos de uso de veículos, enquanto satisfaz restrições de capacidade, bateria e espaço.

Metodologia
Para resolver este problema computacionalmente desafiador e NP-difícil, os autores formulam o processo de construção de rota sequencial como um Processo de Decisão de Markov (MDP) e propõem uma heurística neural baseada em Aprendizado por Reforço Profundo (DRL) de dois estágios.

1. Estágio I: Roteamento Apenas de Caminhão (CVRP):

   • Os autores resolvem primeiro um Problema de Roteamento de Veículos Capacitados (CVRP) para estabelecer a espinha dorsal do roteamento do caminhão.
   • Arquitetura: Uma rede neural codificador-decodificador é empregada. O codificador utiliza um mecanismo de atenção de múltiplas cabeças para mapear as coordenadas dos nós e as demandas em representações latentes. O decodificador utiliza uma Unidade Recorrente de Portão Bidirecional (Bi-GRU) para capturar o contexto sequencial do roteamento (tanto para frente quanto para trás) para a seleção de nós.
   • Treinamento: A política é treinada usando o algoritmo REINFORCE com uma linha de base (baseline) para minimizar os custos da rota. Uma busca local 2-opt leve é aplicada pós-geração para refinar as soluções.

2. Estágio II: Roteamento Coordenado de Caminhão-Drone (LTDRP-PDNF):

   • Estratégia de Transferência: Para lidar com a complexidade do problema completo, os autores empregam uma estratégia de aprendizado por transferência (transfer learning); os parâmetros da rede neural aprendidos no Estágio I (domínio de origem: CVRP) são transferidos para o domínio alvo (LTDRP-PDNF) para gerar rotas de caminhão, reduzindo significativamente o tempo de treinamento.
   • Atribuição de Despacho Híbrido: Uma heurística customizada, MBP-ILS (Maximum Battery and Payload - Improved Local Search), é usada para construir rotas de drones com base nas rotas de caminhão geradas.
     • MBP: Um algoritmo ganancioso baseado em distância atribui armários aos caminhões e constrói rotas iniciais de drones, enquanto impõe estritamente restrições de carga útil e bateria. Se uma restrição for violada, o drone retorna ao caminhão mais próximo para reposição.
     • ILS: Uma busca local melhorada (usando trocas 2-opt) otimiza as rotas dos drones para reduzir a distância de viagem e evitar zonas de não voo, priorizando pontos de encontro de baixo custo.

Principais Contribuições

• Formulação de Problema Inovadora: O artigo introduz o LTDRP-PDNF, um modelo abrangente que considera simultaneamente demandas de múltiplos produtos, coleta/entrega simultânea, consumo de energia dependente da carga, desvios de zonas de não voo e troca de bateria assistida por armários.
• Heurística Neural de Dois Estágios: O desenvolvimento de um framework baseado em DRL que aproveita o aprendizado por transferência de um modelo CVRP para resolver o mais complexo LTDRP-PDNF, aliado a uma heurística híbrida para despacho de drones.
• Formulação MDP: Uma formulação rigorosa de MDP que captura a coordenação assíncrona entre caminhões e drones, incluindo transições de estado para níveis de bateria, carga útil e evasão de zonas de não voo.

Resultados Experimentais
Experimentos numéricos extensivos foram conduzidos em instâncias de várias escalas (20, 50 e 100 nós) e comparados com resolvedores exatos (Gurobi), meta-heurísticas (ALNS, PSO) e baselines neurais (AM).

• Qualidade da Solução: O método proposto superou consistentemente os baselines. Para instâncias de CVRP, alcançou resultados próximos do ótimo (ex: lacuna de 0,66% para 20 nós) e os melhores valores de objetivo para instâncias maiores onde o Gurobi falhou em encontrar soluções dentro do limite de tempo. Para LTDRP-PDNF, alcançou os melhores valores de objetivo para N=50 e N=100, superando o baseline baseado em atenção (AM) por margens significativas (ex: lacunas de 2,24% e 3,34%, respectivamente).
• Eficiência Computacional: O método demonstrou velocidade excepcional, resolvendo instâncias em segundos (ex: 0,09s para CVRP-100, 14,79s para LTDRP-PDNF-100), enquanto o Gurobi falhou em encontrar soluções viáveis para instâncias maiores dentro de 3600 segundos, e as meta-heurísticas exigiram tempos de execução significativamente maiores.
• Generalização: O método exibiu fortes capacidades de generalização, mantendo desempenho superior em instâncias de tamanhos cruzados (30, 60, 110 nós) que não foram vistas durante o treinamento.
• Análise de Sensibilidade: Os resultados indicaram que tanto a carga útil quanto a capacidade da bateria do drone impactam significavelmente os custos totais, com retornos decrescentes observados após certos limiares.

Significância e Alegações
O artigo afirma que o framework proposto oferece uma solução eficaz e escalável para sistemas práticos de entrega de caminhão-drone baseados em armários sob complexas restrições operacionais. Ao integrar DRL com aprendizado por transferência e heurísticas híbridas, o método supera os gargalos computacionais dos métodos exatos e as limitações de adaptabilidade das heurísticas tradicionais. Os autores sustentam que sua abordagem fornece uma representação realista dos desafios logísticos do mundo real, oferecendo um caminho viável para o implante de redes de entrega assistidas por drones em ambientes com espaço aéreo restrito e padrões de demanda complexos. O estudo destaca que equilibrar a configuração do veículo (carga útil/bateria) com o planejamento operacional é crucial para a eficiência de custos em tais sistemas.