O Problema de Roteamento de Frota de Veículos Híbridos Tripulados e não Tripulados: Literatura & Novo Algoritmo
Resumo:
Com a crescente necessidade de soluções mais eficientes para o Problema de Roteamento de Veículos (PRV) clássico, novas variantes do problema foram desenvolvidas com o intuito de aperfeiçoar o processo de roteamento e reduzir custos operacionais. Entre essas varian tes, destaca-se o Problema de Roteamento de Veículos Híbridos, onde a rota é composta por Caminhões e Drones (PRVHCD), para o processo de entrega e coleta de mercadorias, caracterizada pela complementaridade entre suas capacidades e limitações operacionais. Essa combinação permite explorar estratégias colaborativas de entrega, aproveitando a autonomia e agilidade dos drones em conjunto com a maior capacidade e alcance dos caminhões, ampliando as possibilidades de otimização das rotas. Os objetivos centrais deste trabalho foram: em primeiro lugar, realizar uma revisão aprofundada do estado da arte relacionado ao PRVHCD e a outras variantes semelhantes do problema de roteamento; e, em segundo, propor uma versão adaptada do Biased Random-Key Genetic Algorithm (BRKGA), incorporando decodificadores e funções objetivo customizadas e inovadoras, com o propósito de encontrar soluções de alta qualidade em tempos computacionais viá veis. Para isso, o BRKGA foi aplicado sobre um conjunto de instâncias da família EIL, amplamente utilizadas na literatura como referência para problemas de roteamento. Os resultados obtidos indicaram que os decodificadores desenvolvidos se mostraram eficientes e versáteis, capazes de se adaptarem a diferentes funções objetivo — como distância total, tempo de serviço e custo operacional —, demonstrando robustez e flexibilidade no tratamento do PRVHCD.
Abstract:
With the growing need for more efficient solutions to the classical Vehicle Routing Problem (VRP), new variants have been developed to improve routing efficiency and reduce ope rational costs. Among these variants, the Hybrid Truck–Drone Vehicle Routing Problem (HTDVRP) stands out, in which delivery and pickup routes are executed collaboratively by trucks and drones, taking advantage of the complementary nature of their capabilities and operational limitations. This combination enables the exploration of collaborative de livery strategies, leveraging the autonomy and agility of drones together with the higher capacity and range of trucks, thereby expanding the possibilities for route optimization. The main objectives of this work were: first, to conduct a comprehensive review of the current state of the art related to the HVRP-TD and other similar routing problem va riants; and second, to propose an adapted version of the Biased Random Key Genetic Algorithm (BRKGA), incorporating customized and innovative decoders and objective functions, with the goal of finding high-quality solutions within feasible computational times. For this end, the BRKGA was applied to a set of benchmark instances from the EIL family, widely used in the literature as a reference for routing problems. The results obtained indicate that the developed decoders proved to be efficient and versatile, capa ble of adapting to different objective functions — such as total distance, service time, and operational cost — thus demonstrating robustness and flexibility in addressing the HVRP-TD.
Banca examinadora:
Prof. Luiz Satoru Ochi, UFF
Prof. Igor Machado Coelho, UFF
Profa. Loana Tito Nogueira, UFF
Prof. Marcone Jamilson Freitas Souza, UFOP