Solução geométrica plana ao problema do caixeiro viajante utilizando divisão e conquista, curva de Hilbert e branch and bound
Resumo
O problema do caixeiro viajante é uma questão de análise combinatória clássica que consiste em encontrar a rota de menor custo com fim de percorrer determinados pontos em um espaço, podendo ser aplicado em diversos contextos na sociedade. Contudo, sua solução por força bruta possui tempo de resposta incabível, tornando-a inacessível em diversas situações. Sendo assim, foram criadas ao longo do tempo diversas maneiras de resolver o problema do caixeiro viajante com tempo de resposta menor, e este artigo tem por objetivo propor uma abordagem que une três dessas maneiras: divisão e conquista ─ pela aplicação do algoritmo K-Means implementado na biblioteca scikit-learn ─, branch and bound e curva de preenchimento de espaço de Hilbert. O algoritmo descrito neste trabalho foi desenvolvido utilizando a linguagem de programação Python e sua solução trata-se de um caminho hamiltoniano, referente a formação geométrica, plana e completa do problema do caixeiro viajante.
Palavras-chave:
problema do caixeiro viajante, divisão e conquista, K-Means, branch and bound, curva de preenchimento de espaço de Hilbert
Referências
J. Y. Liu, R. Linn, P. S. H. Kowe, "A study on heuristic methods for PCB drilling route optimization", Source International Journal of Industrial Engineering: Theory, Applications and Practice", v. 6, p. 289-296, 1999.
T. C. Holanda, "O Relacionamento do problema de sequenciamento clássico com o problema do caixeiro viajante e sua resolução numa abordagem evolutiva", 2015
C. E. Mokhi, A. Addaim; "Optimization of Wind Turbine Interconnections in an Offshore Wind Farm Using Metaheuristic Algorithms", National School of Applied Sciences, Ibn Tofail University, 14000 Kenitra, Morocco, 2020
W. R. Mendes, "Modelo híbrido constituído por algoritmo genético e Space Filling Curve aplicado à otimização de rotas veiculares.", 2017. 139 f. Dissertação (Mestrado em Engenharia de Controle e Automação) - Instituto Federal do Espírito Santo, Serra, 2017.
K. L. Hoffman, M. Padberg, "Traveling salesman problem." In: Gass S.I., Harris C.M. (eds) Encyclopedia of Operations Research and Management Science. Springer, New York, NY, 2001. https://doi.org/10.1007/1-4020-0611-X_1068
M. Jünger, R. Gerhard, R. Giovanni, "Chapter 4 The traveling salesman problem." in Science Direct, 1995.
I. Tomescu. "An upper bound for the shortest hamiltonian path in the symmetric euclidean case", RAIRO-Operations Research, 1983.
J. Marion, R. Péchoux, "Characterizations of polynomial complexity classes with a better intensionality." in Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming (PPDP '08), Association for Computing Machinery, New York, NY, USA, 79-88, 2008.
A. Paz, S. Moran, "Non Deterministic Polynomial Optimizations Problems and Their Aproximations" in Theoretical Computer Science 15, pp. 51-277, North-Holland Publishing Company, 1979.
J. Carlson, A. M. Jaffe, and A. Wiles, The millennium prize problems. Cambridge, MA: Clay Mathematics Inst., p 87-88, 2006.
A. Lusem "P = NP ou as Sutilezas da Complexidade Computacional" in Matemática Universitária, Instituto de Matemática Pura e Aplicada - CNPq, N° 5, pp. 33-60, 1987.
S. Smale, "On the efficiency of algorithms of analysis", Bulletin Of The American Mathematical Society, 1985.
S. Violina, "Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP)", in Turkish Journal of Computer and Mathematics Education, vol.12, no.8, pp. 1226-1229, 2021.
J. Clausen, "branch and bound algorithms-principles and examples", Department of Computer Science, University of Copenhagen, p. 1-30, 1999.
T. Phienthrakul, "Clustering Evolutionary Computation for Solving Travelling Salesman Problems", International Journal of Advanced Computer Science and Information Technology (IJACSIT), Vol. 3, No. 3, pp. 243-262, 2014.
L. K. Platzman; J. J. Batholdi III, "An O(NlogN) Planar Travelling Salesman Heuristic Based on Spacefilling Curves", School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia 30332, PDRC Report Series 82-07, April 1982.
D. Arthur, S. Vassilvitskii, "How slow is the k-means method?" in SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry, 2006.
scikit-learn.org, 'sklearn.cluster.KMeans - scikit-learn 1.0 documentation', 2007. [Online]. Available: [link]. [Accessed: 27- Sep- 2021].
F. R. Rafaeli et. al., "Introdução à Geração de Malhas Triangulares", Sociedade Brasileira de Matemática Aplicada, Vol 79, pp. 2-3, 2015.
H. Haverkort, "An inventory of three-dimensional Hilbert space-filling curves", 2011.
G. P. Da Cruz. "Fractais: Padrões complexos de incrível beleza", Universidade Federal do Pará, 2014.
H. S. Warren, "Hacker's Delight", Pearson Education, 2013.
T. C. Holanda, "O Relacionamento do problema de sequenciamento clássico com o problema do caixeiro viajante e sua resolução numa abordagem evolutiva", 2015
C. E. Mokhi, A. Addaim; "Optimization of Wind Turbine Interconnections in an Offshore Wind Farm Using Metaheuristic Algorithms", National School of Applied Sciences, Ibn Tofail University, 14000 Kenitra, Morocco, 2020
W. R. Mendes, "Modelo híbrido constituído por algoritmo genético e Space Filling Curve aplicado à otimização de rotas veiculares.", 2017. 139 f. Dissertação (Mestrado em Engenharia de Controle e Automação) - Instituto Federal do Espírito Santo, Serra, 2017.
K. L. Hoffman, M. Padberg, "Traveling salesman problem." In: Gass S.I., Harris C.M. (eds) Encyclopedia of Operations Research and Management Science. Springer, New York, NY, 2001. https://doi.org/10.1007/1-4020-0611-X_1068
M. Jünger, R. Gerhard, R. Giovanni, "Chapter 4 The traveling salesman problem." in Science Direct, 1995.
I. Tomescu. "An upper bound for the shortest hamiltonian path in the symmetric euclidean case", RAIRO-Operations Research, 1983.
J. Marion, R. Péchoux, "Characterizations of polynomial complexity classes with a better intensionality." in Proceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming (PPDP '08), Association for Computing Machinery, New York, NY, USA, 79-88, 2008.
A. Paz, S. Moran, "Non Deterministic Polynomial Optimizations Problems and Their Aproximations" in Theoretical Computer Science 15, pp. 51-277, North-Holland Publishing Company, 1979.
J. Carlson, A. M. Jaffe, and A. Wiles, The millennium prize problems. Cambridge, MA: Clay Mathematics Inst., p 87-88, 2006.
A. Lusem "P = NP ou as Sutilezas da Complexidade Computacional" in Matemática Universitária, Instituto de Matemática Pura e Aplicada - CNPq, N° 5, pp. 33-60, 1987.
S. Smale, "On the efficiency of algorithms of analysis", Bulletin Of The American Mathematical Society, 1985.
S. Violina, "Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP)", in Turkish Journal of Computer and Mathematics Education, vol.12, no.8, pp. 1226-1229, 2021.
J. Clausen, "branch and bound algorithms-principles and examples", Department of Computer Science, University of Copenhagen, p. 1-30, 1999.
T. Phienthrakul, "Clustering Evolutionary Computation for Solving Travelling Salesman Problems", International Journal of Advanced Computer Science and Information Technology (IJACSIT), Vol. 3, No. 3, pp. 243-262, 2014.
L. K. Platzman; J. J. Batholdi III, "An O(NlogN) Planar Travelling Salesman Heuristic Based on Spacefilling Curves", School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, Georgia 30332, PDRC Report Series 82-07, April 1982.
D. Arthur, S. Vassilvitskii, "How slow is the k-means method?" in SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry, 2006.
scikit-learn.org, 'sklearn.cluster.KMeans - scikit-learn 1.0 documentation', 2007. [Online]. Available: [link]. [Accessed: 27- Sep- 2021].
F. R. Rafaeli et. al., "Introdução à Geração de Malhas Triangulares", Sociedade Brasileira de Matemática Aplicada, Vol 79, pp. 2-3, 2015.
H. Haverkort, "An inventory of three-dimensional Hilbert space-filling curves", 2011.
G. P. Da Cruz. "Fractais: Padrões complexos de incrível beleza", Universidade Federal do Pará, 2014.
H. S. Warren, "Hacker's Delight", Pearson Education, 2013.
Publicado
13/10/2021
Como Citar
MAURICIO, Sarah Klock; BORTOLI, André Augusto; VASATA, Darlon.
Solução geométrica plana ao problema do caixeiro viajante utilizando divisão e conquista, curva de Hilbert e branch and bound. In: CONGRESSO LATINO-AMERICANO DE SOFTWARE LIVRE E TECNOLOGIAS ABERTAS (LATINOWARE), 18. , 2021, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 43-52.
DOI: https://doi.org/10.5753/latinoware.2021.19904.
