Komparasi Algoritma Dijkstra dan A-Star untuk Optimasi Rute Kendaraan di Kota Medan
Keywords:
Algoritma A-Star, Algoritma Dijkstra, Navigasi Kendaraan, OpenStreetMap, Rute TerpendekAbstract
Meningkatnya kebutuhan akan efisiensi mobilitas di kawasan perkotaan menuntut adanya sistem navigasi cerdas yang mampu menentukan jalur perjalanan paling optimal. Penelitian ini mengkaji permasalahan pencarian rute terpendek ( shortest path problem ) dengan membandingkan kinerja komputasi algoritma Dijkstra dan A* (A-Star). Eksperimen dilakukan secara komprehensif pada representasi graf jaringan jalan nyata di Kota Medan (terdiri dari 42.692 node dan 99.736 edge ) yang diekstraksi melalui OpenStreetMap (OSM). Pengujian menggunakan 100 test case yang terstratifikasi dalam kategori jarak dekat, sedang, dan jauh. Hasil penelitian menunjukkan bahwa kedua algoritma secara konsisten menghasilkan jarak rute yang identik, membuktikan bahwa penggunaan heuristik hasrsine pada A* tetap menjamin optimalitas jalur. Namun dari segi efisiensi waktu eksekusi, algoritma A* terbukti jauh lebih unggul dengan memenangkan 95% kasus uji dan mencatatkan rata-rata speedup sebesar 2,83 kali lipat dibandingkan Dijkstra. Analisis lebih lanjut mengungkap bahwa keunggulan waktu komputasi A* memuncak pada rute jarak dekat (3,77x) dan perlahan menurun pada rute jarak jauh (1,68x) akibat kompleksitas topologi jaringan jalan. Berdasarkan uji statistik uji t berpasangan, perbedaan kinerja ini dinyatakan signifikan. Hasil analisis ini diharapkan dapat menjadi rujukan strategi bagi pengembangan sistem transportasi digital, khususnya penyesuaian algoritma perutean pada kondisi topologi lalu lintas riil di Indonesia.
References
Al Bager, A. A., & Ahmed, A. S. (2021). Designing and implementing shortest and fastest paths A comparison of Bellman-Ford algorithm, A and Dijkstra’s algorithms. International Journal of Computer Trends and Technology, 69(5), 6–12. httpsdoi.org10.1444522312803IJCTT-V69I5P102
Aldhafferi, N. (2025). Time and Memory Trade-Offs in Shortest-Path Algorithms Across Graph Topologies: A*, Bellman–Ford, Dijkstra, AI-Augmented A* and a Neural Baseline. Computers, 14(12), 545.
Chen, R. (2022). Bus routing system based on Dijkstra algorithm. Advances in Economics, Business and Management Research, 217, 321–325.
Chu, L., Wang, Y., Li, S., Guo, Z., Du, W., Li, J., & Jiang, Z. (2024). Intelligent vehicle path planning based on optimized A-Star algorithm. Sensors, 24(10), 3149.
Elshaer, A. M., Elmanfaloty, R. A., Abou-Bakr, E., Elrakaiby, M., & Saada, K. (2025). Exploring algorithmic efficiency of A-Star and Dijkstra for optimal route planning in green transportation. International Journal of Intelligent Transportation Systems Research, 23(2), 1097–1107.
Grujic, Z., & Grujic, B. (2025). Optimal routing in urban road networks A graph-based approach using Dijkstra’s algorithm. Applied Sciences, 15(8), 4162.
Mienye, I. D., & Jere, N. (2025). Efficient route planning algorithm for special vehicles using large-scale road network data. ISPRS International Journal of Geo-Information, 14(2), 71.
Milin, V., Stanivuk, T., Skoko, I., & Bulic, T. (2025). Dijkstra and A-Star algorithms for algorithmic optimization of maritime routes and offshore wind farm logistics. Journal of Marine Science and Engineering, 13(10), 1863.
Sapundzhi, F., Danev, K., Ivanova, A., Popstoilov, M., & Georgiev, S. (2025). A performance comparison of shortest path algorithms in directed graphs. Engineering Proceedings, 100(31), 1–12.
Singh, H., Gumber, S., & Rishu. (2025). A review and comparative analysis of fundamental shortest path algorithms. International Journal for Research in Applied Science and Engineering Technology, 13(12).
Ugwoke, K. C., Nnanna, N. A., & Abdullahi, S. E. Y. (2025). A simulation-based review of classical, heuristic, and metaheuristic path planning algorithms. Scientific Reports, 15, 12643.
Verma, G., & Kumar, A. (2024). Algorithmic pathfinding Comparing Dijkstra’s and A algorithms in complex grid environment. International Journal of Engineering Research and Development, 20(8), 70–79.
Vijayalaxmi, M. K. (2024). Finding the shortest path in the transport problem using Dijkstra algorithm. International Journal of Engineering Research and Technology, 13(7).
Wang, R., Lu, Z., Jin, Y., & Liang, C. (2022). Application of A algorithm in intelligent vehicle path planning. Mathematical Models in Engineering, 8(3), 82–90. httpsdoi.org10.21595mme.2022.22828
