| Penelitian ini bertujuan untuk menganalisis dan membandingkan kinerja enam algoritma pencarian jalur, yaitu A*, Dijkstra, Breadth First Search (BFS), Depth First Search (DFS), Best First Search, dan Jump Point Search (JPS), dalam konteks perencanaan jalur evakuasi bencana letusan Gunung Semeru. Fokus utama penelitian ini adalah mengevaluasi efisiensi waktu komputasi, jumlah node yang dikunjungi, dan akurasi jalur dalam menghadapi kondisi darurat dengan kemungkinan rintangan (obstacle) di medan nyata berbasis peta jalan OpenStreetMap. Pengujian dilakukan melalui metode Ten-Fold Cross Validation serta skenario dengan dan tanpa obstacle untuk menilai performa algoritma secara menyeluruh. Hasil penelitian menunjukkan bahwa algoritma A* merupakan algoritma paling optimal dengan performa yang stabil dan efisien, memiliki waktu komputasi rata-rata 0.0046 detik dan jumlah node yangrelatif rendah tanpa mengorbankan akurasi jalur. Dijkstra juga menghasilkan jalur yang akurat, namun memiliki waktu komputasi lebih lambat dan sangat terpengaruh oleh keberadaan obstacle, dengan lonjakan waktu hingga 10 kali lipat. Best First Search menunjukkan kecepatan tertinggi namun tidak selalu menghasilkan jalur terpendek. BFS dan DFS masing-masing memiliki keterbatasan dalam mempertimbangkan bobot dan kedalaman pencarian, sehingga kurang direkomendasikan untuk peta graf berbobot. Jump Point Search tidak dapat diuji secara maksimal karena keterbatasan struktur graf jalan yang tidak mendukung prinsip kerja grid-based. Dengan demikian, algoritma A* direkomendasikan sebagai algoritma terbaik untuk perencanaan jalur evakuasi bencana berbasis graf jalan. Penelitian ini diharapkan dapat menjadi kontribusi praktis dalam pengembangan sistem evakuasi bencana yang cepat dan akurat, serta menjadi referensi teoritis bagi studi lanjutan di bidang perencanaan jalur dan mitigasi bencana berbasis algoritma graf. |