Penyelesaian Traveling Salesman Problem Dengan Algoritma Ant Colony Menggunakan Multi Processing

Muhammad Andika Saputra, Abdul Rahim, Mufti Kholil Romadhoni, Muhammad Shochibul Burhan

Abstract


Traveling Salesman Problem (TSP) adalah tantangan utama dalam optimasi kombinatorial, di mana menemukan rute terpendek menjadi sulit dengan bertambahnya skala rute. Ant Colony Optimization (ACO) adalah metode populer berbasis perilaku semut untuk menjelajahi solusi optimal. Namun, ACO sering membutuhkan waktu komputasi tinggi, terutama untuk masalah berskala besar. Penelitian ini mengusulkan penggabungan pemrograman paralel melalui multiprocessing dan multithreading untuk mempercepat eksekusi tanpa mengurangi kualitas solusi. Hasil implementasi menunjukkan bahwa multithreading memberikan waktu eksekusi tercepat dengan nilai fitness konsisten, yaitu 0.0030 pada iterasi 100 dan 0.0022–0.0024 pada iterasi 1000. Pada iterasi 100, multithreading mencatat waktu 0.0023–0.0037 detik, sementara multiprocessing membutuhkan 0.1889–0.2041 detik. Pada iterasi 1000, multithreading mencapai 0.0032–0.0042 detik, sedangkan multiprocessing berkisar antara 0.1919–0.2266 detik. Multithreading meningkatkan efisiensi waktu eksekusi hingga sekitar 99,83% dibandingkan dengan ACO standar pada iterasi 100, dan sekitar 99,80% pada iterasi 1000, tanpa mengorbankan kualitas solusi. Penelitian ini menegaskan bahwa multithreading lebih efisien dibandingkan multiprocessing untuk menyelesaikan TSP menggunakan ACO.

Keywords


Ant Colony; Multi Processing; Multi Threading; Parallel programming; Traveling Salesman Problem

Full Text:

PDF

References


Z. hong Jia, X. xue Zhuo, J. Y. T. Leung, and K. Li, “Integrated production and transportation on parallel batch machines to minimize total weighted delivery time,” Comput Oper Res, vol. 102, pp. 39–51, Feb. 2019, doi: 10.1016/j.cor.2018.07.026.

L. Yang, T. Jiang, and R. Cheng, “Tensorized Ant Colony Optimization for GPU Acceleration,” 2024, doi: 10.1145/3638530.

R. Skinderowicz, “Improving Ant Colony Optimization efficiency for solving large TSP instances,” Appl Soft Comput, vol. 120, May 2022, doi: 10.1016/j.asoc.2022.108653.

D. M. Chitty, “Applying ACO To Large Scale TSP Instances,” Sep. 2017, doi: 10.1007/978-3-319-66939-7_9.

S. Chowdhury, M. Marufuzzaman, H. Tunc, L. Bian, and W. Bullington, “A modified Ant Colony Optimization algorithm to solve a dynamic traveling salesman problem: A case study with drones for wildlife surveillance,” J Comput Des Eng, vol. 6, no. 3, pp. 368–386, Jul. 2019, doi: 10.1016/j.jcde.2018.10.004.

J. M. Cecilia, A. Llanes, J. L. Abellán, J. Gómez-Luna, L. W. Chang, and W. M. W. Hwu, “High-throughput Ant Colony Optimization on graphics processing units,” J Parallel Distrib Comput, vol. 113, pp. 261–274, Mar. 2018, doi: 10.1016/j.jpdc.2017.12.002.

R. Skinderowicz, “Implementing a GPU-based parallel MAX–MIN Ant System,” Future Generation Computer Systems, vol. 106, pp. 277–295, May 2020, doi: 10.1016/j.future.2020.01.011.

M. Pedemonte, S. Nesmachnow, and H. Cancela, “A survey on parallel ant colony optimization,” Applied Soft Computing Journal, vol. 11, no. 8, pp. 5181–5197, 2011, doi: 10.1016/j.asoc.2011.05.042.

Z. Wu, “A comparative study of solving traveling salesman problem with genetic algorithm, ant colony algorithm, and particle swarm optimization,” in ACM International Conference Proceeding Series, Association for Computing Machinery, Dec. 2020, pp. 95–99. doi: 10.1145/3450292.3450308.

A. M. Abdelmoaty and I. I. Ibrahim, “Comparative Analysis of Four Prominent Ant Colony Optimization Variants: Ant System, Rank-Based Ant System, Max-Min Ant System, and Ant Colony System,” May 2024, [Online]. Available: http://arxiv.org/abs/2405.15397

B. Ghimire, A. Mahmood, and K. Elleithy, “Hybrid Parallel Ant Colony Optimization for Application to Quantum Computing to Solve Large-Scale Combinatorial Optimization Problems,” Applied Sciences (Switzerland), vol. 13, no. 21, Nov. 2023, doi: 10.3390/app132111817.

Z. Zheng, “Improved ant colony-based algorithm for solving traveling salesmen problem,” Applied and Computational Engineering, vol. 10, no. 1, pp. 265–271, Sep. 2023, doi: 10.54254/2755-2721/10/20230191.

I. Dzalbs and T. Kalganova, “Accelerating supply chains with Ant Colony Optimization across range of hardware solutions,” 2020.

A. A. Ismail, R. Krisnaputra, and I. Bahiuddin, “Application of Ant Colony Optimization for the Shortest Path Problem of Waste Collection Process,” Kinetik: Game Technology, Information System, Computer Network, Computing, Electronics, and Control, Aug. 2021, doi: 10.22219/kinetik.v6i3.1307.

T. Dokeroglu, E. Sevinc, T. Kucukyilmaz, and A. Cosar, “A survey on new generation metaheuristic algorithms,” Comput Ind Eng, vol. 137, Nov. 2019, doi: 10.1016/j.cie.2019.106040.

S. Hougardy and X. Zhong, “Hard to solve instances of the Euclidean Traveling Salesman Problem,” Math Program Comput, vol. 13, no. 1, pp. 51–74, Mar. 2021, doi: 10.1007/s12532-020-00184-5.

B. A. de Melo Menezes, N. Herrmann, H. Kuchen, and F. Buarque de Lima Neto, “High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons,” Int J Parallel Program, vol. 49, no. 6, pp. 776–801, Dec. 2021, doi: 10.1007/s10766-021-00714-1.

K. Tang, X. F. Wei, Y. H. Jiang, Z. W. Chen, and L. Yang, “An Adaptive Ant Colony Optimization for Solving LargeScale Traveling Salesman Problem,” Mathematics, vol. 11, no. 21, Nov. 2023, doi: 10.3390/math11214439.

B. A. De Melo Menezes, L. F. De Araujo Pessoa, H. Kuchen, and F. Buarque De Lima Neto, “Parallelization strategies for GPU- ased ant colony optimization applied to TSP,” in Advances in Parallel Computing, IOS Press BV, 2020, pp. 321– 330. doi: 10.3233/APC200057.

C. S, H. S. Seshadri, and V. Lokesha, “An Effective Parallelism Topology in Ant Colony Optimization algorithm for Medical Image Edge Detection with Critical Path Methodology (PACO-CPM),” International Journal of Recent Contributions from Engineering, Science & IT (iJES), vol. 3, no. 4, p. 12, Dec. 2015, doi: 10.3991/ijes.v3i4.5139.

H. Ismkhan, “Effective heuristics for ant colony optimization to handle large-scale problems,” Swarm Evol Comput, vol. 32, pp. 140–149, Feb. 2017, doi: 10.1016/j.swevo.2016.06.006.

E. K. and M. S. B. A. Aslam, Multi -Threading based Implementation of Ant-Colony Optimization Algorithm for Image Edge Detection. IEEE, 2015.

M. Dorigo and T. Stützle, “Ant Colony Optimization,” 2004.

M. Melanie, “An Introductions to Genetic Algorithims,” 1999.

J. Si and X. Bao, “A novel parallel ant colony optimization algorithm for mobile robot path planning,” Mathematical Biosciences and Engineering, vol. 21, no. 2, pp. 2568–2586, 2024, doi: 10.3934/mbe.2024113.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 Muhammad Andika Saputra, Abdul Rahim, Mufti Kholil Romadhoni, Muhammad Shochibul Burhan

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.