Comparative performance evaluation between CPU and GPU processors for the traveling salesman problem

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.