Ant Colony Optimization for Jakarta Historical Tours:  A Comparative Analysis of GPS and Map Image Approaches

Gabriel Bodhi; Charleen; Devi Fitrianah

doi:10.29207/resti.v9i1.5968

Gabriel Bodhi Bina Nusantara University
Charleen Bina Nusantara University
Devi Fitrianah Bina Nusantara University

DOI: https://doi.org/10.29207/resti.v9i1.5968

Keywords: Ant Colony Optimization, Historical Sites, Intelligent System, Tour Planning, Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is a problem that represents a difficult combinatorial optimization problem starting from practical problems. The ant colony optimization (ACO) algorithm is implemented in several topics, particularly in solving combinatorial optimization problems. ACO is inspired by the behavior of ants in searching for the shortest path between a food source and their nest. In this research, ACO is used to find the best path or traveling salesman problem for museums and historical sites in Jakarta capital city of Indonesia. This research employs an approach based on the location's coordinates or latitude and longitude, while another method depends on coordinate data obtained from a supplied map image. After implementing both models, it can be concluded that the ACO model is not very good at solving TSP using actual coordinates. Meanwhile, the algorithm can quickly find near-optimal paths when using coordinates from a map image. The algorithm generates the optimal path in 11 seconds, reducing the initial distance from 17.938 to 4.430, using 4.731 ants and 75 trips with a distance power of 1. Statistical random variation was also performed, which proved that the algorithm is flexible and reliable when tested under various conditions.

Downloads

Download data is not yet available.

References

G. Dhiman, “ESA: a hybrid bio-inspired metaheuristic optimization approach for engineering problems,” Eng Comput, vol. 37, no. 1, 2021, doi: 10.1007/s00366-019-00826-w.

N. Rokbani et al., “Bi-heuristic ant colony optimization-based approaches for traveling salesman problem,” Soft comput, vol. 25, no. 5, 2021, doi: 10.1007/s00500-020-05406-5.

A. A. Hopgood, Intelligent Systems for Engineers and Scientists : A Practical Guide to Artificial Intelligence, vol. 4. 2021.

P. C. Pop, O. Cosma, C. Sabo, and C. P. Sitar, “A comprehensive survey on the generalized traveling salesman problem,” 2024. doi: 10.1016/j.ejor.2023.07.022.

B. P. Silalahi, N. Fathiah, and P. T. Supriyo, “Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes,” Jurnal Matematika “MANTIK,” vol. 5, no. 2, 2019, doi: 10.15642/mantik.2019.5.2.100-111.

Y. Wang and Z. Han, “Ant colony optimization for traveling salesman problem based on parameters optimization,” Appl Soft Comput, vol. 107, 2021, doi: 10.1016/j.asoc.2021.107439.

A. Akhtar, “Evolution of Ant Colony Optimization Algorithm,” Computer Science - Cornell University , 2019.

S. Li, Y. Wei, X. Liu, H. Zhu, and Z. Yu, “A New Fast Ant Colony Optimization Algorithm: The Saltatory Evolution Ant Colony Optimization Algorithm,” Mathematics, vol. 10, no. 6, 2022, doi: 10.3390/math10060925.

A. L. Anindya, K. B. Y. Bintoro, and S. D. H. Permana, “Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem,” JISA(Jurnal Informatika dan Sains), vol. 3, no. 2, 2020, doi: 10.31326/jisa.v3i2.704.

M. Dorigo and T. Stützle, “Ant colony optimization: Overview and recent advances,” in International Series in Operations Research and Management Science, vol. 272, 2019. doi: 10.1007/978-3-319-91086-4_10.

Z. Zhang, Z. Xu, S. Luan, X. Li, and Y. Sun, “Opposition-based ant colony optimization algorithm for the traveling salesman problem,” Mathematics, vol. 8, no. 10, 2020, doi: 10.3390/MATH8101650.

W. Gao, “Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem,” Soft comput, vol. 25, no. 4, 2021, doi: 10.1007/s00500-020-05376-8.

W. Gao, “New ant colony optimization algorithm for the traveling salesman problem,” International Journal of Computational Intelligence Systems, vol. 13, no. 1, 2020, doi: 10.2991/ijcis.d.200117.001.

C. Jin et al., “Development and evaluation of an artificial intelligence system for COVID-19 diagnosis,” Nat Commun, vol. 11, no. 1, 2020, doi: 10.1038/s41467-020-18685-1.

M. Ponjavic and A. Karabegovic, “Location intelligence systems and data integration for airport capacities planning,” Computers, vol. 8, no. 1, 2019, doi: 10.3390/computers8010013.

Y. Wang, L. Wang, G. Chen, Z. Cai, Y. Zhou, and L. Xing, “An Improved Ant Colony Optimization algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice,” Swarm Evol Comput, vol. 55, 2020, doi: 10.1016/j.swevo.2020.100675.

S. M. de Oliveira, L. C. T. Bezerra, T. Stützle, M. Dorigo, E. F. Wanner, and S. R. de Souza, “A computational study on ant colony optimization for the traveling salesman problem with dynamic demands,” Comput Oper Res, vol. 135, 2021, doi: 10.1016/j.cor.2021.105359.

P. Stodola, P. Otřísal, and K. Hasilová, “Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem,” Swarm Evol Comput, vol. 70, 2022, doi: 10.1016/j.swevo.2022.101056.

A. S. Bin Shahadat, M. A. H. Akhand, and M. A. S. Kamal, “Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem,” Mathematics, vol. 10, no. 14, 2022, doi: 10.3390/math10142448.

T. Fei, X. Wu, L. Zhang, Y. Zhang, and L. Chen, “Research on improved ant colony optimization for traveling salesman problem,” Mathematical Biosciences and Engineering, vol. 19, no. 8, 2022, doi: 10.3934/mbe.2022381.

P. Du, N. Liu, H. Zhang, and J. Lu, “An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem,” J Adv Transp, vol. 2021, 2021, doi: 10.1155/2021/6642009.

S. Kumar, D. R. Parhi, M. K. Muni, and K. K. Pandey, “Optimal path search and control of mobile robot using hybridized sine-cosine algorithm and ant colony optimization technique,” Industrial Robot, vol. 47, no. 4, 2020, doi: 10.1108/IR-12-2019-0248.

G. Che, L. Liu, and Z. Yu, “An improved ant colony optimization algorithm based on particle swarm optimization algorithm for path planning of autonomous underwater vehicle,” J Ambient Intell Humaniz Comput, vol. 11, no. 8, 2020, doi: 10.1007/s12652-019-01531-8.

R. Behmanesh and I. Rahimi, “Improved ant colony optimization for multi-resource job shop scheduling: A special case of transportation,” Econ Comput Econ Cybern Stud Res, vol. 55, no. 4, 2021, doi: 10.24818/18423264/55.4.21.18.

B. A. M. Menezes, H. Kuchen, H. A. Amorim Neto, and F. B. De Lima Neto, “Parallelization Strategies for GPU-Based Ant Colony Optimization Solving the Traveling Salesman Problem,” in 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings, 2019. doi: 10.1109/CEC.2019.8790073.

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

L. Eskandari, A. Jafarian, P. Rahimloo, and D. Baleanu, “A Modified and Enhanced Ant Colony Optimization Algorithm for Traveling Salesman Problem,” 2019. doi: 10.1007/978-3-319-91065-9_13.

W. Deng, J. Xu, and H. Zhao, “An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem,” IEEE Access, vol. 7, 2019, doi: 10.1109/ACCESS.2019.2897580.

K. Yang, X. You, S. Liu, and H. Pan, “A novel ant colony optimization based on game for traveling salesman problem,” Applied Intelligence, vol. 50, no. 12, 2020, doi: 10.1007/s10489-020-01799-w.

C. Liu et al., “An improved heuristic mechanism ant colony optimization algorithm for solving path planning,” Knowl Based Syst, vol. 271, 2023, doi: 10.1016/j.knosys.2023.110540.

A. Thammano and Y. Oonsrikaw, “Improved Ant Colony Optimization with Local Search for Traveling Salesman Problem,” in Proceedings - 20th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2019, 2019. doi: 10.1109/SNPD.2019.8935817.