Efisiensi dan Efektivitas Algoritme Pencarian Rute Tercepat Dengan Perhitungan Bobot Jalur Optimal

ISNAENI SETIYADI, Teguh Bharata Adji, S.T., M.T., M.Eng., Ph.D.; Noor Akhmad Setiawan, S.T., M.Eng., Ph.D.

2015 | Tesis | S2 Teknik Elektro

Algoritme Dijsktra merupakan salah satu algoritme yang digunakan untuk pencarian jalur terpendek. Optimalisasi algoritme ini sudah banyak dilakukan, salah satunya adalah dengan memberikan bobot optimal pada jalur-jalurnya. Pada Algoritme Dijsktra standar, bobot masing-masing jalur hanya terdiri atas satu nilai. Namun pada bobot optimal, pembobotan pada masing-masing jalur terdiri atas beberapa variasi nilai. Pengembangan algoritme, tak lepas dari pengujian performa dan keakuratan dalam menghasilkan solusi sesuai dengan fungsinya. Dalam penelitian ini, akan dilakukan pengujian terhadap pengembangan Algoritme Dijsktra menggunakan bobot optimal. Untuk menguji algoritme tersebut, dipilih objek penelitian di jalan raya Kota Palu, Provinsi Sulawesi Tengah. Untuk menguji efisiensi penggunaan processor, memori dan waktu eksekusi, dibuat dua buah simulator menggunakan bahasa pemrograman Java. Kemudian menguji peningkatan penggunaan sumber daya tersebut menggunakan Uji-t. Sedangkan untuk menguji efektivitas perkiraan waktu tempuh, dilakukan pengukuran rata-rata error menggunakan Mean Square Error (MSE). Digunakan perjalanan yang sesungguhnya sebagai pembanding antara hasil dari simulator dengan aplikasi pencarian rute yang sudah populer di masyarakat, yaitu Google Maps. Hasil perbandingan dengan Algoritme Dijsktra standar menunjukkan algoritme yang dikembangkan dengan bobot optimal masih efisien dalam menggunakan processor dan waktu eksekusi. Namun penggunaan memori tidak efisien lagi dengan peningkatan yang signifikan. Untuk keakuratan dalam memperkirakan waktu tempuh Algoritme Dikjstra dengan bobot optimal tidak efektif dengan MSE sebesar 435,25 bila dibandingkan dengan hasil pencarian rute dari Google Maps dengan MSE sebesar 265,85.

Dijkstra Algorithm is one of the algorithm that used to search the shortest path. This algorithm optimization has been lot of made, which one was to provide optimal weight on the edge. At the origin of Dijkstra Algorithm, the weight of each track is only one value. However in the Dijkstra Algorithm with optimal weight, the weighting on each track were consists of a variety of values. The Algorithm development, could not be separated from the test performance and accuracy in generating solutions according to its function. This study tested the algorithm development Dijkstra using optimal weights. To test these algorithms, have been the object of research in highway Palu, Sulawesi Tengah. To test the efficiency of the processor usage, memory usage and execution time, we made of two simulators using the Java programming language. And we tested the increased of resources usage using the t-test method. Meanwhile, when to tested the effectiveness of the estimated travel time, we used the average of measurement error using the Mean Square Error (MSE), and used this value to made the comparison between the results of the simulator with the result from applications for tracking route searches that have been popular in the community, namely Google Maps. The comparison with standard algorithms Dijsktra showed algorithms developed with optimal weight was still efficient in using processor and execution time. However, no efficient memory usage again with a significant increase. For accuracy in estimating the travel time algorithm Dikjstra with optimal weight was not effective with the MSE of 435.25 when compared to the search results of Google Maps with MSE of 265.85.

Kata Kunci : Pencarian Rute Terbaik, Algoritme Dijkstra, Bobot Optimal, Bobot Dinamik, Performa, Shortest Path Algorithm, Dijkstra Algorithm, Optimal Weight, Dynamic Weight, Performance