Otimização de Rotas de Transporte com Múltiplos Drones: Proposta utilizando Machine Learning, Meta-Heurísticas e Solução Exata

• Ricardo Vieira Chagas de Oliveira PUC-GO
• Alexandre Ribeiro PUC-GO
• Maria José Pereira Dantas PUC-GO

DOI: https://doi.org/10.5753/erigo.2025.17111

Resumo

A crescente utilização de drones para entregas de última milha, motivada pela redução do tempo de entrega e dos custos de manutenção, bem como pela mitigação das emissões de CO₂, demanda soluções robustas para o problema de otimização de rotas de transporte com múltiplos drones (Covering Salesman Problem with Multiple Drones – CSPMD). O presente artigo propõe uma solução multifásica para este desafio, em uma abordagem que integra técnicas de aprendizado de máquina (Machine Learning - ML), meta-heurística e programação dinâmica. Os resultados obtidos apontam que o emprego de meta-heurísticas específicas, no contexto desta estrutura multifásica, constitui uma estratégia promissora para a resolução do CSPMD. A avaliação de desempenho dessas meta-heurísticas indicou que o Algoritmo Genético apresentou custo até 0.49% menor em instâncias pequenas, ao passo que o Simulated Annealing demonstrou custo até 1.93% menor em instâncias grandes.

Palavras-chave: Otimização de rotas, Drones, CSPMD, Machine Learning, Meta-heurísticas

Referências

Andrei, L. and Pietro, S. O. (2019). Computational complexity analysis of genetic programming. Accessed on: 2025-11-13.

Avrim, B., Chen, D., and Saeed, S. (2021). Learning complexity of simulated annealing. Accessed on: 2025-11-13.

Bezdek, J. C., Ehrlich, R., and Full, W. (1984). Fcm: The fuzzy c-means clustering algorithm. Computers & Geosciences. Accessed on: 2025-08-21.

Kaufman, L. and Rousseeuw, P. J. (1987). Clustering by means of medoids. Journal of Computational and Applied Mathematics. Accessed on: 2025-08-20.

ONU (2018). Transporte sustentável é destaque na conferência do clima da onu. Technical report. Accessed on: 2025-11-13.

Paul, B., Niels, A., and Marie, S. (2018). Dynamic programming approaches for the traveling salesman problem with drone. Accessed on: 2025-11-13.

Pratik, S. T., Rohit, K. V., and Rakesh, T. (2024). Analysis of time complexity of k-means and fuzzy c-means clustering algorithm. Engineering Mathematics Letters. Accessed on: 2025-11-13.

Song, H., Jingi, A. M., and Yang, X. (2022). Drone-assisted last-mile delivery problem by covering salesman problem with nodes and segments. SSRN Electronic Journal. Accessed on: 2024-04-14.

Toaza, B. and Esztergár-Kiss, D. (2023). A review of metaheuristic algorithms for solving tsp-based scheduling optimization problems. Applied Soft Computing. Accessed on: 2025-08-20.

Wen, X. and Wu, G. (2022). Heterogenous multi-drone routing problem for parcel delivery. Computers & Operations Research. Accessed on: 2025-02-01.

Yoo, W., Yu, E., and Jung, J. (2018). Drone delivery: Factors affecting the public’s attitude and intention to adopt. Telematics and Informatics. Accessed on: 2024-04-14.