About the journal

• Home page
• Contact information
• Aims and scope
• Indexing information
• Editorial policies
• ComSIS consortium
• Journal boards
• Managing board

For authors

• Information for contributors
• Paper submission
• Article submission through OJS
• Copyright transfer form
• Download section

For readers

• Forthcoming articles
• Current issue
• Archive

For reviewers

• View and review submissions

News

• Journal's Facebook page
• Calls for special issues
• New issue notification

Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO

Gozde Karatas Baydogmus¹

1. Department of Computer Engineering, Marmara University
   Istanbul, 34722
   gkaratas@marmara.edu.tr

Abstract

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.

Key words

ACO, Parallel ACO, Parallel Kmeans, TSP

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS220820053B

Publication information

Volume 20, Issue 1 (January 2023)
Year of Publication: 2023
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

Available in PDF
Portable Document Format

How to cite

Baydogmus, G. K.: Solution for TSP/mTSP with an Improved Parallel Clustering and Elitist ACO. Computer Science and Information Systems, Vol. 20, No. 1, 195–214. (2023), https://doi.org/10.2298/CSIS220820053B