Wednesday, May 16, 2018

PENCARIAN RUTE TERPENDEK DENGAN MENGGUNAKAN ALGORITMA BELLMAN-FORD





“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: