Available Online at http://ojs.uho.ac.id/index.php/JIPFI p-ISSN: 2502-3861    |    e-ISSN: 2715-551X
Implementasi Algoritme Bellman-Ford dalam Menentukan Rute Terpendek
Pembuangan Sampah Di Kota Kendari
Ma’arif 1) *, Maoudy Bastutiar Mhadjid 2) , M. Syadam Purwanto 3)
1)* Jurusan Matematika MIPA, Universitas Halu Oleo 2,3) Jurusan Matematika MIPA, Universitas Halu Oleo
*Korespondensi Author Email: youngauthorkendari@gmail.com
Abstrak: Berbagai masalah muncul diantaranya kurangnya fasilitas pengangkut sampah yang diberikan oleh  pemerintah kepada dinas terkait, sehingga pengangkutan sampah dari Tempat Penampungan Sementara (TPS) sampai ke Tempat Pembuangan Akhir (TPA)  tidak  optimal  dalam  pelaksanaanya.    Tujuan  dari  kajian  ini  adalah  untuk  menerapkan  Algoritme  Bellman-  Ford  dalam penentuan rute terpendek pengangkutan sampah dari TPS ke TPA di Kota Kendari. Tahapan Algoritme Bellman-Ford dimulai dari tahap analisis kebutuhan data, perancangan, implementasi, dan pengujian. Sedangkan data yang digunakan pada kajian ini berupa data  primer  dan  data  sekunder  tentang  lintasan  pengangkutan  sampah  dari  TPS  ke  TPA  yang  ada  di  Kota  Kendari.  Perhitungan koordinat akan dihitung menggunakan konsep graf dan haversine formula berantuan Global Positioning System (GPS). Data hasil analisis  berupa  simpul  yang  merepresentasikan  TPS  yang  ada  di  Kota  Kendari,  sedangkan  sisi  merepresentasikan  lintasan  yang menghubungkan antar TPS ke TPA. Sedangkan bobot merepresentasikan jarak (km) antar TPS dan TPA. Algoritme Bellman-Ford memungkinkan  adanya  bobot  yang  negatif  untuk  nilai  edge-nya,  sehingga  dapat  mengantisipasi  kemungkinan  adanya  cost  yang harus dikeluarkan dalam pemilihan jalur pengambilan sampah. Dampak dari penelitian ini yaitu dapat diketahuinya jalur tercepat dan terpendek pembuangan sampah ke tempat pembuangan akhir di Kota Kendari.
Kata Kunci : Algoritme Bellman-Ford; pembuangan sampah; rute terpendek
Abstract: Various  problems  arise,  including  the  lack  of  waste  transportation  facilities  provided  by  the  government  to  related agencies, so that the transportation of waste from the Temporary Storage (TPS) to the Final Disposal Site (TPA) is not optimal in its  implementation.  The  purpose  of  this  study  is  to  apply  the  Bellman-Ford  Algorithm  in  determining  the  shortest  route  for transporting  waste  from  TPS  to  TPA  in  Kendari  City.  The  Bellman-Ford  algorithm  stages  start  from  the  data  requirements analysis, design, implementation, and testing stages. Meanwhile, the data used in this study are primary data and secondary data on the route of transporting waste from TPS to TPA in Kendari City. The calculation of coordinates will be calculated using the graph concept and the haversine formula based on the Global Positioning System (GPS). The data from the analysis are in the form  of  nodes  that  represent  the  TPS  in  Kendari  City,  while  the  sides  represent  the  paths  that  connect  between  TPS  and  TPA. While the weight represents the distance (km) between TPS and TPA. The Bellman-Ford algorithm allows a negative weight for the edge value, so as to anticipate the possible costs involved in selecting the waste collection path. The impact of this research is to find out the fastest and shortest paths for dumping waste to landfills in Kendari City .
Keywords : Algoritme Bellman-Ford; Garbage disposal; Shortest route

## PENDAHULUAN
Berdasarkan  peraturan  Menteri  Pekerjaan  Umum (Pemen  PU)  Nomor  :  21/PRT/M/2006  untuk  mencapai kondisi  masyarakat  yang  sehat  dan  sejahtera  di  masa yang  akan  datang,  akan  sangat  diperlukan  adanya lingkungan  permukiman  yang  sehat.  Kata  sehat  akan berarti  sebagai  kondisi  yang  akan  dapat  dicapai  bila keadaan air, udara, dan tanah bersih dari sampah maupun polusi.  Sampah  dapat  dikelola  secara  baik  sehingga bersih  dari  lingkungan  permukiman  dimana  manusia beraktifitas di dalamnya.
Sampah  pada  umumnya  merupakan  permasalahan yang  menjadi  fokus  utama  di  kota-kota  besar  di
Indonesia,  salah  satunya  yang  terdapat  di  Kota  Kendari. Permasalahan  utamanya  adalah  kurang  optimalnya pengangkutan sampah yang dilakukan, sehingga membuat  sampah  yang  berada  di  tempat  penampungan sementara tidak terangkut secara keseluruhan. Selain itu, berbagai  faktor  lainnnya  adalah  kurangnya  optimalisasi pengangkutan sampah juga disebabkan karena kurangnya fasilitas  TPS  yang  disediakan  dan  jalur  pengangkutan yang  jauh  dalam  pengangkutan  sampah  untuk  menuju TPA (Prasetyo, 2017). Hal ini mengakibatkan keterbatasan  waktu  operasional  dan  jarak  pembuangan sampah yang sangat relatif besar (Aji, 2017). Oleh karena itu,  diperlukan  sebuah  solusi  alternatif  dalam  membuat
Available Online at http://ojs.uho.ac.id/index.php/JIPFI p-ISSN: 2502-3861    |    e-ISSN: 2715-551X
sebuah  rute  yang  efektif  dan  efisien  dalam  proses pengangkutan  sampah.  Salah  satunya  yaitu  dengan menggunakan Algoritme Bellman-Ford. Algoritme Bellman-Ford  merupakan  sebuah  sistem  algoritma  yang digunakan  untuk  pencarian  rute  terpendek  dalam  sebuah lintasan  (Lestari,  2018;  Radiana,  2015).  Selama  ini Algoritme  Bellman-Ford  hanya  digunakan  dalam pemetaan sistem informasi dan pemetaan protocol system dalam sebuah sistem telekomunikasi (Pramudita& Safitri, 2018;  Sulaiman  dkk.  2018).  Akan  tetapi,  kajian  terbaru yang  dilakukan  oleh  Azdy  &  Darnis  (2019)  berhasil mengimplementasikan  dan  membuat  jalur  terpendek pembuangan  sampah  di  Kota  Palembang  dengan menggunakan Algoritme Bellman-Ford.
Kajian  ini  pun  menggunakan  konsep  graf  dalam penyelesaiannya,  secara  geometri  graf  digambarkan sebagai  sekumpulan  noktah  (simpul)  di  dalam  bidang dwimatra  yang  dihubungkan  dengan  sekumpulan  garis (sisi) (Nugraha, 2011; Munir, 2009). Algoritma Bellman- Ford  ini  dikenal  dengan  kelebihan  dalam  menangani kasus-kasus  graf  berbobot  negatif  jika  dibandingkan dengan  algoritma-algoritma  lainnya  (Yudi,  2009;  Hamdi & Prindahoko, 2018). Penelitian ini bertujuan utuk Untuk menentukan rute terpendek pada pemodelan jaringan rute pengangkutan  sampah  di  wilayah  Kota  Kendari (Kecamatan Puuwatu) dari TPS menuju ke TPA Puuwatu dan  Mengetahui  hasil  perbandingan  rute  pengangkutan sampah  yang  selama  ini  diterapkan  oleh  Dinas Lingkungan Hidup Kota Kendari dengan rute pangangkutan sampah menggunakan perhitungan Algoritme Bellman-Ford.

## METODE
Jenis  penelitian  yang  digunakan  adalah  studi  kasus yang  bertujuan  untuk  mengumpulkan  informasi  (Daniel &  Prida,  2019)  yaitu  nama-nama  jalan  yang  ada  di kecamatan  Puuwatu,  kemudian  menentukan  jarak  antara
setiap  batas-batas  jalan  dengan  menggunakan  aplikasi Mapit GIS. Kemudian diselesaikan dengan menggunakan Algoritma Bellman-Ford. Rancanga penelitian menggunakan  Studi  literatur,  yaitu  membahas  dan menjabarkan  serta  mengaitkan  konsep-  koensep  yang sudah  ada  di  dalam  tinjauan  pustaka.  Studi  lapangan, yaitu  dengan  meneliti  langsung  rute  truk  pengangkut sampah  di  Kecamatan  Puuwatu  sehingga  didapat  rute yang  efisien.  penelitian  dilakukan  di  Kecamatan Puuwatu.
Selanjutnya  prosedur  penelitian  dilakukan  sebagai berikut. Melakukan pengumpulan data Pengumpulan data diperoleh  dari internet  menggunakan  aplikasi  Mapit  GIS dan  dari  kepala  Dinas  Lingkungan  Hidup  Kota  Kendari. Mencari  jalur  minimum  truk  sampah  pada  kecamatan Puuwatu  ke  tempat  pembuangan  akhir  (TPA)  dengan menggunakan  metode  Algoritma  Bellmand-Ford  secara manual.
Langkah-langkahnya  yaitu  sebagai  berikut:  (a.) Menentukan titik asal dan mendaftar semua titik maupun sisi.  (b).Memberi  nilai  untuk  titik  asal  sama  dengan  nol dan  titik-titik  lainnya  dengan  tak  hingga.  (c).Memulai iterasi terhadap semua titik yang ada dimulai dengan titik asal,  untuk  menentukan  jarak  dari  semua  titik  yang berhubungan  dengan  titik  asal  dengan  formula  seperti berikut:  U  =  titik  asal,  V  =  titik  tujuan,  UV  =  sisi  yang menghubungkan  U  dan  V.  Jika  jarak  V  lebih  besar  dari jarak  U  +  bobot  UV  maka  jarak  V  diisi  dengan  jarak U+bobot  UV,  dilakukan  hingga  semua  titik  terjelajahi. Mencari  jalur  minimum  truk  sampah  menggunakan Algoritma Bellmand-Ford.

## HASIL DAN PEMBAHASAN
Berdasarkan  investigasi  yang  dilakukan  dengan menggunakan  aplikasi  Google  Maps  dan  Mapit  GIS, diperoleh  peta  serta  jarak  antar  jalan  di  kecamatan Puuwatu. Tahapan tersebut adalah sebagai berikut.
Gambar 1. Peta Kecamatan Puuwatu
Available Online at http://ojs.uho.ac.id/index.php/JIPFI p-ISSN: 2502-3861    |    e-ISSN: 2715-551X
Berdasarkan  penelitian  yang  dilakukan  dengan menggunakan  aplikasi  Google  Maps  dan  Mapit  GIS, diperoleh  peta  kecamatan  Puuwatu.  Peta  kecamatan Puuwatu  yang  dijadikan  sampel  dalam  penelitian  ini
terdapat  pada  Gambar  1.  Pada  peta  kecamatan  Puuwatu terdapat tujuh jalan yang akan diteliti dan dituangkan ke dalam bentuk graf. Adapun gambarnya sebagai berikut.
Gambar 2. Graf Rute Jalan Kecamatan  Puwatu Gambar 3. Rute Awal Dinas Lingkungan Hidup Kota
Kendari
Keterangan :
Titik 0 – 2 – 5 : Jl. Raden Soeprapto; Titik 2 – 3 – 4 : Jl.
H. Latama Bunggulawa; Titik 5 – 6 – 7 : Jl. Banda; Titik
3 – 6 : Anonim Street; Titik 5 – 8 – 9 : Jl. Pattimura; Titik 8 – 10 : Jl. Ratnasari; Titik 9 – 10 – 11 – 7 – 4 : Jl. Chairil Anwar; Titik 11 – 12 : Jl. TPA Puwatu
Pada  Gambar  2.  terdapat  12  titik.  Titik  tersebut merupakan  batas-  batas  jalan,  dimana  titik  0  merupakan titik  awal.  Data  jalan  yang  digunakan  untuk  mengetahui jalur  terpendek  dari  rute  truk  pengangkutan  sampah  ke semua  titik  batas  jalan.  Satuan  yang  digunakan  dalam penelitian  ini  adalah  meter  (m).  Berdasarkan  hasil wawancara  dengan  Kepala  Dinas  Lingkungan  Hidup Kota  Kendari  bahwa  rute  yang  biasa  diterapakan  oleh truk  pengangkut  sampah  menuju  ketempat  pembuangan akhir  (TPA)  yaitu  sebagai  berikut.  Mencari  Rute Minimum  Truk  Pengangkut  Sampah  pada  Kecamatan Puwatu  menggunakan  Metode  Algoritme  Bellman-Ford. Algoritme  Bellman  Ford  digunakan  untuk  menghitung jarak  terpendek  dari  satu  titik  pada  grafik  berbobot. Maksudnya  adalah  Algoritme  Bellman-Ford  menghitung jarak  terpendek  dari  semua  titik.  Adapun  langkah-
langkahnya  berdasarkan  prosedur  penelitian  sebagai berikut.
a. Menentukan titik  awal dan  menguraikan  semua  titik maupun sisi
b. Memberi  nilai  untuk  titik  awal  =  0  dan titik  lainnya dengan nilai tak hingga (∞)
c. Memulai  iterasi  terhadap  semua  titik  yang  dimulai dengan titik asal,untuk menentukan jarak dari semua titik yang berhubungan dengan titik asal dengan cara :
Jika  jarak  V  lebih  besar  dari  jarak  U  +  bobot  UV maka jarak V diisi dengan jarak U + bobot UV. Dimana: U  =  titik  asal  V  =  titik  tujuan  UV  =  sisi  yang menghubungkan  U  dan  V.  Langkah  ini  digunakan  agar semua  titik  tekunjungi.    Berikut  penyelesaian  secara manual.
(a) (b)                                                  (c)
(d)
(e) (f) (g)
Gambar 4. Pemeteraan posisi sesuai interasi (a) interasi 1, (b) interasi 2, (c) interasi 3, (d) iterasi 4, (e) iterasi 5, (f) iterasi 6, (g) iterasi 7.
iterasi 5, (f) iterasi 6, (g) iterasi 7
Dari ketujuh iterasi yang ada terdapat beberapa warna yang  dijadikan  sebagai  node  rute  perjalanan.  Warna tersebut  meliputi  hijau,  merah  dan  biru  dimana  warna hijau  digunakan  sebagai  node  untuk  menandai rute  yang belum  dilintasi.  Warna  merah  digunakan  sebagai  node acuan.  Sedangkan  warna  biru  digunakan  sebagai  node akhir  yang  telah  diperoleh  dari  penjumlahan  node  awal dan bobot antar  node.
Berdasarkan  hasil  investigasi  yang  telah  dilakukan terdapat  tujuh  nama  jalan  yang  diteliti  di  kecamatan Puuwatu,  kemudian  di  interpretasikan  ke  dalam  bentuk graf  dimana  terdapat  12  titik  yang  dicari  rute terpendeknya.  Dua  belas  titik  tersebut  merupakan  batas- batas  jalan  yang  dimana  bias  dilihat  pada  Gambar  4 sebagai  rute  jalan  kecamatan  Puwatu.  Dari  hasil penelitian  untuk  mencari  rute  terpendek  melalui Algoritme Bellman-Ford yaitu dengan menggunakan cara manual.  Penyelesaian  pada  kasus  ini  menggunakan Algoritme  Bellman-Ford  menggunakan  beberapa  tahap. Namun, sebelum menyelesaikan kasus ini terlebih dahulu mencari jarak dari masing-masing titik. Untuk menghitung jarak dari masing-masing titik menggunakan aplikasi MapitGIS.
Mapit  GIS  adalah salah satu  aplikasi  yang  digunakan untuk  yang  mengukur  jarak  antar  setiap  titik  yang tersedia  (Ariwibowo  dlk.  2020).  Dengan  menggunakan aplikasi  ini,  setiap  batas-batas  jalan  dapat  terlihat layaknya  google  Maps  kemudian  didapatkan  jarak  antar setiap  titik  dengan  cara  menghubungkan  setiap  titik  ke titik  lainnya  dilihat  bahwa  rute  pengangkutan  sampah yang  biasa  diterapkan  oleh  Dinas  Lingkungan  Hidup Kota  Kendari  yaitu  melalui  titik  0-2-3-4-7-11-12.  Rute pengangkutan  sampah  tersebut  jika  dihitung  secara manual  yaitu  berjarak  7510  m  sedangkan  jika menggunakan Algoritma Bellmand-Ford rute pengangkutan sampah menuju TPA yaitu melalui titik 0- 2-5-6-7-11-12  berjarak  7225  m.  Hal  ini  menunjukkan bahwa  dengan  menggunakan  Algoritma  Bellmand-Ford rute  yang  didapatkan  lebih  minimum  dibandingkan
dengan rute yang diterapkan oleh Dinas Lingkungan Kota Kendari.
Rute  pengangkutan  sampah  yang  didapatkan  melalui Algoritma  Bellmand-Ford  lebih  minimum  dibandingkan rute  yang  diterapkan  saat  ini  oleh  Dinas  Lingkungan Hidup  Kota  Kendari.  Rute  yang  didapatkan  melalui Algoritma  Bellmand-Ford  dapat  menghemat  perjalanan hingga  3,8%  sehingga  rute  pengangkutan  sampah  lebih optimal dan efisien.

## KESIMPULAN  DAN SARAN
Berdasarkan  hasil  penelitian  dan  pembahasan  dapat disimpulkan  bahwa:  (1)  Pada  penelitian  ini  terdapat  7 nama jalan yang diteliti di kecamatan Puuwatu kemudian dituangkan  kedalam  bentuk  graf.  Pada  graf  yang terbentuk terdapat 12 titik yang dicari rute minimumnya,dimana  12  titik  tersebut  merupakan  batas- batas  jalan  yang  ada  di  kecamatan  Puuwatu.  Untuk menentukan  rute  minimum  menggunakan  Algoritma Bellmand-  Ford  dilakukan  dengan  cara  menentukan  titik awal kemudian menghubungkan titik-titik yang terhubung  dari  titik  awal  tersebut,  lalu  setiap  titik  diisi dengan  jarak  terpendek  dari  titik  awal  yang  telah  di tentukan.  Perhitungan  selesai  jika  semua  titik  sudah saling  terhubung  dengan  jarak  terpendek;  (2)  Untuk menentukan  studi  kasus  di  kecamatan  Puuwatu  dalam mencari  rute  minimum  pengangkutan  sampah  menuju tempat  pembuangan  akhir(TPA)  membutuhkan  7  iterasi dari  12  titik  yang  dicari  rute  minimumnya  sehingga semua  titik  terhubung.  Rute  pengangkutan  sampah  yang diterapkan  saat  ini  adalah  7.510  m  sedangkan  setelah dihitung menggunakan Algoritma Bellmand-Ford menjadi  7.225  m.  Kajian  ini  termasuk  penelitian pendahuluan  sebagai  landasan  pengembanagn  kajian selanjutnya.

## REFERENCES
Aji,  A.  (2017).  Optimasi  Jalur  Tercepat  Dengan Menggunakan  Modifikasi  Algoritma  Bellman
Iterasi 1 :
0 – 2 = 0 + 2300 = 2300 m Iterasi 2 : 2 – 5 = 2300 + 620 = 2920m 2 – 3  = 2300 + 540 = 2840m Iterasi 3 : 5 – 8 = 2920 + 1100 = 4020m 5 – 6 = 2920 + 285 = 3205m 3 – 4 = 2840 +1250 = 4090m Iterasi 4 : 8 – 9 = 4020 + 1070 = 5090m 6 – 7 = 3205 + 980 = 4185m Iterasi 5 : 8 – 10 = 4020 + 1500 = 5520m Iterasi 6 : 7 – 11 = 4185 + 1310 = 5495m Iterasi 57: 11 – 12 = 5495 + 1730 = 7225m
Available Online at http://ojs.uho.ac.id/index.php/JIPFI p-ISSN: 2502-3861    |    e-ISSN: 2715-551X
Ford (Studi Kasus Lintas Antar Kecamatan Kota Malang). Jurnal EECCIS , 9 (2), 168-172.
Ariwibowo, M. M., Suharno, S., & Wahyuni, W. (2020).
Efektivitas  Pemanfaatan  Aplikasi  LOCUS  GIS dan  MAPIT  GIS  Untuk  Pengumpulan  Data Pendaftaran  Tanah. Jurnal  Tunas  Agraria , 3 (1 Jan), 116-144. Azdy,  R.  A.,  &  Darnis,  F.  (2019).  Implementasi Bellman-Ford untuk Optimasi Rute Pengambilan Sampah  di  Kota  Palembang. Jurnal  Nasional Teknik Elektro dan Teknologi Informasi (JNTETI) , 8 (4), 327-333. Daniel,  Farida.,  &  Prida,  N,  L,  T,.  (2019). Teori  graf . Yogyakarta: CV  budi Utama. Hamdi, S., & Prihandoko, P. (2018). Analisis Algoritma Dijktra  dan  Algoritma  Bellman-Ford  Sebagai Penentuan  Jalur  Terpendek  Menuju  Lokasi Kebakaran  (Studi  Kasus:  Kecamatan  Praya Kota). Energy , 8 (1), 26-32.
Lestari,  S.  (2018).  Perbandingan  Algoritma  Floyd- Warshall  dan  Bellman-Ford  dalam  Pencarian Jarak  Terpendek  Antar  ATM  di  Kota  Tebing
Tinggi.
Munir,  R.  (2009). Matematika  Diskrit .  Bandung : Informatika,
Nugraha,  D.  W.  (2011,  September).  Aplikasi  algoritma prim untuk menentukan minimum spanning tree suatu  graf  berbobot  dengan  menggunakan pemrograman berorientasi objek. In FORISTEK:
Forum Teknik Elektro
dan Teknologi
Informasi (Vol. 1, No. 2). Rasdiana.  (2015). Aplikasi  Algoritma  Bellman-Ford dalam  Meminimumkan  Rute  Perjalanan  Tukang Bentor  di  Kecamatan  Biringkanaya .  Makassar  : UIN Alauddin Makassar.
Yudi,  R.  (2009).  Algoritma  Dijkstra  dan  Bellman-Ford dalam  Pencarian  Jalur  Terpendek. Makalah
IF2091  Shortest  Path  Algorithm. Diakses Tanggal 25 Maret 2020. https://informatika.stei.itb.ac.id/~rinaldi.munir/
Matdis/2009/2010/Makalah0910/MakalahStrukd is0910-082.pdf Pramudita, R., & Safitri, N. (2018). Algoritma Bellman- Ford  Untuk  Menentukan  Jalur  Tercepat  Dalam Sistem Informasi Geografis. PIKSEL: Penelitian
Ilmu Komputer Sistem Embedded and Logic , 6 (2), 105-114. Prasetyo,  A.  (2017). Optimasi  Jalur  Tercepat  Dengan Menggunakan  Modifikasi  Algoritma  Bellman Ford  (Studi  Kasus  Lintasan  Antar  Kecamatan Kota Malang) (Doctoral dissertation, Universitas Brawijaya).
Sulaiman,  O.  K.,  Siregar,  A.  M.,  Nasution,  K.,  & Haramaini,  T.  (2018).  Bellman  Ford  algorithm- In  Routing  Information  Protocol  (RIP).  In J. Phys. Conf. Ser (Vol. 1007, No. 1).