Implementasi Customizable Route Planning untuk Pencarian Rute Tercepat pada Jaringan Jalan OpenStreetMap di Wilayah Indonesia

Lintang Birda Saputra, Faizal Makhrus, S.Kom., M.Sc., Ph.D.

2026 | Skripsi | ILMU KOMPUTER

Pencarian  rute tercepat antara dua lokasi dalam graf yang merepresentasikan jaringan jalan merupakan fitur utama dalam aplikasi peta online yang memiliki aplikasi, seperti navigasi, logistik, dan lain lain. Graf yang mereperesentasikan jaringan jalan seringkali memiliki jumlah simpul yang sangat besar, dengan jumlah simpul bisa mencapai puluhan juta. Algoritma Dijkstra membutuhkan waktu beberapa ratus milidetik untuk mencari rute tercepat antara dua simpul pada graf jaringan jalan Indonesia. 

Pendekatan kombinasi Customizable Route Planning (CRP) dan algoritma ALT (A* search,  landmarks, dan triangle inequality) menjadi algoritma mutakhir untuk pencarian rute tercepat antara dua lokasi pada graf jaringan jalan karena pendekatan ini mengurangi ruang pencarian dengan cara mempartisi graf dan membuat shortcut edges pada fase prapemrosesan. Fase kueri menjalankan algoritma ALT yang memanfaatkan shortcut edges untuk mempercepat kueri. Meskipun demikian, penelitian mengenai pencarian rute tercepat antara dua lokasi pada peta wilayah Indonesia belum ada yang mengeksplorasi metode ini.

Penelitian ini bertujuan untuk mengevaluasi kinerja pendekatan kombinasi Customizable Route Planning dan algoritma ALT pada graf yang merepresentasikan jaringan jalan Openstreetmap di wilayah Indonesia. Berdasarkan hasil pengujian, algoritma kueri dari kombinasi teknik CRP dan algoritma ALT terbukti mempercepat kinerja kueri pencarian rute tercepat antara dua lokasi pada graf jaringan OpenStreetMap Wilayah Indonesia sebesar 216,8 kali jika dibandingkan dengan algoritma Dijkstra.

Finding the fastest route between two points in a graph representing a road network is a key feature in online map applications, including navigation, and other applications. Graphs representing road networks often have a large number of nodes, often reaching tens of millions. Dijkstra's algorithm requires several hundred milliseconds to find the fastest route between two points in the Indonesian road network graph.

The combined approach of Customizable Route Planning (CRP) and the ALT algorithm (A* search, landmarks, and triangle inequality) is a cutting-edge algorithm for finding the fastest route between two locations on a road network graph, as it reduces the search space by partitioning the graph and creating shortcut edges during the preprocessing phase. The query phase runs the ALT algorithm, which utilizes shortcut edges to speed up queries. However, no research has explored this method on finding the fastest route between two locations on a map of Indonesia. 

This study aims to evaluate the performance of the combination of CRP approach and the ALT (A* search, landmarks, and triangle inequality) on a graph representing the OpenStreetMap road network in Indonesia. Test results demonstrate that the query algorithm resulting from combination of CRP approach and the ALT algorithm accelerates the process of finding the fastest route between two locations on the Indonesian OpenStreetMap graph by a factor of 216.8 compared to Dijkstra's algorithm.

Kata Kunci : Jaringan Jalan, Perencanaan Rute, Customizable Route Planning, Rute Tercepat, Rute Terpendek