PENCARIAN LINTASAN TERPENDEK UNTUK MENENTUKAN RESTORAN DI KOTA PALEMBANG MENGGUNAKAN ALGORITMA DIJKSTRA BERBASIS ANDROID Indra Komala1, Ahmad Yani Ranius 2, Rasmila 2 Dosen Universitas Bina Darma2.2, Mahasiswa Universitas Bina Darama1 Jurusan Teknik Informatika, Fakultas Ilmu Komputer, Universitas Bina Darma Palembang Jl. Jenderal Ahmad Yani No.12, 9 Ulu, Seberang Ulu I, Kota Palembang Pos-el :
[email protected],
[email protected],
[email protected]
Abstract : In the field of the restaurant business is growing like mushrooms in Palembang with a wide variety of menus offered. Hargapun combination of assortment, ranging from a simple menu at a cheap price to the kind of lavish menu of course the price is more expensive. With the development of the restaurant business, causing many positive aspects that make tartarik researchers that provides information on the location of the restaurant closest to us and according to our needs. To facilitate and assist in finding a restaurant with the shortest path in the city of Palembang to the development of information technology of Global Positioning System (GPS) is then needed a tool or directions that aims to facilitate users to obtain the location of a restaurant in the city of Palembang by using Dijkstra's algorithm. The programming language used in this study is that Eclipse based programming android with phonegap library. Keywords: restaurant, GPS, android, Dijkstra's algorithm. Abstrak : Dalam bidang usaha restoran tumbuh bagaikan jamur di kota Palembang dengan berbagai macam variasi menu yang ditawarkan. Kombinasi hargapun bermacam-macam, mulai dari menu yang sederhana dengan harga yang murah sampai pada jenis menu mewah tentunya dengan harga yang lebih mahal. Dengan berkembangnya usaha restoran tersebut, menimbulkan banyak segi positif yang membuat peneliti tartarik yaitu memberikan informasi mengenai lokasi restoran yang terdekat dengan kita dan sesuai dengan kebutuhan kita. Untuk mempermudah dan membantu dalam mencari restoran dengan lintasan terpendek yang ada di kota Palembang dengan berkembangnya teknologi informasi Global Positioning System(GPS) ini maka diperlukan sebuah alat atau petunjuk arah yang bertujuan untuk memfasilitasi pengguna untuk memperoleh lokasi restoran di kota Palembang dengan menggunakan algoritma Dijkstra. Bahasa pemrograman yang digunakan dalam penelitian ini adalah pemrograman berbasis android yaitu Eclipse dengan library phonegap. Kata kunci : restoran, GPS, android, Algoritma Dijkstra.
1. PENDAHULUAN
memesan makanan maupun minuman
1.1 Latar Belakang
untuk
jamuan
makan,
baik
yang
restoran merupakan suatu usaha berskala besar maupun kecil. Dalam dalam
bidang
jasa
boga
yang bidang usaha restoran tumbuh bagaikan
memberikan pelayanan dengan baik jamur kepada
semua
pelanggan
dalam
di
kota
Palembang
dengan
berbagai macam variasi menu yang
semua kemungkinan bobot terkecil dari
ditawarkan.
setiap titik.
Dengan
berkembangnya
usaha restoran tersebut, menimbulkan banyak segi positif yang membuat peneliti
tartarik
yaitu
1.2 Rumusan Masalah
memberikan
Berdasarkan latar belakang yang
informasi mengenai lokasi restoran
telah
yang sesuai dengan kebutuhan kita.
penulis merumuskan masalah yang ada
Dengan berkembangnya
teknologi
untuk dijadikan titik tolak pembahasan
informasi maka diperlukan sebuah alat
dalam penulisan laporan penelitian ini
atau petunjuk arah yang bertujuan
adalah “Bagaimana membuat sebuah
untuk memfasilitasi pengguna untuk
Pencarian Lintasan Terpendek Untuk
memperoleh lokasi restoran di kota
Menentukan
Palembang
Palembang
dengan
menggunakan
algoritma Dijkstra. Algoritma Dijkstra
diuraikan
sebelumnya,
Restoran
Di
maka
Kota
Menggunakan Algoritma
Dijkstra Berbasis Android”.
merupakan salah satu algoritma yang digunakan permasalahan
untuk
memecahkan
menemukan
1.3 Batasan Masalah
jalur
Agar tidak meluasnya pembahasan
terpendek berdasarkan bobot terkecil
dalam laporan skripsi ini, maka penulis
dari satu titik ke titik lainnya. Misalnya
ingin membatasi permasalahan sebagai
titik mengambarkan gedung dan garis
berikut :
menggambarkan jalan, maka algoritma
a.
Dijkstra melakukan kalkulasi terhadap
Pembuatan Lintasan
aplikasi
Pencarian
Terpendek
Menentukan Restoran Di
Untuk Kota
Palembang Algoritma
Menggunakan Djikstra
ada atau diketahui. Permasalahan
Berbasis
manusia dan lingkungan alamnya
Android menggunakan phonegap.
selalu berkembang yang kesemuanya
Rute jalan yang digunakan hanya
ini harus memperoleh jawaban yang
jalan utama, tidak termasuk jalan-
simbang.(Supardi, 2005).
jalan kecil / gang. b.
Kawasan pemetaan yang dijadikan titik lokasi adalah restoran yang
2.2 Metode Pengumpulan Data Metode Pengumpulan Data yang
terdaftar di Dinas Kebudayaan dan
digunakan dalam penelitian ini adalah :
Pariwisata Kota Palembang.
A. Dokumentasi Dalam metode ini penulis mencari data
2. METODOLOGI PENELITIAN 2.1 Metode Penelitian
suatu cara yang dapat digunakan mencapai
tujuan
yang
diharapkan melalui suatu penelitian dengan teknik-teknik dan alat-alat tertentu.
Adapun
hal-hal
berupa
catatan,
transkip, buku, surat kabar, majalah,
Metode penelitian merupakan
untuk
mengenai
metode
yang
digunakan dalam penelitian ini yaitu metode development research suatu kegiatan penelitian yang bertujuan dan berusaha mengembangkan atau melengkapi pengetahuan yang sudah
prasasti, agenda dan sebagainya. B. Kepustakaan Mengumpulkan
data
dengan
cara
mencari dan mempelajari data-data dari buku-buku ataupun dari referensi lain yang berhubungan dengan penulisan laporan penelitian proposal. Buku yang digunakan penulis sebagai referensi, adapun metode yang digunakan penulis
dalam merancang dan mengembangkan
Fase-fase
dalam
model
waterfall
dapat dilihat pada daftar pustaka.
menurut referensi Sommerville.
C. Observasi Metode ini dilakukan dengan cara mengamati
langsung
keadaan
dan
restoran sebagai guna mendapatkan keterangan yang akurat. Gambar 1.1 Waterfall Sommerville 2.3 Metode Pengembangan Sistem Menurut Sommerville (2011)
1. Requirements Analysis and
model waterfall adalah kerangka model
Definition
proses
Pada tahap ini dikumpulkan secara
dasar
megenai
spesifikasi,
lengkap
kebutuhan-kebutuhan
dibagi menjadi beberapa tahapan yaitu
mengenai
perangkat
analisis dan definisi kebutuhan, desain
kemudian
sistem
untuk
pengembangan
dan
implementasi,
dan
validasi,
yang
perangkat
lunak,
pengujian
serta
pemeliharaan. Karena pencapaian tiap tahap dalam prosesnya digambarkan
peneliti
didefenisikan
lunak,
menganalisis kebutuhan-
kebutuhan yang dibutuhkan pada perangkat lunak. 2. System and Software Design
seperti proses yang mengalir, maka
Pada tahap ini peneliti melakukan
model
desain setelah kebutuhan selesai
ini
dikenal
dengan
nama
waterfall model. Berikut ini gambaran
dikumpulkan secara lengkap.
proses berdasarkan rencana dan jadwal.
3. Implementation and Unit Testing
Pada proses ini desain program
atau
diterjemahkan kedalam kode-kode
dengan situasi sebenarnya.
dengan
menggunakan
pemrograman
perubahan karena
adaptasi
bahasa
yang
sudah
3. ANALISA DAN PERAMCANGAN 3.1 Requirements Analysis and
ditentukan. Program yang dibangun Definition langsung diuji dengan tujuan agar Pada tahap ini dikumpulkan program dapat diuji dengan baik. secara lengkap kebutuhan-kebutuhan 4. Intergration and System Testing yang dibutuhkan secara lengkap setelah pada proses ini adalah penyatuan itu unit-unit
program.
Setelah
dianalisis
pengujian
keseluruhan
mengenai
kemudian
itu didefenisikan
dilakukan
dan
kebutuhan-kebutuhan
secara yang dibutuhkan pada aplikasi yang perangkat akan dibuat. Hal ini diperlukan karena
lunak pencarian restoran. aplikasi harus dapat digunakan dengan 5. Operation and Maintenance hal-hal yang lain seperti perangkat Pada
proses
ini
dilakukan keras, tempat penyimpanan data dan
pengujicobaan
perangkat
lunak lainya.
pencarian
restoran,
tujuan
dari 3.1.1 Analisis Kebutuhan Perangkat
proses
ini
adalah
mengurangi Lunak
kesalahan yang ada pada perangkat Dalam
pembuatan
perangkat
lunak yang dibuat dan sesuai dengan lunak
pencarian
lintasan
terpendek
kebutuhan. mengoprasikan program untuk menentukan restoran di Kota dilingkungannya
dan
melakukan Palembang
menggunakan
Algoritma
pemeliharaan, seperti penyesuaian Dijkstra Berbasis Android, alat dan
bahan
yang
digunakan
meliputi
3.1.2 Analisis Algoritma Djikstra
hardware, software serta bahan-bahan
Adapun analisia dari algoritma
penunjang lainnya.
djikstra
1. Perangkat Keras (Hardware)
tahapan sebagai berikut ini :
Perangkat keras yang digunakan adalah
1. Beri nilai bobot (jarak) untuk setiap
laptop dengan spesifikasi berikut :
ini
adalah
sesuai
dengan
titik ke titik lainnya, lalu set nilai 0
a. Laptop TOSHIBA
pada node awal dan nilai tak hingga
b. RAM 2GB
terhadap node lain (yang belum
c. Hardisk 250 GB
terisi).
d. Printer HP Deskjet 1510
Tabel 3.1 Menentukan Titik Awal dan
e. Flashdisk 16 GB
Tujuan
2. Perangkat Lunak (Software)
No 1.
a. Windows 7 ultimate sebagai operating 2.
system b. Microsoft word 2007 untuk penulisan
3. 4.
laporan tugas akhir ini
5.
c. Software pendukung yaitu Eclipse 6.
sebagai Editor
7.
Nama Node Universitas Bina Darma Simpang Kanan Lintas Sumatera Lurus Taman Tugu Belok Kanan Jl. Gub. H Bastari Jl. KH. Azhari Belok Kiri Jl. KH. Azhari Lurus Kampung Kapiten
Nilai Bobot -2.999510, 104.77043 -2.999837, 104.768725 -3.002640, 104.764891 -3.006757, 104.773546 -2.994318, 104.765046 -2.995547, 104.764102 -2.994121, 104.762674
d. Phonegap yaitu sebagai library 2. Set semua node “Belum terjamah”
pemrograman e.
Adobe
Photosop
yaitu
aplikasi manipulasi gambar
sebagai
dan set node awal sebagai “Node keberangkatan”.
simpul B3 (Belok Kanan Jl. Gub. H Bastari) (Simpang Kanan Lintas Sumatera) menuju simpul C (Jl. KH. Azhari Belok Kiri) (Jl. KH. Azhari Belok Kiri) menuju simpul D (Jl. KH. Azhari Lurus) (Jl. KH. Azhari Lurus) menuju simpul E (Kampung Kapiten)
Tabel 3.2 Set Node Awal dan 4.
Keberangkatan No
1.
2.
3.
4.
5.
6.
Node Awal dan Tujuan Universitas Bina Darma Simpang Kana n Lintas Sumatera
(Universitas Bina Darma) - simpul B2 (ke Lurus Taman Tugu) (Universitas Bina Darma) - simpul B3 (Belok Kanan Jl. Gub. H Bastari) (Simpang Kanan Lintas Sumatera) simpul C (Jl. KH. Azhari Belok Kiri) (Jl. KH. Azhari Belok Kiri) simpul D (Jl. KH. Azhari Lurus) (Jl. KH. Azhari Lurus) - simpul E (Kampung Kapiten)
3. Dari
Titik Lokasi
5.
(-2.999510, 104.77043) -(-2.999837, 104.768725)
6.
(-2.999510, 104.77043) (-3.002640, 104.764891)
tandai node yang telah terjamah sebagai “Node terjamah”. Node
(2.999837, 104.768725) - (-2.994318, 104.765046)
terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah
(-2.994318, 104.765046) - (-2.995547, 104.764102)
(-2.995547, 104.764102) - (-2.994121, 104.762674)
node
keberangkatan,
jarak terakhir dan yang paling minimal bobotnya. Tabel 3.4 Pemberian tanda pada node No 1.
2.
dari titik keberangkatan. Tabel 3.3 Set Node Awal dan Keberangkatan Dengan Jarak
2. 3.
3,4 KM
setiap jarak terhadap node tetangga,
belum terjamah dan hitung jaraknya
1.
5,4 KM
4. Setelah selesai mempertimbangkan
(-2.999510, 104.77043) (-3.002640, 104.764891)
pertimbangkan node tetangga yang
No
56 KM
Node Awal dan Tujuan Universitas Bina Darma Simpang Kanan Lintas Sumatera (Universitas Bina Darma) menuju simpul B2 (ke Lurus Taman Tugu) (Universitas Bina Darma) menuju
Jarak node titik 9,98 KM
20 KM
14,5 KM
3.
Node Awal dan Tujuan
Jarak node titik
Universitas Bina Darma Simpang Kanan Lintas Sumatera (Universitas Bina Darma) menuju simpul B2 (ke Lurus Taman Tugu) (Universitas Bina Darma) menuju simpul B3 (Belok Kanan Jl. Gub. H Bastari)
9,98 KM
Tanda Node Dilalui
20 KM
14,5 KM
5. Set “Node belum terjamah” dengan jarak
terkecil
(dari
node
keberangkatan)
sebagai
“Node
Keberangkatan”
peta,
Tabel 3.5 Pemberian tanda pada node Node Awal dan Tujuan
Jarak node titik
Universitas Bina Darma Simpang Kanan Lintas Sumatera (Simpang Kanan Lintas Sumatera) menuju simpul C (Jl. KH. Azhari Belok Kiri) (Jl. KH. Azhari Belok Kiri) menuju simpul D (Jl. KH. Azhari Lurus) (Jl. KH. Azhari Lurus) menuju simpul E (Kampung Kapiten)
9,98 KM
No
1.
2.
3.
4.
jalan. Berdasarkan hasil analisa pada
Tanda Node Dilalui
terdapat
rute
jalan
yang
memungkinkan menuju lokasi tujuan restoran kampung kapiten dari lokasi asal kampus Bina Darma. Berikut
adalah hasil rute yang yang dapat dilihat pada gambar dibawah ini.
56 KM
5,4 KM
3,4 KM
4. HASIL DAN PEMBAHASAN 4.1 Pembahasan Perhitungan diterapkan
algoritma
pada
ini
analisa
akan
Gambar 4.1 Pengujian dari Universitas
kasus
Bina Darma Menuju Restoran Kampung Kapiten
pencaian rute terpendek menuju loksai tujuan
restoran
memanfaatkan mencari
jalan,
pada google jarak
peta maps dan
dengan untuk
Pada gambar 4.1, node A merupakan
langkah
lokasi asal kampus Bina Darma dan
menuju tujuan persimpangan dan ruas
node
R
merupakan
lokasi
tujuan
kampung kapiten, sedangkan node A-
Berikuti
B1-B2-B3-C-D-E,
bobotnya :
merupakan
nodes
yang memungkin menuju lokasi tujuan.
ini
1. Langkah
perhitungan
ke
1
penentuan
Titik
Awal
Keterangan pada gambar diatas dapat
Universitas Bina Darma ke Simpang
dilihat pada table di bawah ini.
Kanan Lintas Sumatera, Simpul A (Universitas Bina Darma) menuju
Tabel 4.1 Rute Yang Dilalui dari Universitas Bina Darma Menuju Restoran Kampung Kapiten No A
B1
B2 B3
C
D E
Nama Universitas Bina Darma Simpang Kanan Lintas Sumatera Lurus Taman Tugu Belok Kanan Jl. Gub. H Bastari Jl. KH. Azhari Belok Kiri Jl. KH. Azhari Lurus Kampung Kapiten
Titik Koordinat -2.999510, 104.77043
simpul B1 (Simpang Kanan Lintas Sumatera) A (-2.999510, 104.77043) ke B (2.999837, 104.768725) = 9,98 KM 2. Langkah
ke
2
Titik
Awal
Universitas Bina Darma ke Lurus
-2.999837, 104.768725
Taman Tugu, Simpul A (Universitas
-3.002640, 104.764891
Lurus Taman Tugu)
-3.006757, 104.773546 -2.994318, 104.765046
Bina Darma) menuju simpul B2 (ke
A (-2.999510, 104.77043) ke B (3.002640, 104.764891) = 20 KM 3. Langkah
ke
3
Titik
Awal
Universitas Bina Darma ke Belok -2.995547, 104.764102 -2.994121, 104.762674
Kanan Jl. Gub. H Bastari, Simpul A (Universitas Bina Darma) menuju simpul B3 (Belok Kanan Jl. Gub. H Bastari)
A (-2.999510, 104.77043) ke B3 (-
4.2 Hasil
3.002640, 104.764891) = 14,5 KM 4. Langkah ke 4 Titik Simpang Kanan
Hasil dari pembuatan perangkat lunak
ini
adalah
halaman-halaman
Lintas Sumatera ke Jl. KH. Azhari
informasi yang nantinya dijalankan
Belok Kiri, Simpul B1 (Simpang
dengan
Kanan Lintas Sumatera) menuju
smartphone android. Adapun tampilan
simpul C (Jl. KH. Azhari Belok
perangkat lunak ini memiliki sub-sub
Kiri)
menu sebagai berikut :
B1 (-2.999837, 104.768725) ke C (-
4.2.1 Tampilan Index
2.994318, 104.765046) = 56 KM 5. Langkah ke 5 Jl. KH. Azhari Belok
menggunakan
borwser
dan
Tampilan index merupakan menu yang
ditampilkan lunak
saat
pertamakali
Kiri ke Jl. KH. Azhari Lurus,
perangkat
dibuka
melalui
Simpul C (Jl. KH. Azhari Belok
Android. Pada tampilan ini memiliki 3
Kiri) menuju simpul D (Jl. KH.
pilihan menu yang terdiri dari menu
Azhari Lurus)
petunjuk, restoran dan keluar.
A (-2.994318, 104.765046) ke B (2.995547, 104.764102) = 5,4 KM 6. Langkah ke 6 Jl. KH. Azhari Lurus ke Kampung Kapiten, Simpul D (Jl. KH. Azhari Lurus) menuju simpul E (Kampung Kapiten) A (-2.995547, 104.764102) ke B (2.994121, 104.762674) = 3,4 KM
Gambar 4.2 Halaman Index
yang ingin di tujuh dan melihat rute dan
4.2.2 Tampilan Menu Petunjuk Pada tampilan menu petunjuk akan
simulasinya.
ditampilkan bila pengguna memilih menu petunjuk pada perangkat lunak, menu ini akan menampilkan informasi petunjuk yang sudah diinputkan oleh admin pada server.
Gambar 4.4 Tampilan Menu Restoran
4.2.4 Tampilan Peta Restoran Tapmilan
peta
restoran
akan
ditampilkan bila pengguna memilih Gambar 4.3 Tampilan Menu
salah satu restoran pada perangkat lunak untuk
Petunjuk
restoran.
restoran
Dan
akan
rute
menuju
menampilkan
informasi simulasi algoritma dijkstra
4.2.3 Tampilan Menu Restoran Menu
menampilkan
akan
ditampilkan bila pengguna memilih menu restoran pada perangkat lunak. Disini pengguna dapat memilih restoran
untuk menampilkan jalur jalan yang akan diikuti.
Gambar 4.5 Universitas Bina Darma
Gambar 4.6 Tampilan Si mulasi Algoritma Dijkstra
Menuju Restoran Kampung Kapiten
4.2.5 Tampilan Simulasi Algoritma
5. Kesimpulan Dari keseluruhan bab diatas,
Dijkstra Halaman simulasi restoran akan
hasil
penelitian
penulis
yang
ditampilkan bila pengguna memilih
dilakukan pada Pencarian Lintasan
simulasi restoran pada perangkat lunak.
Terpendek
Disini akan menampilkan informasi
Restoran
jarak setiap rute yang dilewati. Sebagai
Menggunakan
contoh Rute awal Universitas Bina
Berbasis Android serta pembahasan
Darma
yang dilakukan oleh penulis maka
Kapiten.
menuju
Restoran
Kampung
Untuk Di
Kota
Menentukan Palembang
Algoritma
Dijkstra
dapat diambil kesimpulan bahwa : 1. Hasil Penelitian ini berupa sebuah perangkat
lunak
yang
dapat
digunakan untuk menentukan rute
smartphone
terpendek menuju lokasi restoran
System Android.
yang
ada
sehingga
dikota
pengguna
dalam mencari jalur terdekat untuk lokasi
restoran
yang
diinginkan. 2. Perangkat lunak ini dikembangkan dengan
menggunakan
algoritma
Dijkstra dalam menentukan rute terpendek menuju lokasi tujuan dan menggunakan
metode
pengembangan proses
waterfall
pengembangan
dalam
perangkat
phonegap, MySQL
DAFTAR PUSTAKA A.S Rosa dan Salahuddin M, 2011. Modul Pembelajaran Rekayasa Perangkat Lunak (Terstruktur dan Berorientasi Objek), Modula, Bandung Bernhardsen, T. 2009. Geographic Information Systems: An Introduction, 3rd Edition. John Wiley & Sons Ltd. Canada Irawan, 2009. aplikasi java mobile, Maxikom, Palembang. Mohapatra, P.K.J(2010). Software Engineering-A Lifecycle Approach. New Delhi: New Age International Publishers Pvt td Munir,
lunak. 3. Bahasa
pemrograman javascript, dipilih
library PHP
karena
dan
alasan
kompatibilitas, yaitu menyesuaikan dengan aplikasi lain yang telah lebih dahulu beroperasi. 4. Perangkat disimulasikan
lunak pada
Operating
Palembang,
membantu
menuju
berbasis
ini
dapat perangkat
Rinaldi,2005. “Matematika Diskrit”. Bandung: Informatika Bandung. http://www.scribd.com/doc/2774 5962/Microsoft-Access-2007, dikunjungi terakhir pada tanggal 22 agustus 2011, pukul 7.36 WIB.
Simarmata. Janner (2010), Rekayasa Perangkat Lunak, Andi Offset, Yogyakarta Suarthana. 2006. Manajemen Perhotelan Edisi Kantor Depan. Kuta Utara: Mapindo. Safaat
H. 2012 (Edisi Revisi). Pemograman Aplikasi Mobile
Smartphone dan Tablet PC Berbasis Android. Informatika. Bandung. Sommerville, Ian. 2011. Software Engineering (Rekayasa Perangkat Lunak). Jakarta: Erlangga. Supardi.2005. “Metodologi Penelitian Ekonomi dan Bisnis”. Yogyakarta:UII Press Rosa dan Salahuddin M, 2011. “Modul Pembelajaran Rekayasa Perangkat Lunak (Terstruktur dan Berorientasi Objek)”. Modula, Bandung Wisnu. “Aplikasi Peta Mobile untuk pencarian jalur terpendek pada operasi android”. Yogyakarta : Ilmu Komputer FMIPA UGM, 2010
