OPTIMASI RUTE ARMADA KEBERSIHAN KOTA GORONTALO MENGGUNAKAN ANT COLONY OPTIMIZATION Zulfikar Hasan, Novianita Achmad, Nurwan ABSTRAK Secara umum, penentuan rute terpendek dapat dibagi menjadi dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional lebih mudah dipahami daripada metode heuristik, tetapi jika dibandingkan, hasil yang diperoleh dari metode heuristik lebih variatif dan waktu perhitungan yang lebih singkat, salah satunya adalah Ant Colony Optimization. Penelitian ini bertujuan untuk Optimasi Rute Armada Kebersihan Kota Gorontalo Menggunakan Algoritma Ant Colony Optimization. Metode penelitian dilakukan dengan studi pustaka untuk menunjukkan penerapan dari Ant Colony Optimization dalam penentuan rute terpendek. Pembuatan program dengan MATLAB untuk memudahkan perhitungan secara numerik dan juga untuk memudahkan dalam penentuan rute terpendek masing-masing armada kebersihan. Penelitian dilakukan dengan menganalisis data hasil perhitungan program. Hasil penelitian adalah rute hasil perhitungan dengan menggunakan Ant Colony Optimization lebih optimal dari rute yang selama ini dilalui oleh armada kebersihan. Penghematan jarak yang didapatkan adalah 10.6%. Kata kunci : Optimasi, Heuristik, Ant Colony Optimization. PENDAHULUAN Salah satu bidang ilmu yang sering digunakan dalam pemecahan masalah adalah matematika. Dalam matematika terdapat kajian ilmu yang sangat erat dengan pemecahan masalah
yaitu
matematika
terapan.
Matematika
terapan
dapat
dimanfaatkan
dalam
menyelesaikan berbagai masalah, salah satunya masalah optimasi. Salah satu masalah optimasi adalah penentuan rute terpendek. Secara umum, penentuan rute terpendek dapat dibagi menjadi dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional lebih mudah dipahami daripada metode heuristik, tetapi jika dibandingkan, hasil yang diperoleh dari metode heuristik lebih variatif dan waktu perhitungan yang lebih singkat, salah satunya adalah Ant Colony Optimization (Mutakhirah, I., Indrato dan Hidayat, T., 2007). Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Berdasarkan prinsip algoritma yang diilhami dari perilaku koloni semut dalam menemukan jarak rute paling pendek, algoritma semut
sangat tepat diterapkan dalam penyelesaian optimasi, salah satunya adalah untuk menentukan rute terpendek pada armada kebersihan atau truk pengangkut sampah. Permasalahan pengelolaan sampah adalah permasalahan yang selalu dihadapi oleh kota berkembang. Kota Gorontalo merupakan salah satunya. Kota Gorontalo berupaya meningkatkan pelayanan publik di bidang pengelolaan sampah, khususnya pengangkutan sampah. Proses pengangkutan sampah dilakukan dengan cara pengambilan sampah pada pewadahan sampah (wadah komunal) yang tersebar di setiap jalan umum. Namun proses ini belum ditunjang dengan sistem pengangkutan sampah yang efektif dan efisien. Untuk itu diperlukan sistem pengangkutan sampah yang lebih teratur, sehingga dapat mengurangi pencemaran lingkungan yang disebabkan oleh penumpukan sampah tersebut. Proses pengangkutan sampah ini harus mempertimbangkan efisiensi waktu dan biaya sehingga diperlukan ketepatan dalam menentukan rute terpendek dalam proses ini. Berdasarkan uraian tersebut, penulis tertarik melakukan penelitian dengan judul “Optimasi Rute Armada Kebersihan Kota Gorontalo Menggunakan Algoritma Ant Colony Optimization”. Adapun yang menjadi tujuan dalam penelitian ini yaitu untuk Optimasi Rute Armada Kebersihan Kota Gorontalo Menggunakan Algoritma Ant Colony Optimization.
KAJIAN TEORI 1. Teori Graph Graph adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain melalui sisi/busur (edges) (Zakaria dalam Muttakhiroh, 2007). Suatu Graph G terdiri dari dua himpunan yaitu himpunan V dan himpunan E. a. Verteks (simpul) :V = himpunan simpul yang terbatas dan tidak kosong. b. Edge (sisi/busur):E = himpunan busur yang menghubungkan sepasang simpul. Simpul-simpul pada graph dapat merupakan obyek sembarang seperti kota, atom-atom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Busur dapat menunjukkan hubungan (relasi) sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. Notasi graph: G(V,E) artinya graph G memiliki V simpul dan E busur . 2. Macam-macam Graph Menurut arah dan bobotnya, graph dibagi menjadi empat bagian, yaitu:
a. Graph berarah dan berbobot : tiap busur mempunyai anak panah dan bobot. Gambar 2.1 menunjukkan graph berarah dan berbobot yang terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik menujukkan arah ke titik B dan titik C, titik B menunjukkan arah ke titik D dan titik C, dan seterusnya. Bobot antar titik A dan titik B pun telah diketahui. b. Graph tidak berarah dan berbobot : tiap busur tidak mempunyai anak panah tetapi mempunyai bobot. Gambar 2.2 menunjukkan graph tidak berarah dan berbobot. Graph terdiri dari tujuh titik yaitu titik A,B,C,D,E,F,G. Titik A tidak menunjukkan arah ke titik B atau C, namun bobot antara titik A dan titik B telah diketahui. Begitu juga dengan titik yang lain. c. Graph berarah dan tidak berbobot: tiap busur mempunyai anak panah yang tidak berbobot. Gambar 2.3 menunjukkan graph berarah dan tidak berbobot. d. Graph tidak berarah dan tidak berbobot: tiap busur tidak mempunyai anak panah dan tidak berbobot. 3. Graph Hamilton Graph hamilton diambil dari nama Sir William Rowan Hamilton. Suatu graph terhubung adalah graph hamilton memuat sirkuit yang melalui setiap vertex tepat satu kali disebut sirkuit hamilton. Lintasan hamilton adalah lintasan yang melalui tiap vertex di dalam graph tepat satu kali. Graph yang hanya memiliki lintasan hamilton disebut graph semi Hamilton. Teorema 3.1 Syarat cukup (jadi bukan syarat perlu) supaya graph sederhana G dengan n adalah graph hamilton ialah bila tiap vertex paling sedikit
(yaitu, d(v)
3 buah vertex
untuk setiap simpul
v di G). Teorema 3.2 Setiap graph lengkap adalah graph hamilton. Graph lengkap dengan n buah simpul dilabangkan dengan Kn. Jumlah sisi pada graph lengkap yang terdiri dari n buah simpul adalah
.
Teorema 3.3 Di dalam graph lengkap G dengan n buah vertex (n
3), terdapat
buah sirkuit hamilton.
Teorema 3.4 Di dalam graph lengkap G dengan n buah simpul (n
3 dan n ganjil), terdapat
hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n G terdapat
buah sirkuit hamilton yang saling lepas.
buah sirkuit 4, maka di dalam
Teorema 3.5 Misalkan G adalah graph terhubung sederhana dengan n titik, dengan n
3 dan deg v + deg w
n. Untuk tiap-tiap pasangan titik yang tidak berdekatan v dan w, maka G adalah graph Hamilton. Teorema 3.6 Misalkan G adalah graph sederhana dengan n vertex. Jika jumlah dari derajat masing-masing vertex di G paling sedikit n – 1, maka ada lintasan hamilton di G. 4. Optimisasi Optimasi ialah Suatu proses untuk mencapai hasil yang ideal atau optimal (nilai efektif uang dapat dicapai). Dalam disiplin matematika optimisasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi nyata. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara variabel integer atau nyata yang akan memberikan solusi optimal (Wardy, 2007). 5. Algoritma Pohon Rentang Minimal Sebuah graph yang setiap sisinya dikaitkan dengan suatu bilangan real disebut graph bobot. Bilangan yang dikaitkan ke suatu sisi G disebut bobot sisi tersebut. Bobot graph G, dilambangkan w(G), adalah jumlah bobot semua sisi G. diberikan graph bobot G terhubung. Sebuah pohon rentang di G dengan bobot minimum disebut Pohon Rentang Minimal (Budayasa, 2007). Algoritma Prim INPUT : Graph bobot G terhubung dengan n titik. STEP 1: Pilih sebuah titik v di G dan tulis T1 = v. STEP 2: Pilih sebuah sisi ek dengan bobot minimal yang menghubungkan sebuah titik Tk dengan sebuah titik G yang bukan di Tk. Jika terdapat lebih dari satu sisi yang demikian, pilih salah satu sebarang. Tulis Tk+1 = Tk
{ek}
STEP 3: Jika n-1 sisi telah terpilih (k = n-1), STOP dan beri pesan Tk+1 adalah pohon rentang minimal di G. Jika k < n-1, kembali ke STEP 2. 6. Ant Colony Optimization Pada tahun 1996, dunia AI (Artifiacial Intellegence) pun ikut belajar dari semut dengan diperkenalkannya algoritma semut, atau Ant Colony Optimization, sebagai sebuah simulasi multi
agen yang menggunakan metafora alami semut untuk menyelesaikan problem ruang fisik. Algoritma koloni semut diperkenalkan oleh Moyson dan Manderick kemudian secara meluas dikembangkan oleh Marco Dorigo, merupakan teknik probabilistik untuk menyelesaikan masalah komputasi dengan menemukan jalur terbaik melalui graphik. Algoritma ini terinspirasi oleh perilaku semut dalam menemukan jalur dari koloninya menuju makanan (Wardy, 2007). Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek (Mutakhiroh, I., Indrato, Hidayat, T., 2007), yaitu: Langkah 1: a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang diinisialisasikan adalah: 1. Intensitas jejak semut antar kota dan perubahannya (
)
2. Banyak kota (n) termasuk x dan y (koordinat) atau dij (jarak antar kota) 3. Penentuan kota berangkat dan kota tujuan 4. Tetapan siklus-semut (Q) 5. Tetapan pengendali intensitas jejak semut ( ) 6. Tetapan pengendali visibilitas ( ) 7. Visibilitas antar kota =
(
)
8. Jumlah semut (m) 9. Tetapan penguapan jejak semut ( ) 10. Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan akan selalu diperbaharui harganya pada setiap siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah siklus maksimum (NC=NCmax) atau sampai terjadi konvergensi b. Inisialisasi kota pertama setiap semut Setelah inisialisasi
dilakukan, kemudian m semut ditempatkan pada kota pertama yang
telah ditentukan. Langkah 2: Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama semut pada langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota pertama.
Langkah 3: Penyusunan jalur kunjungan setiap semut ke setiap kota. Koloni semut yang sudah terdistribusi ke kota pertama akan mulai melakukan perjalanan dari kota pertama sebagai kota asal dan salah satu kota-kota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masingmasing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabuk sebagai kota tujuan selanjutnya. Perjalanan koloni semut berlangsung terus menerus hingga mencapai kota yang telah ditentukan. Jika s menyatakan indeks urutan kunjungan, kota asal dinyatakan sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {Ntabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut, [ ∑[
] [
]
] [
]
untuk j {N-tabuk}j {N-tabuk} untuk j lainnya
dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan. Langkah 4: a. Perhitungan panjang jalur setiap semut. Perhitungan panjang jalur tertutup (length closed tour) atau Lk setiap semut dilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan dilakukan berdasarkan tabuk masingmasing dengan persamaan berikut: ∑ dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan: √ b. Pencarian rute terpendek Setelah Lk setiap semut dihitung, akan diperoleh harga minimal panjang jalur tertutup setiap siklus atau LminNC dan harga minimal panjang jalur tertutup secara keseluruhan adalah atau Lmin. c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota. Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat, menyebabkan kemungkinan
terjadinya perubahan harga intensitas jejak kaki semut antar kota. Persamaan perubahannya adalah: ∑ Dengan
adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang
dihitung berdasarkan persamaan untuk (i,j) kota asal dan kota tujuan dalam tabuk untuk (i,j) lainnya Langkah 5: a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan berubah karna adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung dengan persamaan:
b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota. untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur kembali agar memiliki nilai sama dengan nol. Langkah 6: Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan. Tabu list perlu dikosongkan untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus maksimum belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui. METODOLOGI PENELITIAN Kebutuhan Masukan Simulasi algoritma ini menggunakan program MATLAB R2012a. Untuk menjalankan simulasi diperlukan input atau masukan berupa parameter-parameter yang diperlukan dalam algoritma ACO, yaitu:
a. Peta dua dimensi yang dilengkapi dengan banyaknya titik kunjungan (n) termasuk koordinat (x,y). (n) dan (x,y) ditentukan oleh pengguna. b. Parameter-parameter yang diperlukan dalam perhitungan algoritma ACO, yaitu: 1. Jumlah Semut (m) = 200. Ditentukan berdasarkan atau disesuaikan dengan jumlah titik. Jumlah semut ini akan berpengaruh pada banyaknya variasi rute yang dihasilkan. 2. Jumlah Siklus Maksimum (NCmax) = 500. Digunakan untuk menghentikan program dan berpengaruh pada waktu komputasi, semakin besar jumlah siklus maksimumnya maka semakin besar waktu komputasinya. 3. Tetapan Siklus Semut (Q). Q merupakan konstanta yang digunakan untuk menentukan nilai selisih intensitas jejak kaki semut. 4. Tetapan Pengendali Intensitas Jejak Semut ( ) = 1. Digunakan untuk perhitungan probabilitas pemilihan rute yang akan dilalui semut. 5. Tetapan Pengendali Visibilitas (
) = 5. Kemampuan semut memberikan atau
memancarkan sinyal pada semut-semut selanjutnya. Digunakan dalam persamaan probabilitas pemilihan rute yang akan dilalui semut. 6. Tetapan Penguapan Jejak Semut ( ) = 1. Digunakan untuk menentukan jejak semut sebelumnya. 7. Intensitas Jejak Semut (
) dan perubahannya (
). Memberi informasi jumlah semut
yang memilih jejak yang sama. Flowchart Algoritma Ant Colony Optimization Dari algoritma yang telah ditentukan dapat dibuat flowchart yang ditunjukkan oleh gambar berikut
Desain Penelitian
Mulai Pengamatan Awal Merumuskan Masalah dan Tujuan
Studi Pustaka
Pengumpulan Data
Tidak
Data Lengkap?
Ya Penentuan Parameter Algoritma
Penyusunan Algoritma Program
Pembuatan Program
Mengolah dan Menganalisis Data Hasil Penelitian Simpulan
Selesai
HASIL PENELITIAN DAN PEMBAHASAN 4.1 Klasifikasi Rute Layanan Armada Berdasarkan data yang didapatkan dari Badan Lingkungan Hidup Kota Gorontalo dapat dihitung rute layanan armada kebersihan Badan Lingkungan Hidup adalah sebagai berikut: Tabel Jarak Tempuh Masing-masing Armada NO
Armada
Jarak (Km)
1
DM 8049 A
15.3
2
DM 8010 A
7.52
3
DM 8051 A
17.2
4
DM 8135 A
11.03
5
DM 8011 A
13.76
6
DM 8136 A
7.83
7
DM 8027 A
16.27
8
DM 8114 A
4.06
Total Jarak
92.97
Rute dan Jarak Tempuh Optimal Hasil Ant Colony Optimization Algoritma Ant Colony Optimization diimplementasikan dan diuji dengan dengan data masukan berupa parameter-parameter dan koordinat titik (x,y) yang ditentukan dengan bantuan software CorelDraw X6 menghasilkan rute dan jarak tempuh optimal sebagai berikut: a. Armada Kebersihan DM 8049 A
Berdasarkan gambar dengan skala 1 : 17.400 diatas dapat dilihat bahwa rute dan jarak optimal dari Armada Kebersihan DM 8049 A adalah: Jarak
Rute Layanan
Tempuh
1-2-3-4-5-6-7-8-9-33-10-11-14-12-13-29-17-18-19-28-16-15-30-32-31-27-26-
72.68
25-23-24-20-21-22-1
Perhitungan jarak sebenarnya: 72,68 cm x 17.400 cm = 1.264.632 cm = 12,64 km. Untuk armada kebersihan lainnya dihitung dengan cara yang sama, maka didapatkan hasil berikut: Tabel Total Jarak Tempuh Rute Hasil Perhitungan ACO NO
Armada
Jarak (Km)
1
DM 8049 A
12.64
2
DM 8010 A
5.63
3
DM 8051 A
14.04
4
DM 8135 A
10.01
5
DM 8011 A
10.72
6
DM 8136 A
14.24
7
DM 8027 A
12.2
8
DM 8114 A
3.6
Total Jarak
83.08
Tabel Perbandingan Jarak Tempuh NO
Armada
Jarak
Jarak Hasil
Sebelumnya
Perhitungan ACO
(Km)
(Km)
Selisih
1
DM 8049 A
15.3
12.64
2.66
2
DM 8010 A
7.52
5.63
1.89
3
DM 8051 A
17.2
14.04
3.16
4
DM 8135 A
11.03
10.01
1.02
5
DM 8011 A
13.76
10.72
3.04
6
DM 8136 A
16.27
14.24
2.03
7
DM 8027 A
14.34
12.2
2.14
8
DM 8114 A
4.06
3.6
0.46
Tabel di atas menunjukkan bahwa jarak tempuh rancangan rute dengan menggunakan Ant Colony Optimization merupakan rancangan rute yang optimal. Penghematan jarak = (Total jarak Awal – Total Jarak Hasil Pengolahan ACO) km Penghematan jarak = (92.97 – 83.08) km = 9,89 km Penghematan (%) =
10.6%.
PENUTUP Berdasarkan uraian pembahasan di atas, dapat disimpulkan bahwa: 1. Perancangan rute menggunakan Ant Colony Optimization berdasarkan letak titik yang sudah ditentukan lebih optimal daripada rute yang selama ini dilalui oleh armada kebersihan. 2. Penghematan jarak yang peroleh dari hasil pengolahan data menggunakan Ant Colony Optimization adalah 10.6% dari jarak tempuh rute yang digunakan saat ini. Saran: 1. Pada penelitian ini, program Ant Colony Optimization belum memperhatikan data masukan titik koordinat untuk persimpangan jalan atau pengaturan jalan yang harus dilalui. Oleh karena itu, penulis menyarankan kepada pembaca yang tertarik dengan masalah optimasi ini agar dapat menyertakan titik koordinat dari persimpangan jalan tersebut. 2. Pada kasus ini terjadi local optimum, oleh karena itu program Ant Colony Optimization yang digunakan perlu dimodifikasi. 3. Diharapkan pada penelitian selanjutnya dapat membandingkan antar metode heuristik yang lainnya. DAFTAR PUSTAKA Berlianty Intan, Miftahol Arifin. 2010. Teknik-Teknik Optimasi Heuristik. Graha Ilmu. Yogyakarta. Budayasa, Ketut. 2007. Teori Graph dan Aplikasinya. Surabaya: UNESA. Dorigo, M. dan Stutzle, T. 2004. Ant Colony Optimization.A Bradford book.The MIT Press Cambridge, Massachussetts London, England. Hoetomo, M. A. 2005. Kamus Lengkap Bahasa Indonesia. Mitra Pelajar. Surabaya.
Leksono, Agus. 2009. Algoritma Ant Colony Optimization (ACO) untuk Menyelesaikan Traveling Salesman Problem (TSP).Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Diponegoro Semarang. Skripsi Dipublikasikan (online). Mutakhiroh I., Indrato dan Hidayat T. 2007. Pencarian Jalur Terpendek Menggunakan Algoritma Semut. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 1907-5022. Yogyakarta. Mutakhiroh I., Saptono F., Hasanah N., dan Wiryadinata R. 2007. Pemanfaatan Metode Heuristik dalam Pencarian Jalur Terpendek dengan Algoritma Semut dan Algoritma Genetik. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 1907-5022. Yogyakarta. Pranata R. A., Prasetyaningrum I., Fariza A., dan Martiana E. 2011. Perancangan Sistem Optimasi Rute Distribusi Pengangkutan Sampah di Surabaya Secara Adaptif Menggunakan Metode Algoritma Koloni Semut. Jurusan Teknik Informatika, PENS-ITS. Surabaya. Suyanto. 2010. Algoritma Optimasi Deterministik atau Probabilitik. Graha Ilmu. Bandung. Wardy, I. S. 2007. Penggunaan Graph dalam Algoritma Semut untuk Melakukan Optimisasi. Program Studi Teknik Informatika, Institut Teknologi Bandung. Bandung.
