Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
PENCARIAN RUTE TERPENDEK OBJEK WISATA DI MAGELANG MENGGUNAKAN ANT COLONY OPTIMIZATION (ACO) Bagus Fatkhurrozi *, Ika Setyowati Jurusan Teknik Elektro, Fakultas Teknik, Universitas Tidar Jl. Kapten Suparman 39 Magelang, 56116. * Email:
[email protected] ABSTRAK Obyek wisata di wilayah Magelang sangat banyak. Wisatawan yang akan berwisata ke Magelang memiliki keterbatasan waktu untuk mengujungi semua tempat wisata sehingga harus memilih beberapa tempat wisata yang akan dikunjungi. Dari tempat-tempat wisata yang sudah dipilih, menimbulkan permasalahan yaitu bagaimana cara menentukan rute terpendek antar wisata. Penelitian ini dilakukan di wilayah Magelang dengan empat tempat awal tujuan dan sebelas tempat wisata tujuan. Penelitian ini bertujuan untuk menerapkan algoritmaAnt Colony Optimization(ACO) pada pencarian rute terpendek jalur objek wisata di Kota dan Kabupaten Magelang.ACO adalah algoritma yang diadopsi dari perilaku koloni semut. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Untuk menentukan rute terpendek dengan ACO, ada beberapa langkah. Pertama inisialisasi harga parameter-parameter algoritma. Kedua pengisian kota pertama ke dalam tabu list. Ketiga penyusunan jalur kunjungan setiap semut ke setiap kota. Keempat perhitungan panjang jalur setiap semut. Kelima perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Keenam pengosongan tabu list, dan ulangi langkah dua jika diperlukan. Hasil penelitian menunjukkan bahwa ACO dapat dipakai untuk mencari rute terpendek jalur wisata di Magelang. Kata kunci: rute terpendek, wisata, ACO. PENDAHULUAN Di wilayah Kota dan Kabupaten Magelang terdapat banyak objek wisata, untuk mengunjungi objek wisata tersebut tidak hanya cukup waktu satu hari. Wisatawan biasanya memliki keterbatasan waktu untuk memilih objek wisata mana saja yang akan dikunjungi. Pemilihan objek wisata tersebut juga harus memperhitungkan jarak terpendek yang harus ditempuh sehingga bisa memperkirakan berapa lama waktu yang dibutuhkan. Pencarian jalur terpendek untuk tempat wisata sudah pernah dilakukan, antara lain dengan pembangunan Sistem Informasi Geografis (SIG) pariwisata (Widianto, 2009). Berdasarkan hasil pengujian website SIG pariwisata Jakarta Utara dapat dinyatakan bahwa aplikasi jalur terpendek untuk pencarian rute pariwisata sudah berhasil dan berjalan dengan baik. Mutakhiroh dkk., (2007) telah menggunakan Ant Colony Optimization (ACO)/algoritma semut pada pencarian jalur terpendek. Penelitiannya menyatakan bahwa algoritma semut sangat tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan jalur terpendek. ACO adalah algoritma yang diadopsi dari perilaku koloni 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 pada lintasan yang telah dilewati. Semakin banyak semut yang melewati suatu lintasan, maka akan semakin jelas bekas jejak kakinya (Sari dan Maharani, 2014). Berkenaan dengan hal tersebut penelitian ini bertujuan untuk menerapkan algoritma ACO pada pencarian rute terpendek jalur objek wisata di Kota dan Kabupaten Magelang. Diharapkan nantinya bisa memperoleh informasi rute terpendek yang harus ditempuh wisatawan untuk menuju lokasi wisata.
205
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
METODE PENELITIAN Tahapan penelitian yang pertama kali dilakukan adalah pencarian literatur yang terkait dengan penelitian. Literatur didapatkan baik dari publikasi seminar, jurnal ilmiah maupun buku-buku penunjang lainnya. Tahap berikutnya adalah pengumpulan dan pengalahan data. Data merupakan data primer yang didapatkan dengan pengukuran langsung rute di objek wisata menggunakan Global Positioning System (GPS) yang terdapat di gadget. Tahap selanjutnya adalah pembuatan program dan kemudian setelah program jadi dilakukan pengujian. Apabila hasil pengujian sudah baik maka bisa dilakukan penarikan kesimpulan dan kemudian melakukan penyusunan laporan. Digram alir tahapan penelitian ditunjukkan pada Gambar 2.
Gambar 2. Tahapan Penelitian Penelitian ini menggunakan metode Ant Colony Optimization (ACO)/algoritma semut untuk mencari rute terpendek rute wisata di Magelang. ACO diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut. Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan (Dorigo, 1996). Koloni semut dapat menemukan jalur terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada lintasan yang telah dilewati. Semakin banyak semut yang melewati 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 akan tidak dilewati sama sekali. Sebaliknya lintasan yang dilalui semut dalam jumlah banyak semakin lama akan semakin bertambah kepadatan semut yang melewatinya atau bahkan semua semut melewati lintasan tersebut.
206
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
Gambar 1. Perjalanan semut menemukan sumber makanan. Gambar 1.a menujukkan perjalanan semut dalam menemukan jalur terpendek dari sarang ke sumber makanan, terdapat dua kelompok semut yang melakukan perjalanan. Kelompok semut L berangkat dari arah kiri ke kanan dan kelompok semut R berangkat dari kanan ke kiri. Kedua kelompok berangkat dari titik yang sama dan dalam posisi pengambilan keputusan jalan sebelah mana yang akan diambil. Kelompok L membagi dua kelompok lagi. Sebagian melewati jalan atas dan sebagian melewati jalan bawah. Hal ini juga berlaku pada kelompok R. Gambar 1.b dan Gambar 1.c menunjukkan bahwa kelompok semut berjalan pada kecepatan yang sama dengan meninggalkan feromon atau jejak kaki di jalan yang telah dilalui. Feromon yang ditinggalkan oleh kumpulan semut yang melewati jalan atas telah mengalami banyak penguapan karena semut yang melewati jalan atas berjumlah lebih sedikit dibandingkan jalan yang di bawah. Hal ini disebabkan jarak yang ditempuh lebih panjang dibandingkan jalan bawah. Gambar 1.d menunjukkan bahwa semut-semut yang lain pada akhirnya memutuskan untuk melewati jalan bawah karena feromonyang ditinggalkan masih banyak, sedangkan feromon pada jalan atas sudah banyak menguap sehingga semut-semut tidak memilih jalan atas. Semakin banyak semut yang melewati jalan maka semakin banyak semut yang mengikutinya, semakin sedikit semut yang melewati jalan, maka feromonyang ditinggalkan semakin berkurang bahkan hilang. Dari sinilah kemudian terpilihlah jalur terpendek antara sarang dan sumber makanan. Dalam algoritma semut, diperlukan beberapa variabel dan langkah-langkah untuk menentukan jalur terpendek, yaitu: Langkah 1: a. Inisialisasi harga parameter-parameter algoritma. Parameter-parameter yang di inisialisasikan adalah: 1) Intensitas jejak semut antar kota dan perubahannya (τij) 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 = 1/dij(ηij) 8) Jumlah semut (m) 9) Tetapan penguapan jejak semut (ρ) 10) Jumlah siklus maksimum (NCmax) bersifat tetap selama algoritma dijalankan, sedangkan τij 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 τij dilakukan, kemudian m semut ditempatkan pada kota pertama yang telah ditentukan.
207
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
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 kotakota lainnya sebagai kota tujuan. Kemudian dari kota kedua, masing-masing koloni semut akan melanjutkan perjalanan dengan memilih salah satu dari kota-kota yang tidak terdapat pada tabu k 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 {N-tabuk}, maka untuk menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai berikut,
dan
=
.
∑ ′∈
∈
.
−
(1)
= 0
(2)
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 tabu k masing-masing dengan persamaan berikut: = ∑
(3)
dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan persamaan: =
−
+
b. Pencarian rute terpendek.
−
(4)
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. 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: ∆
= ∑
∆
(5)
dengan ∆ adalah perubahan harga intensitas jejak kaki semut antar kota setiap semut yang dihitung berdasarkan persamaan: ∆
=
(6)
208
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
untuk (i,j) ∈kota asal dan kota tujuan dalam tabuk = 0, 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 karena 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: =
.
+ ∆
(7)
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 dua 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 dua dengan harga parameter intensitas jejak kaki semut antar kota yang sudah diperbaharui.
HASIL DAN PEMBAHASAN Untuk mendapatkan jalur terpendek pada penelitian ini, program ACO dibuat dengan bantuan perangkat lunak Matlab 7.8.0. Setelah program jadi, untuk mendapatkan hasil terbaik dilakukan beberapa tahap yang dilalui, yaitu: 1) Masukkan titik awal dan titik tujuan yang berupa tempat wisata. 2) Inisialisasi Parameter berupa α, β, ρ, q0, dan m, dimana nilai parameter ini telah ditentukan dan merupakan nilai terbaik. Parameter yang digunakan mengacu pada penelitian Triandi (2012). Parameter–parameter yang digunakan adalah: α = 1.00 β = 1.00 ρ = 0.50 τij (awal) = 0.01 Maksimum siklus (NCmax) = 2 Tetapan siklus semut (Q) = 1 Banyak semut (m) = 5 Proses menghitung dengan menggunakan ACO. Untuk memulai perhitungan terdapat 2 siklus, untuk siklus pertama maka proses pencarian dengan jumlah semut 2 lalu dimulai dengan menghitung nilai probabilitas. Pengujian dilakukan dengan memilih salah satu titik awal dan tiga/empat titik tujuan. Hasil pengujian sebagai berikut.
209
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
Pengujian dari titik awal Secang
Tabel 1. Jarak Antar Tempat Wisata Secang
Candi Borobudur
Secang Candi Borobudur Curug Kedung Kayang Ketep Pass
Curug Kedung Kayang
Ketep Pass
0
27,8
32
28,4
27,8
0
29,4
26,8
32
29,4
0
3,6
28,4
26,8
3,6
0
Dari hasil pengukuran didapatkan jarak tempuh dari tempat awal dan tujuan, serta jarak antar tempat wisata. Misalnya dari Secang ke Candi Borobudur 27,8 km. Kemudian dari Candi Borobudur ke Curug Kedung Kayang 29,4 km dan dari Kedung Kayang ke Ketep Pass 3,6 km. Kemudian jarak tersebut dimasukkan ke sistem. Setelah dilakukan pengujian sebanyak 2 siklus didapatkan hasil sebagai berikut.
Tabel 2. Rute Terpendek Semut
Rute
1
Secang
Borobudur
Ketep
Kedungkayang
2
Secang
Borobudur
Ketep
Kedungkayang
3
Secang
Ketep
Kedungkayang
Borobudur
4
Secang
Borobudur
Ketep
Kedungkayang
5
Secang
Borobudur
Ketep
Kedungkayang
Dari hasil pengujian siklus kedua, sebagian besar semut telah menemukan rute terpendek jalur wisata di Magelang. Titik awal berangkat adalah dari Secang, kemudian tempat wisata yang terdekat adalah Candi Borobudur. Setelah dari Borobudur, rute selanjutnya menuju Ketep Pass dan kemudian menuju Curung Kedung Kayang. Dari 5 semut hanya satu semut, yaitu semut ke-3 yang tujuannya ke Ketep Pass dulu, terus ke Curug Kedung baru selanjutnya ke Candi Borobudur. Pengujian dari Titik Awal Ngablak
Tabel 3. Jarak Antar Tempat Wisata Ngablak
Candi Mendut
Mesastilla
Kyai Langgeng
Ngablak
0
40,7
16
19,5
Candi Mendut
41
0
40,3
16,3
16
40,3
0
26,2
19,5
16,3
26,2
0
Mesastilla Kyai Langgeng
Dari hasil pengukuran didapatkan jarak tempuh dari tempat awal dan tujuan, serta jarak antar tempat wisata. Titik awal adalah Ngablakdan jaraknya ke Candi Mendut 40,7 km. Kemudian dari Candi Mendut ke Mesastilla 40,3 km dan dari Mesastilla ke Kyai Langgeng 26,2 km. Kemudian jarak tersebut dimasukkan ke sistem. Setelah dilakukan pengujian sebanyak 2 siklus didapatkan hasil sebagai berikut.
Tabel 4. Rute Terpendek Semut
Rute 1
Ngablak
Mesastilla
Langgeng
Mendut
2
Ngablak
Mesastilla
Langgeng
Mendut
3
Ngablak
Mesastilla
Langgeng
Mendut
4
Ngablak
Mesastilla
Langgeng
Mendut
5
Ngablak
Mesastilla
Langgeng
Mendut
210
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
Berdasarkan pengujian siklus kedua, semua semut telah menemukan rute terpendek wisata Magelang. Dari titik awal Ngablak tujuan pertama adalah Mesastilla, kemudian ke Taman Kyai Langgeng, dan terakhir ke Candi Mendut. Pengujian dari Titik Awal Salam
Tabel 5. Jarak Antar Tempat Wisata Salam
Candi Ngawen
Candi Gunung Wukir
Candi Selogriyo
Candi Gunungsari
0
6,8
1,8
39,2
4,9
6,8
0
8,3
33
3,5
Salam Candi Ngawen Candi Gunung Wukir
1,8
8,3
0
39,4
6,4
Candi Selogriyo
38,1
31,4
37
0
32,4
Candi Gunungsari
4,9
3,5
6,4
32,4
0
Pada pengujian ini, dilakukan pengukuran dari titik awal Salam dengan semua tujuan adalah wisata Candi. Dari Salam ke Candi Ngawen 6,8 km, dari candi Ngawen ke Candi Gunung Wukir 8,3 km, dari Candi Gunung Wukir ke Candi Selogriyo 39,4 km, dan dari Candi Selogriyo ke Candi Gunungsari 32,4 km. Setelah pengujian sebanyak 2 siklus, didapatkan rute sebagai berikut:
Tabel 6. Semut
Rute Terpendek Siklus Rute
1
Salam
Gunung Wukir
Gunungsari
Ngawen
Selogriyo
2
Salam
Gunung Wukir
Gunungsari
Ngawen
Selogriyo
3
Salam
Gunung Wukir
Gunungsari
Ngawen
Selogriyo
4
Salam
Gunung Wukir
Gunungsari
Ngawen
Selogriyo
5
Salam
Gunung Wukir
Gunungsari
Ngawen
Selogriyo
Dari hasil pengujian juga didapatkan semua semut telah menemukan rute terpendek tempat wisata Magelang. Dari titik awal adalah Salam tujuan pertama yaitu Candi Gunung Wukir, terus ke Candi Gunungsari, setelah itu ke Candi Ngawen, dan terakhir ke Candi Selogriyo. Pengujian dari Titik Awal Salaman
Tabel 7. Salaman Salaman
C. Borobudur
Ketep Pass
10,8
36,7
10,8
0
36,7
26,8
Kyai Langgeng
16,1
Telaga Bleder
39
C. Borobudur Ketep Pass
0
Jarak Antar Tempat Wisata Kyai Langgeng
Telaga Bleder
16,1
39
26,8
18
40,1
0
27,2
22,2
18
27,2
0
23,8
40,1
22,2
23,8
0
Hasil pengukuran menunjukkan bahwa dari jarak dari titik awal Salaman menuju candi Borobudur adalah 10,8 km. Dari Candi Borobudur ke Ketep Pass 26,8 km, dari Ketep Pass ke Taman Kyai Langgeng 27,2 km, dan dari Kyai Langgeng ke Telaga Bleder 23,8 km. Setelah 2 siklus, didapatkan rute sebagai berikut:
211
Prosiding SENATEK 2015 Fakultas Teknik, Universitas Muhammadiyah Purwokerto Purwokerto, 28 November 2015, ISBN 978-602-14355-0 -2
Tabel 8.
Rute Terpendek Siklus
Semut
Rute
1
Salaman
Borobudur
Langgeng
Bleder
Ketep
2
Salaman
Borobudur
Ketep
Salaman
Bleder
Ketep
4
Salaman
Langgeng Borobudur
Langgeng Borobudur
Bleder
3
Langgeng
Bleder
Ketep
5
Salaman
Borobudur
Langgeng
Bleder
Ketep
Dari hasil pengujian didapatkan hasil bahwa sebagain besar semut telah menemukan rute terpendek tempat wisata. Hanya pada semut ke-4 yang berbeda, yaitu dari titik awal Salaman tujuan pertama adalah Taman Kyai Langgeng, terus ke Candi Borobudur kemudian Telaga Bleder dan terakhir ke Ketep Pass. Sedangkan 4 semut lainnya sama rutenya, dari titik awal Salaman menuju Candi Borobudur, kemudian ke Taman Kyai Langgeng, terus ke Telaga Bleder dan terakhir ke Ketep Pass.
KESIMPULAN ACO dapat digunakan pada pencarian jarak terpendek. Pada penelitian ini, ACO digunakan untuk mencari rute terpendek jalur wisata di Magelang. Hasil pengujian menunjukkan bahwa ACO dapat digunakan untuk mencari rute terpendek wisata Magelang. Dengan hasil ini diharapkan orang yang akan berwisata ke Magelang bisa mempersiapkan tempat yang dituju dengan baik. Penelitian selanjutnya diharapkan bisa mencari waktu tempuh yang optimal. Kendala-kendala di rute wisata juga hendaknya diperhatikan.
DAFTAR PUSTAKA Dorigo, M., (1996), The Ant System: Optimization by a colony of cooperating agents, IEEE transactions on Systems, Man, and Cybernetics–Part B, Vol.26, No.1. Mutakhiroh, I., Indrato., Hidayat, T., (2007), Semut, Yogyakarta, SNATI 2007.
Pencarian Jalur Terpendek Menggunakan Algoritma
Sari, D.N., dan Maharani, S., (2014), Algoritma Semut Untuk Optimasi Penentuan Jalur Terpendek Fasilitas Umum (Studi kasus : Kota Samarinda), Scan Vol. IX Nomor 1 Februari 2014. Triandi, B., (2012), Penemuan Jalur Terpendek Dengan Algoritma Ant Colony, CSRID Journal, Vol.4 No.2 Juni 2012, Hal. 73 – 80 Widianto, S.R., (2009), Aplikasi Jalur Terpendek Dalam Pencarian Rute Situs Pariwisata, http://www.gunadarma.ac.id, diakses tanggal 13 Juli 2014, jam 14.30.
212
