Claim Missing Document
Check
Articles

Perbandingan Algoritma Dijkstra dan A-Star untuk Pencarian Rute Transportasi Umum Pada Perangkat Bergerak Afirianto, Tri; Arwani, Issa; Akbar, Muhammad Aminul; Pinandito, Aryo
Jurnal Teknologi Informasi dan Ilmu Komputer Vol. 13 No. 5: Oktober 2026
Publisher : Fakultas Ilmu Komputer, Universitas Brawijaya

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.25126/jtiik.2026135

Abstract

Transportasi merupakan suatu proses perpindahan barang atau manusia dari tempat asal ke tempat tujuan dengan menggunakan alat bantu. Angkutan kota (angkot) merupakan salah satu bentuk transportasi umum yang memiliki berbagai macam rute, sehingga penumpang dapat memilih rute sesuai dengan keperluannya. Ada kalanya, penumpang mengalami kesulitan ketika memilih angkot untuk menuju ke tempat tujuan dari posisi penumpang berada saat itu. Terkadang terdapat beberapa angkot dengan tujuan yang berbeda-beda yang melintasi jalan yang sama. Untuk membantu penumpang memilihkan angkot yang tepat menjadi suatu tantangan yang kompleks. Hal ini dikarenakan pengaruh dari berbagai faktor, seperti kemacetan, biaya, waktu tempuh, dan kondisi jalan yang kurang memadai. Penelitian terhadap algoritma pencarian rute yang efisien, baik dari kecepatan maupun penggunaan sumber daya, telah dilakukan selama beberapa dekade. Dua algoritma yang umum diteliti adalah Dijkstra dan A-Star (A*). Penelitian yang dilakukan bertujuan untuk (i) mengimplementasikan algoritma Dijkstra dan A-Star pada perangkat bergerak untuk menentukan rute angkot terpendek; serta (ii) menganalisis performa dari komputasi algoritma tersebut dengan studi kasus di Kota Malang. Hasil penelitian menunjukkan bahwa A-Star lebih efisien dalam waktu eksekusi, meskipun A-Star membutuhkan lebih banyak memori dari pada Dijkstra. Kecepatan waktu eksekusi A-Star lebih cepat dikarenakan memanfaatkan fungsi heuristik untuk memandu proses pencarian, namun, hasil ini membutuhkan memori lebih banyak. Kebalikannya, Dijkstra harus mengevaluasi setiap bobot node yang ada yang membutuhkan waktu lebih lama namun menggunakan memori lebih efisien. Temuan ini memberikan kontribusi dalam pengembangan aplikasi pencarian rute transportasi umum yang lebih responsif dan efisien pada perangkat bergerak.   Abstract Transportation is the process of moving goods or people from an origin to a destination using supporting tools. City transportation (commonly known as angkot in Indonesia) is one form of public transportation that operates on various routes, allowing passengers to choose a route based on their needs. However, the passengers often face difficulties when selecting the appropriate angkot to reach their destination from their current location. In some cases, multiple angkot lines with different destinations operate on the same road. Assisting passengers in choosing the most suitable angkot presents a complex challenge due to various influencing factors, such as traffic congestion, cost, travel time, and poor road conditions. Research on efficient route-finding algorithms, in terms of both speed and resource usage, has been conducted for decades. Two commonly studied algorithms are Dijkstra and A-Star (A*). This study aims to (i) implement the Dijkstra and A-Star algorithms on mobile devices to determine the shortest angkot routes; and (ii) analyze the computational performance of these algorithms using a case study in Malang City. The results show that A-Star is more efficient in terms of execution time, although it requires more memory compared to Dijkstra. A-Star achieves faster execution time by utilizing a heuristic function to guide the route-finding process; however, this results in higher memory consumption. In contrast, Dijkstra must evaluate the weight of every node, which takes more time but uses memory more efficiently. These findings contribute to the development of more responsive and efficient public transportation route-finding applications on mobile devices.
Co-Authors Adharul Muttaqin Adhitya, I Made Yoga Admaja Dwi Herlambang, Admaja Dwi Agan Philothra, Gerry Agung Ari Wibowo Agustian, Muhammad Prio Akbar, Muhamad Aminul Akbar, Muhammad Aminul Alif Arsan, Danish Aminuyati Ardana, Firdausi Baiq Arief Andy Soebroto Arsan, Danish Alif Aryo Pinandito Aswin Suharsono, Aswin Aydin, Radithya Az Zahra, Hamidah Azizi, Maulana Raga Bayu Rahayudi Budi Darma Setiawan Candra, Abhirama Andhika Dahnial Syauqy Deary, Daniel Dian Eka Ratnawati Djoko Pramono Dwija Wisnu Brata Dzulfiqar, Muhammad Dzulkarnain, Tsania Easterita, Bella Krisanda Efendi, Archie Vian Nizam Fadhil, Muhammad Farrasseka Fajar Pradana Fanoja, Galang Farisi, Hariz Firmansyah, Rizaldy Wahyu Ghani Wijaya, Alfiyanto hamdi, ghazian Hanggara, Buce Trias Haposan, Rivan Henryranu Prasetio, Barlian Imannuel, Yehezkiel Indriati Indriati Ismiarta Aknuranda Kasyful Amron Khoba, Ahmad Faiz Lailil Muflikhah Leonardo, Ryan Maulana, Hesi Taka Milzam Radifan, Muhammad Abroor Muh Arif Rahman MUHAJIR Nurhadinata, I Kadek Dwi Cahya Oktasena, Audima Parameswari, Savira Yudith Paraswati, Jasmine Pratiwi Putri Pardede, Rizaldi Permana, Rendra Eka Pradipta, Arya Pratama, Bagas Ramadhani Purnomo, Welly Putra, Widhy Hayuhardika Nugraha Raden Arief Setyawan Raharjo, Adhimas Suryo Ramadhan, Fachri Ramawijaya, Valentinus Rekyan Regasari MP, Rekyan Regasari Riswan Septriayadi Sianturi Sabriansyah Rizqika Akbar Sabriansyah Rizqika Akbar, Sabriansyah Saputro, Dimas Sativandi Putra Satrio Agung Wicaksono Satrio Hadi Wijoyo Septriayadi Sianturi, Riswan Simbolon, Fran Stinky Sudjianto, Aulia Heppy Cahya Syaekhoni, Muhammad TABAYUNI, RAHIMI ILLONG Tibyani Tibyani Tibyani, Tibyani Tri Afirianto, Tri Varendra, Andrian Fatta Wahyudiansyah, Hafidz Wibisono Sukmo Wardhono Widhy Hayuhardhika Nugraha Putra Wiranata, Danuar Zahra, Rifa Fairuz