ABSTRAKSI: Di Bandung setidaknya terdapat 44 trayek angkutan kota (angkot) baik dalam maupun antar kota. Ketika orang ingin bepergian menggunakan angkot, banyaknya trayek angkot ini sering kali justru membingungkan terutama bagi calon penumpang yang tidak familiar dengan trayek angkot Bandung seperti wisatawan atau pendatang baru.
Metode pencarian yang sering digunakan pada kasus rute terpendek adalah algoritma A*. Namun ketika diimplementasikan pada ruang masalah yang besar A* membutuhkan memori penyimpanan yang besar pula. Iterative Deepening A* (IDA) merupakan algoritma modifikasi dari A yang mampu mengatasi masalah memori ini. Tetapi karena penulusuran dilakukan secara iteratif, IDA* harus membangkitkan simpul-simpul yang sama secara berulang, sehingga penghematan memori harus dibayar dengan pemborosan waktu eksekusi. Dengan kekurangan dan kelebihannya masing-masing, kedua algoritma ini tidak sesuai jika diterapkan pada perangkat mobile yang memiliki berbagai keterbatasan sumber daya. Dengan melakukan pencarian dari dua arah yaitu dari arah maju dan mundur, Bidirectional IDA* (BIDA) mengkonsumsi memori lebih sedikit dibandingkan A. Sedangkan dari sisi waktu eksekusi BIDA* lebih cepat daripada IDA*.
Hasil akhir dari penelitian ini adalah BIDA* complete tetapi mungkin tidak optimal. Dari 50 pengujian terdapat 5 path yang solusinya tidak optimal dengan perbedaan jarak yang masih dapat diterima. Tetapi dari segi efektivitas BIDA* mengkonsumsi memori jauh lebih sedikit dibandingkan A* dengan waktu eksekusi yang jauh lebih cepat dibandingkan IDA*, sehingga dapat disimpulkan BIDA* mampu mengatasi kekurangan dua algoritma tersebut agar dapat diimplementasikan pada perangkat mobile.
Kata Kunci : A*, IDA*, BIDA*, heuristik, memori, waktu eksekusiABSTRACT: There are at least 44 routes of Bandung public transportation (angkot), both within the city itself and between its neighboring cities. When people wants to travel by this angkot, those large number of routes frequently confusing especially for those who not familiar with the angkot routes of Bandung such as tourist or newcomers.
A searching method that often used in shortest path cases is the A* algorithm. However, when implemented on a large problem space A* requires a large storage memory as well. Iterative Deepening A* (IDA) is a modification of the A algorithm that is able to overcome this memory problem. But for the searching done iteratively, IDA* must generate the same nodes repeatedly, thus saving memory should be paid to waste the time of execution. With the disadvantages and advantages of each, the two algorithms is not appropriat e when applied to mobile devices that have a variety of limited resources. By doing a search of two directions ie forward and backward, Bidirectional IDA* (BIDA) consumes less memory than A and in terms of execution time BIDA* is faster than IDA*.
The end result of this research is to BIDA* complete but may not be optimal. Of the 50 tests there are 5 sub-optimal solution paths with the differences that still acceptable distance. But in terms of effectiveness BIDA* consumes much less memory than A * with execution time which is much faster than IDA*, so it can be concluded BIDA* is able to overcome these shortcomings for the two algorithms can be implemented on mobile devices.
Keyword: A*, IDA*, BIDA*, heuristic, memory, time of execution