Electronic Theses and Dissertation

Penentuan rute terpendek merupakan salah satu permasalahan penting dalam teori graf yang banyak diterapkan pada bidang transportasi, khususnya dalam sistem distribusi barang. Pemilihan rute yang optimal berpengaruh terhadap efisiensi jarak tempuh dan waktu pengiriman. Oleh karena itu, diperlukan suatu metode yang mampu menentukan rute terpendek secara optimal. Penelitian ini bertujuan untuk menerapkan Algoritma A*dalam menentukan rute terpendek antar agen Jalur Nugraha Ekakurir (JNE) di Kota Banda Aceh serta menentukan rute optimal berdasarkan nilai heuristik yang digunakan. Data yang digunakan dalam penelitian ini berupa jarak antar agen JNE yang diperoleh melalui Google Maps dan dimodelkan ke dalam bentuk graf berbobot. Nilai heuristik yang digunakan adalah jarak garis lurus dari setiap simpul menuju simpul tujuan. Hasil penelitian menunjukkan bahwa Algoritma A* berhasil menentukan rute terpendek antar agen JNE serta menghasilkan rute-rute optimal dengan jarak tempuh paling minimum dibandingkan dengan rute alternatif lainnya. Penggunaan nilai heuristik terbukti mampu mengarahkan proses pencarian secara efektif sehingga solusi rute terpendek dapat diperoleh secara optimal berdasarkan jarak tempuh.
Kata Kunci: Rute Terpendek, Algoritma A*, Graf, JNE Banda Aceh

Determining the shortest route is an important problem in graph theory that is widely applied in the field of transportation, particularly in goods distribution systems. Selecting an optimal route affects the efficiency of travel distance and delivery time. Therefore, an appropriate method is required to determine the shortest route optimally. This study aims to apply the A* algorithm to determine the shortest routes between Jalur Nugraha Ekakurir (JNE) agents in Banda Aceh City and to identify optimal routes based on the heuristic values used. The data used in this study consist of distances between JNE agents obtained from Google Maps and modelled as a weighted graph. The heuristic value applied is the straight-line distance from each node to the destination node. The results show that the A* algorithm successfully determines the shortest routes between JNE agents and produces optimal routes with minimum travel distances compared to alternative routes. The use of heuristic values effectively guides the search process of the A* algorithm, enabling optimal shortest-route solutions based on travel distance. Keywords: Shortest Path, A* Algorithm, Graph, JNE Banda Aceh