J-ICON, Vol. 2 No. 1, Maret 2014, pp. 1~9
1
PENERAPAN ALGORITMA DIJKSTRA PADA PERMASALAHAN LINTASAN TERPENDEK OBJEK WISATA ALAM KOTA KUPANG BERBASIS WEB Ahmad Rizal 1, Sebastianus A. S. Mola 2, Tiwuk Widiastuti 3 1,2,3
Jurusan Ilmu Komputer, Fakultas Sains dan Teknik, Universitas Nusa Cendana
ABSTRAK Pesona wisata alam Kota Kupang tidak kalah dibandingkan dengan wisata alam yang berada di kotakota besar di Indonesia yang banyak dikunjungi oleh wisatawan asing maupun lokal. Kota Kupang memiliki lima belas titik lokasi wisata alam. Letak objek wisata alam Kota Kupang memiliki akses jalan yang baik sehingga wisatawan dapat menggunakan kendaran pribadi maupun biro perjalanan yang telah disediakan hotel-hotel. Dalam perjalanan wisata seringkali wisatawan mengalami masalah dalam menentukan rute mana yang harus dilalui agar tidak membutuhkan banyak waktu dan biaya perjalanan. Algoritma Dijkstra adalah algoritma pencarian pada graph untuk mencari rute dari satu titik asal ke sebuah titik akhir yang telah ditentukan agar mendapatkan bobot jarak yang minimum. Hasil akhir dari penelitian ini adalah sebuah sistem pencarian rute terpendek objek wisata alam Kota Kupang dari asal ke tujuan dengan bobot jarak yang minimum sehingga memudahkan wisatawan dalam menentukan rute mana yang harus dilalui dan informasi lokasi wisata. Pengujian secara manual dengan sistem mendapatkan hasil yang sama. Kata kunci : Graph, Rute terpendek, Dijkstra, Objek wisata alam
ABSTRACT Charm of Kupang nature not less than the natural attractions in big cities in Indonesia, which is often visited by foreign and local tourists. Kupang has fifteen points of natural tourist sites. The location of the natural attractions of Kupang has good road access so that tourists can use private vehicles or a travel agency that has supplied by hotels. In a tour travelers often encounter problems in determining which route to go through so they don’t use a lot of time and expenses. Dijkstra Algorithm is a search algorithm on the graph to find a route from one start point of to the end point in order to get the minimum distance. The result of this research is a system of searching the shortest route of Kupang natural attractions from the origin to the destination with the minimum distance so that make it easier for travelers to determine which route must be passed and tourist sites information. Manually testing the system gets the same results. Keywords : Graph, Shortest Route, Dijkstra's, Natural attractions
I.
PENDAHULUAN
Kota Kupang merupakan salah satu daerah otonom yang memiliki pesona alam maupun pesona budaya. Objek wisata yang paling disukai wisatawan adalah objek wisata alam dari suatu daerah. Masing-masing daerah memiliki keunikan wisata alam yang berbeda sehingga membuat wisatawan ingin berkunjung dan menikmati keunikan serta atraksi yang dipertunjukan. Pesona objek wisata alam Kota Kupang tidak kalah dibandingkan dengan objek wisata alam yang berada di kotakota besar di Indonesia yang banyak di kunjungi oleh wisatawan asing maupun lokal, Kota Kupang memiliki 15 titik lokasi objek wisata alam yaitu Pantai Nunsui, Panatai Kelapa Lima, Gua Jepang, Kolam Airnona, Mata Air Oelon, Gua Monyet Alak, Taman Nostalgia, Pantai Flobamor, Pantai Paradiso, Gua Monyet Alak, Pantai Ketapang Satu, Pantai Koepang, Pantai Nunhila, Mata Air Bakunase dan Pantai Lasiana yang menjadi unggulan wisata alam Kota Kupang, tidak hanya memilki pantai berpasir putih saja namun Pantai Lasiana juga memiliki keunikan atraksi pembuatan gula nira sebagai oleh-oleh khas Kota Kupang. Potensi ini merupakan aset yang sangat bernilai bagi suatu daerah.
ISSN 2337-7631
2
ISSN 2337-7631
Letak objek wisata di Kota Kupang memiliki akses jalan yang baik sehingga memudahkan wisatawan dalam menempuh perjalanan menggunakan kendaraan pribadi maupun kendaraan umum dan jasa dari biro perjalanan wisata yang telah disediakan oleh hotel-hotel yang berada di Kota Kupang. Namun demikian, permasalahan yang sering dialami wisatawan dalam memulai perjalanan adalah menentukan rute mana yang harus dilalui agar tidak membutuhkan banyak waktu dan biaya perjalanan dari asal ke tujuan. II. MATERI DAN METODE 2.1
Definisi Graph Secara matematis Graph G didefinisikan sebagai pasangan himpunan (V,E), ditulis dengan notasi G(V,E), dimana V adalah sekumpulan dari titik (verteks/node) dan E adalah sekumpulan garis (rusuk/edge) yang menghubungkan titik yang satu ke titik yang lain. Titik-titik pada graph dapat merupakan obyek sembarang seperti kota, atom-atom suatu zat, nama anak, jenis buah, komponen alat elektronik dan sebagainya. Edge dapat menunjukkan hubungan sembarang seperti rute penerbangan, jalan raya, sambungan telepon, ikatan kimia, dan lain-lain. Jika terdapat sebuah rusuk e yang menghubungkan titik A dan B, ditulis edge (A,B). Gambar 1 merupakan contoh dari suatu graph G [2]. B e1 e2
e3
A e4
C
Gambar 1. Contoh Graph G
Pada gambar 2.4 graph terdiri dari himpunan V dan E yaitu: V = {A, B, C} E = {e1, e2, e3, e4} = {(A,B),(B,C),(B,C),(A,C)} 2.2
Terminologi Dasar Graph Dalam Teori graph terdapat beberapa terminologi (istilah) yang berkaitan dengan graph antara lain: a.
b.
c.
Bertetangga (Adjacent) Dua buah simpul pada graph tak-berarah G dikatakan bertetangga bila keduanya terhubung langsung oleh sebuah sisi. Dengan kata lain, vj bertetangga dengan vk jika (vj,vk) adalah sebuah sisi pada graph G. Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graph G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,..., vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graph G. Istilah lain untuk lintasan adalah jalur. Graph Berbobot (Weighted graph) Graph berbobot adalah graph yang setiap sisinya diberi sebuah harga (bobot). Bobot pada tiap sisi dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain (dalam jaringan komputer), ongkos produksi dan sebagainya. Contoh Graph berbobot dapat dilihat pada gambar 2. a
10 e
15 d
8
12 b
9 11 14
c
Gambar 2. Graph Berbobot
J-ICON, Vol. 2 No. 1, Maret 2014 : 1~9
J-ICON
ISSN 2337-7631
3
2.3
Repersentasi Graph Graph akan diproses dengan program komputer, maka graph harus direpresentasikan di dalam memori. Terdapat tiga macam representasi yang sering digunakan [2]. a. Matriks Ketetanggaan (Adjacency matrix) Matriks ketetanggaan adalah reprsentasi graph yang paling umum. Misalkan G = (V,E) adalah graph dengan n simpul, n ≥ 1 matriks ketetanggaan yaitu matriks dwintara yang berukuran n x n bila matriks tersebut dinamakan A= [aij], maka aij = 1 jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks bertetangga hanya berisi 0 dan 1, maka matriks tersebut juga dinamakan matriks nol-satu (zero-one). Selain dengan angka 0 dan 1, elemen matriks dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true (menyatakan 1). .
2.4
Aplikasi Graph Terdapat banyak aplikasi yang berkaitan dengan graph, dimana graph digunakan sebagai alat untuk merepresentasikan atau memodelkan persoalan. Ada beberapa aplikasi yang berkaitan dengan lintasan/sirkuit di dalam graph, diantaranya adalah menentukan lintasan terpendek (shortest path), persoalan pedagang keliling (Traveling Salesman Problem) dan pewarnaan graph (graph [2] coloring) . 2.5
Optimasi Optimisasi adalah suatu proses untuk mencapai hasil yang ideal atau optimal (nilai efektif yang dapat dicapai). Dalam matematika, optimisasi merujuk pada studi permasalahan yang mencoba untuk mencari nilai minimal atau maksimal dari suatu fungsi riil. Untuk dapat mencapai nilai optimal baik minimal atau maksimal tersebut, secara sistematis dilakukan pemilihan nilai variabel integer atau riil yang akan memberikan solusi optimal. Tujuan dari permasalahan lintasan terpendek adalah mencari lintasan terpendek dan biaya termurah dari sebuah perjalanan [3]. 2.5.1 Penyelesaian Masalah Optimasi Secara umum penyelesaian masalah pencarian jalur terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik. Metode konvensional dihitung dengan perhitungan matematika biasa, sedangkan metode heuristik dihitung dengan menggunakan sistem pendekatan. a.
b.
Metode Konvensional Metode konvensional adalah metode yang menggunakan perhitungan matematis biasa, ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya algoritma Dijkstra, algoritma floyd-warshall, dan algoritma bellmanford. Metode Heuristik Metode heuristik adalah suatu metode yang menggunakan sistem pendekatan dalam melakukan pencarian dalam optimasi. Ada beberapa Algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma genetika, ant colony optimization, logika fuzzy, jaringan syaraf tiruan, tabu search, simulated annealing dan lainlain[1]
2.6
Lintasan Terpendek Persoalan mencari lintasan terpendek di dalam graph merupakan salah satu persoalan optimasi. Graph yang digunakan dalam pencarian lintasan terpendek adalah graph berbobot (weighted graph), yaitu graph yang setiap sisinya diberikan nilai atau bobot. Bobot pada sisi graph dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya. Asumsi yang kita gunakan disini adalah bahwa semua bobot bernilai positif . Kata “terpendek” tidak selalu diartikan secara fisik sebagai panjang minimum, sebab kata “terpendek” berbeda maknanya bergantung tipikal persoalan yang akan diselesaikan. Namun, secara umum “terpendek” berarti meminimalisasikan bobot. Ada beberapa macam persoalan lintasan terpendek, antara lain:
Penerapan Algoritma Dijkstra Pada Permasalahan Lintasan Terpendek Objek Wisata Alam Kota Kupang Berbasis Web (Ahmad Rizal)
4
a. b. c. d.
ISSN 2337-7631
Lintasan terpendek antara dua buah pasangan simpul tertentu. Lintasan terpendek antara semua pasangan simpul. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
Pada dasarnya, jenis persoalan a mirip dengan jenis persoalan c dapat dihentikan bila simpil tujuan yang dikehendaki sudah ditemukan lintasan terpendeknya. Deskripsi persoalan lintasan terpendek pada jenis persoalan c adalah sebagai berikut: Diberikan bobot G=(V,E) dan sebuah simpul awal a. tentukan lintasan terpendek dari a ke setiap simpul lainnya di dalam G. Sebagai ilustrai, tinjau graph jaringan jalan pada gambar 3. 45 1
50
2
10
5
40 20
15
10
3
15
20
4
35 30
3
6
Gambar 3. Contoh Graph Jaringan Jalan
Lintasan terpendek dari simpul satu ke semua simpul lain diberikan pada tabel 1 di bawah ini (diurut dari lintasan terpendek pertama, kedua, ketiga dan seterusnya). Tabel 1. Hasil Lintasan Terpendek Simpul Simpul Lintasan asal tujuan terpendek 1 3 1,3 1 4 1,3,4 1 2 1,3,4,5 1 5 1,5 1 6 Tidak ada
jarak 10 25 45 45 -
2.7
Algoritma Dijkstra Sudah banyak algoritma mencari lintasan terpendek yang pernah ditulis orang. Algoritma lintasan terpendek yang paling terkenal adalah algoritma Djikstra (sesuai dengan nama penemunya, Edsger W. Dijkstra). Dalam naskah aslinya algoritma Dijkstra diterapkan untuk mencari lintasan terpendek pada graph berarah. Namun algoritma ini juga benar untuk graph tak-berarah. Algoritma Dijkstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip Greedy. Prinsip Greedy pada alagoritma Dijkstra menyatakan bahwa setiap langkah kita memiliki sisi yang berboot minimum dan memasukkannya kedalam himpunan solusi[2]. Properti algoritma Dijkstra: 1. Matriks ketetanggaan M[mij] mij = bobot sisi (i, j) (pada graph tak-berarah mij = mji ) mii = 0 mij = , jika tidak ada sisi dari simpul i ke simpul j 2. Larik S = [si] yang dalam hal ini, si = 1, jika simpul i termasuk ke dalam lintasan terpendek si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek 3. Larik/tabel D = [di] yang dalam hal ini, di = panjang lintasan dari simpul awal s ke simpul i 2.7.1 Contoh Cara Kerja Algoritma Dijkstra Jaringan Jalan Tinjau kembali graph jaringan jalan pada gambar 3 dengan matriks ketetanggaan m dapat dilihat pada tabel 2 .
J-ICON, Vol. 2 No. 1, Maret 2014 : 1~9
J-ICON
ISSN 2337-7631
5
Tabel 2. Matriks Ketanggaan m
Perhitungan lintasan terpendek dari simpul awal a = 1 ke semua simpul lainnya dapat dilihat pada tabel 3. Tabel 3. Hasil Algoritma Dijkstra Dari Simpul 1 Ke Semua Simpul
(Keterangan: Angka-angka dalam kurung menyatakan lintasan terpendek dari 1 ke simpul tersebut)
Jadi, lintasan terpendek dari: 1 ke 3 adalah 1, 3 dengan panjang = 10 1 ke 4 adalah 1, 3, 4 dengan jarak = 25 1 ke 2 adalah 1, 3, 4, 2 dengan jarak = 45 1 ke 5 adalah 1, 5 dengan jarak = 45 1 ke 6 tidak ada 2.7.2 Flowchart Algoritma Dijkstra Proses algoritma Dijkstra merupakan proses pencarian lokasi wisata alam asal tujuan yang telah ditentukan wisatawan untuk menghasilkan rute terpendek dengan bobot jarak yang minimum. Flowchart proses cari dapat dilihat pada gambar 4. Mulai
Penetapan Matriks Ketetanggaan
Pilih Titik Asal dan Titik Tujuan
Titik Asal = Titik Tujuan?
Ya
Tidak Pembaruan Bobot Jarak Ketetanggaan yang Terhubung Dengan Titik Terpilih Pilih Titik Tetangga dengan Bobot terkecil sebagai titik Terpilih
Tidak
Titik Tetangga yang terhubung dengan Titik terpilih = Titik Tujuan?
Ya Tampilkan Titik-Titik Terpilih
Selesai
Gambar 4. Flowchart Proses Algoritma Dijkstra
Penerapan Algoritma Dijkstra Pada Permasalahan Lintasan Terpendek Objek Wisata Alam Kota Kupang Berbasis Web (Ahmad Rizal)
6
ISSN 2337-7631
III. 3.1
HASIL DAN PEMBAHASAN
Hasil
Hasil dari penelitian ini adalah terciptanya sistem pencarian rute terpendek dari lokasi asal ke lokasi tujuan objek wisata alam di Kota Kupang menggunakan algoritma Dijkstra berbasis web. Kegunaan dari sistem ini adalah untuk mendapatkan rute terpendek lokasi wisata alam yang ingin dikunjungi wisatawan dengan total jarak minimum sehingga mendapatkan biaya perjalanan yang minimum, informasi lokasi wisata alam dan perkiraan biaya perjalanan.Untuk dapat menggunakan sistem silahkan mengunjungi situs www.wisataku.hol.es. 3.2
Pembahasan Sistem secara umum dirancang untuk mencari rute perjalanan dengan total jarak yang terpendek menggunakan perhitungan algoritma Dijkstra, perkiraan waktu perjalanan, perkiraan biaya perjalanan dan informasi objek wisata alam Kota Kupang. 3.2.1 Pembahasan Halaman Hasil Pencarian Pada sistem, halaman hasil pencarian menampilkan visual rute asal dan tujuan lokasi wisata alam yang telah dipilih oleh wisatawan dan hasil perkiraan biaya perjalanan wisatawan. Pembahasan halam hasil pencarian dapat dilihat pada gambar 5.
Gambar 5. Halaman Hasil Pencarian
Pada gambar 5 dapat dijelaskan bahwa rute terpendek dari Pantai Lasiana ke Permandian Airnona dengan total jarak 11.35 Km dengan biaya perjalanan Rp7.378.-. 3.3
Pengujian Terdapat 15 titik objek wisata alam yang berada di Kota Kupang. Dari data titik lokasi dan peta jalan Kota Kupang penulis membuat pemodelan graph untuk digunakan dalam perhitungan algoritma Dijkstra agar mendapatkan rute terpendek dari titik asal ke titik tujuan objek wisata alam. Dalam graph tersebut titik objek wisata alam merupakan node, titik atau vertex sedangkan jalan merupakan garis atau edge yang menghubungkan antara titik objek wisata alam bobot jarak antara titik didapat menggunakan perhitungan jarak garis lurus antara dua titik koordinat. Untuk penerapkan algoritma Dijkstra dalam pencarian rute terpendek dibutuhkan pemodelan graph dan direpresentasikan dalam matriks ketetanggaan. Gambar 6 merupakan pemodelan graph jaringan jalan Kota Kupang.
J-ICON, Vol. 2 No. 1, Maret 2014 : 1~9
J-ICON
ISSN 2337-7631
2.68 1.05
8
0.77
3.67
4
1.51
9
2
5
10 0.74
1.25
0.58
7
1.16 1
1.75 5.29
3.44 14
3.32
6
2.47
4.26
2.75 2.34
4.36
5.51 3.96
0.93
15
6.37
7 5.91
11
3.46
4.19 4.76 1.65
2.64
12
3
4.9 9,29
4.97 2.51 3.71 13
15 TITIK/ NODE/ VERTEX 34 EDGE/ GARIS
: Lokasi Wisata : Jalan
Gambar 6. Pemodelan Graph Jaringan Jalan Kota Kupang
3.3.1
Pengujian Secara Manual Algoritma Dijkstra mencari panjang lintasan terpendek dari node/simpul a ke z dalam sebuah Graph berbobot terhubung. Dari hasil pemodelan graph jaringan jalan Kota Kupang dan pembentukan matriks ketetanggaan 15 titik objek wisata alam maka akan dilakukan perhitungan manual untuk mencari lintasan terpendek simpul asal a = 1 ke simpul lainnya menggunakan algoritma Dijkstra. Hasil tabulasi algoritma Dijkstra 1 ke semua simpul dapat dilihat pada tabel 4. Tabel 4. Hasil tabulasi algoritma Dijkstra 1 ke semua simpul
Hasil akhir dari algoritma Dijkstra adalah jalur terpendek dari simpul asal a ke semua simpul lain. Untuk mencari jalur terpendek dari semua titik. Algoritma Dijkstra dapat diulang-ulang sebanyak n kali yang dimulai dari semua titik, simpul atau node
Penerapan Algoritma Dijkstra Pada Permasalahan Lintasan Terpendek Objek Wisata Alam Kota Kupang Berbasis Web (Ahmad Rizal)
8
ISSN 2337-7631
3.3.2
Pengujian Dengan Sistem Pada pengujian sistem penulis mencoba mengambil 7 (tujuh) contoh kasus secara acak dari titik asal ke titik tujuan untuk dibandingkan dengan perhitungan manual apakah hasil yang didapat dari sistem sama dengan perhitungan manual. Pantai Lasiana ke Gua Monyet Alak (1 ke 15) Pada sistem titik asal dimulai dari Pantai Lasiana ke titik tujuan Gua Monyet Alak terlihat seperti gambar 7.
Gambar 7. Hasil Pencarian Dijkstra Pantai Lasiana Ke Gua Monyet Alak Tabel 5. Hasil Manual Dijkstra Pantai Lasiana ke Gua Monyet Alak Asal ke tujuan
1-15
Rute
Keterangan
Jarak
Total Jarak
(1-2-6-9-10-14-15)
Pantai Lasiana – Pantai Nunsui – Gua Monyet Kelapa Lima – Pantai Ketapang Satu – Pantai Koepang – Pantai Nunhila – Gua Monyet Alak
(1.16+5.29+3.32+1.05 +1.25+4.26)
16.33
Dari hasil pencarian rute dengan menggunakan algoritma Dijkstra secara manual dengan sistem yang telah dibuat dari titik 1 Pantai Lasiana ke titik 15 Gua Monyet Alak maka hasil yang diperoleh sama dengan rute yang ditempuh yaitu Pantai Lasiana => Pantai Nunsui => Gua Monyet Kelapa Lima => Pantai Ketapang Satu => Pantai Koepang => Pantai Nunhila => Gua Monyet alak dengan total jarak 16.33 Km.
IV.
KESIMPULAN DAN SARAN
4.1
Kesimpulan Dari analisis, pembahasan dan pengujian yang telah dilakukan, maka dapat diambil beberapa kesimpulan sebagai berikut: a. Algoritma Dijkstra telah berhasil diterapkan untuk menyelesaikan masalah lintasan terpendek rute asal ke tujuan objek wisata alam Kota Kupang. b. Didalam sistem ini, output memberikan solusi rute perjalanan dengan total jarak yang minimum dari titik asal ke titik tujuan yang ingin dikunjungi wisatawan. c. Hasil perhitungan secara manual dan hasil perhitungan dengan sistem diperoleh hasil yang sama. 4.2
Saran Berdasarkan kesimpulan yang diperoleh, maka penulis dapat memberikan beberapa saran yang mungkin dapat digunakan untuk keperluan pengembangan selanjutnya : a. Sistem yang dibuat hanya membahas permasalahan jalur terpendek dengan algoritma Dijkstra saja. Untuk pengembangan lebih lanjut dapat ditambahkan algoritma lain yang dapat dijadikan bahan pertimbangan dalam permasalahan rute terpendek.
J-ICON, Vol. 2 No. 1, Maret 2014 : 1~9
J-ICON
b.
c.
ISSN 2337-7631
9
Pada sistem, visual rute perjalanan dari asal ke tujuan tidak sesuai jalan sebenarnya hanya garis lurus. Untuk penelitian selanjutnya disarankan visual rute sesuai dengan jalan sebenarnya. Untuk penelitian selanjutnya disarankan menggunakan jalur dua arah. DAFTAR PUSTAKA
[1] Hasanah, N, dkk., 2007, Pemetaan Metode Heuristik Dalam Pencarian Jalur Terpendek dengan Algoritma Semut dan Algoritma Genetik, Seminar Nasional Aplikasi Teknologi Informasi, Yogyakarta. [2] Munir, R., 2005, Matematika Diskrit. Informatika Bandung, Bandung. [3] Wardy, I, S., 2007, Penggunaan Graph Dalam Algoritma Semut Untuk Melakukan Optimisasi, Program Studi Teknik Informatika, Jurnal Prodi Teknologi Informasi, Institut Teknologi Bandung(ITB), Bandung.
Penerapan Algoritma Dijkstra Pada Permasalahan Lintasan Terpendek Objek Wisata Alam Kota Kupang Berbasis Web (Ahmad Rizal)
