Perbandingan Algoritma A*Star dan Dijkstra untuk Penentuan Rute Tercepat
Main Article Content
Abstract
Penelitian ini membandingkan kinerja algoritma AStar dan Dijkstra dalam menentukan rute tercepat dari Cakung ke Stasiun Bekasi. Algoritma AStar mengintegrasikan fungsi heuristik untuk memperkirakan biaya menuju tujuan, sedangkan Dijkstra menghitung jalur terpendek berdasarkan bobot jarak tanpa estimasi. Data waktu tempuh diperoleh melalui Google Maps API pada kondisi lalu lintas normal, sibuk, dan non-sibuk. Hasil pengujian menunjukkan bahwa A*Star lebih efisien pada kondisi lalu lintas padat karena heuristik mempercepat proses pencarian jalur optimal. Sebaliknya, Dijkstra lebih unggul pada graf sederhana dengan sedikit pengaruh kemacetan. Temuan ini memberikan panduan pemilihan algoritma yang sesuai untuk aplikasi navigasi berbasis pencarian rute real-time di wilayah perkotaan, sekaligus berkontribusi pada pengembangan sistem perencanaan rute adaptif yang responsif terhadap perubahan kondisi lalu lintas.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
References
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NJ: Prentice Hall.
Badan Pusat Statistik Kota Bekasi. (2024). Statistik daerah Kota Bekasi 2024. Bekasi: BPS Kota Bekasi.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). Cambridge, MA: MIT Press.
Dechter, R., & Pearl, J. (1985). Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3), 505–536. https://doi.org/10.1145/3828.3830
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. https://doi.org/10.1007/BF01386390
Google. (2023). Google Maps platform: Routes. Retrieved from https://developers.google.com/maps/documentation/routes
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Reading, MA: Addison-Wesley.
Prasetyo, A. C., Arnandi, M. P., Hudnanto, H. S., & Setiaji, B. (2019). Perbandingan algoritma A*Star dan Dijkstra dalam menentukan rute terdekat. Jurnal Ilmiah Sisfotenika, 9(1), 1–10. http://www.sisfotenika.stmikpontianak.ac.id/index.php/ST/article/view/456/316
Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem. Journal of Physics: Conference Series, 1566, 012061. https://doi.org/10.1088/1742-6596/1566/1/012061
Russell, S., & Norvig, P. (2010). Artificial intelligence: A modern approach (3rd ed.). Upper Saddle River, NJ: Prentice Hall.
Sulistiani, H., & Wibowo, D. A. (2018). Perbandingan algoritma A* dan Dijkstra dalam pencarian kecamatan dan kelurahan di Bandar Lampung. Seminar Nasional Teknologi Informasi dan Multimedia, 6(1), 7–12.
TomTom Traffic Index. (2024). Traffic congestion statistics. Retrieved from https://www.tomtom.com/traffic-index/
Zeng, W., Church, R. L., & Chen, X. (2010). Finding shortest paths on real road networks: The case for A*. International Journal of Geographical Information Science, 24(3), 451–476. https://doi.org/10.1080/13658810902904964