Determination of the Shortest Path Using the Ant Colony Optimization (ACO) Algorithm Approach

Authors

  • Hengki Tamando Sihotang STMIK Pelita Nusantara

DOI:

https://doi.org/10.21512/comtech.v12i2.7964

Keywords:

shortest path, Ant Colony Optimization (ACO), algorithm

Abstract

Distribution is one of the essential activities in business because it determines the price of products or goods in the market. So, choosing the shortest path is considered one of the most important things in business, especially distributors. PT Everbright, one of the business actors engaged in the manufacture of batteries and as the main distributor, hopes that the distribution of goods to have the shortest route so that costs can be minimized. The aim of the research was to determine the shortest path in distributing goods in the Medan area to the location of consumers. The research used Ant Colony Optimization (ACO). Determination of the shortest path is based on distance calculations in kilometers, protocol roads, gangs, normal road conditions, and differences between small and major roads. Based on the research results, it is found that the J1 line has the greatest value. So, the path chosen by the ants to pass is J1 which is 11 km away from the departure location (PT Everbright) to the destination (Pasar Glugur Kota). It passes through PT Everbright --> Jln. Gatot Subroto --> Jln. Kapt. Muslim --> Jln. Tgk. Amir Hamzah --> Jln. KH. Syeikh Abdul Wahab Rokan --> Pasar Glugur Kota.

Dimensions

Plum Analytics

Author Biography

Hengki Tamando Sihotang, STMIK Pelita Nusantara

Teknik Informatika

References

Baek, S. G., Lee, S., & Eom, Y. I. (2021). Efficient single-pair all-shortest-path query processing for massive dynamic networks. Information Sciences, 546, 1306-1327. https://doi.org/10.1016/j.ins.2020.08.111

Dahni, Y. S., & Rahmiati. (2017). Sistem informasi penentuan jalur terpendek bagi pengantar surat menggunakan algoritma semut. Jurnal INOVTEK Polbeng - Seri Informatika, 2(2), 148-160. https://doi.org/10.35314/isi.v2i2.202

Demir, H. I., & Erden, C. (2020). Dynamic integrated process planning, scheduling and due-date assignment using ant colony optimization. Computers & Industrial Engineering, 149(November), 1-12 https://doi.org/10.1016/j.cie.2020.106799

Desiaman, D. (2019). Penentuan jalur terpendek dengan menggunakan algoritma Djikstra dalam pencarian kost di Kota Medan. KAKIFIKOM (Kumpulan Artikel Karya Ilmiah Fakultas Ilmu Komputer), 1(1), 1-5.

Dzalbs, I., & Kalganova, T. (2020). Accelerating supply chains with ant colony optimization across a range of hardware solutions. Computers & Industrial Engineering, 147(September), 1-14. https://doi.org/10.1016/j.cie.2020.106610

Guan, B., Zhao, Y., & Li, Y. (2021). An improved ant colony optimization with an automatic updating mechanism for constraint satisfaction problems. Expert Systems with Applications, 164(February), 1-7. https://doi.org/10.1016/j.eswa.2020.114021

Gupta, A., & Srivastava, S. (2020). Comparative analysis of ant colony and particle swarm optimization algorithms for distance optimization. Procedia Computer Science, 173, 245-253. https://doi.org/10.1016/j.procs.2020.06.029

Hinz, A. M., & Heide, C. H. A. D. (2014). An efficient algorithm to determine all shortest paths in Sierpiński graphs. Discrete Applied Mathematics, 177, 111-120. https://doi.org/10.1016/j.dam.2014.05.049

Jha, B., Chen, Z., & Shima, T. (2020). On shortest Dubins path via a circular boundary. Automatica, 121(November), 1-9. https://doi.org/10.1016/j.automatica.2020.109192

Kumar, R., Singh, R., & Ashfaq, H. (2020). Stability enhancement of multi-machine power systems using ant colony optimization-based static synchronous compensator. Computers & Electrical Engineering, 83(May), 1-17. https://doi.org/10.1016/j.compeleceng.2020.106589

Liang, F., Kang, C., & Fang, F. (2020). A smooth tool path planning method on NURBS surface based on the shortest boundary geodesic map. Journal of Manufacturing Processes, 58(October), 646-658. https://doi.org/10.1016/j.jmapro.2020.08.047

Liu, L., Luo, S., Guo, F., & Tan, S. (2020). Multi-point shortest path planning based on an improved discrete bat algorithm. Applied Soft Computing, 95(October), 1-10. https://doi.org/10.1016/j.asoc.2020.106498

Lubiw, A., Maftuleac, D., & Owen, M. (2020). Shortest paths and convex hulls in 2D complexes with non-positive curvature. Computational Geometry, 89(August), 1-24. https://doi.org/10.1016/j.comgeo.2020.101626

Maheshwari, P., Sharma, A. K., & Verma, K. (2021). Energy efficient cluster based routing protocol for WSN using butterfly optimization algorithm and ant colony optimization. Ad Hoc Networks, 110. https://doi.org/10.1016/j.adhoc.2020.102317

Miao, M., Zhang, W., Hu, W., & Wang, R. (2020). An adaptive multi-domain feature joint optimization framework based on composite kernels and ant colony optimization for motor imagery EEG classification. Biomedical Signal Processing and Control, 61(August), 1-15. https://doi.org/10.1016/j.bspc.2020.101994

Pan, M., Li, C., Gao, R., Huang, Y., You, H., Gu, T., & Qin, F. (2020). Photovoltaic power forecasting based on a support vector machine with improved ant colony optimization. Journal of Cleaner Production, 277, 1-12. https://doi.org/10.1016/j.jclepro.2020.123948

Patino-Ramirez, F., Layhee, C., & Arson, C. (2020). Horizontal Directional Drilling (HDD) alignment optimization using ant colony optimization. Tunnelling and Underground Space Technology, 103(September), 1-13. https://doi.org/10.1016/j.tust.2020.103450

Phanden, R. K., Sharma, L., Chhabra, J., & Demir, H. İ. (2021). A novel modified ant colony optimization based maximum power point tracking controller for photovoltaic systems. Materials Today: Proceedings, 38, 89-93. https://doi.org/10.1016/j.matpr.2020.06.020

Rosa, W. R., Suhartono, S., & Wibawa, H. A. (2013). Penentuan jalur terpendek pada pelayanan agen travel khusus pengantaran wilayah Semarang berbasis SIG dengan algoritma branch and bound. Jurnal Masyarakat Informatika, 4(7), 9-14. https://doi.org/10.14710/jmasif.4.7.9-14

Soetomo, C. A. L. (2018). Penentuan jalur terpendek dengan menggunakan metode ant colony optimization (Undergraduate Thesis). Universitas Islam Negeri Maulana Malik Ibrahim.

Tuani, A. F., Keedwell, E., & Collett, M. (2020). Heterogenous adaptive ant colony optimization with 3-opt local search for the travelling salesman problem. Applied Soft Computing, 97, 1-14. https://doi.org/10.1016/j.asoc.2020.106720

Wen, X. (2020). Modeling and performance evaluation of wind turbine based on ant colony optimization-extreme learning machine. Applied Soft Computing, 94(September). https://doi.org/10.1016/j.asoc.2020.106476

Xin, S. Q., & Wang, G. J. (2007). Efficiently determining a locally exact shortest path on polyhedral surfaces. Computer-Aided Design, 39(12), 1081-1090. https://doi.org/10.1016/j.cad.2007.08.001

Zeng, W., Miwa, T., & Morikawa, T. (2017). Application of the support vector machine and heuristic k-shortest path algorithm to determine the most eco-friendly path with a travel time constraint. Transportation Research Part D: Transport and Environment, 57(December), 458-473. https://doi.org/10.1016/j.trd.2017.10.001

Zhang, T., Cheng, Y., Wu, H., Song, Y., Yan, S., Handroos, H., Zheng, L., Ji, H., & Pan, H. (2020). Dynamic Accuracy Ant Colony Optimization of Inverse Kinematic (DAACOIK) analysis of Multi-Purpose Deployer (MPD) for CFETR remote handling. Fusion Engineering and Design, 156(July), 1-9. https://doi.org/10.1016/j.fusengdes.2020.111522

Zhao, D., Liu, L., Yu, F., Heidari, A. A., Wang, M., Oliva, D., Muhammad, K., & Chen, H. (2021). Ant colony optimization with horizontal and vertical crossover search: Fundamental visions for multi-threshold image segmentation. Expert Systems with Applications, 167. https://doi.org/10.1016/j.eswa.2020.114122

Zhao, H., Zhang, C., & Zhang, B. (2020). A decomposition-based many-objective ant colony optimization algorithm with adaptive reference points. Information Sciences, 540(November), 435-448. https://doi.org/10.1016/j.ins.2020.06.028

Downloads

Published

2021-12-13

Issue

Section

Articles
Abstract 317  .
PDF downloaded 448  .