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

Juliana Verga Shirabayashi, Dandara de Almeida Machado, Marco Aurélio Reis dos Santos, Wesley Vagner Ines Shirabayashi

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.

Texto completo:

PDF

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.


Apontamentos

  • Não há apontamentos.


O CONTEÚDO DOS ARTIGOS É DE RESPONSABILIDADE EXCLUSIVA DOS AUTORES.