Determining the Shortest Route for Eid Homecoming Route Using the Haversine Formula Method and A Star Algorithm
-
Finsa Nurpandi
*
Universitas Suryakancana, Cianjur,
Indonesia
- Diny Syarifah Sany Universitas Suryakancana, Cianjur, Indonesia (*) Corresponding Author
Abstract
Eid homecoming, also known as "Mudik" in Indonesia, is an annual tradition that involves the mass movement of people from cities to their hometowns to celebrate the Eid al-Fitr holiday. Based on data from the Ministry of Transportation of the Republic of Indonesia, there are five major regions that serve as the primary destinations for homecoming travelers: West Java, Central Java, East Java, DI Yogyakarta, and the Jabodetabek region. The Central Java region is estimated to receive the largest number of homecoming travelers, with an estimated 61.6 million people. Given the potential for human movement of up to 193.6 million people during this period, it poses a significant traffic burden, and an efficient determination of the shortest route is crucial. To address this challenge, the study utilizes the Haversine Formula, which calculates the distance between two geographic points on the earth's surface by considering the curvature of the earth. This approach provides a more accurate distance estimate compared to traditional linear distance calculations. Additionally, the A* algorithm is employed to determine the shortest path from the starting point to the destination. The A* algorithm combines the distance calculation results from the Haversine Formula as a heuristic component in the search process, effectively optimizing the route selection. The results of the A* algorithm search identified the shortest route for homecoming travelers, which starts from the city of Jakarta, passes through West Karawang, Indramayu, Cirebon, Tegal, Pekalongan, Semarang, and Salatiga, before reaching the final destination of Klaten. This optimized route covers a total distance of 599.4 km, providing an efficient and cost-effective option for travelers during the Eid homecoming period
Downloads
References
K. P. R. I. Biro Komunikasi dan Informasi Publik, “Potensi Pergerakan Masyarakat Selama Lebaran 2024 Mencapai 193,6 juta Orang, Pemerintah Terapkan Kebijakan Efektif Untuk Antisipasi,” Kementrian Perhubungan Republik Indonesia, Jakarta, Mar. 12, 2024. Accessed: Jun. 06, 2024. [Online]. Available: https://dephub.go.id/post/read/potensi-pergerakan-masyarakat-selama-lebaran-2024-mencapai-193,6-juta-orang,-pemerintah-terapkan-kebijakan-efektif-untuk-antisipasi#:~:text=Potensi%20Pergerakan%20Masyarakat%20Selama%20Lebaran,Antisipasi%20Kementerian%20Perhubungan%20Republik%20Indonesia
Tasya Natalia, “5 Provinsi Tujuan Mudik Paling Banyak, Jawa Tengah Teratas!,” CNBC Indonesia, Jakarta, Apr. 06, 2024. Accessed: Jun. 06, 2024. [Online]. Available: https://www.cnbcindonesia.com/research/20240405010837-128-528505/5-provinsi-tujuan-mudik-paling-banyak-jawa-tengah-teratas
D. Marcelina and E. Yulianti, “Aplikasi Pencarian Rute Terpendek Lokasi Kuliner Khas Palembang Menggunakan Algoritma Euclidean Distance dan A*(Star),” Jurnal Sisfokom (Sistem Informasi dan Komputer), vol. 9, no. 2, pp. 195–202, Jun. 2020, doi: 10.32736/sisfokom.v9i2.827.
R. Hidayati and N. Mutiah, “Penerapan Metode Haversine Formula Pada Pencarian Lokasi Fasilitas Kesehatan Terdekat,” Jurnal Media Informatika Budidarma, vol. 6, no. 1, p. 278, Jan. 2022, doi: 10.30865/mib.v6i1.3445.
M. Kisanrao Nichat, N. RChopde, and M. K. Nichat, “Landmark based shortest path detection by using A* Algorithm and Haversine Formula Landmark Based Shortest Path Detection by Using A* and Haversine Formula,” International Journal of Innovative Research in Computer and Communication Engineering, vol. 1, no. 2, Apr. 2013, [Online]. Available: www.ijircce.com
H. Rahmania Hatta, M. Hadi Suroso, I. F. Astuti, D. M. Khairina, and S. Maharani, “Application of Haversine Formula in Education Game ‘Landmark Nusantara,’” in Proceedings of the 2nd Borobudur International Symposium on Science and Technology (BIS-STE 2020), Magelang: Atlantis Press, Aug. 2021. doi: 10.2991/aer.k.210810.039.
Z. A. Puspita, F. Fauziah, and I. D. Sholihati, “Metode Haversine Formula Pada Pencarian Rumah Sakit di Wilayah Jakarta Selatan Berbasis Android,” JIPI (Jurnal Ilmiah Penelitian dan Pembelajaran Informatika), vol. 8, no. 4, pp. 1142–1153, Nov. 2023, doi: 10.29100/jipi.v8i4.3962.
S. Kartika and dan Raissa Amanda Putri, “Sistem Pencarian Lokasi dan Rute Terdekat Menggunakan Metode Haversine Formula Pada Aplikasi Donatur Pakaian Berbasis Android,” Al Ulum Sains dan Teknologi, vol. 7, no. 1, pp. 14–20, Nov. 2021, doi: 10.31602/ajst.v7i1.5678.
A. Bramato Wicaksono Putra, A. Aulia Rachman, and A. Santoso, “Perbandingan Hasil Rute Terdekat Antar Rumah Sakit di Samarinda Menggunakan Algoritma A*(star) dan Floyd-Warshall,” Sistem Informasi dan Komputer, vol. 09, no. 1, pp. 59–68, Mar. 2020, doi: 10.32736/sisfokom.v9.i1.685.
S. Russell and P. Norvig, Artificial Intelligence A Modern Approach Third Edition, 3rd ed. Upper Saddle River: Pearson Education Limited, 2016.
Y. Miftahuddin, S. Umaroh, and F. R. Karim, “Perbandingan Metode Perhitungan Jarak Euclidean, Haversine, dan Manhattan Dalam Penentuan Posisi Karyawan,” Jurnal Tekno Insentif, vol. 14, no. 2, pp. 69–77, Aug. 2020, doi: 10.36787/jti.v14i2.270.
R. H. D. Putra, H. Sujiani, and N. Safriadi, “Penerapan Metode Haversine Formula Pada Sistem Informasi Geografis Pengukuran Luas Tanah,” Jurnal Sistem dan Teknologi Informasi (JUSTIN), vol. 4, no. 1, Mar. 2016.
D. Malik, V. Rosalina, J. Raya Serang, and T. Drangong Serang, “Sistem Pemesanan Makanan Tradisional Berbasis Android Menggunakan Metode Haversine Formula,” Jurnal Sistem Informasi (JSiL), vol. 6, no. 1, pp. 12–19, Mar. 2019.
I. Irwan and D. Atmajaya, “Sistem Informasi pencarian lokasi Perguruan Tinggi di Makassar,” ILKOM Jurnal Ilmiah, vol. 10, no. 2, pp. 232–236, Aug. 2018, doi: 10.33096/ilkom.v10i2.251.232-236.
M. F. Mahatmi, T. Hasanuddin, and F. Umar, “Implementasi Metode Haversine Formula Untuk Menentukan Jarak Terdekat Pada Pengantaran Air Galon Depot Anantama Berbasis Android,” Buletin Sistem Informasi dan Teknologi Islam, vol. 3, no. 1, pp. 69–78, Feb. 2022, doi: 10.33096/busiti.v3i1.1098.
M. Kisanrao Nichat, N. RChopde, and M. K. Nichat, “Landmark based shortest path detection by using A* Algorithm and Haversine Formula Landmark Based Shortest Path Detection by Using A* and Haversine Formula,” International Journal of Innovative Research in Computer and Communication Engineering, vol. 1, no. 2, Apr. 2013, [Online]. Available: www.ijircce.com
I. B. G. W. A. Dalem, “Penerapan Algoritma A* (Star) Menggunakan Graph Untuk Menghitung Jarak Terpendek,” Jurnal RESISTOR (Rekayasa Sistem Komputer), vol. 1, no. 1, pp. 41–47, Apr. 2018, doi: 10.31598/jurnalresistor.v1i1.253.
M. Ardiansyah Muktadir Gasba, U. Sumoharjo Km, and S. Selatan, “Implementasi Algoritma A* (A Star) dalam Menentukan Jarak Terpendek Menuju Rumah Sakit Rujukan Covid-19,” Buletin Sistem Informasi dan Teknologi Islam, vol. 3, no. 3, pp. 203–212, 2022, doi: 10.31598/jurnalresistor.v1i1.253.
Y. Mananoma, S. R. Sentinuwo, and A. M. Sambul, “Waste Transportation Route Optimization in Manado using A-Star Algorithm (A*),” Jurnal Teknik Informatika, vol. 16, no. 3, Sep. 2021, doi: 10.35793/jti.v16i3.34193.
Suyanto, Artificial Intelligence Searching, Reasoning, Planning, dan Learning, 2nd ed. Bandung: Informatika Bandung, 2014.
Zakaria, Teknologi Informasi dan Komunikasi. Jakarta: Arya Duta, 2016.
Bila bermanfaat silahkan share artikel ini
Berikan Komentar Anda terhadap artikel Determining the Shortest Route for Eid Homecoming Route Using the Haversine Formula Method and A Star Algorithm
Pages: 581-590
Copyright (c) 2025 Finsa Nurpandi, Diny Syarifah Sany
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under Creative Commons Attribution 4.0 International License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- 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.
- 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 (Refer to The Effect of Open Access).
