Bellman-ford and greedy algorithms to optimize the shortest route of PT. TIKI Jalur Nugraha Ekakurir (JNE)

Riska Evita Putri Harahap, Ismail Husein

Abstract


The purpose of this research is to find a comparison of Bellman-Ford and Greedy algorithms to optimize the shortest route of PT Tiki Jalur Nugraha Ekakurir (JNE). Bellman-Ford and Greedy algorithms are two algorithms that are often used in finding the shortest distance or optimal solution on a weighted graph. This research will be carried out at the JNE Medan Representative Office located on Jl. SM Raja Km 10.5 Amplas Trade Center Complex Blok F-10, while the type of research that will be used in this paper is applied research. The results of the study indicated the selection of the Bellman-Ford method because the Bellman-Ford method provides a more optimal route in terms of distance. Where the total initial distance used by PT Tiki Jalur Nugraha Ekakurir (JNE) is 20.5 km through routes including A→C → D → E → G→ H → J→ K→ L → N → O → P → R. While the total distance from the results of the new route sequence using the Bellman-Ford algorithm is 17.3 km by going through routes including A→B→D→E→F→H→I→K→L→M→O→Q→R And the total distance of the new sequence results using the Greedy algorithm is 17.5 km by going through routes A→B → D → E → F→ H → J→ K→ L → N → O → Q → R. This shows an efficiency of 15% in comparing existing routes with routes resulting from data analysis using Bellman-Ford.


Keywords


Bellman-Ford; Greedy; Shortest Route.

Full Text:

PDF

References


Alfioza, Y., & Sahputra, E. (2022). Penerapan metode algoritma bellman-ford dalam aplikasi pencarian indekos di kecamatan gading cempaka. Journal Innovation Informatics, 1(3), 142–151.

Azdy, R. A., & Darnis, F. (2019). Implementasi bellman-ford untuk optimasi rute pengambilan sampah di kota palembang. Jurnal Nasional Teknik Elektro Dan Teknologi Informasi (JNTETI), 8(4). https://doi.org/10.22146/jnteti.v8i4.532

Basriati, S., Safitri, E., Yesti, S. A., & Andiraja, N. (2022). Implementasi algoritma bellman-ford dalam menentukan lintasan terpendek truk pembuangan sampah. SNTIKI: Seminar Nasional Teknologi Informasi, Komunikasi Dan Industri, 174–184.

Berggren, U., Kjær-Rasmussen, T., Thorhauge, M., Svensson, H., & Brundell-Freij, K. (2022). Public transport path choice estimation based on trip data from dedicated smartphone app survey. Transportmetrica A: Transport Science, 18(3), 1813–1846. https://doi.org/10.1080/23249935.2021.1973146

Bhat, R., Rao, P. K., Kamath, C. R., Tandon, V., & Vizzapu, P. (2024). Comparative analysis of bellman-ford and dijkstra’s algorithms for optimal evacuation route planning in multi-floor buildings. Cogent Engineering, 11(1). https://doi.org/10.1080/23311916.2024.2319394

Chou, H.-J., Liu, J.-S., & Tung, W.-C. (2020). Numerical simulation of collision-free near-shortest path generation for dubins vehicle via hamilton–jacobi–bellman equation: A case study. Cogent Engineering, 7(1), 1782710. https://doi.org/10.1080/23311916.2020.1782710

Drakakis, S., & Kotropoulos, C. (2024). Applying the neural bellman-ford model to the single source shortest path problem. Proceedings of the 13th International Conference on Pattern Recognition Applications and Methods, 386–393. https://doi.org/10.5220/0012425800003654

Fitriani, S., Notiragayu, N., Wamiliana, W., & Faisol, A. (2022). Penerapan algoritma bellman-ford dalam menentukan rute terpendek objek wisata kabupaten lampung timur. Jurnal Siger Matematika, 3(2).

Hadibrata, B., & Maudin, S. (2020). Pencarian rute terpendek menuju tempat wisata menggunakan metode algoritma greedy pada dinas pemuda olahraga kebudayaan dan pariwisata kota cirebon. Syntax Literate ; Jurnal Ilmiah Indonesia, 5(5). https://doi.org/10.36418/syntax-literate.v5i5.1157

Iskandar, J. S., & Riti, Y. F. (2022). Perbandingan algoritma greedy dan algoritma dijkstra dalam pencarian rute terpendek dari kabupaten tuban ke kota surabaya. Jurnal PETIK, 8(2).

Jukna, S., & Schnitger, G. (2016). On the optimality of bellman–ford–moore shortest path algorithm. Theoretical Computer Science, 628, 101–109. https://doi.org/10.1016/j.tcs.2016.03.014

Liu, P., & Huang, W. (2022). A graph algorithm for the time constrained shortest path. Connection Science, 34(1), 1500–1518. https://doi.org/10.1080/09540091.2022.2061916

Liu, S., Peng, Y., Song, Q., & Zhong, Y. (2018). The robust shortest path problem for multimodal transportation considering timetable with interval data. Systems Science & Control Engineering, 6(2), 68–78. https://doi.org/10.1080/21642583.2018.1531082

Melliana, Mesra, T., Yusrizal, & Sirlyana. (2023). Pemilihan rute terpendek menggunakan algoritma bellman ford. Prosiding Seminar Nasional Teknik Industri (SENASTI), 1, 608–618.

Ningrum, E. R., Sanwidi, A., Akbarita, R., & Qomaruddin, M. N. H. (2023). Optimasi rute pendistribusian gas elpiji menggunakan algoritma floyd warshall dan algoritma greedy. JURNAL ILMIAH MATEMATIKA DAN TERAPAN, 20(1), 1–14. https://doi.org/10.22487/2540766X.2023.v20.i1.15568

Pratama, V. L., & Dermawan, D. A. (2022). Sistem informasi geografis pencarian rute terdekat bengkel motor di kota surabaya menggunakan algoritma bellman-ford. Journal of Informatics and Computer Science (JINACS), 3(04). https://doi.org/10.26740/jinacs.v3n04.p580-599

Puja Kekal, H., Gata, W., Nurdiani, S., Setio Rini, A. J., & Sely Wita, D. (2021). Analisa pencarian rute tercepat menuju tempat wisata pulau kumala kota tenggarong menggunakan algoritma greedy. JURNAL ILMIAH ILMU KOMPUTER, 7(1). https://doi.org/10.35329/jiik.v7i1.179

Quiaro, A., & Sacchi, M. D. (2024). Shortest-path ray tracing on self-adapting random grids. Geophysical Journal International, 237(2), 872–886. https://doi.org/10.1093/gji/ggae087

Saktia Purnama, R. D., Nisa, F., Tundo, T., Nurohman, K., Fakhrurrofi, F., Nugrahaini, L., & Dalail, D. (2024). Implementasi penggunaan algoritma greedy best first search untuk menentukan rute terpendek dari cilacap ke yogyakarta. Jurnal Informatika Dan Teknik Elektro Terapan, 12(2). https://doi.org/10.23960/jitet.v12i2.4068

Santi, I. H., & Budianti, D. (2023). Penerapan algoritma greedy dalam mencari rute terdekat lokasi spbu berbasis web. Penelitian Multidisiplin Ilmu, 2(1).

Tiara Pratiwi, I., Zulfikar, & Anshori Aris Widya, M. (2021). Sistem informasi manajemen paket ekspedisi cv. mk express penulis korespondensi. Jurnal Sistem Informasi Dan Teknologi, Vol. 04(No. 01).

Wang, M., Zhu, C., Wang, F., Li, T., & Zhang, X. (2020). Multi-factor of path planning based on an ant colony optimization algorithm. Annals of GIS, 26(2), 101–112. https://doi.org/10.1080/19475683.2020.1755725

Wayahdi, M. R., Ginting, S. H. N., & Syahputra, D. (2021). Greedy, a-Star, and dijkstra’s algorithms in finding shortest path. International Journal of Advances in Data and Information Systems, 2(1), 45–52. https://doi.org/10.25008/ijadis.v2i1.1206

Yusuf, Moh. R., Nurwan, N., Wungguli, D., & Yahya, L. (2023). Implementation of the floyd-warshall algorithm and bellman-ford algorithm to determine the shortest path in the distribution of lpg gas. E3S Web of Conferences, 400, 03004. https://doi.org/10.1051/e3sconf/202340003004

Zhao, J., Ma, X., Yang, B., Chen, Y., Zhou, Z., & Xiao, P. (2022). Global path planning of unmanned vehicle based on fusion of a* algorithm and voronoi field. Journal of Intelligent and Connected Vehicles, 5(3), 250–259. https://doi.org/10.1108/JICV-01-2022-0001




DOI: http://dx.doi.org/10.24042/djm.v7i2.23792

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Desimal: Jurnal Matematika

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

  Creative Commons License
Desimal: Jurnal Matematika is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.