A GPU IMPLEMENTATION OF LOCAL SEARCH OPERATORS FOR SYMMETRIC TRAVELLING SALESMAN PROBLEM

摘要

Problem trgovačkog putnika (TSP) je često proučavan problem kombinatorne optimizacije i bitan je za mnoge praktične primjene u području transporta. TSP je NP-težak problem, za čije je optimalno rješavanje egzaktnim algoritmima potrebna značajna računalna snaga. Zadnjih godina brz razvoj grafičkih procesnih jedinica (GPU) za opću namjenu donio je mogućnost značajnog smanjenje vremena izvršavanja algoritama. U ovom radu implementirali smo 2-opt i 3-opt operatore lokalnog pretraživanja za rješavanje problema trgovačkog putnika na GPU koristeći CUDA sučelje za programiranje. Doprinos ovog rada očituje se u paralelnoj implementaciji iterativnog lokalnog pretraživanja s 2-opt i 3-opt operatorima za simetričan problem trgovačkog putnika koji je optimiziran za izvršavanja na GPU-u. Opisani algoritam rješava velike probleme trgovačkog putnika (do 85,900 gradova). U radu je pokazano da GPU implementacija može biti i do 27 puta brža od implementacije na centralnoj procesnoj jedinici (CPU) bez da se izgubi kvaliteta rješenja. Rezultati su dani za probleme iz TSPlib biblioteke kao i za predloženi CRO TSP problem.%The Travelling Salesman Problem (TSP) is one of the most studied combinatorial optimization problem which is significant in many practical applications in transportation field. The TSP is an NP-hard problem and requires large computational power to be optimally solved by exact algorithms. In the past few years, fast development of general-purpose Graphics Processing Units (GPUs) has brought huge improvement in decreasing the algorithms execution time. In this paper, we implement 2-opt and 3-opt local search operators for solving the TSP on the GPU using its respective application programming interface. The novelty presented in this paper is a new parallel iterated local search implementation with 2-opt and 3-opt operators for symmetric TSP, optimized for the execution on GPUs. With our implementation large TSP problems (up to 85,900 cities) can be solved using the GPU. We show that our GPU implementation can be up to 27 times faster than central processing unit (CPU) implementation without losing solution quality for TSPlib problems as well as for our CRO TSP problem.