## Penerapan algoritma koloni semut untuk optimisasi rute distribusi pengangkutan sampah di kota Yogyakarta
(The application of ant colony algorithm to optimize the distribution route of waste collection in Yogyakarta)
Himmawati Puji Lestari 1 dan Eminugroho Ratna Sari 2
1,2 Jurusan Pendidikan Matematika FMIPA UNY, Kampus Karangmalang, Sleman, DI Yogyakarta 55281 / 1 email: himmawatipl@yahoo.com dan 2 email: eminugroho@uny.ac.id

## Abstrak
Sistem pengangkutan sampah di Kota Yogyakarta dilakukan dari Kelurahan/Kecamatan (KK) ke Tempat Pembuangan Sementara (TPS), selanjutnya dari TPS ke Tempat Pembuangan Akhir (TPA). TPS sendiri  terbagi  atas  tiga  jenis:  depo, container ,  dan  landasan  (bangunan  permanen).  Di  lain  pihak, pengambilan  sampah  oleh  kendaraan  truk  pengangkut  sampah  seringkali  tidak  teratur  mengakibatkan volume  sampah  di  Kota  Yogyakarta  yang  cukup  besar  tidak  dapat  didistribusikan  dengan  baik  ke  TPA Piyungan. Sehubungan dengan masalah tersebut sistem optimasi rute distribusi ini dirancang agar sistem distribusi  pengangkutan  sampah  di  Kota  Yogyakarta  dapat  berfungsi  secara  optimal.  Dalam  hal  ini digunakan  Algoritma  Koloni  Semut  untuk  menyelesaikan  masalah.  Pada  penelitian  ini,  TPS  yang  akan dibahas  berupa  bangunan  permanen.  Selanjutnya  penyelesaian  algoritma  koloni  semut  dibantu  dengan software Macro Excel. Diperoleh 12 rute pengangkutan sampah setiap hari di Kota Yogyakarta.
Kata kunci: sampah, TPS, algoritma koloni semut.

## Abstract
Waste  collection  transportation  system  in  Yogyakarta  is  begun  from  District  to  Temporary Shelters  (TPS),  then  from  TPS  to  End  Shelter/landfill  (TPA).  TPS  is  divided  into  three  types:  depot, container,  and  permanent  buildings.  On the  other  hand,  collecting  waste  in  each  TPS is  often irregular. This causes the garbage cannot be distributed properly to landfill in Piyungan. Based on the problem, an optimization  system  of  distribution  route  is  designed  so  that  the  distribution  of  waste  collection transportation  system  in  Yogyakarta  becomes  optimal.  In  this  case,  the  ant  colony  algorithm  is  used  to solve the problem. In this research, the type of TPS discussed is a permanent building. Furthermore, the optimal solution of distribution problem using ant colony algorithm is calculated via software Macro Excel. The result is 12 daily routes of waste collection in Yogyakarta.
Key words: waste, TPS, ant colony algorithm

## Pendahuluan
Sampah  merupakan  hal  yang  telah menjadi  bagian  dari  kehidupan  sehari-hari.
Berdasarkan Peraturan Daerah Kota Yogyakarta No 18 tentang Pengelolaan Kebersihan, walikota Yogyakarta telah mewajibkan pada instansi yang bertanggung jawab  terhadap  pengawasan  pengelolaan sampah. Kegiatan monitoring ini  pun mempunyai  banyak  kendala.  Salah  satunya adalah kurangnya prasarana truk
pengangkut  sampah  yang  mengakibatkan sampah menumpuk di Tempat Pembuangan Sementara (TPS) tertentu.
Sistem Pengangkutan sampah di Kota Yogyakarta  dibagi  menjadi  dua,  dilakukan dari Kelurahan/Kecamatan (KK) ke TPS dan dari  TPS  diangkut  ke  Tempat  Pembuangan Akhir (TPA). TPS sendiri dibagi menjadi tiga jenis:  depo, container , dan  bangungan permanen.  Depo  artinya  tempat  dimana gerobak-gerobak pengangkut sampah berkumpul  menunggu  untuk  diambil  truk, sehingga  sekali  truk  datang  ke  depo,  maka muatan truk sudah penuh. Container artinya bak terbuka yang merupakan  bagian belakang  dari  truk  yang  ditinggalkan  di tempat-tempat  tertentu,  sehingga  setiap pengambilan  sampah  di  tempat  tersebut, container langsung dipasang kembali ke truk kemudian  dibawa  ke  TPA.  Sedangkan  TPS yang merupakan bangunan permanen, rata- rata  memiliki  kapasitas  2  m 3 ,  sehingga  truk yang  bisa  memuat  8-12  m 3 sampah  dapat mengambil  sampah  dari  beberapa  TPS tersebut.  Untuk  itu,  pada  penelitian  ini, hanya  akan  dibahas  TPS  yang  berupa bangunan permanen.
Salah  satu  TPA  terbesar  di  Provinsi DIY  adalah  TPA  Piyungan.  TPA  ini  mampu menampung  sampah-sampah  kiriman  dari Kota  Yogyakarta,  Kabupaten  Bantul  dan Kabupaten  Sleman.  Sebanyak  180-200  ton sampah  per  hari  dibuang  ke  TPA  ini  dan 70%  diantaranya  merupakan  sampah  dari Kota  Yogyakarta  [1].  Di  lain  pihak,  Kota Yogyakarta yang memiliki lebih dari 100 TPS tidak  sebanding  dengan  jumlah  truk  yang hanya  28  truk.  Truk-truk  inilah  yang digunakan  untuk  mengangkut  sampah  dari TPS  ke  TPA  Piyungan.  Keadaan  ini  harus dicermati dengan seksama karena jika tidak, maka  sampah  tersebut  dapat  menumpuk dan bertambah banyak di suatu TPS tertentu dan  akan  dapat  mengganggu  masyarakat sekitar,  mulai  dari  bau  yang  tidak  sedap, lingkungan  menjadi  kotor  bahkan  dapat menjadi sumber penyakit.
Jumlah  rute  pengangkutan  sampah dari  TPS  ke  TPA  bergantung  pada  faktor- faktor  kapasitas  TPS,  jarak  antar  TPS  dan dari  TPS  ke  TPA,  dan  rute  pengangkutan. Pada  penelitian  ini  akan  dibahas  rute  yang tergantung  dari  kapasitas  TPS  dan  jarak antar  TPS.  Dari  data-data  yang  telah
dikumpulkan  maka  dapat  dianalisa  dan dilakukan  pemilihan  rute-rute  pengangkutan alternatif  yang  dapat  lebih  mengoptimalkan sistem  pengangkutan  sampah  di  Kota Yogyakarta.
Algoritma  Koloni  Semut  ( Ant  Colony
Optimization )
digunakan untuk menyelesaikan permasalahan  ini.  Pencarian solusi  dimulai  dengan  melakukan  pemilihan secara  bertahap  berdasarkan  nilai  fungsi pheromone trail dan informasi heuristik yang terbesar. Pheromone  trail menunjukkan kualitas solusi yang telah dicapai oleh semut dari  perjalanan  sebelumnya,  sedangkan informasi heuristik sesuai dengan input data dari  suatu  permasalahan.  Kegiatan  ini dilakukan  oleh  semua  semut  dalam  satu koloni. Setelah satu koloni semut menyusun kombinasi  solusi,  maka  dilakukan  pemilihan semut  terbaik  yang  akan  dibandingkan dengan semut terbaik secara global sehingga menghasilkan solusi akhir [2].
Pada  awalnya  penerapan  algoritma koloni semut untuk pencarian solusi travelling  salesman  problem [3].  Seiring dengan  perkembangan  penelitian,  algoritma ini  digunakan  untuk  solusi vehicle  routing problem [4].  Bahkan  sangat  variatif,  antara lain  digunakan  untuk  mensimulasikan  rute- rute  jalan  protokol  [5].  Bahkan  juga  telah diaplikasikan  untuk  sistem  pencarian  cepat [6].  Selain  itu,  algoritma  koloni  semut digunakan  untuk  optimisasi  perencanaan produksi  [7-10].  Berdasarkan  penelitian- penelitian  sebelumnya,  Algoritma  Koloni Semut  digunakan  untuk  menyelesaikan masalah  system  distribusi  sampah  dengan memilih rute-rute yang tepat dan cepat untuk sampai ke TPA Piyungan dengan memperhatikan  kapasitas  masing-masing TPS.  Pada  penelitian  ini,  TPS  yang dimaksud yang berupa bangunan permanen.

## Metode Penelitian

## Perilaku Semut
Secara  alamiah  koloni  semut  mampu menemukan rute terpendek dalam perjalanan  dari  sarang  ke  tempat-tempat sumber  makanan.  Koloni  semut  dapat menemukan  rute  terpendek  antara  sarang dan sumber makanan berdasarkan jejak kaki
yang mengandung pheromone pada lintasan yang  telah  dilalui.  Semakin  banyak  semut yang  melalui  suatu  lintasan,  maka  semakin jelas bekas jejak kakinya. Hal ini menyebabkan  lintasan  yang  dilalui  semut dalam jumlah sedikit, semakin lama semakin berkurang kepadatan
semut yang melewatinya,  atau  bahkan  tidak  dilewati sama sekali. Sebaliknya lintasan yang dilalui semut  dalam  jumlah  banyak,  semakin  lama semakin  bertambah  kepadatan  semut  yang melewatinya,  atau  bahkan  semua  semut melalui  lintasan  tersebut  [2].  Ilustrasi  rute yang  dibentuk  oleh  semut  dan  koloninya dapat dilihat pada Gambar berikut [11].
Gambar 1 . Ilustrasi rute yang dibentuk semut dan koloninya.

## Algoritma Koloni Semut
Parameter-parameter  yang  digunakan dalam Algoritma Koloni Semut antara lain:
1.  Intensitas      jejak      semut  ( ij  )      dan
perubahannya ( ij   ). ij  harus
diinisialisasi sebelum memulai siklus.
ij  digunakan  dalam  persamaan probabilitas node yang akan
dikunjungi. ij   diinisialisasi  setelah
selesai  satu  siklus. ij   digunakan untuk  menentukan ij  untuk  siklus selanjutnya.
2.  Tetapan  siklus  semut  (Q),  Q
merupakan konstanta yang digunakan  dalam  persamaan  untuk menentukan ij   .  Nilai  Q  ditentukan oleh pengguna.
3.  Tetapan  pengendali  intensitas  jejak semut  (α),  α  digunakan  dalam
persamaan  probabilitas  node  yang akan dikunjungi yang berfungsi sebagai  pengendali  intensitas  jejak semut.  Nilai  α  ditentukan  oleh pengguna.
4. Tetapan pengendali visibilitas (β)
β  digunakan  dalam  persamaan probabilitas node yang akan dikunjungi  yang  berfungsi  sebagai pengendali v isibilitas. Nilai β ditentukan oleh pengguna.
5. Visibilitas antar kota ( ij  )
ij  digunakan  dalam  persamaan
probabilitas node yang akan dikunjungi.  Nilai ij  merupakan  hasil
dari 1 ij d , .
6. Banyak semut (m) m  merupakan  banyak  semut  yang akan melakukan siklus dalam algoritma  semut.  Nilai  m  ditentukan oleh  pengguna.  Disini  banyak  semut diibaratkan  sama  dengan  banyak kota yang dilalui.
7. Tetapan penguapan jeja k semut (ρ) ρ  digunakan  untuk  menentukan  τij untuk  siklus  selanjutnya.  Nilai  ρ ditentukan oleh pengguna.
Adapun langkah-langkah penyelesaian menggunakan algoritma koloni semut adalah
1.  Dari sarang, semut berkeliling secara acak  mencari  makanan  kemudian dicatat  jarak  antar node yang  semut lalui.
2.  Ketika  sampai  ke  makanan,  total jarak  dari  tiap node yang  telah ditempuh  oleh  semut,  dijumlahkan untuk mendapatkan jarak dari sarang ke makanan.
3.  Ketika  kembali  ke  sarang,  sejumlah pheromone ditambahkan  pada  jalur yang  telah  ditempuh  berdasarkan total  jarak  jalur  tersebut.  Semakin kecil  total  jarak,  maka  semakin banyak kadar pheromone yang ditambahkan  pada  masing-masing busur pada jalur tersebut.
4.  Untuk  memilih  busur  mana  yang harus  dilalui  berikutnya,  dihitung menggunakan rumus
    k i ij ij k ij il il l p                    N untuk k i j  N
dengan 1 ij ij d   ij d 5.  Pada iterasi selanjutnya, busur-busur yang  mengandung pheromone lebih tinggi akan dipilih sebagai busur yang harus ditempuh berikutnya berdasarkan probabilitas yang ada di langkah  ke-4.  Akhirnya  diperoleh jalur optimal, yaitu jalur yang dibentuk  oleh  busur-busur  dengan kadar pheromone tinggi.

## Hasil dan Diskusi
Penerapan  Algoritma  Koloni  Semut  untuk Pengambilan Sampah di Kota Yogyakarta
Selanjutnya,  algoritma  koloni  semut akan diimplementasikan untuk rute distribusi sampah.  Adapun  TPS  yang  dimaksud adalah  yang  berupa  bangunan  permanen. Berikut daftar TPS yang akan dibahas:

## Tabel 1. Lokasi TPS
No Lokasi TPS
1 TPS di Jln.Hos Cokroaminoto
2 TPS di Pasar Serangan (Jalan RE Martadinata)
3 TPS di Asrama Brimob (Jalan Imogiri Timur
4 TPS di Pabrik kulit (Jln Ki Mangunsarkoro)
5 TPS di Gunung Ketur (Kantor Pengadilan, PDK)
6 TPS di Jalan Cantel
7 TPS di Jalan Cantel Baru
8 TPS di Jalan Gajah
9 TPS di Jalan Argolobang, Baciro
10 TPS di Jalan Hayam Wuruk
11 TPS di Jalan Melati Wetan
12 TPS di Jalan Bausasran, Danurejan
13 TPS di Jalan Gajah Mada
14 TPS di Jalan Beji
15 TPS di LP Wirogunan, Jalan Tamsis
16 TPS di STIE YO, Jalan Glagah Sari (Universitas Teknologi Yogyakarta FE)
17 TPS di Wisma Sargede
18 TPS di BKKBN, muja muju
19 TPS di Kricak
20 TPS di Poltabes Malioboro
21 TPS di Jalan Prawirotaman
22 TPS di Tamansari
23 TPS di Jalan C. Simanjuntak
24 TPS di Jalan AM Sangaji
25 TPS di Jalan FM Noto
26 TPS di Jalan Nyoman Oka
27 TPS di Jalan Abu Bakar Ali
28 TPS di Jalan Krasak
29 TPS di Jalan Sabirin
30 TPS di Jalan Prof dr.Ir.Yohanes
31 TPS di Jalan Sagan
32 TPS di Jalan Terban
33 TPS di Jalan Suroto
34 TPS di Jalan Atmosukarto
35 TPS di Jalan Wardani
36 TPS di Jalan dr Wahidin (UKDW)
37 TPS di Jalan Yos Sudarso
38 TPS di Jalan Tribrata
39 TPS di Jalan Kalisahak
40 TPS di Jamsostek (Jl.Urip Sumoharjo)
41 TPS di Superindo (Jalan Solo)
Menggunakan algoritma koloni semut, sesuai dengan langkah-langkah
penyelesaiannya,  perlu  dilakukan  inisialisasi parameter terlebih dahulu. Parameter- parameter yang digunakan adalah:
1.  Intensitas  jejak  kaki  semut, ij 
sebesar 0,01
2.  Tetapan siklus semut, Q = 20
3.  Tetapan  pengendali  intensitas jejak semut, α = 1
4. Tetapan  pengendali  visibilitas,  β
= 1
5.  Banyak  semut,  dalam  hal  ini sebanyak TPS yang akan dibahas, dinotasikan dengan m =
41
6.  Tetapan  penguapan  jejak  semut,
ρ = 0,5
Setelah dilakukan inisialisasi, langkah- langkah selanjutnya adalah sebagai berikut:
1.  Dilakukan pengacakan jalur.
Dalam  hal  ini,  masing-masing  semut ditempatkan  di  masing-masing  TPS,
kemudian masing-masing semut tersebut  akan  memilih  jalur  mereka masing-masing. Pada langkah pengacakan  ini,  digunakan software bantu  Macro  Excel  dengan  perintah Rnd.
2.  Menghitung total jarak dari jalur yang telah diperoleh dari Langkah 1.
Berikut  total  jarak  dari  masing-masing  jalur yang dimulai dari masing-masing TPS.
Tabel  2 .  Total  jarak  yang  diperoleh berdasarkan rute acak.
Dimulai dari Total jarak (km) TPS 1 114.15 TPS 2 114.25 TPS 3 111.15 TPS 4 116.55 TPS 5 111.62 TPS 6 119.6 TPS 7 125.25 TPS 8 119.12 TPS 9 120.2 TPS 10 126.47 TPS 11 112.55 TPS 12 116.65 TPS 13 114.55 TPS 14 120.78 TPS 15 126.11 TPS 16 114.07 TPS 17 113.85 TPS 18 110.2 TPS 19 118.08 TPS 20 114.6 TPS 21 119.3 TPS 22 126.77 TPS 23 117.97 TPS 24 121.8 TPS 25 113.65 TPS 26 113.35 TPS 27 114.95
TPS 28 115.72 TPS 29 114.98 TPS 30 119 TPS 31 133.65 TPS 32 124.62 TPS 33 119.5 TPS 34 102.7 TPS 35 120.25 TPS 36 118.42 TPS 37 120.25 TPS 38 113.85 TPS 39 126.12 TPS 40 119.55 TPS 41 120.8 3.  Dilakukan  pembaharuan pheromone setelah diketahui perubahan intensitas pheromone. Jika
perubahan intensitas pheromone dari node i ke  node j adalah ij x , maka pembaharuan pheromone dari node i ke node j dilakukan dengan
  ij Q x    .
4.  Menghitung  visibilitas  antar  TPS.
Visibilitas merupakan invers jarak.
5.  Menghitung probabilitas TPS berikutnya yang akan dilalui,
menggunakan rumus
    k i ij ij k ij il il l p                    N untuk k i j  N
dengan
1 ij ij d   ij d
6.  Berdasarkan  langkah  5,  diperoleh rute  terbaik  yaitu  yang  dimulai  dari TPS  8,  dengan  total  jarak  61,52  km. Selanjutnya diketahui bahwa masing- masing  truk  dapat  memuat  12  m 3 sampah  sekali  angkut  dan  volume sampah  per  hari  adalah  sebagai berikut
Tabel  3 .  Data  volume  sampah  di  masing- masing TPS per hari.
TPS Volume sampah per hari (m 3 ) 1 2 2 3 3 2.1
4 4 5 3.2
6 2.6
7 2.5 8 3.1
9 3.5 10 4.2 11 3.2 12 2.6 13 2.5 14 3.1 15 2 16 3 17 2.1 18 4 19 3.1 20 3.5 21 4.2 22 2.4 23 3.6 24 3 25 2 26 3 27 2.1 28 4 29 3.2 30 2.6 31 2.5 32 3.1 33 3.5 34 4.2 35 3.6 36 3 37 2 38 3 39 2.8 40 2.6 41 3.9
Akibatnya,  diperoleh  rute  pengangkutan dengan  memperhatikan  volume  sampah masing-masing TPS per hari adalah sebagai berikut:
Tabel  4 .  Rute  dan  volume  sampah  yang dapat terangkut per hari.
jalur 1 8-16-18-6 volume 10.1 m 3 jalur 2 7-4-14 volume 9.6 m 3 jalur 3 13-15-20-26 volume 11 m 3 jalur 4 33-29-25-27 volume 10.8 m 3 jalur 5 12-10-11 volume 10 m 3 jalur 6 39-41-31-30 volume 11.8 m 3 jalur 7 36-37-28 volume 9 m 3 jalur 8 34-40-38 volume 9.8 m 3 jalur 9 9-35-22 volume 9.5 m 3 jalur 10 21-3-17-2 volume 11.4 m 3 jalur 11 24-23-32 volume 9.7 m 3 jalur 12 19-1-5 volume 8.3 m 3

## Kesimpulan
Menggunakan  algoritma  koloni semut, pengambilan sampah oleh Badan Lingkungan  Hidup  Kota  Yogyakarta menjadi  lebih  efektif.  Pengambilan  yang biasanya dilakukan seminggu dua sampai  tiga  kali  untuk  masing-masing TPS,  dapat  dilakukan  setiap  hari.  Selain lebih  efektif  dilihat  dari  jarak  yang ditempuh,  hal  ini  akan  berakibat  efektif dari  segi  biaya.  Oleh  karena  sampah juga  terambil  setiap  hari,  maka  keluhan masyarakat akan menumpuknya sampah dapat diminimalisir.

## Ucapan Terima Kasih
Penulis  mengucapkan  terima  kasih kepada  pemberi  dana  sehingga  penelitian dapat  dilakukan  secara  maksimal,  kepada Badan  Lingkungan  Hidup  Kota  Yogyakarta atas  data-data  yang  diperlukan  untuk penelitian.

## Daftar Pustaka
[1].  Agus  Sigit  Cahyana.  2012.  BLH  Kota Yogyakarta.  Kedaulatan  Rakyat online
diakses melalui http://krjogja.com/read/117785/blh-kota- yogya-tambah-tiga-truk-pengangkut- sampah.kr  tanggal 12 April 2012 .
[2].  Dorigo,  Marco  and  Stützle,  Thomas. 2004. Ant Colony Optimization . London: MIT Press.
[3]. Dorigo M., Gambardella L. M. (1997) Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE
Transactions on Evolutionary Computation 1(1): 52 –56 [4]. Donati A. V., Montemanni R., Casagrande N., Rizzoll A. E., Gambardella L. M. (2008) Time
dependent  vehicle  routing  problem  with a  multi  ant  colony  system.  European Journal of Operational Research 185(3): 1174 –1191
[5].  Tarek  Helmi  Abd  El-Nabi  Ali  Ahmed. 2005. Modeling  And  Simulation  Of  A
Routing Protocol For Ad Hoc Networks Combining  Queuing  Network  Analysis And Ant Colony Algorithms.
Dissertation.  Institut  für  Informatik  und Wirtschaftsinformatik  der  Universität Duisburg-Essen (Campus Essen).
[6].  Yoshikawa,  Masaya  &  Otani,  Kazuo.
2010. Ant Colony Optimization Routing Algorithm with Tabu Search. Proceedings of the International MultiConference  of  Engineers  and Computer Scientists. Vol III. Hongkong. [7].  Liu,Xiao-jun;  Yi,Hong;  Ni,  Zhong-hua. 2013. Application of Ant Colony Optimization Algorithm in Process Planning Optimization. Journal of Intelligent  Manufacturing. Vol  24(1)  pp
1-13.
[8]. Huang K. L., Liao C. J. 2008. Ant colony optimization combined with taboo search  for  the  job  shop  scheduling problem. Computers & Operations Research 35(4): 1030 –1046 [9].  Liao  C.  J.,  Liao  C.  C.  (2008)  An  ant colony optimisation algorithm for scheduling in agile manufacturing. International Journal  of Production
Research 46(7): 1813 –1824 [10].  Prakash  A.,  Tiwari  M.  K.,  Shankar  R. (2008) Optimal job sequence determination  and  operation  machine allocation  in  flexible  manufacturing systems:  An  approach  using  adaptive hierarchical ant colony algorithm.
Journal  of  Intelligent  Manufacturing 19(2): 161 –173 [11]. Raditya Arizal Pranata, Ira Prasetyaningrum  S.Si,MT,  dkk.  2011. Perancangan  Sistem  Optimasi  Rute Distribusi  Pengangkutan  Sampah  di Surabaya Secara Adaptif Menggunakan Metode Algoritma Koloni Semut. ITS Surabaya.