Implementação Paralela do PSO para o Problema do Roteamento de Veículos Capacitado com uso de OpenMP

• Luiz Felipe Xavier Alves UFMS
• Bianca de Almeida Dantas UFMS

DOI: https://doi.org/10.5753/eradco.2026.34561

Resumo

O Problema de Roteamento de Veículos Capacitado (PRVC) é um desafio clássico de otimização combinatória com ampla relevância prática. Dada sua natureza NP-difícil, o uso de meta-heurísticas que equilibram diversificação e intensificação, como o Particle Swarm Optimization (PSO) híbrido, é essencial para obter soluções subótimas em tempo hábil. Entretanto, a incorporação de algoritmos robustos de busca local impõe um severo gargalo computacional, limitando a escalabilidade. Neste contexto, este artigo propõe uma estratégia de paralelismo de granulação grossa baseada em OpenMP. Os experimentos conduzidos demonstram a eficácia da abordagem, alcançando expressivos valores de speedup, assegurando a viabilidade temporal para instâncias complexas.

Palavras-chave: Problema de Roteamento de Veículos, Particle Swarm Optimization, Computação Paralela, OpenMP

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: 09 ago. 2026.

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.