Geodesic
Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO
Computer Science and Information Systems, Tome 20 (2023) no. 1.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

Many problems that were considered complex and unsolvable have started to solve and new technologies have emerged through to the development of GPU technology. Solutions have established for NP-Complete and NP-Hard problems with the acceleration of studies in the field of artificial intelligence, which are very interesting for both mathematicians and computer scientists. The most striking one among such problems is the Traveling Salesman Problem in recent years. This problem has solved by artificial intelligence’s metaheuristic algorithms such as Genetic algorithm and Ant Colony optimization. However, researchers are always looking for a better solution. In this study, it is aimed to design a low-cost and optimized algorithm for Traveling Salesman Problem by using GPU parallelization, Machine Learning, and Artificial Intelligence approaches. In this manner, the proposed algorithm consists of three stages; Cluster the points in the given dataset with K-means clustering, find the shortest path with Ant Colony in each of the clusters, and connect each cluster at the closest point to the other. These three stages were carried out by parallel programming. The most obvious difference of the study from those found in the literature is that it performs all calculations on the GPU by using Elitist Ant Colony Optimization. For the experimental results, examinations were carried out on a wide variety of datasets in TSPLIB and it was seen that the proposed parallel KMeans-Elitist Ant Colony approach increased the performance by 30% compared to its counterparts.
Keywords: ACO, Parallel ACO, Parallel Kmeans, TSP 
@article{CSIS_2023_20_1_a13,
     author = {Gozde Karatas Baydogmus},
     title = {Solution for {TSP/mTSP} with an {Improved} {Parallel} {Clustering} and {Elitist} {ACO}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2023},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2023_20_1_a13/}
}
TY  - JOUR
AU  - Gozde Karatas Baydogmus
TI  - Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO
JO  - Computer Science and Information Systems
PY  - 2023
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2023_20_1_a13/
ID  - CSIS_2023_20_1_a13
ER  - 
%0 Journal Article
%A Gozde Karatas Baydogmus
%T Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO
%J Computer Science and Information Systems
%D 2023
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2023_20_1_a13/
%F CSIS_2023_20_1_a13
Gozde Karatas Baydogmus. Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO. Computer Science and Information Systems, Tome 20 (2023) no. 1. http://geodesic.mathdoc.fr/item/CSIS_2023_20_1_a13/