Comparative performance evaluation between CPU and GPU processors for the traveling salesman problem
a computational benchmarking study using brute-force algorithm
DOI:
https://doi.org/10.47385/cadunifoa.v21.n56.5758Keywords:
Traveling Salesman Problem, CUDA, Parallel Computing, GPU, Combinatorial OptimizationAbstract
The Traveling Salesman Problem (TSP) is one of the most studied combinatorial optimization problems in computer science and belongs to the NP-hard class. This work presents a comparative analysis between sequential CPU implementations and parallel GPU implementations using CUDA to solve the TSP through the brute-force algorithm. The study was conducted using Python with the NumPy and CuPy libraries in the Google Colab environment. For a graph with 10 vertices, totaling 362,880 permutations, the GPU implementation showed a speedup of 1.30x compared to the CPU, reducing execution time from 1.3622 seconds to 1.0450 seconds. The results highlight the potential of GPU parallel computing for combinatorial optimization problems, especially when the computational volume justifies the data transfer overhead between CPU and GPU.
Downloads
References
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
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Cadernos UniFOA
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Declaração de Transferência de Direitos Autorais - Cadernos UniFOA como autor(es) do artigo abaixo intitulado, declaro(amos) que em caso de aceitação do artigo por parte da Revista Cadernos UniFOA, concordo(amos) que os direitos autorais e ele referentes se tornarão propriedade exclusiva desta revista, vedada qualquer produção, total ou parcial, em qualquer outra parte ou meio de divulgação, impressa ou eletrônica, sem que a prévia e necessária autorização seja solicitada e, se obtida, farei(emos) constar o agradecimento à Revista Cadernos UniFOA, e os créditos correspondentes. Declaro(emos) também que este artigo é original na sua forma e conteúdo, não tendo sido publicado em outro periódico, completo ou em parte, e certifico(amos) que não se encontra sob análise em qualquer outro veículo de comunicação científica.
O AUTOR 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;
- 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 Autor deverá justificar a submissão à Editora da FOA, que analisará o pedido, podendo ser autorizado ou não.
O AUTOR 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.
