RANCANG BANGUN APLIKASI PENCARIAN JALUR TERPENDEK MENGGUNAKAN ALGORITMA FLOYD WARSHALL (STUDI KASUS KOTA SINGKAWANG) Mohammad Hendra Istyanto Program Studi Teknik Informatika Jurusan Teknik Elektro Fakultas Teknik Universitas Tanjungpura
[email protected]
ABSTRACT There are many tourist place located around Singkawang and make the tourist hard to choose the best route to go to the place that they want. That problem is the background of the writer to make an application that can show the most efficient route to the tourism place with maps view. The algorithm that writer use in this application is floyd warshall algorithm. This algorithm search the shortest route from the position of user to the tourism place that he want to go. The input of this application is the place chosen by user and the output is the shortest route to that place. The data of tourism place are came from Dinas Kebudayaan, Pariwisata, Pemuda dan Olahraga and the data of the distant route are came from Dinas Pekerjaan Umum Singkawang. Based on the research, the writer conclude that the application succeed in applying floyd warshall algorithm to search the shortest route to go to tourism place in Singkawang. In this application, there also a features for showing the location of all tourism place in Singkawang. Keyword : singkawang, tourism, shortest route, floyd warshall algorithm.
1.
PENDAHULUAN Perkembangan teknologi semakin pesat seiring meningkatnya kebutuhan masyarakat akan informasi. Salah satu alat komunikasi yang saat ini menjadi kebutuhan mayarakat adalah telepon seluler. Salah satu telepon seluler yang saat ini tengah popular adalah telepon seluler berbasis android. Sundar Pichai sebagai Vice President android dan chrome mengatakan pada bulan Mei 2013 sudah 900 juta perangkat android telah diaktifkan di seluruh dunia. Hal ini menumbuhkan minat developer software mobile phone untuk membuat aplikasi yang dapat memenuhi kebutuhan manusia seharihari. Salah satu aplikasi yang dapat dibangun adalah aplikasi untuk mencari jalur terpendek menuju tempat wisata yang berada di Kota Singkawang.
Singkawang merupakan tempat tujuan wisata di Kalimantan Barat yang banyak diminati wisatawan domestik maupun mancanegara. Tempat-tempat wisata di Singkawang tersebar di penjuru Kota Singkawang. Untuk menuju ke tempat wisata, ada beberapa jalur yang dapat ditempuh. Pencarian jalur terpendek menuju tempat wisata menggunakan algoritma floyd warshall untuk meminimalisir kemungkinan berputarputar mengitari kota Singkawang. Algoritma floyd warshall dipilih karena merupakan salah satu varian dari pemrogaman dinamis atau algoritma yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. 2. TEORI DASAR 2.1 Sistem Operasi Android Android adalah sistem operasi berbasis Linux yang dikembangkan oleh Android.inc dengan dukungan dana/finansial dari Google untuk perangkat seluler layar sentuh (touchscreen) . Dirilis secara resmi pada tahun 2007, bersamaan dengan berdirinya Open Handset Alliance, konsorsium dari perusahaanperusahaan perangkat keras, perangkat lunak, dan telekomunikasi yang bertujuan untuk memajukan perangkat seluler open source. Android adalah sistem operasi terbuka (open source), berbasis lisensi dari Apache, sistem operasi ini memungkinkan untuk dimodifikasi dan didistribusikan secara bebas. Android juga memiliki sejumlah komunitas pengembang perangkat lunak yang berguna untuk memperluas fungsi perangkat android itu sendiri, ditulis dan dikustomisasi dengan
perangkat lunak pemrograman java.
berbasis
bahasa
2.2 Pariwisata Menurut Gamal, pariwisata didefinisikan sebagai bentuk suatu proses kepergian sementara dari seorang atau lebih menuju ketempat lain diluar tempat tinggalnya. Dorongan kepergiannya adalah karena berbagai kepentingan baik karena kepentingan ekonomi, sosial, budaya, politik, agama, kesehatan maupun kepentingan lain 2.3 Sistem Informasi Geografis Menurut Shunji Murai, Sistem Informasi Geografis (SIG) adalah sistem informasi yang digunakan untuk memasukkan, menyimpan, memangggil kembali, mengolah, menganalisis dan menghasilkan data bereferensi geografis atau data geospasial, untuk mendukung pengambilan keputusan dalam perencanaan dan pengelolaan penggunaan lahan, sumber daya alam, lingkungan transportasi, fasilitas kota dan pelayanan umum lainnya.
Jika W[i,j] > W[i,k] + W[k,j] maka Tukar W[i,j] dengan W[i,k] + W[k,j] 3. W* = W Dalam iterasinya untuk mencari path terpendek, algoritma warshall mementuk n matrik sesuai dengan iterasi k. Itu menyebabkan waktu prosesnya lambat, terutama untuk n yang besar. 3. PERANCANGAN SISTEM 3.1 Perancangan Diagram UseCase Diagram use case berikut menggambarkan perilaku dari aktor yang terlibat dalam aplikasi. Dalam aplikasi ini user dapat melakukan beberapa perilaku meliputi menampilkan daftar kriteria wisata, menampilkan daftar tempat wisata, menampilkan informasi tempat wisata, menampilkan jalur terpendek, menampilkan peta wisata serta menampilkan bantuan dan tentang aplikasi. Menampilkan Informasi Tempat Wisata «extends»
Menampilkan Daftar Kriteria Wisata
«extends»
Menampilkan Daftar Tempat Wisata
«extends»
Menampilkan Jalur Terpendek
2.4 Algoritma Floyd Warhsall Algoritma yang ditemukan oleh Warshall untuk mencari path terpendek merupakan algoritma yang sederhana dan mudah implementasinya. Masukan algoritma warshall adalah matrik hubung graf berarah berlabel dan keluarannya adalah path terpendek dari semua titik ke semua titik. Dalam usaha untuk mencari path terpendek, algoritma warshall memulai iterasi dari titik awalnya kemudian memperpanjang path dengan mengevaluasi titik demi titik hingga mencapai titik tujuan dengan jumlah bobot yang seminimum mungkin. Misalkan W0 adalah matrik hubung graf berarah berlabel mula-mula. W* adalah matrik hubung minimal dengan Wij* = path terpendek dari titik vi ke vj. Algoritma warshall untuk mencari path terpendek adalah sebagai berikut: 1. W = W0 2. Untuk k = 1 hingga n, lakukan: Untuk i = 1 hingga n, lakukan: Untuk j = 1 hingga n, lakukan:
Menampilkan Peta Wisata
Menampilkan Nama Jalan
<
>
user Menampilkan Tentang Aplikasi
Gambar 3.1 Diagram Use Case Dalam diagram use case (Gambar 3.1) terlihat bahwa user harus memilih kriteria wisata untuk melihat daftar tempat wisata, setelah itu untuk mendapatkan jalur terpendek user harus memilih salah satu tempat wisata yang akan dituju. Selain itu user juga dapat menampilkan peta wisata dan tentang aplikasi. 3.2 Activity Diagram Activity diagram (Gambar 3.2) menggambarkan berbagai alir aktivitas dalam sistem yang sedang dirancang, bagaimana masing-masing alir berawal, decision yang mungkin terjadi, dan bagaimana mereka berakhir. Dalam activity diagram berikut terlihat alur aktifitas user saat menggunakan aplikasi ini. Aktifitas yang dilakukan mulai dari masuk ke tampilan utama, memilih menu
kriteria wisata, memilih tempat wisata, melihat informasi detail, melihat jalur terpendek, memilih tentang aplikasi dan keluar aplikasi.
masuk ke tampilan utama
memilih peta wisata
memilih kriteria wisata
memilih keluar
memilih about
terdiri dari satu bagian yaitu bagian yang dapat diakses oleh pengguna. Adapun perancangan antarmuka tersebut adalah sebagai berikut. Antarmuka beranda merupakan antarmuka yang pertama kali muncul ketika aplikasi ini pertama dijalankan. Pada antarmuka ini terdapat empat menu pilihan yang dapat dipilih oleh pengguna yaitu daftar wisata, peta wisata, tentang aplikasi dan keluar. Adapun antarmuka beranda dapat dilihat pada Gambar 4.1.
memiliih tempat wisata
melihat informasi tempat wisata
memilih pencarian jalur
Gambar 3.2 Activity pencarian jalur tependek
diagram
aplikasi
3.2 Perancangan Struktur Antarmuka Aplikasi pencarian jalur terpendek yang dibuat adalah aplikasi berbasis android yang dirancang memiliki beberapa layout yang disesuaikan dengan kebutuhan aplikasi. Struktur antarmuka aplikasi yang dirancang dapat dilihat pada Gambar 3.3 berikut :
Daftar Kriteria Wisata
Daftar Tempat Wisata
Antarmuka daftar kriteria wisata akan tampil pada saat pengguna memilih menu daftar wisata pada antarmuka beranda. Didalam menu ini terdapat lima pilihan kriteria wisata yaitu air terjun, danau, gunung, pantai dan taman. Adapun antarmuka daftar kriteria wisata dapat dilihat pada Gambar 4.2.
Informasi Detil
Rute terpendek Beranda
Gambar 4.1 Antarmuka beranda
Daftar Nama Jalan
Peta Wisata
Tentang Aplikasi
Gambar 3.3 Struktur antarmuka aplikasi 4.
HASIL PERANCANGAN Aplikasi yang dirancang merupakan aplikasi pencarian jalur terpendek menggunakan algoritma floyd warshall (studi kasus kota singkawang) yang bertujuan untuk mencari jalur terpendek untuk menuju tempat wisata yang ada di Kota Singkawang. Antarmuka sistem yang dirancang hanya
Gambar 4.2 Antarmuka daftar kriteria wisata Antarmuka daftar tempat wisata akan tampil pada saat pengguna memilih kriteria wisata. Daftar wisata yang ditampilkan berdasarkan kriteria wisata yang dipilih oleh
pengguna. Adapun antarmuka daftar tempat wisata dapat dilihat pada Gambar 4.3.
Gambar 4.5 Antarmuka peta jalur
Gambar 4.3 Antarmuka daftar tempat wisata Antarmuka detail tempat wisata akan tampil pada saat pengguna memilih tempat wisata. Pada halaman ini terdapat informasi mengenai tempat wisata seperti gambar, alamat, fasilitas dan menu jalur ke sini untuk melihat jalur menuju tempat wisata yang telah dipilih. Adapun antarmuka detail tempat wisata dapat dilihat pada Gambar 4.4.
Antarmuka daftar nama jalan akan muncul pada saat pengguna memilih menu tampilkan nama jalan pada antarmuka peta jalur. Antarmuka ini menampilkan daftar nama jalan yang dilewati untuk menuju tempat wisata yang telah dipilih. Adapun antarmuka daftar nama jalan dapat dilihat pada Gambar 4.6.
Gambar 4.6 Antarmuka daftar nama jalan
Gambar 4.4 Antarmuka detail tempat wisata Antarmuka peta jalur akan tampil pada saat pengguna memilih menu jalur ke sini pada antarmuka detail tempat wisata. Pada halaman ini terdiri dari layer peta yang menggambarkan jalur terpendek yang dapat dilewati pengguna dan menu tampilkan nama jalan untuk melihat daftar nama jalan yang dapat dilewati. Adapun antarmuka peta jalur dapat dilihat pada Gambar 4.5.
Antarmuka peta wisata akan muncul pada saat pengguna memilih menu peta wisata pada antarmuka beranda. Halaman ini menampilkan layer peta yang berisikan titik lokasi tempat wisata. Adapun antarmuka peta wisata dapat dilihat pada Gambar 4.7.
yang dapat membantu pengguna untuk menuju tempat wisata. 3. Implementasi dari algoritma floyd warshall yang digunakan dalam aplikasi ini hanya dapat menghitung hingga 100 titik simpul jalan. 4. Aplikasi ini memberikan hasil berupa jalur menuju tempat wisata dengan jarak yang terpendek dari posisi pengguna. Gambar 4.7 Antarmuka peta wisata Antarmuka akan muncul pada saat pengguna memilih menu tentang aplikasi pada halaman beranda. Antarmuka ini berisikan informasi mengenai minimal versi sistem operasi, tujuan pembuatan aplikasi dan pembuat aplikasi. Adapun antarmuka tentang aplikasi dapat dilihat pada Gambar 4.8 berikut.
Gambar 4.8 Antarmuka tentang aplikasi 5.
Kesimpulan Setelah dilakukan analisis dan pengujian terhadap Aplikasi Pencarian Jalur Terpendek Menggunakan Algoritma Floyd Warshall (Studi Kasus Kota Singkawang), dapat disimpulkan bahwa : 1. Penelitian ini berhasil merancang sebuah sistem yang mampu mencari jalur terpendek menuju tempat wisata di Kota Singkawang dan memvisualisasikan dalam bentuk peta. 2. Penelitian ini berhasil menerapkan algoritma floyd warshall dalam pencarian jalur terpendek menuju tempat wisata di Kota Singkawang
Referensi [1] Andriansyah, Sofyan. 2010. Sistem Informasi Tourism Guide Kota Jakarta Dengan Menggunakan Algoritma Djikstra. Malang: Universitas Islam Negeri. [2] Dewi, L. J. E. 2010. Pencarian Rute Terpendek Tempat Wisata Di Bali Dengan Menggunakan Algoritma Dijkstra. Seminar Nasional Aplikasi Teknologi Informasi 2010 (SNATI 2010). Yogyakarta, tanggal 19 Juni 2010. Universitas Pendidikan Ganesha. [3] Murai, Shunji. 2007. Sistem Informasi Geografis (Bab I GIS Worldbook Vol I) Pengantar GIS. University of Tokyo. [4] Riyanti, Eka. 2004. Penerapan Algoritma Branch and Bound Untuk Penentuan Rute Objek Wisata. Bandung: Universitas Komputer Indonesia. [5] Siang, Jong Jek. 2006. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: Andi. [6] Suwantoro, Gamal.1997. Dasar-dasar Pariwisata. Yogyakarta: Andi. Biografi Mohammad Hendra Istyanto, lahir di Pontianak, Kalimantan Barat, Indonesia, 25 September 1991. Mahasiswa Program Studi Teknik Informatika Universitas Tanjungpura Pontianak. Telah menerima gelar sarjana teknik (S.T.) pada 21 Oktober 2014.
