Solução do problema de roteamento de veículos com o algoritmo de otimização por enxame de partículas

• Luiz F. Xavier Alves UFMS
• Graziela Santos de Araújo UFMS
• Bianca de Almeida Dantas UFMS

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

Resumo

O Problema de Roteamento de Veículos (PRV) é um dos temas mais estudados em otimização combinatória, devido à sua ampla aplicabilidade prática. Dada a sua complexidade, conhecidamente NP-difícil, o uso de metaheurísticas tem sido explorado como forma de obter boas soluções em tempo computacional razoável. Nesse contexto, este artigo apresenta a implementação da meta-heurística populacional Particle Swarm Optimization (PSO), em conjunto com métodos de busca local, para a resolução do PRV Capacitado (PRVC). Os resultados obtidos indicam que o método é capaz de gerar soluções competitivas para instâncias de referência da literatura.

Palavras-chave: Problema de Roteamento de Veículos, Particle Swarm Optimization, Otimização Combinatória

Referências

Christofides, N. and Eilon, S. (1969). An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society, 20(3):309–318.

CVRPLib (2025). All instances. [link]. Acesso em: 30 nov. 2025.

Dantzig, G. B. Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1):80–91.

Kennedy, J., E. R. (1995). Particle swarm optimization. In Proceedings of ICNN’95 - International Conference on Neural Networks, volume 4, pages 1942–1948.

Vidal, T. (2021). Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. Computers & Operations Research.