Determination of the Shortest Path Using the Ant Colony Optimization (ACO) Algorithm Approach
DOI:
https://doi.org/10.21512/comtech.v12i2.7964Keywords:
shortest path, Ant Colony Optimization (ACO), algorithmAbstract
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.
Plum Analytics
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
Issue
Section
License
Copyright (c) 2021 Hengki Tamando Sihotang
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this journal agree to the following terms:
a. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License - Share Alike that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
b. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
c. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
USER RIGHTS
All articles published Open Access will be immediately and permanently free for everyone to read and download. We are continuously working with our author communities to select the best choice of license options, currently being defined for this journal as follows:
