Pengembangan Algoritma A-Star dengan Penyesuaian Heuristik untuk Pencarian Rute Optimal

Achmad Faiz Sukroni, Juhari Juhari, Achmad Nasichuddin

Abstract


The The A-Star algorithm is one of the most popular shortest route search algorithms due to its effectiveness in finding optimal solutions. This study focuses on modifying the A-Star algorithm to improve its performance in optimizing the shortest route. The study was conducted by comparing the standard A-Star algorithm and its modified version based on the number of iterations required to reach the optimal solution. The assessment was carried out manually and through a computer program using sample data from tourist locations in Blitar as a case study. The results of the analysis in 20 comparative experiments showed that the modified A-Star algorithm was able to minimize the number of iterations by up to 32% compared to the standard A-Star algorithm. This finding indicates that the modifications made to the A-Star algorithm can increase efficiency without reducing the accuracy of the results. This study provides an important contribution to the development of shortest route search algorithms, especially in their application to the tourism sector and navigation systems.


Keywords


A-Star; Algoritma Pencarian; Rute Terpendek; Modifikasi Algoritma; Optimalisasi;

Full Text:

PDF

References


R. Munir, “Graf,” Revisi Buku Mat. Disk. 2012, no. Update, 2023.

T. Liao, F. Chen, Y. Wu, H. Zeng, S. Ouyang, and J. Guan, “Research on Path Planning with the Integration of Adaptive A-Star Algorithm and Improved Dynamic Window Approach,” Electron., vol. 13, no. 2, pp. 1–20, 2024, doi: 10.3390/electronics13020455.

N. N. Sania and I. Sari, “Implementasi Rencana Perjalanan Wisata Di Kota Bogor Menggunakan Algoritma Greedy Berbasis Website,” J. Ilm. Teknol. dan Rekayasa, vol. 24, no. 2, pp. 114–130, 2019, doi: 10.35760/tr.2019.v24i2.2390.

A. S. R. Maula, Tundo, S. Adrianto, Kastum, and N. Sutisna, “Implementasi Penggunaan Algoritma A* pada Penentuan Jarak Terpendek dari Cilacap ke Yogyakarta,” J. Ilm. Inform. Komput., vol. 29, no. 1, pp. 73–82, 2024, doi: https://doi.org/10.35760/ik.2024.v29i1.10661.

E. Sumantri and S. Hidayattullah, “Penerapan Algoritma A*Star untuk Mencari Rute Terpendek dari Kemayoran ke Destinasi Monumen Nasional (MONAS),” J. Sains dan Teknol., vol. 5, no. 2, pp. 673–680, 2023, doi: 10.55338/saintek.v5i2.1432.

Ropiqoh and R. S. Lubis, “Implementation of a-Star Algorithm in Finding the Shortest Route of Cooking Oil Distribution in Karo Regency Using Graph,” Mathline, vol. 8, no. 2, pp. 725–738, 2023, [Online]. Available: http://doi.org/10.31943/mathline.v8i2.442

S. R. Aulia, W. Wamiliana, A. Asmiati, and N. Notiragayu, “Perbandingan Algoritme Dijkstra dan Algoritme A* (A-Star) dalam Penentuan Lintasan Terpendek dari Dinas Pendidikan Provinsi Lampung ke Beberapa Sekolah Menengah Atas (SMA) Negeri di Provinsi Lampung,” J. Pepadun, vol. 4, no. 2, pp. 183–190, 2023, doi: 10.23960/pepadun.v4i2.177.

M. H. P. Yudha, S. Supian, and H. Napitupulu, “Optimalization Route to Tourism Places in West Java Using A-STAR Algorithm,” CAUCHY J. Mat. Murni dan Apl., vol. 7, no. 3, pp. 464–473, 2022, doi: 10.18860/ca.v7i3.17032.

S. J. Russel and P. Norvig, Artificial intelligence : Moder Approach, Third edit., vol. 4. United States of America: Pearson Education, Inc., Upper Saddle River, New Jersey, 2010. doi: 10.1109/ICCAE.2010.5451578.

F. Desiderio, “Development Of A Modified A-Star Algorithm For Path Planning,” Politec. milano 1863, pp. 1–63, 2022, [Online]. Available: https://www.politesi.polimi.it/retrieve/c90d6703-d52d-42a9-a250-7a4fec04282a/Msc_Thesis_Desiderio_finale.pdf

R. N. B. Sitepua and G. N. A. C. Putra, “Penentuan Rute Terpendek Menggunakan Algoritma A Star,” J. Nas. Teknol. Inf. dan Apl., vol. 1, no. November, pp. 431–440, 2022.

Y. Fernando, M. A. Mustaqov, and D. A. Megawaty, “Penerapan Algoritma A-Star pada Aplikasi Pencarian Lokasi Fotografi di Bandar Lampung Berbasis Android,” J. Teknoinfo, vol. 14, no. 1, pp. 27–34, 2020, doi: 10.33365/jti.v14i1.509.

S. S. GANNETT, “Department of the Interior United States Geological Survey,” Pubs.Usgs.Gov, vol. 19, p. 388, 1916, [Online]. Available: http://pubs.usgs.gov/wri/1985/4075/report.pdf

W. F. Anshoriy, “Penerapan Metode Algoritma Clarke and Wright Savings pada Penentuan Rute Terpendek (Studi Kasus di Kantor Pos Pemeriksa Kabupaten Blitar),” Universitas Islam Negeri Maulana Malik Ibrahim Malang, 2023.




DOI: https://doi.org/10.18860/jrmm.v4i2.31208

Refbacks

  • There are currently no refbacks.