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

Autores

  • Juliana Verga Shirabayashi UFPR - Campus Jandaia do Sul
  • Dandara de Almeida Machado UFPR - Campus Jandaia do Sul
  • Marco Aurélio Reis dos Santos UFPR - Campus Jandaia do Sul
  • Wesley Vagner Ines Shirabayashi Universidade Estadual de Maringá

Resumo

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.

Biografia do Autor

Juliana Verga Shirabayashi, UFPR - Campus Jandaia do Sul

Doutora em Eng. Elétrica, Profa. Doutora

Dandara de Almeida Machado, UFPR - Campus Jandaia do Sul

Graduanda em Engenharia de Produção

Marco Aurélio Reis dos Santos, UFPR - Campus Jandaia do Sul

Doutor em Eng. de Produção

Wesley Vagner Ines Shirabayashi, Universidade Estadual de Maringá

Doutor em Matemática Aplicada. Prof. Associado - DMA - UEM

Referências

ALINAGHIAN, M. & SHOKOUHI, N. Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhoord search. Omega, v. 76, p. 85–99, 2018.

ARENALES, M.; ARMENTANO, V.; MORABITO, R. & YANASSE, H. Pesquisa Operacional. Rio de Janeiro: Editora Campus, 2006.

BARBOZA, A. Simulação e técnicas da computação evolucionária aplicadas a problemas de Programação Linear Inteira Mista. 113p. Tese de Doutorado. CPGEI, Universidade Tecnológica Federal do Paraná, Curitiba-PR, 2005.

BELFIORE, P.& FÁVERO, L. P. Pesquisa operacional para cursos de Engenharia. Rio de Janeiro: Elsevier, 2013.

CARVALHO, M. B. Aplicações de meta-heurística genética e fuzzy no sistema de colônia de formigas para o problema do caixeiro viajante. 78p. Dissertação de Mestrado. Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas-SP, 2007.

CUNHA, C.;BONASSER, U. & ABRAHÃO, F. Experimentos computacionais com heurísticas de melhorias para o problema do caixeiro viajante. In: Anais do XVI Congresso da Associação Nacional de Pesquisa em Transportes. Natal, RN, 2002.

DORIGO, M. & CARO, G. Ant colony optimization: a new meta-heuristic. In: Proceedings of the congress on evolutionary computation. Piscataway, USA. IEEE, 1999. p. 1470–1477.

DORIGO, M. & GAMBARDELLA, L. Ant colonies for the traveling salesman problem. BioSystems, v.43, n. 2, p. 73–81, 1997.

EDGAR, T. & HIMMELBLAU, M. Optimization of chemical processes. New York: McGraw-Hill, 1989.

HOLLAND, J. Adaptation in natural and artificial systems. USA: MIT Press, 1975.

LAWLER, E.; RINNOOY-KAN, A.; LENSTRA, J. & SHMOYS, D. The traveling salesman problem: a guided tour of combinatorial optimization. New York: Wiley, 1985.

LINDEN, R. Algoritmos Genéticos: uma importante ferramenta de inteligência computacional. Rio de Janeiro: Editora Brasport, 2006.

MALAQUIAS, N. Uso dos algoritmos genéticos para a otimização de rotas de distribuição. 113p. Dissertação de Mestrado. Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia,

Uberlândia-MG, 2006.

MICHALEWICZ, Z. Genetic Algorithms + Data Structures = Evolution Programs. London: Springer-Verlag, 1996.

PINHO, A.; MONTEVECHI, J.; MARINS, F., & MIRANDA, R. Meta-heurísticas em Pesquisa Operacional (Algoritmos Genéticos: Fundamentos e Aplicações- Capítulo 2). Curitiba: Editora Omnipax, 2013.

RASMUSSEN, R. TSP in spreadsheets -a fast and flexible tool. Omega, v. 39, p. 51–63, 2011. RODRIGUES, G. Otimização de rotas através da aplicação de algoritmos exatos. Trabalho de conclusão de curso, Universidade Presidente Antônio Carlos, 2004.

SANTOS, F. & MUNARI, P. Otimização do agrupamento de ordens e roteirização de coleta: um estudo de caso em um armazém de e-commerce. Pesquisa Operacional para o Desenvolvimento, v. 9, n. 2, p. 62–81, 2017.

SIMON, D. Evolutionary optimization algorithms-biologically inspired and population based approaches to computer intelligence. New York: Wiley, 2013.

Downloads

Publicado

2019-04-12

Edição

v. 11 n. 1 (2019)

Seção

Artigos

Licença

Licença Creative Commons
Este obra está licenciado com uma Licença Creative Commons Atribuição 4.0 Internacional.