Pencarian Rute Terpendek pada Tempat Wisata di Kota Bogor Menggunakan Metode Heuristik Irwansyah Saputra Jurusan Ilmu Komputer, STMIK Nusa Mandiri Jakarta
[email protected]
Abstrak: Pencarian rute terpendek saat berwisata sangat berguna untuk meringkas perjalanan dan menghemat biaya, sehingga waktu liburan dapat digunakan lebih optimal. Pencarian rute terpendek dapat dilakukan menggunakan metode heuristik. Heuristik seringkali disebut sebagai lawan dari kata algoritmik dalam dunia pemrograman. Heuristik adalah suatu proses yang mungkin dapat menyelesaikan suatu masalah tetapi tidak ada jaminan bahwa solusi yang dicari selalu dapat ditemukan. Dengan kata lain, heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness). Salah satu metode heuristic adalah Hill Climbing. Metode ini dapat mengubah alur lintasan menjadi graf yang memiliki titik sebagai pengganti kota dan sisi untuk jarak antar kota agar lebih mudah dihitung. Keunggulan metode Hill Climbing yaitu semua solusi yang mungkin akan diperoleh kemudian diperiksa dari sisi kiri satu persatu, sehingga akan diperoleh solusi dengan hasil yang optimal. Kata Kunci: Heuristik, Hill Climbing, Wisata Kota Bogor
1. Pendahuluan 1.1. Latar Belakang Bogor merupakan kota yang sering dijadikan tujuan oleh beberapa kota di sekitarnya seperti Jakarta, depok, tangerang dan bekasi. Menurut data Dinas Kebudayaan dan Pariwisata kota Bogor yang dilansir oleh BPS, rata-rata orang yang berwisata di kota Bogor sekitar 2 juta wisatawan antara tahun 2008 hingga 2014. Bahkan kota Bogor selalu dikunjungi warga Belanda yang tinggal di Batavia sebelum kemerdekaan karena cuaca yang sejuk dan nyaman. Selain
memiliki cuaca yang sejuk, Bogor juga memiliki beberapa tempat wisata yang dapat dikunjungi antara lain Istana Bogor, Kebun Raya Bogor, Prasasti Batu Tulis dan Setu Gede. Saat melakukan perjalanan ke tempat wisata sering kali seseorang membawa peta sebagai petunjuk jalan. Penggunaan peta dalam bentuk ini secara visual mampu menggambarkan rute yang akan ditempuh dari kota asal ke tempat wisata. Pemakain peta kertas mempunyai kendala secara visual harus dapat mengurutkan rute mana yang akan di tempuh, selain itu penggunaan peta jenis ini tidak memungkinkan untuk dapat memberikan suatu saran rute mana yang paling efektif dan efisien. Sehingga, jarak tempuh antar tempat wisata tidak menentu
1
yang mengakibatkan kunjungan ke tempat wisata menjadi tidak optimal. Algoritma pencarian (searching algorithm) memiliki cara kerja yang berbeda karena didasarkan pada relevansi masalah dari kasus terkait. Salah satu metode algoritma pencarian adalah Hill Climbing. Metode ini merupakan proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Permasalahan yang muncul dari latar belakang di atas adalah saat melakukan suatu perjalanan hendaknya dapat menemukan suatu rute yang paling efektif dan efisien sehingga dapat menekan biaya selama dalam perjalanan dan kunjungan ke tempat wisata menjadi lebih optimal.
Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Metode ini merupakan proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin. Sehingga, dengan metode ini eksplorasi terhadap keputusan dilakukan dengan cara pencarian mendalam dengan mencari jalur yang bertujuan menurunkan biaya untuk menuju kepada tujuan/keputusan, yaitu dengan selalu memilih nilai heuristik terkecil.
1.2. Tujuan
2.1. Metode
Penelitian ini bertujuan untuk menemukan rute yang efektif dan efisien dengan penerapan algortima pencarian Hill Climbing.
Berikut adalah algoritma dari Simple Hill Climbing:
1.3. Tinjauan Pustaka 1.3.1. Metode Hill Climbing Metode Hill Climbing hampir sama dengan metode pembangkitan & pengujian (Generate and Test), hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan.
1.3.2. Rute Terpendek Menurut Pawitri (2007), Lintasan terpendek merupakan lintasan minumum yang diperlukan untuk mencapai suatu titik dari titik tertentu. 2. Bagian Inti
1. Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal. 2. Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang: a) Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru. b) Evaluasi keadaan baru tersebut.
2
1) Jika keadaan baru merupakan tujuan, keluar. 2) Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. 3) Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi. 3. Pada simple Hill Climbing ini, ada 3 masalah yang mungkin, yaitu: 4. Algoritma akan berhenti kalau mencapai nilai optimum lokal. 5. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. 6. Tidak diijinkan untuk melihat satupun langkah sebelumnya.
* Tukar 1, 2 (menukar urutan posisi kota ke-1 dengan kota ke-2). * Tukar 2, 3 (menukar urutan posisi kota ke-2 dengan kota ke-3). * Tukar 3, 4 (menukar urutan posisi kota ke-3 dengan kota ke-4). * Tukar 4, 1 (menukar urutan posisi kota ke-4 dengan kota ke-1). * Tukar 2, 4 (menukar urutan posisi kota ke-2 dengan kota ke-4). * Tukar 1, 3 (menukar urutan posisi kota ke-1 dengan kota ke-3). Gambar 3. Proses Perhitungan Hill Climbing
1.3.3. Studi Kasus Pencarian rute dilakukan pada proses berikut ini, Gambar 2. Pola Rute Wisata Kota Bogor
Keterangan: A : ISTANA BOGOR
C : SETU GEDE
B : PRASASTI BATU TULIS
D : KEBUN RAYA BOGOR
Operator yang akan kita gunakan adalah menukar urutan posisi 2 kota dalam suatu lintasan. Ada 4 kota dalam kasus ini, sehingga dapat diperoleh: kombinasi. Keenam kombinasi ini akan dipakai sebagai operator, yaitu:
Pada Gambar 3 terlihat bahwa keadaan awal lintasan terpilih adalah ABCD (29). Pada level pertama, Hill Climbing akan mengunjungi ABDC (17,7) yang ternyata memiliki nilai heuristik lebih kecil dibandingkan dengan ABCD (17,7 < 29), sehingga ABDC menjadi pilihan selanjutnya dengan operator terpakai Tukar 2,3. Kemudian Hill Climbing akan mengunjungi BADC (14,35). Karena nilai heuristik BADC lebih kecil jika dibanding dengan ABDC (14,35 < 17,7), pencarian rute dilanjutkan ke layer berikutnya. Ada dua node yang memiliki nilai sama yaitu node BDAC (13,75) dan node CADB (13,75). Kedua node inilah yang memiliki nilai terkecil. Karena node di layer selanjutnya memiliki nilai yang lebih besar dari keduanya. Sehingga node ini yang dipilih dan menjadi solusi. 3. Penutup 3.1. Kesimpulan
3
1. Hasil yang didapatkan menggunakan metode Hill Climbing pada permasalahan di atas adalah sebesar 13,75 KM dengan rute B – D - A - C (Prasasti Batu Tulis – Kebun Raya Bogor – Istana Bogor – Setu Gede) dan C – A – D - B (Setu Gede – Istana Bogor – Kebun Raya Bogor – Prasasti Batu Tulis). 2. Metode Hill Climbing memiliki optimasi yang sangat baik untuk melakukan pencarian rute terpendek pada kasus wisata di Kota Bogor.
4
4. Daftar Pustaka Evan, 2008, Penggunaan Depth First Search Dalam Pengambilan Kepu-tusan Pada Klimaks Permainan Scrabble, Makalah If2251 Strategi Algoritmik Tahun 2008 Lanny W, 2007 Pandjaitan, Dasar-dasar komputasi cerdas, Andi Offset, Yogyakarta. Pawitr, Yanti, K. A. & Purwadi, J. 2007. Implementasi Algoritma PHYSICAL-A* (PHA*) untuk menemukan Lintasan Terpendek, http://journal.amikom.ac.id/ index.php/SN/article/view/2075 (5 Juli 2017). Riki Aditia, Fachrul Prasodjo, Irwansyah Ritonga, 2008, Pencarian Jalur Dengan Breadth First Search Dan Depth First Search, MAKALAH IF2251 STRATEGI ALGORITMIK TAHUN 2008
5
