Prosiding – Seminar Nasional Ilmu Komputer 2014
ISBN: 978-602-19406-2-4
Implementasi Algoritma Djikstra pada SMS Gateway Lokasi Wisata Kabupaten SBD Paskalis Andrianus Nani Abstract1— Southwest Sumba district (SBD) as one of Indonesia’s district that has a famous tourist sites, doesn’t have a source of information about the distance to tourist sites itself. BPS noted an increase number of tourists by 243.33% in 2011, but declined 53.33% in 2012. Probably the problem is the promotion and access to tourist sites. Many web-based systems that have been developed previously could be used as a solution to the problems of digital resources to search the quickest route to tourist sites in the region, but the entire system is very dependent on the internet connection, whereas in NTT generally and particularly in SBD hasn’t had adequate internet connection for the most of its people. Existing GSM network can be optimized, with developing a system with SMS interaction and can be accessed anytime, anywhere. Therefore, this study attempts to implement Djikstra Algorithm on SMS Gateway-based system to obtain the fastest route towards the tourist sites at SBD that will help travelers and local citizen in finding the quickest route to a particular tourist sites which can certainly save transport costs and time and also can help SBD in tourism promotion that may increasing own-source revenue of SBD. Keywords — SMS Gateway, Djikstra Algorithm, GIS
1. PENDAHULUAN
P
encarian rute tercepat saat melakukan perjalanan merupakan hal yang perlu dilakukan untuk meringkas perjalanan dan menghemat biaya perjalanan. Saat melakukan perjalanan ke tempat tujuan 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 kota tujuan. Pemakaian peta kertas mempunyai kendala secara visual harus dapat mengurutkan rute mana yang akan ditempuh, salain itu penggunaan peta jenis ini tidak memungkinkan untuk dapat memberikan suatu saran rute mana yang paling efektif yang dapat dilalui [1].
Paskalis Andrianus Nani, Jurusan Teknik Informatika, Universitas Katolik Widya Mandira, Jl. Jend. Achmad Yani No.5052 Kupang 85225 (
[email protected]).
Perkembangan teknologi informasi memungkinkan penerapan sistem informasi dengan memasukan informasi keruangan. Dengan adanya informasi keruangan maka pencari informasi tidak hanya disuguhi huruf dan angka akan tetapi visualisasi tempat dimana informasi tersebut dihasilkan, sebagai contoh situs http://maps.google.com yang menyediakan layanan pencarian tempat dan rute. Situs ini mencoba menyediakan layanan dinamis, dimana pengguna dapat melakukan pencarian rute yang harus dilalui untuk sampai ke suatu tujuan. Namun penggunaannya sangatlah bergantung pada koneksi internet dan device yang digunakan untuk mengakses situs tersebut. Algoritma Djikstra merupakan algoritma yang paling sering digunakan dalam pencarian rute terpendek. Banyak peneliti sebelumnya yang mengkaji tentang algoritma Djikstra dan implementasinya pada kasus pencarian rute tercepat yang dijadikan dasar atau arah penelitian yang akan dilakukan saat ini. Purwananto,dkk [2] pernah melakukan studi perbandingan terhadap waktu eksekusi pada algoritma Dijkstra, algoritma Floyd, dan algoritma Two Queues, dimana waktu eksekusi yang diperlukan oleh algoritma Djikstra dan algoritma Two Queues berbanding quadratic dengan jumlah node yang diperiksa, sedangkan untuk algoritma Floyd waktu eksekusinya berbanding cubic dengan pertambahan jumlah node dalam jaringan. Dari hasil penelitian tersebut dapat ditarik kesimpulan bahwa kinerja algoritma Djikstra lebih baik daripada dua algoritma penghitungan rute terpendek yang lainnya. Ada juga penelitian yang dilakukan oleh Dewi [3] yang mencoba mengimplementasikan algoritma Djikstra pada kasus pencarian jalur terpendek di Bali dan menggunakan format file SVG (Scalable Vector Graphics) untuk diintegrasikan menjadi sebuah sistem web-base. Hasil penelitian Dewi menunjukkan bahwa algoritma Djikstra dapat mencari jalur terpendek dalam waktu yang singkat. Ini terbukti dari beberapa percobaan yang dilakukan dimana 237
Prosiding – Seminar Nasional Ilmu Komputer 2013
kisaran waktu yang dibutuhkan adalah 0,034 detik sampai dengan 0,044 detik. Aplikasi pencarian rute terpendek web-base lainnya adalah yang dikembangkan oleh Pugas, dkk [4] dengan mengimplementasikan algoritma Djikstra dan Astar (A*) dimana kesimpulan yang diperoleh tidak jauh berbeda dengan penelitian sebelumnya walaupun sistem ini lebih kompleks, dengan parameter inputan yang lebih beragam. Sistem web-base yang telah dikembangkan sebelumnya bisa saja digunakan sebagai solusi atas permasalahan sumber informasi digital untuk pencarian rute tercepat menuju lokasi-lokasi wisata di wilayah Kabupaten Sumba Barat Daya (SBD), namun seluruh sistem tersebut sangat bergantung pada koneksi internet, sedangkan di NTT pada umumnya dan Kabupaten Sumba Barat Daya khususnya belum memiliki koneksi internet yang memadai yang dapat diakses oleh sebagian besar masyarakatnya. Jaringan GSM yang sudah ada dapat dioptimalkan untuk solusi terhadap kasus ini yaitu dengan mengembangkan sebuah sistem yang interaksinya hanya melalui SMS saja [5,6]. Oleh karena itu, penelitian ini mencoba mengimplementasikan algoritma Djikstra pada pencarian rute tercepat menuju lokasi-lokasi wisata di Kabupaten Sumba Barat Daya berbasis SMS Gateway.
ISBN:XXXX
Berikut ini disajikan diagram tahapan penelitian implementasi algoritma Djikstra[9] pada aplikasi berbasis sms-gateway.
Gambar 1. Diagram Tahapan Penelitian
3. HASIL DAN PEMBAHASAN Bagian ini akan dijelaskan mengenai proses pengumpulan data dan peta digital, digitasi peta, pembutan matriks jarak, implementasi algoritma dan pembuatan basis data serta pengujian fungsi sms dalam sistem yang dikembangkan. 3.1. Pengumpulan Data dan Peta Digital
2. METODE PENELITIAN Bagian metode penelitian ini, akan dibagi menjadi 3 (tiga) bagian, yaitu: metode pengumpulan data, metode rekayasa perangkat lunak dan tahapan penelitian yang masingmasing bagiannya dijelaskan sebagai berikut: 2.1. Metode Pengumpulan Data Proses pengumpulan data dilakukan dengan beberapa cara, yaitu studi kepustakaan, observasi dan wawancara. Hal ini dilakukan untuk memperoleh data primer yaitu peta digital Kabupaten Sumba Barat Daya, lokasi-lokasi wisata di wilayah Kabupaten Sumba Barat Daya serta teori-teori yang mendukung penelitian ini. 2.2. Metode Rekayasa Perangkat Lunak Metode rekayasa perangkat lunak yang digunakan dalam penelitian ini adalah metode prototype[7][8]. Metode ini dipilih karena kesederhanaannya dan dirasa cocok untuk digunakan dalam pengembangan sistem ini. 2.3. Tahapan Penelitian
3.1.1. Lokasi Wisata Lokasi-lokasi wisata yang berhasil dikumpulkan dari hasil telewicara dengan salah seorang pegawai Dinas Pariwisata Kabupaten Sumba Barat Daya dapat dibagi menjadi tiga jenis, yaitu wisata alam, wisata kampung adat dan wisata upacara adat. Tabel 1. Potensi Wisata Alam NO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
NAMA Pantai Katewel Pantai Managa Aba Pantai Oro Pantai Newa Pantai Waikelo Danau Wee Wini Gua Alam Rambe Manu Danau Wee Kuri Pantai Mandorak Pantai Karoso Pantai Bondo Kawango Pantai Tosi Pantai Pero Pantai Reda Kapal Pantai Wainyapu Pantai Marapu Pantai Watu Maladong Air Terjun Pabeti Lakera Gua Alam Waikelo Sawah
LOKASI Kecamatan Loura Kec Loura Kec Loura Kec Loura Kec Loura Kec Loura Kec Kodi Utara Kec Kodi Utara Kec Kodi Utara Kec Kodi Kec Kodi Kec Kodi Kec Kodi Kec Kodi Bangedo Kec Kodi Bangedo Kec Kodi Bangedo Kec Kodi Bangedo Kec Wewewa Selatan Kec Wewewa Timur
Prosiding – Seminar Nasional Ilmu Komputer 2014
Tabel 2. Potensi Wisata Kampung Adat NO 1 2 3 4 5 6 7 8 9 10 11 12 13
NAMA Kampung Mboku Bani Kampung Tosi Kampung Bongu Kampung Toda Kampung Waidimu Kampung Parona Baroro Kampung Ratenggaro Kampung Wainyapu Kampung Totok Kampung Bondo Kapumbu Kampung Weeleo Kampung Manola Kampung Umbu Koba
LOKASI Kec Kodi Kec Kodi Kec Kodi Kec Kodi Kec Kodi Bangedo Kec Kodi Bangedo Kec Kodi Bangedo Kec Kodi Bangedo Kec Wewewa Selatan Kec Wewewa Selatan Kec Wewewa Timur Kec Loura Kec Loura
Tabel 3. Potensi Wisata Upacacara Adat NO 1 2 3 4 5
NAMA Pasola Upacara Wulla Podu Ritual Teda Upcr Penarikan Batu Kubur Pacuan Kuda Tradisional
LOKASI Kec Kodi Kec Kodi Bangedo Kec Wewewa Selatan Kec Wewewa Selatan Kec Loura
3.1.2. Peta Wilayah Kabupaten SBD Peta wilayah Kabupaten Sumba Barat Daya yang berhasil dikumpulkan dari situs maps.google.com adalah sebagai berikut:
ISBN: 978-602-19406-2-4
3.3. Pembuatan Matriks Jarak Pada tahapan ini dilakukan penghitungan panjang tiap-tiap edge yang terbentuk berdasarkan proses digitasi di atas, baik itu edge yang terbentuk antar simpul maupun antara simpul dan lokasi wisata. 3.4. Implementasi Algoritma Untuk pencarian jalur tercepat digunakan algoritma djikstra dengan langkah-langkah sebagai berikut (dalam pseudocode) [10]: procedure Djikstra(input m: matriks, a: simpul awal) { Mencari lintasan terpendek dari simpul awal a ke semua simpul lainnya Masukan: Matriks ketetanggaan(m) dari graf berbobot G dan simpul awal a Keluaran: Lintasan terpendek dari a ke semua simpul lainnya } Deklarasi s1, s2, ……, sn : integer (tabel integer) d1, d2, ……, dn : integer (tabel integer) i, j, k : integer Algoritma { Langkah 0 (inisialisasi) : } for i ← 1 to n do si ← 0 di ← mai endfor { Langkah 1 : } sa ← 1 {karena simpul a adalah simpul asal lintasan terpendek, jadi simpul a sudah pasti terpilih dalam lintasan terpendek} da ← ~ {tidak ada lintasan terpendek dari a ke a} { langkah 2, 3, ……, n-1 : } for k ← 2 to n-1 do j ← simpul dengan sj = 0 dan dj minimal si ← 1 {simpul j sudah terpilih ke dalam lintasan terpendek} { perbarui tabel d } for semua simpul i dengan si = 0 do if dj + mji < di then di ← dj + mji endif endfor endfor
Gambar 2. Peta Pulau Sumba (warna putih: wilayah Kab. Sumba Barat Daya)
3.2. Digitasi Peta Proses digitasi ini dilakukan untuk membuat layer jalan (shape jalan) sehingga diketahui titiktitik simpul yang nanti akan digunakan dalam penentuan jalur tercepat.
3.5. Pembuatan Basis Data Basis data yang dibuat merupakan modifikasi dari basis data gammu [11] dengan tambahan beberapa tabel yaitu Tabel Jarak dan Tabel Lokasi dengan struktur sebagai berikut:
Gambar 4. Struktur Tabel Lokasi
Gambar 5. Struktur Tabel Jarak
Tabel lokasi berfungsi untuk mencatat setiap lokasi wisata yang berhasil diidentifikasi (dalam aplikasi akan dianggap sebagai point/titik) sedangkan tabel jarak berfungsi untuk mencatat jarak antar lokasi/point terdekat (dalam aplikasi akan dianggap sebagai edge). Ket: Biru = Batas Kabupaten; Hijau = Batas Kecamatan; Merah = Shape Jalan (edge)
Gambar 3. Hasil pembuatan layer (shape) jalan
239
Prosiding – Seminar Nasional Ilmu Komputer 2013
3.6. Pengembangan Aplikasi Setelah mendigit peta dan mengimplementasikan basis data, selanjutnya masuk dalam tahap coding. Proses permintaan informasi rute terpendek dengan teknologi sms-gateway yang akan dikembangkan dapat dilihat pada diagram berikut: Start
Kirim Pesan dengan format: LIST atau INFO*
*
ISBN:XXXX
SMS sesuai dengan format yang telah ditentukan maka akan ada balasan SMS yang memberitahukan bahwa format SMS yang barusan dikirimkan tidak sesuai dengan format (isi SMS = “FORMAT SALAH”). 3.7.2. Pengujian SMS “LIST” Pada pengujian yang kedua, SMS yang dikirimkan adalah “LIST”. Hasil yang diharapkan dari pengujian ini adalah memberitahukan kepada pengirim SMS tentang format SMS yang harus dikirim untuk memperoleh informasi rute tercepat.
Server membaca sms masuk dan mengenali format sms
Ya
Format Sesuai ?
Kirim informasi rute terpendek
Tidak
Kirim Informasi: “Format Salah”
Gambar 8. Tampilan SMS balasan yang memberitahukan format SMS untuk memperoleh informasi rute tercepat End
Gambar 6. Prosedur aplikasi sms-gateway
3.7. Pengujian Fungsi SMS Pada tahapan ini dilakukan pengiriman SMS untuk mengecek apakah informasi yang dikirimkan kembali sesuai dengan permintaan atau tidak. Berikut adalah pengujian-pengujian yang dilakukan pada tahapan ini: 3.7.1. Pengujian Format SMS Pada pengujian yang pertama, SMS yang dikirimkan tidak mengikuti aturan yang telah ditentukan sebelumnya. Hasil yang diharapkan dari pengujian ini adalah pemberitahuan kepada pengirim SMS bahwa format SMS yang dikirim tidak sesuai.
Dari hasil pengujian di atas, dapat dilihat bahwa SMS yang dikirim berisi format SMS untuk memperoleh informasi rute tercepat menuju lokasi wisata yang diinginkan (isi SMS = “Format sms info rute: INFO*kodeasal*kodetujuan”). 3.7.3. Pengujian SMS “INFO” Pada pengujian yang ketiga, SMS yang dikirim adalah “INFO*L001*W003”. Hasil yang diharapkan dari pengujian ini adalah informasi rute tercepat sesuai dengan kode format yang dikirim.
Gambar 9. Tampilan SMS balasan yang memberikan informasi rute tercepat sesuai format SMS
Gambar 7. Tampilan SMS balasan yang memberitahukan bahwa format SMS yang dikirim oleh pengirim masih salah
Dari hasil pengujian di atas, dapat dilihat bahwa SMS yang dikirim berisi informasi rute tercepat dari kota Waitabula menuju pantai Newa (isi SMS = “Jalur terpendek Waitabula-Pantai
Dari hasil pengujian di atas, dapat dilihat bahwa jika pengirim SMS tidak mengirimkan
Newa: Tambolaka-Radamata-Karuni-Cabang Desa Lololage. Total jarak 7,8 Km”).
Prosiding – Seminar Nasional Ilmu Komputer 2014
4. KESIMPULAN Berdasarkan pembahasan sebelumnya, maka dapat disimpulkan bahwa algoritma Djikstra dapat diimplementasikan pada pencarian rute tercepat menuju lokasi-lokasi wisata di Kabupaten Sumba Barat Daya berbasis SMSGateway sehingga dapat membantu wisatawan dan warga lokal dalam mencari rute tercepat menuju lokasi wisata tertentu yang tentunya dapat menghemat biaya transportasi dan menghemat waktu perjalanan serta dapat membantu Pemkab Sumba Barat Daya dalam promosi pariwisata yang nantinya dapat mempengaruhi peningkatan PAD Kabupaten tersebut. 5. SARAN Fitur SMS “LIST” akan memberikan informasi mengenai lokasi-lokasi wisata di wilayah Kabupaten SBD, namun SMS balasan yang dikirim akan sangat panjang, mengingat jumlah lokasi wisata yang sangat beragam. Hal ini masih membutuhkan perbaikan, karena sms yang dikirim pasti akan terpotong jika tidak diblock terlebih dahulu.
ISBN: 978-602-19406-2-4 [6] Thoyib, 2010, Pelayanan Pelanggan Berbasis SMS Gateway, Skripsi, Jurusan Teknik Informatika, Universitas Mercu Buana, Jakarta. [7] Rosmala, D., Djatmiko, M. D., Julianto, B., 2012, Implementasi Aplikasi Website E-Commerce Batik Sunda dengan Menggunakan Protokol Secure Socket Layer (SSL), Jurnal Informatika ITENAS Bandung, Vol. 3, No. 3, hal. 58-67. [8] Mufadhol, 2011, Pemanfaatan Pemrograman Visual untuk Aplikasi Sistem Pembagian Warisan Menggunakan Metode Prototype Paradigma pada Sistem Pakar, Jurnal Transformatika, Vol. 9, No. 1, hal. 37-45, 1693-3656. [9] Santoso, D., Harianto, Ihyaudin, 2012, Pencarian Rute Terpendek Pada Citra Labirin Menggunakan Algoritma Djikstra Sebagai Pemandu Gerak Micromouse Robot, Jornal of Controls and Network Systems, Vol. 1, No. 2, http://jurnal.stikom.edu/index.php/jcone/article/download/ 28/19. [10] Munir, R., 2012, Matematika Diskrit (Revisi Kelima), Informatika, Bandung. [11] Suryana, T., 2012, SMS Gateway Kannel Sebagai Sarana Penunjang Informasi Akademik, Jurnal Ilmiah Komputer dan Informatika (KOMPUTA), Vol.1, No.2, hal.17-30.
Ucapan Terima kasih Penulis mengucapkan terima kasih kepada Direktorat Penelitian dan Pengabdian Kepada Masyarakat Dirjen Dikti Kemdikbud yang telah memberikan dukungan financial terhadap penelitian ini melalui skim Penelitian Dosen Pemula (PDP) Tahun 2014. DAFTAR PUSTAKA [1] Pribadi, F.S., Mulwinda, A., 2010, Pencarian Rute Terpendek dengan Menggunakan Algoritma Depth First, Breath First dan Hill Climbing (Study Comparative), Jurnal Kompetensi Teknik, Vol.2, No.1, hal.57-64. [2] Purwananto, Y., Purwitasari, D., Wibowo, A.W., 2005, Implementasi dan Analisis Algoritma Pencarian Rute Terpendek di Kota Surabaya, Jurnal penelitian dan Pengembangan TELEKOMUNIKASI, Vol.10, No.2, hal.94-101. [3] Dewi, L.J.E., 2010, Pencarian Rute Terpendek Tempat Wisata Di Bali Dengan Menggunakan Algoritma Djikstra, Prosiding Seminar Nasional Aplikasi Teknologi Informasi (SNATI), ISSN: 1907-5022, hal.D-46−D-49. [4] Pugas, D.O., Somantri, M., Satoto, K.I., 2011, Pencarian Rute Terpendek Menggunakan Algoritma Djikstra Dan Astar (A*) Pada SIG Berbasis Web Untuk Pemetaan Pariwisata Kota Sawahlunto, Jurnal TRANSMISI, Vol.13, No.1, hal.27-32. [5] Wiharto, Y., 2011, Sistem Informasi Akademik Berbasis SMS Gateway, Jurnal Teknologi dan Informatika (TEKNOMATIKA), Vol.1, No.1 : http://news.palcomtech. com/wp-content/uploads/2012/01/YUDIWIHARTOTE01012011.pdf
241
