“PENCARIAN RUTE TERPENDEK DENGAN
MENGGUNAKAN ALGORITMA BELLMAN-FORD”
(Studi kasus pada kunjungan wisata di Kabupaten Jember)
BAB I
PENDAHULUAN
1.1
Latar Belakang Penelitan
Kabupaten Jember merupakan tempat
tujuan wisata yang banyak diminati wisatawan domestik maupun mancanegara.
Keindahan alam, keunikan budaya, keamanan, kenyamanan, keramah-tamahan yang
dimiliki, merupakan faktor penyebab kenapa orang ingin menghabiskan liburan di
Jember. Bahkan menurut Jakarta, CNN Indonesia --, Jember Fashion Carnival (JFC)
semakin memesona. Karnaval itu kian meneguhkan posisinya sebagai karnaval
terbaik di Tanah Air. JFC bahkan sudah diakui sebagai event
yang ada di peringkat ketiga karnaval terbesar di dunia.
Selain JFC, Tempat-tempat wisata di Kabupaten Jember tersebar di
berbagai penjuru Jember. Untuk menuju ke tempat wisata, ada beberapa rute yang
bisa ditempuh. Wisatawan pastinya menginginkan jalur yang paling efisien untuk
menuju tempat wisata tujuan sehingga dapat menghemat waktu dan biaya. Tentunya
masih banyak para wisatawan tidak mengetahui jalur-jalur untuk mengakses tempat
wisata di Jember.
Sebuah media yang sangat berkembang saat ini adalah Internet. Lewat
internet, informasi bisa disampaikan secara cepat, luas, dapat diakses oleh
siapa saja dan dimana saja. Berbagai informasi bisa didapatkan dari internet
mulai dari informasi tentang pendidikan, kesehatan, hiburan, keadaan suatu
wilayah, dan lain-lain. Berkaitan dengan hal wilayah, terdapat beberapa
aplikasi yang sudah ada di internet. Misalnya jika ingin mengetahui lokasi
suatu tempat di Jember, bisa menggunakan fasilitas search yang ada pada google
earth atau google maps. Sistem yang seperti ini disebut sistem informasi
geografis.
Dengan memanfaatkan keunggulan internet ini, sebuah sistem
informasi geografis akan
dikembangkan
untuk mengatasi persoalan pencarian rute terpendek dari dan menuju suatu tempat
wisata di Bali. Sistem ini nantinya diharapkan dapat membantu untuk mencari
rute terpendek dari dan menuju suatu tempat wisata di Bali. Proses pencarian
rute unruk menentukan lintasan terpendek salah satunya adalah dengan menggunakan
algoritma Bellman-Ford, algoritma
ini dapat digunakan dalam graf untuk bobot yang dapat bernilai positif ataupun
bernilai negatif dan digunakan dalam graf berarah saja. Hasil akhir yang
ditampilkan sistem adalah informasi rute jalan yang harus dilalui, jarak yang
ditempuh, dan peta Pariwisata Bali dengan berbasis vektor.
1.2
Rumusan Masalah
Memberikan informasi pada sesorang mengenai rute terpendek menuju
tempat wisata yang ada di Kabupaten Jember.
1.3
Tujuan dan Manfaat Penelitian
Berikut tujuan
dan manfaan yang akan dicapai dalam Penulisan ini.
1.3.1
Tujuan Penelitian
Tujuan
Penulisan ini adalah untuk mengeksplorasi terhadap metode dan masalah yang dipelajari dalam
pengembangan serta menyebarkan aplikasi yang mendukung materi optimasi, sebagai
media untuk berbagi informasi hasil-hasil pemikiran dan penelitian dan sebagai
referensi untuk penyelesaian masalah rute (lintasan) terpendek supaya bisa
diperoleh hasil yang optimal.
1.3.2
Manfaat Penelitian
1.
Diharapkan dapat
membantu menentukan rute terpendek pencarian tempat wisata di Kabupaten Jember
2.
Diharapkan dijadikan
sebagai dasar untuk penelitian selanjutnya.
3. Dapat
meningkatkan keiilmuan yang sudah ada
BAB
II TINJAUANPUSTAKA
2.1 Penelitan Terdahulu
Peneleitian terdahulu dilakukan
dengan menerapkan metode algoritma BELLMAN-FORD yaitu dengan judul “PENCARIAN
LINTASAN TERPENDEK DENGAN MENGGUNAKAN ALGORITMA BELLMAN-FORD(Studi kasus
pada kunjungan wisata di Kabupaten dan Kota Probolinggo)” yang dilakukan oleh Amalia Dwi Wardani jurusan Matematika –
Fakultas Matematika dan Ilmu Pengetahuan Alam.
PENENTUAN JALUR
TERPENDEK MENUJU CAFE DI KOTA MALANG MENGGUNAKAN METODE BELLMAN-FORD DENGAN
LOCATION BASED SERVICE BERBASIS ANDROID M.Rofiq, Riza Fathul Uzzy STMIK ASIA
Malang
2.2 Algoritma Bellman-Ford
Algoritma
Bellman-Ford adalah algoritma untuk menghitung jarak terpendek (dari satu
sumber) pada sebuah digraf berbobot. Maksudnya dari satu sumber ialah bahwa ia
menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma
Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada
sisi(edge) yang berbobot negatif . Maka Algoritma Bellman-Ford hanya digunakan
jika ada sisi berbobot negatif.
Keunggulan lain
yang membuat algoritma ini lebih baik dari algoritma lainnya yaitu algoritma
ini memungkinkan bobot pada sisi yang menghubungkan antara dua simpul berupa
bilangan negatif. Hal tersebut seperti dijelaskan oleh contoh di bawah ini.
Gambar Salah
satu contoh graf dengan sisi bernilai negatif.
Dalam algoritma Bellman-Ford, apabila ingin dicari
lintasan dengan bobot paling sedikit dari satu ke dua, maka lintasannya adalah
1-4-3-2, sehingga bobot yang didapat adalah 7 -3 -2 = 2. Berikut akan disajikan
algoritma umum dari Bellman-ford dalam notasi matematika :
M [i,v] = min(
M [i-1,v] , ( M [i-1,n]+ Cvn))
i = iterasi, v = vertex = node, n = node neighbor, C = cost
Sebelum memulai
perhitungan dan penganalisaan, terlebih dahulu yang harus dilakukan adalah
menamai setiap simpul dan memberikan bobot dari tiap sisi. Untuk sisi pada graf
tak berarah harus mendefinisikannya sebanyak 2 kali, yakni dari titik pertama
ke titik kedua dan sebaliknya dengan nilai yang sama. Namun, apabila yang akan
diimplementasikan adalah suatu graf yang berarah maka cukup dengan
mendefinisikannya sebanyak satu kali sesuai dengan arah graf.
Langkah pertama
yang harus dilakukan dalam analisis graf menggunakan algoritma Bellman-Ford
adalah menentukan titik asal setelah menetapkan titik asal dari lintasan,
lalu melakukan penandaan simpul(marking). Dalam hal ini, semua titik
yang bukan titik asal harus ditandai dengan infinity(∞). Titik asal sendiri,
sebagai titik pangkal dari lintasan yang akan dibentuk, ditandai dengan nol
(0).
Gambar Melakukan penandaan simpul.
Selanjutnya
melakukan relaxing pada simpul yang terdapat pada graf. Simpul yang di relaxing
adalah simpul selain simpul asal. Berikut adalah gambar yang menjelaskan
salah satu dari proses relaxing dari graf tersebut.
Gambar Relaxing tahap 1
Relaxing disini berarti
membandingkan bobot suatu titik, dalam hal ini telah ditandai dengan infinity,
dengan titik lain yang berada disekitarnya yang menghubungkannya dengan titik
asal. Dalam relaxing tahap 1 ditunjukkan bahwa simpul 2 langsung
diberikan bobot 6. Hal ini terjadi karena 6, besar bobot sisi yang
menghubungkan antara simpul asal dengan simpul 2, lebih kecil daripada nilai
sebelumnya, yakni infinity. Begitu pun yang terjadi pada simpul 4.
simpul 4 diberikan bobot 7 karena bobot sisi yang menghubungkan simpul 4 dengan
simpul asal adalah 7 yang dalam hal ini lebih kecil jika dibandingkan dengan
nilai sebelumnya (infinity).
Gambar Relaxing tahap 2
Dari gambar
diatas, simpul 3 bernilai 4 karena bobot simpul yang berhubungan dengan simpul
3 ditambah bobot sisi yang menghubungkannya yang paling kecil berasal dari
simpul 4 yang nilainya adalah 4 (hasil penjumlahan 7 -3 ). Simpul 5 bernilai 2
karena bobot hubungan terkecil yang dimilikinya adalah keterhubungan dengan
simpul 2 yakni 2(hasil penjumlahan 6 – 4).
Gambar
Relaxing tahap 3 dan tahap 4
2.3 Model Waterfall
Model waterfall merupakan metode yang
sistematik dan sekuensial yang mulai pada tingkat dan kemajuan sistem sampai
analisis, desain, kode, test dan
pemeliharaan.
BAB III METODE PENELITIAN
3.1
Tahapan
Penelitian
Rancangan menggunakan metode SDLC Waterfall disesuaikan
dengan sistem informasi penentuan rute terpendek pengiriman barang.
3.2
Tahapan
Analisis Kebutuhan
1.
Tahapan Pengumpulan Data
Teknik yang dilakukan dalam penelitian ini antara lain :
a.
Studi Pustaka
Penyusunan teori
b.
Studi Lapang
Melakukan pengumpulan data seperti pengumpulan
lokasi-lokasi melalui maps
2.
Tahapan Pengelolahan Data
Rancangan sistem yang dibuat.
3.3 Informasi/Objek
Penelitian
Kabupaten jember
adalah kabupaten yang berada di provinsi jawa timur indonesia yang beribukota di Jember.
Kabupaten ini berbatasan dengan Kabupaten
Probolinggo dan Kabupaten bodowoso di
utara, Kabupaten Banyuwangi di
timur, Samudera Hindia di selatan,
dan Kabupaten Lumajang di barat.
Kabupaten Jember terdiri dari 31 kecamatan. Kabupaten Jember terletak di
wilayah Tapal Kuda, Jawa Timur.
Kabupaten Jember
dibentuk berdasarkan Staatsblad Nomor 322 tanggal 9 Agustus 1928, yang mulai
berlaku tanggal 1 Januari 1929. Pemerintah Hindia Belanda telah mengeluarkan
ketentuan tentang penataan kembali pemerintah desentralisasi di wilayah Provinsi
Jawa Timur, antara lain dengan menunjuk Regenschap Djember sebagai masyarakat
kesatuan hukum yang berdiri sendiri. Secara resmi ketentuan tersebut
diterbitkan oleh Sekretaris Umum Pemerintah Hindia Belanda (De Aglemeene
Secretaris) G.R. Erdbrink, 21 Agustus 1928.
Jember memiliki luas 3.293,34 Km2 dengan
ketinggian antara 0 - 3.330 mdpl. Iklim Kabupaten Jember adalah tropis dengan
kisaran suhu antara 23oC - 32oC. Bagian selatan wilayah
Kabupaten Jember adalah dataran rendah dengan titik terluarnya adalah Pulau Barong. Pada kawasan ini
terdapat Taman Nasional Meru
Betiri yang
berbatasan dengan wilayah administratif Kabupaten Banyuwangi. Bagian barat laut (berbatasan dengan Kabupaten
Probolinggo adalah pegunungan, bagian dari Pegunungan Iyang,
dengan puncaknya Gunung Argopuro (3.088 m).
Bagian timur merupakan bagian dari rangkaian Dataran
Tinggi Ijen. Jember memiliki
beberapa sungai antara lain Sungai Bedadung yang bersumber dari Pegunungan
Iyang di bagian Tengah, Sungai Mayang yang persumber dari Pegunungan Raung di
bagian timur, dan Sungai Bondoyudo yang bersumber dari Pegunungan Semeru di
bagian barat.
Sumber :
LJE Dewi - Seminar Nasional Aplikasi
Teknologi Informasi (SNATI), 2010 - jurnal.uii.ac.id
PENENTUAN JALUR TERPENDEK MENUJU CAFE DI KOTA MALANG MENGGUNAKAN
METODE BELLMAN-FORD DENGAN LOCATION BASED SERVICE BERBASIS ANDROID M.Rofiq,
Riza Fathul Uzzy STMIK ASIA Malang
https://infojember/Kabupaten_Jember
No comments:
Post a Comment