Penerapan Algoritma Bellman-Ford untuk Penentuan Rute Terpendek Objek Wisata di Kabupaten Lamongan Layla Hidayatus Sholikah Program Studi Matematika.
FMIPA.
Universitas Islam Darul AoUlum Lamongan, 2020@mhs.
Abstract.
In conducting a trip, the shortest route is always a priority so that the trip is more efficient both in terms of time and cost.
In the field of Graph Theory, there are several algorithms that can be applied to get the shortest route, one of which is the Bellman-Ford algorithm.
This research applies the Bellman-Ford Algorithm to find the shortest route to tourist attractions in Lamongan Regency.
The tourist destinations studied were 17 and divided into two groups of northern and southern From the two groupings, two weighted and directed graph models with the shortest route were obtained.
Both can be used as shortest route recommendations for tourists who will visit tourist attractions in Lamongan Regency.
Keywords: Bellman-Ford algorithm, shortest route, graph theory, tourist attraction.
Lamongan district Abstrak.
Dalam melakukan sebuah perjalanan, rute terpendek selalu menjadi prioritas agar perjalanan lebih efisien baik dari segi waktu maupun biaya.
Pada bidang Teori Graf, ada beberapa algoritma yang bisa diterapkan untuk mendapatkan rute terpendek, salah satunya adalah algoritma Bellman-Ford.
Penelitian ini menerapkan Algoritma Bellman-Ford untuk mencari rute terpendek pada objek wisata di Kabupaten Lamongan.
Destinasi objek wisata yang diteliti sebanyak 17 dan dibagi menjadi dua kelompok wilayah utara dan selatan.
Dari dua pengelompokan tersebut diperoleh dua model graf berbobot dan berarah dengan rute terpendek.
Keduanya bisa digunakan sebagai rekomendasi rute terpendek bagi wisatawan yang akan mengunjungi objek wisata di Kabupaten Lamongan.
Kata kunci: Algoritma Bellman-Ford, rute terpendek, teori graf, objek wisata, kabupaten Lamongan Pendahuluan Lamongan merupakan salah satu kabupaten yang berada di Provinsi Jawa Timur yang wilayahnya membentang dari selatan berbatasan dengan kabupaten Mojokerto dan pada bagian utara menyisir pantai utara .
Lamongan mempunyai beragam objek wisata baik itu wisata alam, wisata buatan maupun wisata religi.
Dengan potensi wisata yang dimilikinya.
Lamongan memiliki peluang yang besar untuk menjadi tujuan utama destinasi wisata bagi wisatawan.
Berdasarkan data dinas pariwisata di kabupaten lamongan dalam website Lamongan megilan, jumlah wisatawan mengalami penurunan dimulai pada tahun 2020 sebanyak 610.
410 dikarenakan pandemi.
Selanjutnya menunjukkan peningkatan di tahun 2022 sebanyak 4.
418 wisatawan.
Secara geografis, objek wisata yang ada di Lamongan menyebar di beberapa tempat, sehingga untuk mengunjungi beberapa objek dibutuhkan perencanaan dan waktu yang tepat.
Ada banyak rute yang bisa dipilih, akan tetapi wisatawan pasti menginginkan rute tercepat untuk menuju lokasi wisata demi efisiensi waktu, tenaga dan biaya.
Untuk itu, pencarian rute terpendek menuju tempat wisata menjadi salah satu prioritas utama bagi wisatawan dalam menentukan rute, agar banyak destinasi bisa dikunjungi dalam suatu waktu yang telah ditentukan.
Teori graf merupakan ilmu matematika yang membahas tentang objek diskrit dan konektivitas .
antara objek satu dengan objek lainnya .
Teori Graf dapat digunakan dalam pemecahan masalah rute terpendek dengan menggunakan berbagai macam algoritma, diantaranya adalah algoritma Bellman-Ford, algoritma Dijkstra dan algoritma Floyd Warshall.
Algoritma Bellman-Ford merupakan algoritma yang dapat digunakan untuk mencari rute terpendek dalam suatu lintasan.
Sebagaimana algoritma Dijkstra dan algoritma Floy Warshall.
Algoritma BellmanFord dapat digunakan untuk sisi-sisi yang berbobot negatif namun tidak diperbolehkan memiliki siklus negatif .
Teori-teori yang berhubungan dengan hal tersebut telah banyak dikembangkan dengan berbagai algoritma yang memiliki kelebihan dan kekurangan masing-masing .
Dalam penelitian ini akan dianalisis rute dan jarak terpendek dalam menemukan rute objek wisata di Kabupaten Lamongan dengan menggunakan algoritma Bellman-Ford.
Algoritma Bellman-Ford merupakan algoritma yang dapat digunakan dalam menghitung jarak terpendek dari satu sumber pada sebuah graf berbobot.
Algoritma Bellman-Ford menggunakan ycc .
sebagai batas atas dan jarak ycc.
c, y.
dari u ke v.
Algoritma Bellman-Ford melakukan inisialisasi jarak titik awal menjadi nol dan semua titik tujuan menjadi tak hingga .
Landasan Teori Graf Graf adalah suatu cabang matematika yang mempelajari hubugan himpunan tidak kosong yang memuat elemen-elemen yang disebut titik dan suatu daftar pasangan elemen itu yang disebut sisi .
Teori graf merupakan ilmu matematika yang membahas tentang objek diskrit dan konektivitas .
antara objek satu dengan objek lainnya.
Graf (G) didefinisikan sebagai pasangan dari titik set (V) dan sisi (E) yang ditulis menggunakan notasi G = (V,E), dimana V adalah himpunan simpul dan E merupakan sisi dari himpunan yang menghubungan sepasang simpul .
Dari definisi tersebut dapat disimpulkan bahwa graf adalah sekumpulan simpul yang dihubungkan oleh sisi-sisi.
Berikut pada Gambar 1 ditampilkan visualisasi dari sebuah graf.
Gambar 1.
Graf Graf Berbobot Graf berbobot adalah graf yang setiap sisinya memiliki sebuah harga .
Bobot pada tiap garis menginterpretasikan makna yang berbeda tergantung pada masalah yang dimodelkan.
Bobot dapat menyatakan jarak anatara dua tiang listrik, kapasitas, biaya perjalanan anatar dua kota, waktu tempuh pesan dari sebuah titik komunikasi ke titik lainnya, bahkan ongkos dan produksi.
Secara umum, gambaran dari graf berbobot dapat dilihat pada Gambar 2.
Gambar 2.
Graf berbobot Graf Berarah (Directed Gra.
Graf berarah merupakan graf yang setiap sisinya diberikan orientasi arah.
Sisi yang memiliki arah disebut busur .
Pada graf berarah .
cO, y.
a, ycO) menyatakan dua busur yang berbeda, sehingga .
cO, y.
O .
a, ycO).
Pada graf berarah terdapat gelang .
tetapi tidak diperbolehkan sisi ganda .
Beberapa Pengertian dalam graf berarah :
Derajat ke luar .
ut degre.
suatu titik adalah banyaknya ruas yang mulai/ keluar dari titik tersebut.
Derajat masuk .
n degre.
suatu titik adalah banyaknya ruas yang berakhir/ masuk ke titik tersebut.
Titik berderajat ke dalam = 0 disebut sumber .
, sedangkan titik berderajat ke luar = 0 disebut muara .
Pengertian Walk.
Trail.
Path (Jalu.
dan Sirkuit (Cycl.
berlaku pula pada graf berarah, dimana harus sesuai dengan arah ruas.
Kalau tidak sesuai dengan arah ruas-nya, maka disebut sebagai semi walk, semi path atau semi trail.
Algoritma Bellman-Ford Algoritma ini dikembangkan oleh Richard Bellman and Lester Ford.
Jr.
Algoritma ini sangat mirip dengan Algortima Dijkstra namun algortima ini mampu menangani bobot negatif pada pencarian jalur terpendek pada sebuah graf berbobot.
Algoritma Bellman-Ford merupakan pengembangan dari Algoritma Dijkstra.
Algortima Bellman-Ford akan benar jika dan hanya jika graf tidak terdapat cycle dengan bobot negatif yang dicapai dari sumber .
Secara umum langkah Ae langkah algoritmanya adalah sebagai berikut :
Tentukan vertex source dan daftar seluruh vertices maupun edges.
Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite.
Mulailah iterasi terhadap semua vertices yang berhubungan dengan vertex source dengan formula sebagai berikut ini:
- ycO = Vertex asal - ycO = Vertex tujuan - ycOycO = Edges yang menghubungkan ycO dan ycO - Jika idistance ycO, lebih kecil dari distance ycO Weigh ycOycO maka idistance ycO, diisi dengan idistance ycO iweigh ycOycO - Lakukan hingga semua vertex terjelajahi.
Metode Pada kasus ini, metode yang digunakan mengikuti langkah-langkah berikut:
Pengumpulan Data Data yang digunakan dalam penelitian ini adalah data objek wisata di Kabupaten Lamongan yang terdiri dari 17 objek wisata dan tersebar diseluruh wilayah Kabupaten Lamongan.
Berikut data yang kami gunakan sebagaimana pada Tabel 1.
Tabel 1.
Data Obyek Wisata Di Kabupaten Lamongan Nama Objek Wisata Lokasi Pantai Kutang Pohon Trinil Tlogo Sadang Wisata Bahari Lamongan Makam Sunan Drajat Pantai Putri Klayar Pemandian Air Panas Brumbung Alun-Alun Lamongan Kentong.
Labuhan.
Kec.
Brondong Lembor.
Kec.
Brondong Desa Bluri.
Kecamatan Solokuro Jl.
Raya Paciran.
Paciran.
Kec.
Paciran Dusun Drajat.
Desa Drajat.
Kecamatan Paciran Klayar.
Sidokelar.
Kec.
Paciran Tepanas.
Kranji.
Kec.
Paciran Jl.
Lamongrejo.
Tumenggungan.
Kec.
Lamongan No Nama Objek Wisata Lokasi Jl.
Raya Mantup KM.
Sanur.
Jotosanur.
Kec.
Tikung Jl.
Raya Waduk Gondang.
Juwet.
Deketagung.
Kec.
Sugio Desa Tugu.
Kecamatan Mantup Gondang Lor.
Sugio Karang Asem.
Karangkembang.
Kec.
Babat Area Sawah/ Hutan.
Sekidang.
Kec.
Sambeng JL.
Raya.
Paciran.
Kec.
Paciran Desa Sendang Duwur.
Paciran Jl.
Raya Paciran.
Paciran.
Kec.
Paciran Masjid Namira Wego Gunung Mas Mantup Waduk Gondang Gunung Pegat Gunung Ratu Goa Maharani Desa Sendang Duwur Tanjung Kodok Pemodelan Graf Dari Data Objek Wisata Data pada Tabel 1 selanjutnya akan dibentuk menjadi graf berbobot yang memiliki arah.
Bobot menunjukkan jarak antar obyek wisata, sementara arah merupakan visualisasi dari titik asal menuju titik lokasi yang dituju.
Graf dibuat dengan menentukan titik disetiap jalur dan menentukan pasangan tiap sisi yang saling terhubung.
Dalam penelitian ini rute objek wisata akan dibagi menjadi dua kelompok karena jarak tiap objek wisata letaknya sangat berjauhan sehingga tidak efisien jika di modelkan dalam satu model graf.
Dua kelompok tersebut membagi objek wisata Lamongan pada bagian utara dan Lamongan bagian selatan.
Perhitungan Menggunakan Algoritma Bellman-Ford Dua kelompok destinasi wisata yang telah terbentuk kemudian dilakukan perhitungan untuk menentukan rute terpendek menggunakan Algoritma BellmanFord.
Hasil dan Pembahasan Model Graf 1 (Objek Wisata Bagian Utar.
Pada model graf 1 terdiri dari 10 titik objek wisata di Kabupaten Lamongan .
agian utar.
, dimana setiap objek wisata masing-masing dilambangkan dengan yc1 , yc2 .
A , yc10 yang ditunjukkan pada Tabel 2.
Tabel 2.
Titik Objek Wisata Kabupaten Lamongan Graf 1 Titik ycO1 ycO2 ycO3 Nama Tempat Wisata Pantai Kutang Pohon Trinil Tlogo Sadang Titik ycO4 ycO5 ycO6 ycO7 ycO8 ycO9 ycO10 Nama Tempat Wisata Wisata Bahari Lamongan Makam Sunan Drajat Pantai Putri Klayar Pemandian Air Panas Brumbung Goa Maharani Desa Sendang Duwur Tanjung Kodok Gambar 4.
Visualisasi rute Graf 1 Pada Gambar 4 terlihat hasil graf dari 10 titik objek wisata di Kabupaten Lamongan .
agian utar.
dimana sisi yang memiliki nilai bobot tertinggi .
c1 , yc3 ) dan sisi yang memiliki nilai terendah adalah .
c6 , yc7 ) dan seterusnya.
Model Graf 2 (Objek Wisata Bagian Selata.
Pada model graf 2 terdiri dari 10 titik objek wisata di Kabupaten Lamongan .
agian selata.
dimana setiap objek wisata masing-masing dilambangkan dengan yc11 , yc12 .
A , yc20 yang ditunjukkan pada Tabel 3.
Tabel 3.
Titik Objek Wisata Kabupaten Lamongan Graf 2.
ycO11 ycO12 ycO13 ycO14 ycO15 Nama Tempat Wisata Alun-Alun Lamongan Masjid Namira Wego Gunung Mas Mantup Waduk Gondang indeks Nama Tempat Wisata ycO16 Gunung Pegat ycO17 Gunung Ratu Gambar 5.
Visualisasi rute Graf 2 Pada Gambar 5 terlihat hasil graf dari 10 titik objek wisata di Kabupaten Lamongan .
agian selata.
dimana sisi yang memiliki nilai bobot tertinggi .
c11 , yc.
dan sisi yang memiliki nilai terendah adalah .
c12, yc13 ) dan seterusnya.
Penerapan Algoritma Bellman-Ford Selanjutnya pada bagian ini Algoritma Bellman-Ford diterapkan sesuai dengan data riil yang ada di lapangan.
Perhitungan Rute Terpendek Pada Graf 1 Pada gambar nilai yc1 adalah titik awal dan diasumsikan pada graf 2 terdapat 10 titik.
Langkah-langkah untuk menentukan rute terpendek menggunakan algoritma Bellman-Ford dilakukan dengan proses iterasi.
Proses iterasi terhadap setiap titik yang dilalui adalah:
Iterasi 1 ycO1 Ie ycO2 = 0 11000 = 11000 ycO1 Ie ycO3 = 0 32000 = 32000 Iterasi 2 ycO2 Ie ycO4 = 11000 28000 = 39000 ycO3 Ie ycO5 = 32000 4200 = 35200 ycO3 Ie ycO6 = 32000 450 = 32450 Iterasi 3 ycO4 Ie ycO10 = 39000 7100 = 46100 ycO5 Ie ycO8 = 35200 6400 = 41600 ycO6 Ie ycO7 = 32450 300 = 32750 Iterasi 4 ycO7 Ie ycO9 = 32750 11000 = 43750 Tabel 4.
Hasil Perhitungan Rute Terpendek Graf 1.
Titik Tujuan V10
Lintasan Terpendek V1-V2
V1-V3
V1-V2-V4
V1-V3-V5
V1-V3-V6
V1-V3-V5-V8
V1-V3-V6-V7
V1-V3-V6-V7-V9
V1-V2-V4-V10
Jarak .
Pada tabel 5 ditunjukkan hasil perhitungan dari proses iterasi menggunakan algoritma Bellman-Ford dalam mencari rute terpendek graf 1, terdapat 9 lintasan terpendek yang dimulai dari lintasan yc1 yang dapat digunakan untuk rekomendasi objek wisata yang memiliki jarak terpendek di Kabupaten Lamongan bagian utara, yaitu pantai kutang .
c1 ) Ae pohon trinil .
c2 ) dengan jarak 11000 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) dengan jarak 32000 m, pantai kutang .
c1 ) Ae pohon trinil .
c2 ) Ae wisata Bahari lamongan .
c4 ) dengan jarak 39000 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) Ae makam sunan drajat .
c5 ) dengan jarak 35200 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) Ae pantai putri klanyar .
c6 ) dengan jarak 32450 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) Ae makam sunan drajat .
c5 ) Ae goa maharani .
c8 ) dengan jarak 41600 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) Ae pantai putri klanyar .
c6 )- pemandian air panas brumbung .
c7 ) dengan jarak 32750 m, pantai kutang .
c1 ) Ae tlogo sadang .
c3 ) Ae pantai putri klanyar .
c6 ) - pemandian air panas brumbung .
c7 ) - desa sendang duwur .
c9 ) dengan jarak 43750 m, pantai kutang .
c1 ) Ae pohon trinil .
c2 ) Ae wisata Bahari lamongan .
c4 ) Ae tanjung kodok .
dengan jarak 46100 m.
Perhitungan Rute Terpendek Pada Graf 2 Pada gambar nilai yc11 adalah titik awal.
Langkah-langkah untuk menentukan rute terpendek menggunakan algoritma Bellman-Ford dilakukan dengan proses Proses iterasi terhadap setiap titik yang dilalui :
Iterasi 1 ycO11 Ie ycO17 = 0 33000 = 33000 ycO11 Ie ycO12 = 0 22000 = 22000 ycO11 Ie ycO13 = 0 19000 = 19000 Iterasi 2 ycO17 Ie ycO16 = 33000 3900 = 36900 ycO12 Ie ycO14 = 22000 24000 = 46000 ycO13 Ie ycO15 = 19000 3500 = 22500 Tabel 5.
Hasil Perhitungan Rute Terpendek Graf 2.
Titik Tujuan V17
V12
V13
V16
V14
V15
Lintasan Terpendek V11-V17
V11-V12
V11-V13
V11-V17-V16
V11-V12-V14
V11-V13-V15
Jarak .
Pada tabel 5 ditunjukkan hasil perhitungan dari proses iterasi menggunakan algoritma Bellmon-Ford dalam mencari rute terpendek graf 2, terdapat 6 lintasan terpendek yang dimulai dari lintasan yc11 yang dapat digunakan untuk rekomendasi untuk mencari jalur terpendek dalam objek wisata di Kabupaten Lamongan bagian selatan, yaitu alun-alun lamongan .
c11 ) Ae gunung ratu .
c17 ) dengan jarak 33000 m, alun-alun lamongan .
c11 ) Ae masjid namira .
c12 ) dengan jarak 22000 m, alun-alun lamongan .
Ae wego .
c13 ) dengan jarak 19000 m, alun-alun lamongan .
c11 ) Ae gunung ratu .
c17 ) Ae gunung pegat .
c16 ) dengan jarak 36900 m, alun-alun lamongan .
c11 ) Ae masjid namira .
c12 ) Ae gunung mas mantup .
c14 ) dengan jarak 46000 m, alun-alun lamongan .
c11 ) Ae wego .
c13 ) Ae waduk gondang .
c15 ) dengan jarak 22500 Dari hasil pembahasan dapat disimpulkan bahwa algoritma Bellman-Ford dapat digunakan untuk mencari rute terpendek dari satu titik ke titik lainnya.
Kesimpulan Berdasarkan hasil dari pembahasaan, dalam mencari rute terpendek menuju objek wisata di Kabupaten Lamongan menggunakan algoritma Bellman-Ford.
Dari 17 lokasi objek wisata dikelompokkan menjadi 2 model graf, dihasilkan 9 lintasan terpendek pada objek wisata di Kabupaten Lamongan pada bagian utara dan 6 lintasan terpendek pada bagian Selatan yang dapat digunakan sebagai rekomendasi pencarian rute terpendek dalam objek wisata di Kabupaten Lamongan.
Daftar Pustaka