Problema de roteamento de veículos e drones com entregas fracionadas

Abstract

Avanços tecnológicos recentes vêm transformando setores como medicina, comunicação e logística. A pandemia de Covid-19, em particular, evidenciou a importância de estratégias como o e-commerce e a logística de última milha. Nesse cenário, o uso de drones surge como uma alternativa promissora para otimizar entregas, embora desafios como capacidade de carga e autonomia de voo persistam. A integração de drones ao sistema de roteamento de veículos apresenta-se como uma solução inovadora, motivando pesquisas que buscam otimizar as operações híbridas caminhão-drone. Este trabalho teve como objetivo principal otimizar o roteamento de veículos com drones (VRPD), com foco na logística de última milha. Para isso, a investigação partiu de uma Revisão Sistemática da Literatura (RSL) que mapeou o estado da arte, identificando tendências, desafios e lacunas de pesquisa. A principal lacuna revelada foi a ausência de modelos que considerassem a entrega fracionada, onde um mesmo cliente pode ser atendido por múltiplos veículos. Para endereçar essa lacuna, foi proposto um novo problema, o Split Delivery Vehicle Routing Problem with Drones (SDVRPD), e formulado dois modelos de programação linear inteira mista para sua resolução. Os testes computacionais, realizados com o solver CPLEX, validaram a eficácia dos modelos, demonstrando uma redução de custos de até 20,32\% em uma instância baseada em dados reais, quando comparado à abordagem tradicional sem drones. Contudo, devido à complexidade NP-difícil do problema, o modelo exato mostrou-se computacionalmente inviável para instâncias de maior porte. Para superar essa limitação, foi desenvolvida e implementada uma metaheurística baseada em Variable Neighborhood Search (VNS). Os experimentos demonstraram que a VNS foi capaz de encontrar soluções de alta qualidade com baixo gap e em um tempo computacional significativamente inferior ao do método exato, consolidando-se como uma ferramenta robusta e prática para a resolução de problemas em escala real. Dessa forma, a contribuição central deste trabalho é a proposição e validação de um novo modelo para o roteamento com drones e entregas fracionadas, oferecendo não apenas uma formulação matemática precisa, mas também uma solução metaheurística eficiente e economicamente vantajosa para os desafios da logística moderna.