Perbandingan Metode Euclidean Distance, Manhattan Distance, Chebyshev Distance untuk Menentukan Jarak Terpendek SPBU di Brebes Selatan

Abstrak

Stasiun Pengisian Bahan Bakar Umum (SPBU) adalah infrastruktur publik yang disediakan oleh PT. Pertamina kepada masyarakat luas untuk kebutuhan BBM. Salah satu wilayah di Brebes yang terkesan terpisah dari kabupaten induknya yaitu Brebes Selatan. Permasalahan muncul ketika pengendara bermotor mengalami kehabisan bahan bakar dan ingin melakukan pengisian ulang bahan bakar bensin atau solar, tetapi pengendara tersebut berada di lokasi yang cukup jauh dari SPBU.

Oleh karena itu, diperlukan suatu metode untuk mendapatkan informasi rute menuju SPBU terdekat. Proses pencarian rute terpendek pada penelitian ini menggunakan algoritma A-Star. Proses pengujian rute terpendek dilakukan dengan mencari nilai g(n) dan h(n) dari algoritma A-Star menggunakan beberapa metode perhitungan jarak yang berbeda, yaitu jarak Euclidean, jarak Manhattan dan jarak Chebyshev. Kemudian dilakukan perbandingan nilai hasil dari ketiga metode perhitungan jarak tersebut dengan perhitungan haversine.

Hasil dari 20 kali pengujian pada salah satu lokasi SPBU, didapatkan hasil bahwa Euclidean Distance memiliki persentase sebesar 56 %, Manhattan Distance sebesar 33%, dan Chebyshev Distance sebesar 11%.

Kata Kunci : Algoritma A-star, Heuristic, Euclidean Distance, Manhattan Distance, Chebyshev Distance, Haversine.