APLIKASI PENCARI RUTE OPTIMUM PADA PETA GUNA MENINGKATKAN EFISIENSI WAKTU TEMPUH PENGGUNA JALAN DENGAN METODE A* DAN BEST FIRST SEARCH

Abstract

Nowadays, most people still use conventional map to search for optimum route to travel from one place to another. By using map, people can estimate optimum route by calculate the length of street. However manual pathfinding using a conventional map requires a great deal of precision and takes a lot of time to be accomplished. Therefore in this research, we develop an application to generate the most optimum route on a digital map. In this application we also consider about the factor of traffic, roads condition and the distance. The methods that are used for pathfinding are A* and Best First Search (BFS), that use heuristic function to 'direct' the search on a graph-represented map. The cost on map's graph is given using map color recognition, also we can input the cost for traffic and roads condition. Based on application's testing results for the comparison between A* and BFS method, it can be concluded that A* provides better and more optimized solution than BFS. The optimum level of a route depends on the availability of an accurate and complete data about the roads condition and the process of setting the nodes cost on a given map that represents the actual condition of the roads. Abstract in Bahasa Indonesia : Untuk menempuh perjalanan dari satu tempat ke tempat lain, peralatan yang paling sering digunakan adalah peta, dengan menggunakan peta, dapat diestimasikan rute yang optimum dengan menghitung panjang jalan yang akan ditempuh. Karena merupakan estimasi, maka dengan cara tersebut belum tentu rute yang dipilih merupakan rute yang optimal karena terdapat faktor lain seperti kemacetan atau kondisi jalan. Untuk itu pada penelitian ini dikembangkan aplikasi untuk penentuan rute yang optimum dengan menggunakan peta digital dimana pada aplikasi ini terdapat faktor kemacetan, kondisi jalan dan jarak tempuh. Untuk pencarian rute digunakan metode A* serta Best First Search yang menggunakan fungsi heuristic guna 'mengarahkan' pencarian pada peta yang direpresentasikan dalam konsep graph. Nilai node-node graph pada peta dapat diatur dengan fasilitas pengenalan warna pada peta. Dan dapat ditentukan pula bobot pada masing-masing node yang merupakan kemacetan atau kondisi jalan. Pada pengujian aplikasi ini, selain diuji untuk mencari rute optimum pada sebuah peta, juga dilakukan uji perbandingan antara metode A* dan Best First Seach. Dari hasil pengujian dapat disimpulkan bahwa metode A* memberikan hasil pencarian rute yang lebih pendek daripada BFS. Tingkat optimasi rute yang dihasilkan tergantung pada tersedianya data yang lengkap dan akurat tentang kondisi jalan serta proses pemberian bobot pada node peta yang mewakili kondisi jalan tersebut. Kata kunci: pencarian rute, peta digital, A*, Best First Search.