J. Sains Dasar 2013 2(1)
13 – 19
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 Lestari1 dan Eminugroho Ratna Sari2 1,2
Jurusan Pendidikan Matematika FMIPA UNY, Kampus Karangmalang, Sleman, DI Yogyakarta 55281 / 1email:
[email protected] dan 2email:
[email protected]
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
Himmawati dkk. / J. Sains Dasar 2013 2(1)
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, ratarata memiliki kapasitas 2 m3, sehingga truk yang bisa memuat 8-12 m3 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 faktorfaktor 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
13 – 19
14
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 ruterute 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 penelitianpenelitian 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
Himmawati dkk. / J. Sains Dasar 2013 2(1)
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].
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 2.
selanjutnya. 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
15
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 visibilitas. Nilai β ditentukan oleh pengguna. 5. Visibilitas antar kota ( ij )
ij
digunakan
dalam
persamaan
probabilitas node yang akan dikunjungi. Nilai ij merupakan hasil dari
Gambar 1. Ilustrasi rute yang dibentuk semut dan koloninya.
13 – 19
1 ,. dij
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 jejak 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
Himmawati dkk. / J. Sains Dasar 2013 2(1)
p k ij
ij ij
il il
lN ik
untuk j N
k i
dengan
1 ij dij
d ij
TPS di STIE YO, Jalan Glagah Sari (Universitas Teknologi Yogyakarta FE)
17
TPS di Wisma Sargede
18
TPS di Kricak
20
TPS di Poltabes Malioboro
21 23 24 25
No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
TPS di Tamansari TPS di Jalan C. Simanjuntak TPS di Jalan AM Sangaji TPS di Jalan FM Noto TPS di Jalan Nyoman Oka
27
TPS di Jalan Abu Bakar Ali
28 29
32 33 34 35 36 37 38 39 40
Tabel 1. Lokasi TPS
TPS di Jalan Prawirotaman
26
31
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:
TPS di BKKBN, muja muju
19
30
Hasil dan Diskusi
16
16
22
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.
13 – 19
41
TPS di Jalan Krasak TPS di Jalan Sabirin TPS di Jalan Prof dr.Ir.Yohanes TPS di Jalan Sagan TPS di Jalan Terban TPS di Jalan Suroto TPS di Jalan Atmosukarto TPS di Jalan Wardani TPS di Jalan dr Wahidin (UKDW) TPS di Jalan Yos Sudarso TPS di Jalan Tribrata TPS di Jalan Kalisahak TPS di Jamsostek (Jl.Urip Sumoharjo) TPS di Superindo (Jalan Solo)
Lokasi TPS TPS di Jln.Hos Cokroaminoto TPS di Pasar Serangan (Jalan RE Martadinata) TPS di Asrama Brimob (Jalan Imogiri Timur TPS di Pabrik kulit (Jln Ki Mangunsarkoro) TPS di Gunung Ketur (Kantor Pengadilan, PDK) TPS di Jalan Cantel TPS di Jalan Cantel Baru TPS di Jalan Gajah TPS di Jalan Argolobang, Baciro TPS di Jalan Hayam Wuruk TPS di Jalan Melati Wetan TPS di Jalan Bausasran, Danurejan TPS di Jalan Gajah Mada TPS di Jalan Beji TPS di LP Wirogunan, Jalan Tamsis
Menggunakan algoritma koloni semut, sesuai dengan langkah-langkah penyelesaiannya, perlu dilakukan inisialisasi parameter terlebih dahulu. Parameterparameter 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
13 – 19
Himmawati dkk. / J. Sains Dasar 2013 2(1)
Setelah dilakukan inisialisasi, langkahlangkah 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
17
TPS 28 TPS 29 TPS 30 TPS 31 TPS 32 TPS 33 TPS 34 TPS 35 TPS 36 TPS 37 TPS 38 TPS 39 TPS 40 TPS 41
115.72 114.98 119 133.65 124.62 119.5 102.7 120.25 118.42 120.25 113.85 126.12 119.55 120.8
3. Dilakukan pembaharuan pheromone setelah diketahui perubahan intensitas pheromone. Jika perubahan intensitas pheromone dari node i ke node j adalah xij , maka pembaharuan pheromone dari node i ke node j dilakukan dengan Q xij . 4. Menghitung visibilitas antar TPS. Visibilitas merupakan invers jarak. 5. Menghitung probabilitas TPS berikutnya yang akan dilalui, menggunakan rumus
p k ij
ij ij
il il
lN ik
untuk j N ik
dengan
ij
1 dij
d ij
6. Berdasarkan langkah 5, diperoleh rute terbaik yaitu yang dimulai dari TPS 8, dengan total jarak 61,52 km. Selanjutnya diketahui bahwa masingmasing truk dapat memuat 12 m3 sampah sekali angkut dan volume sampah per hari adalah sebagai berikut
Himmawati dkk. / J. Sains Dasar 2013 2(1)
Tabel 3. Data volume sampah di masingmasing TPS per hari. TPS
3
Volume sampah per hari (m )
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
13 – 19
18
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 volume
8-16-18-6 10.1 m3
jalur 2 volume
7-4-14
jalur 3 volume
13-15-20-26 11 m3
jalur 4 volume
33-29-25-27 10.8 m3
jalur 5 volume
12-10-11 10 m3
jalur 6 volume
39-41-31-30 11.8 m3
jalur 7 volume
36-37-28 9 m3
jalur 8 volume
34-40-38 9.8 m3
jalur 9 volume
9-35-22 9.5 m3
jalur 10 volume
21-3-17-2 11.4 m3
jalur 11 volume
24-23-32 9.7 m3
jalur 12 volume
19-1-5
9.6 m3
8.3 m3
Himmawati dkk. / J. Sains Dasar 2013 2(1)
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-kotayogya-tambah-tiga-truk-pengangkutsampah.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. Casagrande Gambardella
V., Montemanni R., N., Rizzoll A. E., L. M. (2008) Time
13 – 19
19
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.
