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-228Keywords:
Problema do Caixeiro Viajante, Modelo de Fluxo de duas Commodities, Algoritmos Genéticos com Chaves AleatóriasAbstract
Combinatorial optimization problems can model a wide range of real-world problems. However, their typical computational complexity is a challenge when searching for solutions. This study aims to evaluate the performance of two solution approaches for a classic combinatorial optimization problem: the Traveling Salesman Problem. The approaches applied include a linear programming model based on a two-commodity flow formulation and an evolutionary metaheuristic called A-BRKGA. To achieve the proposed goal, these algorithms were implemented and computational tests were performed using a set of benchmark instances. The approaches were compared in terms of solution quality and processing time. The results show that, for the evaluated instances, both algorithms produced high-quality solutions that are also similar, with an average difference of approximately 1%. For the set of instances, the average processing time was slightly lower for the metaheuristic compared to the exact algorithm.
Downloads
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Nathan Batistelli de Oliveira, Eduardo Paz Putti, Carise Elisane Schmidt
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
