KJCKorea
Journal Central

@article{ART002813367},
author={Yunseok Rhee},
title={GPU-based Parallel Ant Colony System for Traveling Salesman Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2022},
volume={27},
number={2},
pages={1-8},
doi={10.9708/jksci.2022.27.02.001}

TY - JOUR
AU - Yunseok Rhee
TI - GPU-based Parallel Ant Colony System for Traveling Salesman Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2022
VL - 27
IS - 2
PB - The Korean Society Of Computer And Information
SP - 1
EP - 8
SN - 1598-849X
AB - In this paper, we design and implement a GPU-based parallel algorithm to effectively solve the traveling salesman problem through an ant color system. The repetition process of generating hundreds or thousands of tours simultaneously in TSP utilizes GPU's task-level parallelism, and the update process of pheromone trails data actively exploits data parallelism by 32x32 thread blocks. In particular, through simultaneous memory access of multiple threads, the coalesced accesses on continuous memory addresses and concurrent accesses on shared memory are supported. This experiment used 127 to 1002 city data provided by TSPLIB, and compared the performance of sequential and parallel algorithms by using Intel Core i9-9900K CPU and Nvidia Titan RTX system. Performance improvement by GPU parallelization shows speedup of about 10.13 to 11.37 times.
KW - Ant colony system;Traveling salesman problem;Graphic processing unit;Metaheuristic;Parallelization
DO - 10.9708/jksci.2022.27.02.001
ER -

Yunseok Rhee. (2022). GPU-based Parallel Ant Colony System for Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 27(2), 1-8.

Yunseok Rhee. 2022, "GPU-based Parallel Ant Colony System for Traveling Salesman Problem", Journal of The Korea Society of Computer and Information, vol.27, no.2 pp.1-8. Available from: doi:10.9708/jksci.2022.27.02.001

Yunseok Rhee "GPU-based Parallel Ant Colony System for Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27.2 pp.1-8 (2022) : 1.

Yunseok Rhee. GPU-based Parallel Ant Colony System for Traveling Salesman Problem. 2022; 27(2), 1-8. Available from: doi:10.9708/jksci.2022.27.02.001

Yunseok Rhee. "GPU-based Parallel Ant Colony System for Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27, no.2 (2022) : 1-8.doi: 10.9708/jksci.2022.27.02.001

Yunseok Rhee. GPU-based Parallel Ant Colony System for Traveling Salesman Problem. Journal of The Korea Society of Computer and Information, 27(2), 1-8. doi: 10.9708/jksci.2022.27.02.001

Yunseok Rhee. GPU-based Parallel Ant Colony System for Traveling Salesman Problem. Journal of The Korea Society of Computer and Information. 2022; 27(2) 1-8. doi: 10.9708/jksci.2022.27.02.001

Yunseok Rhee. GPU-based Parallel Ant Colony System for Traveling Salesman Problem. 2022; 27(2), 1-8. Available from: doi:10.9708/jksci.2022.27.02.001

Yunseok Rhee. "GPU-based Parallel Ant Colony System for Traveling Salesman Problem" Journal of The Korea Society of Computer and Information 27, no.2 (2022) : 1-8.doi: 10.9708/jksci.2022.27.02.001