Avaliação comparativa do desempenho entre processadores CPU e GPU para o problema do caixeiro viajante
um estudo de benchmarking computacional utilizando algoritmo de força bruta
DOI:
https://doi.org/10.47385/cadunifoa.v21.n56.5758Palavras-chave:
Problema do Caixeiro Viajante, CUDA, Computação Paralela, GPU, Otimização CombinatóriaResumo
O Problema do Caixeiro Viajante (PCV) é um dos problemas de otimização combinatória mais estudados na ciência da computação e pertence à classe NP-difícil. Este trabalho apresenta uma análise comparativa entre implementações sequenciais em CPU e implementações paralelas em GPU utilizando CUDA para resolver o PCV por meio do algoritmo de força bruta. O estudo foi realizado em Python com as bibliotecas NumPy e CuPy no ambiente do Google Colab. Para um grafo com 10 vértices, totalizando 362.880 permutações, a implementação em GPU apresentou um speedup de 1,30x em relação à CPU, reduzindo o tempo de execução de 1,3622 segundos para 1,0450 segundos. Os resultados destacam o potencial da computação paralela em GPU para problemas de otimização combinatória, especialmente quando o volume computacional justifica a sobrecarga de transferência de dados entre CPU e GPU.
Downloads
Referências
APPLEGATE, D. L. et al. The traveling salesman problem: a computational study. Princeton: Princeton University Press, 2007.
GUTIN, G.; PUNNEN, A. P. The traveling salesman problem and its variations. Boston: Springer, 2006. DOI: https://doi.org/10.1007/b101971
KIRK, D. B.; HWEU, W. W. Programming massively parallel processors: a hands-on approach. 3. ed. Burlington: Morgan Kaufmann, 2016.
LAWLER, E. L. et al. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985. DOI: https://doi.org/10.2307/2582681
MITTAL, S.; VETTER, J. S. A survey of CPU-GPU heterogeneous computing techniques. ACM Computing Surveys, v. 47, n. 4, p. 1-35, 2015. Available at: https://dl.acm.org/doi/10.1145/2788396. Accessed on: 20 maio 2025. DOI: https://doi.org/10.1145/2788396
SANDERS, J.; KANDROT, E. CUDA by example: an introduction to general-purpose GPU programming. Boston: Addison-Wesley, 2010.
Binjubeir, Mohammed Mahfoudh & Ismail, Mohd Arfian & Tusher, Ekramul Haque & Aljanabi, Mohammad. (2024). A GPU Accelerated Parallel Genetic Algorithm for the Traveling Salesman Problem. Journal of Soft Computing and Data Mining. 5. 137-150. Available at: http://umpir.ump.edu.my/id/eprint/43901/. Accessed on: 26 maio 2025.
EKER, Musa; ŞEN, Baha; KUMRU, Pinar Yildiz. An efficient solving of the traveling salesman problem: the ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, v. 21, n. 7, art. 15, 2013. DOI: https://doi.org/10.3906/elk-1109-44. Available at: https://journals.tubitak.gov.tr/elektrik/vol21/iss7/15. Accessed on: 6 jun. 2025.
K. Rocki and R. Suda. High Performance GPU Accelerated Local Optimization in TSP. 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, Cambridge, MA, USA, 2013, pp. 1788-1796, doi: 10.1109/IPDPSW.2013.227. Accessed on: 6 mai. 2025. DOI: https://doi.org/10.1109/IPDPSW.2013.227
FUJIMOTO, N. TSUTSUI, S. A highly-parallel TSP solver for a GPU computing platform. In: INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2010. Available at: https://link.springer.com/chapter/10.1007/978-3-642-18466-6_31. Accessed on: 1 mai. 2025.
FOSIN, J.; DAVIDOVIĆ, D.; CARIĆ, T. A GPU implementation of local search operators for symmetric travelling salesman problem. Promet - Traffic & Transportation, v. 25, n. 3, p. 225-234, 2013. Available at: https://hrcak.srce.hr/clanak/164448. Accessed on: 10 mai. 2025. DOI: https://doi.org/10.7307/ptt.v25i3.300
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2026 Cadernos UniFOA
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
CESSIONÁRIA
FUNDAÇÃO OSWALDO ARANHA - FOA, mantenedora do CENTRO UNIVERSITÁRIO DE VOLTA REDONDA - UniFOA,
entidade fundacional com personalidade jurídica sem fins lucrativos de direito privado, inscrita no CNPJ sob nº 32.504.995/0001-14, com sede na Avenida Dauro Peixoto Aragão, nº 1325, bairro Três Poços, Volta Redonda – RJ, doravante denominada FOA/UniFOA.
CLÁUSULA PRIMEIRA: O CEDENTE cede e transfere gratuitamente sem direito a remuneração, reembolso ou compensação de qualquer natureza, em caráter irrevogável e irretratável à FOA/UniFOA, todos os direitos autorais (morais e patrimoniais) relativo à obra acima intitulada, tudo em conformidade com a Lei nº 9.610/98.
PARÁGRAFO PRIMEIRO: O CEDENTE desde já, declara que a obra cedida é de sua exclusiva autoria, assumindo total responsabilidade civil e penal, quanto ao conteúdo, citações e referências que fazem parte de seu conteúdo, bem como, por eventuais questionamentos judiciais ou extrajudiciais em decorrência de sua divulgação, devendo concordar inequivocamente com a exclusão da FOA/UniFOA do polo passivo de quaisquer demandas.
PARÁGRAFO SEGUNDO: O CEDENTE assume inteira responsabilidade pelos dados pessoais tratados em função da obra acima intitulada, declarando ainda que observou sempre que possível, os critérios de anonimização ou pseudonimização dos dados para publicação final pela FOA/UniFOA, de acordo com artigo 7º, IV da Lei nº 13.709/2018.
PARÁGRAFO TERCEIRO: Na hipótese de existirem na obra acima intitulada dados pessoais identificados ou identificáveis, que não passaram por processo de anonimização, o CEDENTE declara que informou e disponibilizou aos titulares/terceiros, mecanismos de exercício dos direitos previstos na Lei nº 13.709/18.
PARÁGRAFO QUARTO: Os dados pessoais identificados ou identificáveis presentes na obra acima intitulada, ficarão disponíveis após publicação pela FOA/UniFOA, nos termos do art. 16, II da Lei nº 13.709/2018.
CLÁUSULA SEGUNDA: A FOA/UniFOA fica autorizada a utilizar, reproduzir, distribuir, divulgar, disponibilizar, publicar e licenciar a obra, sob qualquer forma e por quaisquer meios admitidos em lei, inclusive em ambiente digital, observadas as políticas editoriais da instituição e as licenças de uso adotadas para a publicação.
PARÁGRAFO ÚNICO: A utilização, reprodução, divulgação, publicação, compartilhamento, licenciamento ou qualquer outra forma de exploração autorizada da obra pela FOA/UniFOA não gerará ao CEDENTE qualquer direito à remuneração, reembolso, indenização, compensação financeira, participação em receitas ou vantagem econômica de qualquer natureza, permanecendo a presente cessão e autorização em caráter integralmente gratuito.
CLÁUSULA TERCEIRA: A FOA/UniFOA fica autorizada a promover o registro da obra na forma prevista no artigo 19 da Lei nº 9.610/1998, podendo averbar a presente autorização/cessão à margem do registro a que se refere o artigo 19 da Lei nº 9.610/1998, ou não estando a obra registrada, poderá a presente cessão ser registrada em Cartório de Títulos e Documentos, em havendo necessidade.
CLÁUSULA QUARTA: O presente instrumento é firmado por prazo indeterminado.
CLÁUSULA QUINTA: O CEDENTE outorga à FOA/UniFOA, a mais plena, geral, rasa, irretratável, irrestrita e inequívoca quitação pela presente cessão e transferência dos direitos autorais da obra intitulada acima, renunciando a todo e qualquer direito porventura existente, obrigando-se em todos os seus termos e condições, por si, seus herdeiros e sucessores.
CLÁUSULA SEXTA: O CEDENTE desde já está ciente e de acordo que:
- A obra não poderá ser comercializada e sua contribuição não gerará ônus para a FOA/UniFOA;
- A obra será disponibilizada em formato digital no sítio eletrônico do UniFOA para pesquisas e downloads de forma gratuita;
- A obra não será impressa, salvo em casos específicos cabendo à Editora FOA a definição;
- Todo o conteúdo é de total responsabilidade dos autores na sua forma e originalidade;
- Todas as imagens utilizadas (fotos, ilustrações, vetores e etc.) devem possuir autorização para uso;
- Que a obra não se encontra sob a análise em qualquer outro veículo de comunicação científica, caso contrário o CEDENTE deverá justificar a submissão à Editora FOA, que analisará o pedido, podendo ser autorizado ou não.
CLÁUSULA SÉTIMA: A obra objeto da presente cessão poderá ser disponibilizada pela FOA/UniFOA sob a licença Creative Commons Atribuição-NãoComercial (CC BY-NC), identificada na imagem abaixo - ou outra licença que venha a ser definida pela FOA/UniFOA, observados os critérios editoriais, institucionais, científicos e os requisitos estabelecidos por bases indexadoras, repositórios acadêmicos, organismos de fomento, sistemas de divulgação científica ou demais normas aplicáveis à publicação da obra.
PARÁGRAFO ÚNICO: O CEDENTE declara estar ciente e concordar que a escolha, alteração ou atualização da licença de publicação da obra constitui prerrogativa exclusiva da FOA/UniFOA, desde que observadas as finalidades acadêmicas, científicas e institucionais da publicação.
CLÁUSULA OITAVA: O CEDENTE está ciente e de acordo que tem por obrigação solicitar a autorização expressa dos coautores da obra/artigo, bem como dos professores orientadores antes da submissão do mesmo, se obrigando inclusive a mencioná-los no corpo da obra, sob pena de responder exclusivamente pelos danos causados.
