UM ESTUDO DE CASO PARA O PROBLEMA DE ROTAS VIA MÉTODOS EXATOS E HEURÍSTICOS.

Abstract

Neste trabalho lidamos com o problema de rotas de uma empresa de estofados localizada no interior do Paraná. Para solucionar tal problema, primeiramente fizemos uma revisão bibliográfica sobre o Problema do Caixeiro Viajante (PCV) visto que o problema de rotas é uma variante de tal problema. Além disso, realizamos um estudo de métodos heurísticos, neste caso, Algoritmo Genético (AG) e Otimização por Colônia de Formigas (ACO - Ant Colony Optimization) que são comumente utilizados na resolução do PCV e suas variantes. Ambos os métodos foram implementados em Matlab e testes com dados reais da empresa foram realizados a fim de propormos uma melhoria na logística de entrega dos produtos. Os resultados obtidos através do AG e do ACO foram comparados com as rotas realizadas pela empresa e foram satisfatórios. Além dos métodos heurísticos, utilizou-se também o solver do Libre Office que resolve o problema via métodos exatos, mais especificamente, o método Simplex combinado com o Branch and Bound.