PERFORMANCE DE UM ALGORITMO EXATO E DE UMA META-HEURÍSTICA NA RESOLUÇÃO DE UM PROBLEMA CLÁSSICO DE OTIMIZAÇÃO COMBINATÓRIA
DOI:
https://doi.org/10.24325/issn.2446-5763.v11i31p214-228Palavras-chave:
Problema do Caixeiro Viajante, Modelo de Fluxo de duas Commodities, Algoritmos Genéticos com Chaves AleatóriasResumo
Problemas de otimização combinatória podem modelar uma série de problemas reais. Contudo, a complexidade computacional que, em geral, está embutida nesses problemas é um desafio na busca por soluções. Este trabalho tem como objetivo avaliar a performance de duas abordagens de resolução em um problema clássico de otimização combinatória: o Problema do Caixeiro Viajante. Entre as abordagens aplicadas estão um modelo de programação linear baseado no fluxo de duas commodities e uma meta-heurística evolutiva, denominada A-BRKGA. Para atender o objetivo do estudo, esses algoritmos foram implementados computacionalmente e testes foram executados em um conjunto de instâncias da literatura. As abordagens foram comparadas em relação à qualidade da solução e o tempo de processamento. Os resultados mostraram que, nas instâncias avaliadas, ambos os algoritmos geraram soluções de qualidade e também similares entre si, com diferença média próxima a 1%. Nas instâncias testadas, o tempo médio para obtenção das soluções foi levemente inferior para a meta-heurística em relação ao algoritmo exato.
Downloads
Referências
BALDACCI, R.; HADJICONSTANTINOU, E.; MINGOZZI, A. “An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity Network Flow Formulation”. Operations Research, v. 52, n. 5, p. 723–738, 2004.
BALDACCI, R.; HADJICONSTANTINOU, E.; MINGOZZI, A. “An exact algorithm for the Traveling Salesman Problem with Deliveries and Collections”. Networks, v. 42, n. 1, p. 26-41, 2003.
BEAN, J. C. “Genetic algorithms and random keys for sequencing and optimization”. ORSA J. on Computing, v. 6, p. 154–160, 1994.
CHAVES, A. A.; GONÇALVES, J. F.; LORENA, L. A. N. “Adaptive biased random-key genetic algorithm with local search for the capacitated centered clustering problem”. Computers & Industrial Engineering, v. 124, p. 331-346, 2018.
CLAUS, A. “A new formulation for the traveling salesman problem”. SIAM J. Alg. Discrete Methods, v. 5, p. 21–25, 1984.
DANTZIG, G.; FULKERSON, D.; JOHNSON, S. “Solutions of large-scale traveling salesman problem”. Operations Research, v. 2, p. 393–410, 1954.
FINKE, G.; CLAUS, A; GUNN, E. “A two-commodity network flow approach to the traveling salesman problem”. Congressus Numerantium, v. 41, p. 167–178, 1984.
GAVISH, B.; GRAVES, S. “The travelling salesman problem and related problems”. Working Paper. Graduate School of Management, University of Rochester, 1978.
GOLDBERG, D.E.; HOLLAND, J. H. “Genetic Algorithms and Machine Learning”. Machine Learning, v. 3, p. 95–99, 1988.
GONÇALVES, J. F.; RESENDE, M. G. C. “Biased random-key genetic algorithm for combinatorial optimization”. Journal Heuristics, v. 17, p. 487–525, out. 2011.
IMPA. Instituto de Matemática Pura e Aplicada. “O Problema do Caixeiro Viajante”. Disponível em: https://impa.br/noticias/folha-o-problema-do-caixeiro-viajante/. Acesso em: 04 set. 2024.
KARIMI-MAMAGHAN, M. et al. “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art”. European Journal of Operational Research, v. 296, n.2, p. 393–422, 16 jan. 2022.
LANGEVIN, A.; DESROCHERS, M.; DESROSIERS, J.; GÉLINAS, S.; SOUMIS, F. “A two-commodity flow formulation for the traveling salesman and the makespan problems with time Windows”. Networks, v. 23, p. 631–640, 1993.
LAPORTE, G. “The Traveling Salesman Problem: An overview of exact and approximate algorithms”. European Journal of Operational Research, v. 59, n. 2, p. 231–247, 1992.
MATAI, R; SINGH, S. P.; MITALL, M. L. “Traveling salesman problem: an overview of applications, formulations, and solution approaches”. In: DAVENDRA D. (Ed.). Traveling salesman problema, theory and applications. InTech Press, London, p. 1–26, 2010.
MAZYAVKINA, N.; SVIRIDOV, S.; IVANOV, S.; BURNAEV, E. “Reinforcement learning for combinatorial optimization: A survey”. Computers & Operations Research, v. 134, 105400, out. 2021.
MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. “Integer Programming Formulations and Traveling Salesman Problems”. Journal of the Association for Computing Machinery, v. 7, p. 326–329, 1960.
POP, P. C; COSMA, O.; SABO, C.; SITAR, C. P. “A comprehensive survey on the generalized traveling salesman problem”. European Journal of Operational Research, v. 314, n. 3, p. 819–835, 1 mai. 2024.
SPEARS, W. M.; DEJONG, K. A. “On the virtues of parameterized uniform crossover”. Fourth International Conference on Genetic Algorithms. In: Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230–236, 1991.
TSPLIB. “Traveling Salesman Problem Library”. Disponível em: <http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/>. Acesso em: 11 mar. 2024.
WONG, R. T. “Integer programming formulations of the traveling salesman problem”. IEEE International Conference of Circuits and Computers. In: Proceedings of the IEEE International Conference of Circuits and Computers, p. 149–152, 1980.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Nathan Batistelli de Oliveira, Eduardo Paz Putti, Carise Elisane Schmidt
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
