IMPLEMENTASI ALGORITMA A* DENGAN PENDEKATAN GENERATE AND TEST UNTUK MENENTUKAN RUTE TERPENDEK PENJEMPUTAN SAMPAH

Abstract

Pengelolaan sampah di Kabupaten Bengkalis menghadapi kendala operasional dalam efektivitas penjemputan sampah. Penentuan rute yang dilakukan petugas secara manual berdasarkan perkiraan subjektif sering menyebabkan pemborosan waktu dan biaya bahan bakar akibat jalur yang tidak optimal. Penelitian ini bertujuan merancang sistem penentuan rute otomatis yang dinamis untuk mengoptimalkan operasional bank sampah. Pengembangan sistem mengintegrasikan metode Generate and Test untuk memvalidasi urutan alamat kunjungan dan algoritma A* (A-Star) untuk mencari jalur terpendek antar titik koordinat berdasarkan fungsi heuristik. Hasil pengujian menunjukkan sistem berhasil menentukan rute optimal (S-A-C-D-E-B-F-H-G) dengan total jarak tempuh 3,25 km. Implementasi algoritma ini terbukti mampu mengurangi jarak perjalanan, menyusun urutan kunjungan secara teratur, serta menyediakan visualisasi rute secara real-time. Secara keseluruhan, aplikasi ini efektif dalam meningkatkan kualitas layanan penjemputan dan menekan biaya operasional transportasi melalui jalur yang lebih efisien