Problema de Roteirização de Veículos Multi-Depósito com Drones: Replicabilidade, Revalidação e Novas Estratégias
Resumo:
Esta dissertação investiga o Problema de Roteirização de Veículos Multi-Depósito com Drones (MDVRP-D), variante logística que integra caminhões e drones para entregas de última milha. Motivado por preocupações de replicabilidade, o trabalho conduz uma auditoria computacional independente das 1.150 soluções publicadas para a Otimização por Colônia de Formigas Adaptativa com Clusterização de Nós para Drones (AACO-NC-D, Adaptive Ant Colony Optimization with Node Clustering for Drones), algoritmo atual estado da arte. Um validador rigoroso revelou que aproximadamente 81,1% dessas soluções são tecnicamente inviáveis, devido à omissão do tempo de serviço do caminhão no cálculo da autonomia das baterias dos drones. Diante dessa lacuna, a pesquisa propõe o estabelecimento de novos baselines factíveis para o problema.
Como contribuições metodológicas, investigam-se dois eixos. O primeiro propõe e avalia duas estratégias de clusterização de nós: a Setorização Angular Gulosa, que formaliza a divisão geométrica presente de forma ambígua no modelo original, e a Partição de Voronoi com mecanismo de diversidade adaptativa, que demonstrou superioridade na organização espacial das rotas em 22 das 23 instâncias avaliadas. O segundo investiga abordagens de decomposição do problema em sub-instâncias por depósito, obtendo reduções expressivas de custo computacional. A decomposição é investigada em dois papéis distintos: como solução inicial para a fase de otimização do AACO-NC-D sobre o espaço completo do MDVRP-D, guiando a busca desde o início, e como pós-processamento para refinar as soluções por ele produzidas.
Os resultados experimentais confirmam que a clusterização proposta e a decomposição proporcionam melhorias significativas na qualidade do makespan e na robustez das soluções. O trabalho estabelece, ainda, as primeiras referências de soluções válidas auditáveis para o conjunto completo de instâncias MDVRP-D, oferecendo uma base metodológica rigorosa para futuras pesquisas no problema.
Abstract:
This dissertation investigates the Multi-Depot Vehicle Routing Problem with Drones (MDVRP-D), a logistics variant that integrates trucks and drones for last-mile deliveries. Motivated by replicability concerns, the work conducts an independent computational audit of the 1,150 published solutions for the Adaptive Ant Colony Optimization with Node Clustering for Drones (AACO-NC-D), the current state-of-the-art algorithm. A rigorous validator revealed that approximately 81.1% of these solutions are technically infeasible, due to the omission of truck service time in the calculation of drone battery endurance. Given this gap, the research proposes the establishment of new feasible baselines for the problem.
As methodological contributions, two axes are investigated. The first proposes and evaluates two node clustering strategies: the Greedy Angular Sectorization, which formalizes the geometric partitioning described ambiguously in the original model, and the Voronoi Partition with adaptive diversity mechanism, which demonstrated superiority in the spatial organization of routes in 22 out of 23 evaluated instances. The second investigates problem decomposition approaches into sub-instances per depot, achieving significant reductions in computational cost. The decomposition is investigated in two distinct roles: as an initial solution for the AACO-NC-D optimization phase over the complete MDVRP-D solution space, guiding the search from the start, and as a post-processing step to refine the solutions it produces.
Experimental results confirm that the proposed clustering and decomposition provide significant improvements in makespan quality and solution robustness. The work also establishes the first auditable valid solution references for the complete set of MDVRP-D instances, offering a rigorous methodological foundation for future research on the problem.
Banca examinadora:
Prof. Fábio Protti, UFF
Prof. Luiz Satoru Ochi, UFF
Prof. Igor Machado Coelho, UFF
Prof. Luidi Gelabert Simonetti, UFRJ