1

Penerapan Algoritma Greedy Dalam Menentukan Rute Terpendek Puskesmas

(Studi Kasus: Kota Tanjungpinang)

Trisna Aryandi, Hendra Kurniawan, Muhamad Radzi Rathomi

trisna.aryandi@gmail.com, hendra@umrah.ac.id, radzi@umrah.ac.id

Jurusan Informatika, Fakultas Teknik, Universitas Maritim Raja Ali Haji

ABSTRAK

Salah satu faktor yang mempengaruhi rendahnya pemanfaatan pelayanan Puskesmas adalah jarak yang ditempuh. Dimana jarak yang dekat adalah menjadi pilihan utama masyarakat untuk memeriksakan kesehatannya. Dalam penelitian ini akan mencari rute

terpendek dari lokasi user ke Puskesmas tujuan, dimana user akan dapat menghemat waktu dan juga biaya transportasi. Algoritma Greedy dipilih untuk diimplementasikan

kedalam aplikasi berbasis android karena algoritma Greedy adalah algoritma untuk menyelesaikan masalah optimasi secara langkah demi langkah. Pendekatan yang digunakan di dalam algoritma Greedy adalah membuat pilihan yang terlihat

memberikan perolehan terbaik yaitu dengan membuat pilihan optimum lokal pada setiap langkah dan diharapkan akan mendapatkan solusi optimum global. Hasil penelitian

dengan algoritma Greedy ini ditunjukkan dengan 3 skenario pengujian dimana semua skenario menunjukan bahwa algoritma Greedy dapat memberikan hasil yang optimum.

Kata Kunci: Puskesmas, Rute Terpendek, Algoritma Greedy.

PENDAHULUAN

Berdasarkan data Survei Sosial Ekonomi Nasional 2007 menunjukkan sekitar 33% penduduk yang sakit berobat ke Puskesmas, sedangkan layanan kesehatan lain

yang dituju adalah praktik dokter, poliklinik dan rumah sakit swasta. Rendahnya pemanfaatan pelayanan Puskesmas tersebut mungkin dipengaruhi oleh beberapa faktor

diantaranya adalah umur, pengetahuan, status pendidikan, ekonomi, jarak, waktu tempuh, perilaku petugas kesehatan, kebutuhan kesehatan dan stigma atau pengaruh luar terhadap pelayanan Puskesmas (Nurhayati, 2014).

Yang menjadi perhatian dari semua faktor yang mempengaruhi rendahnya pemanfaatan pelayanan Puskesmas adalah jarak yang ditempuh. Dimana jarak yang

dekat adalah menjadi pilihan utama masyarakat untuk memeriksakan kesehatannya. Dengan memilih Puskesmas yang terdekat, masyarakat akan dapat menghemat waktu dan juga biaya transportasi. Dalam hal ini sangat dibutuhkan metode untuk menentukan

rute terpendek agar cepat dan hemat. Algoritma Greedy merupakan algoritma yang dapat memecahkan masalah dengan

membuat pilihan yang tampaknya terbaik pada saat tertentu. Banyak masalah optimasi yang dapat diselesaikan dengan menggunakan algoritma Greedy. Beberapa masalah

2

mungkin tidak menemukan solusi yang efisien, tetapi pada algoritma Greedy mampu

memberikan solusi efisien yang dekat dengan optimal (Malik dkk, 2014).

KAJIAN LITERATUR

Hayati dan Yohanes (2014) dalam penelitiannya menerapkan algoritma Greedy

untuk masalah pencarian rute terpendek. Dimana hasil dari penelitiannya yaitu didapat rute yang optimal dengan jarak yang paling pendek adalah A→B→D→G→I→ K→J→L dengan bobot jarak 12, yaitu Ngaliyan → SPBU Ngaliyan → Pasadena →

Kalipancur → Simongan → SPBU Jembatan Besi → Menoreh → Sampangan. Faisal (2015) dalam penelitiannya mengimplementasi algoritma Greedy untuk

masalah penukaran uang. Tujuan dari persoalan optimasi penukaran uang adalah untuk mencari jumlah penukaran uang seminimal mungkin yang diperlukan solusi yang dihasilkan pada masalah penukaran uang ini adalah paling minimal (empat) yaitu 2 buah

uang pecahan Rp.50.000,00, pilih 1 buah uang pecahan Rp.20.000,00, pilih 1 buah uang pecahan Rp.5.000,00.

Francois dan Boeffard (2002) dalam penelitiannya yang berjudul aplikasi untuk pembangunan kemampuan bicara basis data secara terus menerus menerapkan algoritma Greedy untuk membangun database dan menghadirkan fitur linguistik yang bervariasi

serta mengatur set kalimat dan ucapan agar terdengar baik bagi pendengar. Algoritma Greedy mampu memilih solusi optimal pemilihan 3000 kalimat yang disusun secara

baik dan benar. Hermawan (2012) dalam penelitiannya menjelaskan dan menggambarkan bahwa

algoritma Greedy dapat membantu dalam permainan congklak dan cukup baik dapat

digunakan untuk memilih lubang yang dimungkinkan memperoleh biji terbanyak. Kombinasi dan cara berfikir yang dinamis, pemain komputer dapat memutuskan kapan

harus menyelamatkan biji lubangnya atau lebih memilih memperoleh biji sebanyak-banyaknya.

Passa (2010) dalam penelitiannya yang berjudul “Aplikasi Algoritma Greedy Pada

Persoalan Pewarnaan Graf” menjelaskan bahwa Algoritma Greedy memberikan solusi per langkah dimana setiap langkah yang diambil merupakan solusi lokal optimal yang

bisa didapatkan pada saat itu. Tidak semua persoalan pada pewarnaan graf yang diselesaikan menggunakan algoritma Greedy menuju kepada hasil optimum global.

Herli dkk (2015) dalam penelitiannya yang berjudul “Sistem Pencarian

Berdasarkan Rute Perjalanan Terpendek Dengan Memperhitungkan Daya Tarik Wisata Menggunakan Algoitma Greedy” menyimpulkan bahwa algoritma Greedy dapat

digunakan dalam memberikan rekomendasi rute perjalanan dan pemilihan hotel sebelum atau sesudah wisatawan berwisata. Dan hasil evaluasi sistem dapat disimpulkan bahwa sistem memberikan rekomendasi pemilihan rute perjalanan dan

hotel secara benar dengan memperhitungkan bobot jarak perjalanan. Prasetyo dan Hastuti (2015) dalam penelitiannya yang berjudul “Penerapan

Haversine Formula Pada Aplikasi Pencarian Lokasi dan Informasi Gereja Kristen di Semarang Berbasis Mobile” menjelaskan bahwa Haversine Formula digunakan untuk menghitung jarak antara titik di permukaan bumi menggunakan garis lintang (longitude)

dan garis bujur (lattitude) sebagai variabel inputan. Dan hasil evaluasi sistem dapat disimpulkan bahwa Haversine Formula berhasil diaplikasikan ke dalam aplikasi Church

3

Map yang mampu menampilkan posisi user saat itu, gereja-gereja dari posisi user

berada dan menampilkan rute gereja pada aplikasi berbasis Android.

BAHAN DAN METODE

Data yang digunakan dalam penelitian ini adalah data titik koordinat simpang,

data titik koordinat lokasi Puskesmas dan data koneksi antar simpul. Dimana data ini adalah data lattitude, longitude dan jarak antar simpul pada graf, serta koneksi beberapa

rute jalan di wilayah kota Tanjungpinang yang diperoleh dari website www.google.com/maps/d/. Jumlah titik simpang yang digunakan dalam penelitian ini adalah 99 titik simpang dan lokasi puskesmas yang digunakan adalah 7 titik yaitu

Puskesmas Tanjungpinang, Puskesmas Sei Jang, Puskesmas Mekar Baru, Puskesmas Melayu Kota Piring, Puskesmas Batu Sepuluh, Puskesmas Tanjung Unggat dan

Puskesmas Kampung Bugis.

Tabel 1. Contoh Tabel Data Simpang

No kode_simpang lattitude longitude

1 SDR001 0,92577 104,44142

2 DIO001 0,9275 104,44424

3 DIO002 0,92736 104,44386

4 BBT001 0,92772 104,44493

5 SNR001 0,92352 104,44379

Tabel 2. Contoh Tabel Data Koneksi

No simpul_awal simpul_tujuan jarak

1 SDR001 DIO002 356

2 DIO002 DIO001 45

3 DIO001 DIO002 45

4 DIO001 BBT001 80

5 BBT001 BKM001 921

Adapun langkah-langkah dalam menentukan rute terpendek Puskesmas adalah sebagai berikut: a. Menentukan lokasi awal user dan simpul tujuan untuk menentukan rute terpendek

Puskesmas di Tanjungpinang b. Mencari simpul awal yang terdekat dengan lokasi user dengan menggunakan

persamaan Haversine Formula seperti berikut:

𝑥 = (𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑜𝑛𝑔2 − 𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑜𝑛𝑔1) × cos ((𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑎𝑡1+𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑎𝑡2)

2) ; (1)

𝑦 = (𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑎𝑡2 − 𝑟𝑎𝑑𝑖𝑎𝑛 𝑙𝑎𝑡1); (2)

𝑑 = √(𝑥 2 + 𝑦2)𝑅 (3)

Keterangan:

x = Longitude (Lintang) y= Lattitude (Bujur)

4

d= Jarak

R= Radius bumi= 6.371km 1 derajat= 0.0174532925 radian

c. Setelah mendapatkan hasil perhitungan menggunakan Haversine Formula,

kemudian dilanjutkan dengan perhitugan menggunakan Algoritma Greedy. Adapun elemen-elemen umum yang dimiliki algoritma Greedy antara lain:

1. Himpunan Kandidat Himpunan kandidat merupakan himpunan yang mengandung elemen-elemen yang dapat menjadi bagian dari pembentuk solusi. Pada persoalan pencarian rute

terpendek dalam graf, himpunan kandidat ini adalah himpunan simpul dari graf tersebut.

2. Fungsi Seleksi Fungsi inilah yang berperan dalam pemilihan solusi lokal setiap tahap dalam algoritma Greedy untuk menghasilkan solusi optimal. Kandidat yang sudah

dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

3. Fungsi Kelayakan Fungsi yang memeriksa apakah suatu kandidat yang telah tepilih (diseleksi) dapat memberikan solusi yang layak, yaitu jarak terdekat dengan simpul awal.

4. Fungsi Obyektif Fungsi yang menentukan atau menghitung nilai dari solusi yang didapatkan.

5. Fungsi Solusi Fungsi ini akan menunjukkan proses pencarian yang dilakukan sudah menemukan solusi terbaik.

HASIL

Pada Tabel 3 berikut merupakan simpul-simpul atau titik simpang yang akan

dilalui dari simpul awal user menuju simpul tujuan I (PTPI).

Tabel 3 Keterangan inisial simpul pada graf

No. Simpul Keterangan

1 user Lokasi awal user

2 A SDR001

3 B DIO002

4 C SNR001

5 D DIO001

6 E BBT001

7 F BKM001

8 G BKM002

9 H HJD001

10 I PTPI

11 J IRS001

12 K TPN001

5

Setelah diketahui simpul user, maka selanjutnya dilakukan perhitungan

menggunakan Haversine Formula dan hasil perhitungannya ditunjukan pada Tabel 4 berikut:

Tabel 4. Perhitungan Haversine Formula

Simpul Terdekat dengan lokasi user Keterangan Nilai Satuan

Titik simpul A

x (longitude) 6.99908E-07 y (lattitude) 6.441E-05 d (jarak) 0.410380337 km

410.380337 m

Titik simpul B

x (longitude) 4.32843E-05 y (lattitude) 3.665E-05 d (jarak) 0.361340441 km

361.340441 m

Gambar 1 berikut merupakan gambar graf yang akan digunakan untuk perhitungan penentuan rute terpendek algoritma Greedy dari simpul awal user ke

simpul tujuan I.

. Gambar 1. Graf penentuan rute terpendek Puskesmas

Berdasarkan graf pada Gambar 1 diatas, elemen himpunan kandidat terdiri atas semua simpul yang bisa dilalui menuju solusi optimal, sehingga dapat dituliskan

{A,B,C,D,E,F,G,H,I,J,K,}. Langkah berikutnya bermula dari simpul user berada sebagai simpul awal,

kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul A dan B. Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul user, yaitu simpul B. Fungsi objektif menghitung total jalur yang telah

dilalui sementara ini adalah 361. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 2 sebagai berikut:

6

Gambar 2. Graf rute dari simpul user ke simpul B (garis tebal)

Langkah berikutnya bermula dari simpul B sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul C dan

D. Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul B, yaitu simpul D. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini

adalah 406. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 3 sebagai berikut:

Gambar 3. Graf rute yang terpilih dari simpul B ke simpul D (garis tebal)

Langkah berikutnya bermula dari simpul D sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul E. Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul D,

yaitu simpul E. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini adalah 486. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul

tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 4 sebagai berikut:

7

Gambar 4. Graf rute yang terpilih dari simpul D ke simpul E (garis tebal)

Langkah berikutnya bermula dari simpul E sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul F.

Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul E, yaitu simpul F. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini

adalah 1407. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 5 sebagai berikut:

Gambar 5. Graf rute yang terpilih dari simpul E ke simpul F (garis tebal)

Langkah berikutnya bermula dari simpul F sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul G. Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul F,

yaitu simpul G. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini adalah 1684. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul

tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 6 sebagai berikut:

8

Gambar 6. Graf rute yang terpilih dari simpul F ke simpul G (garis tebal)

Langkah berikutnya bermula dari simpul G sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul H.

Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul G, yaitu simpul H. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini

adalah 2391. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul tujuan. Jika belum, maka algoritma akan kembali menggunakan fungsi seleksi lagi pada langkah berikutnya.

Sehingga penggambaran pada graf ditunjukkan pada Gambar 7 sebagai berikut:

Gambar 7. Graf rute yang terpilih dari simpul G ke simpul H (garis tebal)

Langkah berikutnya bermula dari simpul H sebagai simpul awal, kemudian fungsi seleksi digunakan untuk memilih simpul yang terhubung langsung, yaitu simpul I. Fungsi kelayakan akan memeriksa simpul mana yang lebih dekat dengan simpul H,

yaitu simpul I. Fungsi objektif menghitung total jalur yang telah dilalui sementara ini adalah 2399. Fungsi solusi akan memeriksa apakah pencarian sudah menemukan simpul

tujuan. Jika sudah, maka proses pencarian akan berhenti. Sehingga penggambaran pada graf ditunjukkan pada Gambar 8 sebagai berikut:

9

Gambar 8. Graf rute yang terpilih dari simpul H ke simpul I (garis tebal)

KESIMPULAN

Kesimpulan yang dapat diambil dari hasil penelitian tentang Penentuan Rute Terpendek Puskesmas menggunakan Algoritma Greedy adalah:

a. Penggunaan Algoritma Greedy biasanya digunakan dalam penyelesaian

masalah optimasi, namun dalam kasus pencarian rute terpendek tidak selalu memberikan solusi yang optimal secara keseluruhan (optimum global).

b. Berdasarkan hasil analisa yang telah dilakukan maka dapat disimpulkan bahwa implementasi Algoritma Greedy dalam menentukan rute terpendek Puskesmas dapat memberikan rute yang optimal, yaitu user-B-D-E-F-G-H-I dengan total

jarak 2399.

DAFTAR PUSTAKA

Faisal., 2015, Penerapan Metode Greedy Dalam Optimasi Penukaran Uang Sebesar 125

Ribu Rupiah, Journal of Electrical and Electronic, Universitas Islam “45”, 1-8. Francois, H., dan Boeffard, O., 2002, The Greedy Algorithm and its Application to the

Construction of a Continuous Speech Database, Journal Informatique et Systemes Aleatoires.

Hayati, E.N., dan Yohanes. A., 2014, Pencarian Rute Terpendek Menggunakan

Algoritma Greedy. Seminar Nasional IENACO. Universitas Stikubank Semarang, 1-7.

Herli, A.M., Raharjana, I.K., dan Purbandini., 2015, Sistem Pencarian Hotel Berdasarkan Rute Perjalanan Terpendek Dengan Mempertimbangkan Daya Tarik Wisata Menggunakan Algoritma Greedy, Journal of Information Systems

Engineering and Business Intelligence, Universitas Airlangga, 1-8. Hermawan, G., 2012, Implementasi Algoritma Greedy Best First Search Pada Aplikasi

Permainan Congklak Untuk Optimasi Pemilihan Lubang Dengan Pola Berfikir Dinamis, Jurnal Teknik Informatika.

Malik, A., Sharma, A., dan Sahora, V., 2013, Greedy Algorithm, International Journal

of Scientific and Research Publications, vol. 3.

10

Nurhayati., 2014, Faktor Responsiveness terhadap Kepuasan Pasien di Pelayanan

Kesehatan Ibu dan Anak (KIA), Journal Health Quality Vol. 4, 134-141. Passa, F., 2010, Aplikasi Algoritma Greedy Pada Persoalan Pewarnaan Graf, Makalah

IF3051 Strategi Algoritma Tahun 2010, Institut Teknologi Bandung, 1-8.

Prasetyo, D., dan Hastuti, K., 2015, Penerapan Haversine Formula Pada Aplikasi Pencarian Lokasi Dan Informasi Gereja Kristen Di Semarang Berbasis Mobile.

Universitas Dian Nuswantoro Semarang, 1-8.