OPTIMALISASI RUTE PERJALANAN BPJS KESEHATAN KELILING KOTA PALU MENGGUNAKAN METODE ALGORITMA CHEAPEST INSERTION HEURISTIC

Revfly Ronaldo Labania. Optimalisasi Rute Perjalanan Bpjs Kesehatan Keliling
Kota Palu Menggunakan Metode Algoritma Cheapest Insertion Heuristic
(dibawah bimbingan Agusman Sahari, S.Si., M.Si (I) & Nasria Nacong, S.Si.,
M.Si (II))

Jurusan Matematika
Program Studi Matematika
Fakultas Matematika Dan Ilmu Pengetahuan Alam
Universitas Tadulako

Antrian panjang menjadi salah satu permasalahan yang sering terjadi dalam
pelayanan BPJS Kesehatan sehingga banyak peserta merasa tidak nyaman karena
waktu menunggu terbuang untuk mendapatkan pelayanan. Program BPJS
Kesehatan Keliling hadir untuk membenahi antrian panjang serta meningkatkan
akses layanan jaminan kesehatan masyarakat. Penelitian ini bertujuan menentukan
rute pelayanan BPJS Kesehatan Keliling di Kota Palu menggunakan algoritma
Cheapest Insertion Heuristic (CIH) untuk memperoleh rute dengan jarak perjalanan
yang lebih efisien. Metode yang digunakan adalah metode heuristik dengan
melakukan penyisipan titik berdasarkan pertambahan jarak (insertion cost) terkecil
hingga seluruh titik pelayanan membentuk satu rute tertutup. Data penelitian berupa
jarak antartitik pada 34 lokasi pelayanan yang diperoleh dari Google Maps dan
disusun dalam matriks jarak. Hasil penelitian menunjukkan algoritma CIH
menghasilkan rute dengan total jarak 89,6 km, sedangkan rute awal sebesar 161,0
km, sehingga diperoleh pengurangan jarak sebesar 71,4 km atau 44,35%. Hasil
perhitungan manual sesuai dengan implementasi menggunakan pemrograman
Python sebagai alat bantu verifikasi. Penelitian selanjutnya disarankan dapat
mempertimbangkan faktor lain seperti waktu tempuh, kondisi lalu lintas, dan waktu
pelayanan pada setiap lokasi.

Kata Kunci: BPJS Keliling, Algoritma Cheapest Insertion Heuristic, Optimasi
Rute, Traveling Salesman Problem.