Análise das restrições de eliminação de sub-rotas do tipo fluxo de commodities para o problema do caixeiro viajante assimétrico / Analysis of commodity flow type sub-route elimination constraints for the asymmetric traveling salesman problem

Caroline Sales de Azevedo, Michelli Maldonado

Abstract


O Problema do Caixeiro Viajante é um dos mais estudados na otimização combinatória, assim, diferentes modelos matemáticos para eliminação de possíveis sub-rotas têm sido propostos com o intuito de se resolver conjuntos cada vez maiores de instâncias. Neste trabalho, foram implementadas computacionalmente algumas restrições de eliminação de sub-rotas do tipo fluxo commodities para o Problema do Caixeiro Viajante Assimétrico, a fim de analisar os seus desempenhos computacionais. Os modelos foram implementados na linguagem de modelagem OPL “Optimization Programming Language”, utilizando o CPLEX como solver de otimização, sete instâncias do TSBLIB (REINELT,1991) e uma do acervo pessoal das autoras. Diante dos resultados obtidos, notou-se que a EC-MCF foi a formulação de maior qualidade entre as estudadas, no entanto, demandou muito mais tempo para retornar à solução ideal do que as outras. Desta forma, é possível que ao considerar o tempo computacional de algumas formulações, as hierarquias apresentadas por alguns autores se invertam. Sendo assim, é necessário refletir sobre a finalidade do modelo matemático estudado para se determinar o melhor conjunto de restrições para eliminação de sub-rotas.


Keywords


Otimização, Problema do Caixeiro Viajante, Commodity Flow, Eliminação de Sub-rotas.

References


CLAUS, A. A new formulation for the travelling salesman problem. SIAM Journal on Algebraic Discrete Methods, v. 5, n. 1, p. 21-25, 1984.

CONTE, N. O problema do caixeiro viajante, teoria e aplicações. 2002. 99 f. Dissertação (Mestrado) - Curso de Matemática Aplicada, Universidade Federal do Rio Grande do Sul, Porto Alegre, 2002. Disponível em: https://lume.ufrgs.br/bitstream/handle/10183/118198/000339835.pdf?sequence=1&isAllowed=y. Acesso em: 08 ago. 2020.

DANTZIG, G; FULKERSON, R; JOHNSON, S. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America, v. 2, n. 4, p. 393-410, 1954.

GAVISH, B.; GRAVES, S. C. The travelling salesman problem and related problems. 1978.

GODINHO, M. T.; GOUVEIA, L.; PESNEAU, P. Natural and extended formulations for the time-dependent traveling salesman problem. Discret Appl Math, 2011a. Doi: 10.1016/j.dam.2011.11.019

GODINHO, M. T.; GOUVEIA, L.; PESNEAU, P. On a time-dependent formulation and an updated classification of ATSP formulations. 2011.

FARIAS,N.F.S; RIBEIRO, J.M.A.; BEZERRA, A.A.; ARAÚJO, R.S.A. Dimensionamento de redes de distribuição de água utilizando Teoria dos Grafos. Brazilian Journal of Development, v.7, n.5, p. 52544-52561, 2021.

LANGEVIN, A.; SOUMIS, F.; DESROSIERS, J. Classification of travelling salesman problem formulations. Operations Research Letters, v. 9, n. 2, p. 127–132, 1990.

MENGER, K. Das botenproblem. Ergebnisse eines Mathematischen Kolloquiums, v.2, n.4, p. 11-12, 1932.

MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), ACM New York, NY, USA, v. 7, n. 4, p. 326–329, 1960.

OLIVEIRA, A. F. M. A. Extensões do Problema do Caixeiro Viajante. 2015. 89 f. Dissertação (Mestrado) - Curso de Matemática, Departamento de Matemática, Universidade de Coimbra, Coimbra, 2015. Disponível em: https://eg.uc.pt/bitstream/10316/31684/1/Tese_AndreOliveira.pdf. Acesso em: 09 set. 2020.

ONCAN, T.; ALTINEL, I. K.; LAPORTE, G. A comparative analysis of several asymmetric traveling salesman problem formulations. Computers & Operations Research, v. 36, n. 3, p. 637-654, 2009. DOI:10.1016/j.cor.2007.11.008

PRESTES, Á. N. Uma análise experimental de abordagens heurísticas aplicadas o problema do caixeiro viajante. 2006. 85 f. Dissertação (Mestrado) - Curso de Sistemas e Computação, Departamento de Informatica e Matemática Aplicada, Universidade Federal do Rio Grande do Norte, Natal, 2006.

REINELT, G. TSPLIB—A traveling salesman problem library. ORSA journal on computing, v. 3, n. 4, p. 376-384, 1991.

ROBERTI, R. e TOTH, P. Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison. EURO Journal on Transportation and Logistics, v. 1, n. 1-2, p. 113-133, 2012. DOI: 10.1007/s13676-012-0010-0

SILVA, F. A. M. et al. Estudo de formulações do problema do caixeiro viajante e sequenciamento de tarefas e suas aplicações em um problema prático de produção na indústria de pães e bolos. 2019. 219 f. Tese (Doutorado) - Curso de Matemática Aplicada, Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas, Campinas, 2019. Disponível em: http://repositorio.unicamp.br/bitstream/REPOSIP/335600/1/Silva_FelipeAugustoMoreiraDa_D.pdf. Acesso em: 07 set. 2020.

WONG, R. T. Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE international conference of circuits and computers. IEEE Press Piscataway NJ, 1980. p. 149-152.




DOI: https://doi.org/10.34117/bjdv7n6-565

Refbacks

  • There are currently no refbacks.