## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359

## Implementasi Algoritma Branch and Bound Pada Aplikasi Mobile Pemandu Wisata Untuk Pengembangan UMKM Jawa Barat
Adi Sepriyadi * , Alun Sujjada, Somantri
Teknik Komputer dan Desain, Teknik Informatika, Universitas Nusa Putra, Sukabumi, Indonesia Email: 1 ,* adi.sepriyadi_ti20@nusaputra.ac.id, 2 alun.sujjada@nusaputra.ac.id, 3 somantri@nusaputra.ac.id Email Penulis Korespondensi: adi.sepriyadi_ti20@nusaputra.ac.id Submitted: 16/06/2024 ; Accepted: 26/06/2024 ; Published : 27/06/2024
Abstrak− Pariwisata  merupakan  sektor  ekonomi  krusial  di  Indonesia,  memberikan  kontribusi  signifikan  terhadap  pertumbuhan ekonomi dan  devisa  negara.  Pada  2022, jumlah  kunjungan  wisatawan  nusantara  mencapai 734,86 juta, naik 19,82% dari  tahun sebelumnya. Jawa Timur mencatat kunjungan terbanyak dengan 198,91 juta perjalanan, diikuti Jawa Barat (128,66 juta) dan Jawa Tengah (103,99 juta). Namun, destinasi wisata di Jawa Barat kurang dikenal karena kekurangan informasi, menghambat potensi pariwisata dan perkembangan UMKM setempat. Untuk mengatasi masalah ini, dikembangkan sebuah aplikasi pemandu berbasis Android yang mengintegrasikan informasi destinasi wisata dan UMKM di Jawa Barat. Aplikasi ini menggunakan algoritma Branch and  Bound  untuk  mempermudah  pemilihan  rute  terdekat  dari  lokasi  wisata  ke  beberapa  UMKM  dengan  efisien  dan  akurat. Penelitian  ini  mengidentifikasi  kurangnya  informasi  sebagai  hambatan  utama  pengembangan  pariwisata  di  Jawa  Barat. Pengembangan  dan  pengujian  aplikasi  menunjukkan  efektivitas  algoritma  Branch  and  Bound  dalam  menentukan  rute  terdekat. Implementasi aplikasi ini meningkatkan akses informasi wisata dan UMKM, serta pendapatan pelaku UMKM lokal yang terkait dengan pariwisata. Aplikasi diharapkan dapat berkontribusi positif terhadap pengembangan pariwisata dan UMKM di Jawa Barat serta menjadi model bagi pengembangan aplikasi serupa di daerah lain di Indonesia.
Kata Kunci: Pariwisata; UMKM; Rute Terdekat; Branch and Bound; Android
Abstract− Tourism is a crucial economic sector in Indonesia, contributing significantly to economic growth and foreign exchange. In 2022, the number of domestic tourist visits reached 734.86 million, up 19.82% from the previous year. East Java recorded the most visits with 198.91 million trips, followed by West Java (128.66 million) and Central Java (103.99 million). However, tourist destinations in West Java are less well known due to a lack of information, hampering tourism potential and the development of local MSMEs. To overcome this problem, an Android-based guide application was developed that integrates information on tourist destinations and MSMEs in West Java. This application uses the Branch and Bound algorithm to facilitate the selection of the closest route from tourist sites to several MSMEs efficiently and accurately. This research identifies the lack of information as the main obstacle to tourism development in West Java. Application development and testing showed the effectiveness of the Branch and Bound algorithm in determining the closest route. The implementation of this application increases access to tourist information and MSMEs, as well as the income of local MSME players related to tourism. The application is expected to contribute positively to the development of tourism and MSMEs in West Java and become a model for the development of similar applications in other regions in Indonesia.
Keywords : Tourism; MSME; Nearest Route; Branch and Bound; Android

## 1. PENDAHULUAN
Pariwisata  adalah  salah  satu  sektor  ekonomi  yang  paling  penting  dan  berkembang  pesat  di  Indonesia.  UU  No.  10 Tahun  2009  tentang  Kepariwisataan  diterbitkan  oleh  DPR  RI  untuk  mendorong  usaha  kecil  dan  menengah  dalam industri  pariwisata  berkelanjutan  [1].  Pembangunan  pariwisata  berkelanjutan,  seperti  disebutkan  dalam  Piagam Pariwisata  Berkelanjutan  (1995),  adalah  pembangunan  yang  dapat  didukung  secara  ekologis,  ekonomi,  etika,  dan sosial.  Ini  berarti  bahwa  pembangunan  pariwisata  harus  melestarikan  lingkungan,  membangun  infrastruktur  yang memenuhi kebutuhan wisatawan dan masyarakat tuan rumah, serta mengurangi dampak negatif terhadap masyarakat luas [2]. Pariwisata di Jawa Barat mencakup berbagai jenis daya tarik seperti budaya, alam, petualangan, bisnis, dan religius. Setiap jenis menawarkan daya tarik unik, mulai dari warisan budaya hingga keindahan alam dan aktivitas petualangan. Dengan pilihan yang beragam, pariwisata memenuhi berbagai minat dan kebutuhan wisatawan. Menurut Badan Pusat Statistik (BPS), jumlah kunjungan wisatawan nusantara di Indonesia pada 2022 mencapai 734,86 juta, naik  19,82%  dari  tahun  sebelumnya  (613,30  juta  kunjungan).  Jawa  Timur  adalah  provinsi  yang  paling  banyak dikunjungi dengan 198,91 juta perjalanan, diikuti oleh Jawa Barat (128,66 juta perjalanan) dan Jawa Tengah (103,99 juta perjalanan) [3].
Pada tahun 2023, target devisa dari kontribusi PDB pariwisata Indonesia adalah 4,1%. Provinsi Jawa Barat, dengan beragam destinasi wisata mulai dari pegunungan, pantai, hingga air terjun, menunjukkan potensi yang besar [4]. Namun, banyak destinasi wisata di sana belum dikenal wisatawan, termasuk dalam pemilihan rute terdekat saat merencanakan perjalanan  karena  kurangnya  informasi.  Hal  ini  menghambat  potensi  pariwisata  daerah  ini,  terbukti dari peringkat kedua Jawa Barat dalam jumlah kunjungan wisata, di bawah Jawa Timur. Kurangnya informasi juga mempengaruhi promosi dan perkembangan Usaha Mikro, Kecil, dan Menengah (UMKM) di sekitar destinasi wisata. UMKM (Usaha Mikro, Kecil, dan Menengah) adalah perusahaan kecil yang penting bagi ekonomi Indonesia. Undang- undang  dan  lembaga  seperti  Kementerian  Koperasi  dan  UKM,  BPS,  Keputusan  Menteri  Keuangan  No. 316/KMK.016/1994,  serta  UU  No.  20  Tahun  2008  menegaskan  peran  vital  UMKM  dalam  ekonomi  nasional  [5]. UMKM  merupakan  bagian  penting  dari  pengalaman  wisata,  namun  sulit  untuk  berkembang  karena  kurangnya eksposur dan akses informasi.

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Penelitian  ini  sangat  penting  karena  sektor  pariwisata  di  Indonesia  memiliki  kontribusi  signifikan  terhadap pertumbuhan ekonomi dan devisa negara. Jawa Barat, sebagai salah satu provinsi dengan potensi pariwisata besar, masih memiliki banyak destinasi wisata yang kurang dikenal karena kurangnya informasi. Pengembangan aplikasi Chillgo bertujuan untuk mengatasi masalah ini dengan menyediakan informasi lengkap mengenai destinasi wisata dan UMKM  di  Jawa  Barat.  Hal  ini  diharapkan  dapat  meningkatkan  promosi  pariwisata,  membantu  wisatawan  dalam merencanakan  perjalanan,  dan  mendukung  perkembangan  UMKM  lokal  yang  berperan  penting  dalam  ekonomi regional.
Untuk mengatasi permasalahan ini, telah dikembangkan aplikasi Chillgo,  proses pengembangannya dimulai dari mengidentifikasi kurangnya informasi dan kesulitan menemukan rute terdekat ke destinasi wisata dan UMKM di Jawa  Barat.  Data  dikumpulkan  melalui  observasi,  wawancara,  dan  studi  pustaka.  Kebutuhan  perangkat  keras, perangkat lunak, dan dataset dianalisis untuk mengembangkan aplikasi. Analisis manual algoritma Branch and Bound dilakukan untuk menentukan rute terdekat dengan efisien. Aplikasi Chillgo kemudian dikembangkan dengan fitur- fitur  yang  diperlukan,  seperti  antarmuka  pengguna  dan  integrasi  layanan  GPS.  Implementasi  algoritma  dan  fitur aplikasi dilakukan, diikuti dengan pengujian untuk memastikan fungsionalitas dan pemenuhan kebutuhan pengguna. Dengan proses ini, Chillgo diharapkan menjadi solusi efektif untuk masalah informasi dan rute wisata di Jawa Barat, serta  memberikan  dampak  positif  bagi  pengembangan  pariwisata  dan  UMKM  di  daerah  tersebut.  Sehingga menghasilkan  aplikasi  pemandu  wisata  berbasis  Android  yang  mengintegrasikan  informasi  destinasi  wisata  dan UMKM di Provinsi Jawa Barat. Android, sebagai sistem operasi telepon berbasis Linux untuk smartphone dan tablet, memungkinkan pengembangan aplikasi tanpa biaya tambahan. Gratis dan open source, Android menjadi pilihan yang dominan dan terjangkau di pasar smartphone serta dapat menggunakan layanan GPS melalui Google Maps Service [6]. Google Maps Service adalah layanan peta online gratis dari Google yang menyediakan data geografis global dan opsi rute perjalanan. Dengan Google Maps API dan API Key, aplikasi dapat mengakses dan menampilkan peta, sering digunakan dalam sistem informasi untuk data geografis [7]. Penelitian ini bertujuan menyediakan solusi efektif untuk pencarian  informasi  wisata  dan  UMKM  serta  pemilihan rute  terdekat  menggunakan  algoritma  Branch  and  Bound, untuk mempermudah dan mempercepat proses pemilihan rute wisata.
Berdasarkan  penelitian  terkait  yang  dilakukan  oleh  Heraldi,  Fachry  Dennis  pada  tahun  2022  dengan  judul “Penerapan  Algoritma  Branch  and  Bound  dalam  Menyelesaikan  Travelling  Salesman  Problem  (TSP)  untuk Menentukan  Rute  Perjalanan  11  Kantor  Camat  di  Kota  Padang”.  Penelitian  tersebut  menerapkan  penentuan  rute menggunakan algoritma Branch & Bound sehingga menghasilkan rute perjalanan saat mengunjungi 11 kantor camat kota Padang dengan jarak tempuh 93.4 km [8]. Penelitian terkait selanjutnya oleh Pranata, Andika dan Hutrianto pada tahun 2022 yang berjudul “Rekayasa Perangkat Lunak Penentuan Jarak Terdekat Dalam Pengiriman Darah di PMI Kota Palembang Dengan Algoritma Branch dan Bound”. Implementasi dari penelitian ini menunjukan bahwa metode algoritma Branch and Bound menggunakan 7 data rumah sakit di kota Palembang menghasilkan rute yang baik dan efektif  dengan  jarak  tempuh  masing-masing  simpul  dengan  metode  tambahan  yaitu  FAST  sebagai  metode pengembangan  perangkat  lunak  [9].  Permasalahan  ini  dapat  diatasi  dengan  aplikasi  mobile  yang  menggunakan algoritma Branch & Bound untuk mencari rute terdekat dengan internet dan GPS. Penelitian serupa oleh Maudin et al. (2020) menggunakan algoritma Greedy untuk rute wisata di Cirebon melalui aplikasi web berbasis GIS. Keduanya membahas  pariwisata  dan  metode  kuantitatif,  tetapi  berbeda  dalam  algoritma  (Greedy  vs.  Branch  &  Bound)  dan platform (web vs. mobile) [10]. Penelitian lainnya oleh Hasugian, Halim, dan Hanifah (2023) menerapkan algoritma A  Star  untuk  menemukan  rute  dan  tarif  angkutan  umum  di  Kota  Medan  melalui  sistem  web.  Mereka  berhasil menemukan  rute  terpendek  dari  Perumahan  Simalingkar  ke  Belawan  dengan  jarak  64,3  km  dan  tarif  Rp.  7.000. Meskipun  topiknya  serupa  dengan  penelitian  kami  tentang  penentuan  rute  terdekat,  kami  menggunakan  algoritma Branch  and  Bound  dan  platform  mobile  [11].  Sementara  itu,  Nafiah  dan  Faridatun  (2020)  merancang  aplikasi pencarian rute terdekat jasa binatu online berbasis Android dengan algoritma Dijkstra dan GPS. Meskipun berhasil menentukan lokasi terdekat, perlu peningkatan dalam penerapan algoritma. Meskipun berbeda objek, penelitian ini sejalan  dengan  penelitian  sebelumnya  dalam  mencari  solusi  rute  terdekat  melalui  aplikasi  Android  dengan  GPS, walaupun  menggunakan  algoritma  Branch  and  Bound  [12].  Dengan  aplikasi  Chillgo,  diharapkan  memberikan kontribusi  positif  pada  pengembangan  pariwisata  dan  UMKM  di  Jawa  Barat,  serta  meningkatkan  pengalaman wisatawan dalam menjelajahi destinasi wisata di wilayah tersebut. Aplikasi ini juga diharapkan menjadi contoh bagi pengembangan  aplikasi  serupa  di  daerah  lain,  untuk  meningkatkan  potensi  pariwisata  dan  UMKM  di  seluruh Indonesia

## 2. METODOLOGI PENELITIAN

## 2.1 Tahapan Penelitian
Tahapan penelitian yang dilakukan oleh peneliti dapat dilihat pada gambar 1.

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Gambar 1. Tahapan Penelitian
Berdasarkan gambar 1 terdapat tahapan penelitian dapat dijelaskan sebagai berikut:
a. Identifikasi Masalah
Tahap awal penelitian ini adalah mengidentifikasi masalah dalam mencari rute terpendek ke destinasi wisata dan UMKM, terutama yang kurang dikenal.
b. Pengumpulan Data
Metode pengumpulan data dilakukan melalui observasi, wawancara, dan studi pustaka. c. Analisis Kebutuhan
Langkah  ini  mencakup  kebutuhan  perangkat  keras,  perangkat  lunak  dan  dataset  untuk  menjalankan  sistem aplikasi Pemandu Wisata dan Dukungan UMKM.
d. Analisis Algoritma
Pada tahap ini, dilakukan analisis manual terhadap algoritma pada rute yang telah ditetapkan sebagai dasar implementasi algoritma pada sistem yang direncanakan.
e. Pengembangan Aplikasi
Proses pengembangan aplikasi mencakup pembuatan antarmuka, alur kerja, dan fitur-fitur yang dibahas dalam penelitian.
f. Hasil Implementasi
Tahap  implementasi  melibatkan  pengkodean  hasil  perancangan  agar  aplikasi  dapat  dibuat  sesuai  dengan algoritma yang telah dianalisis.
g. Pengujian
Uji  coba  dilakukan  untuk  mengumpulkan  data  dari  aplikasi,  termasuk  pengujian  oleh  pengembang  untuk mendeteksi kesalahan dan oleh pengguna untuk memberikan masukan terhadap pengalaman pengguna.

## 2.2 Metodologi Penelitian
Metodologi penelitian adalah pendekatan terstruktur untuk merancang dan mengevaluasi penelitian. Pendekatannya bervariasi seperti kuantitatif, kualitatif, dan campuran. Penelitian ini mengembangkan aplikasi mobile untuk pemandu wisata dan UMKM, menggunakan algoritma Branch and Bound untuk mencari rute terdekat. Pendekatan kualitatif memastikan kelancaran penelitian dengan data deskriptif melalui wawancara dan observasi [13].

## 2.3 Metode Pengumpulan Data
Data  dikumpulkan  melalui  observasi,  wawancara  dan  studi  literatur.  Berikut  penjelasan  lebih  dalam  mengenai beberapa macam metode pengumpulan data:
a. Observasi
Observasi  adalah  metode  pengumpulan  fakta  atau  informasi  melalui  pengamatan  dan  perhatian  langsung terhadap objek, peristiwa, atau kejadian [14]. Oleh karena itu, penelitian ini mencakup observasi langsung terhadap perkembangan data wilayah wisata dan pengembangan UMKM, serta pemasaran dengan teknologi.
b. Wawancara
Teknik  wawancara  dilakukan  dengan  tanya  jawab  dengan  narasumber  yang  relevan.  Misalnya,  wawancara dengan Kepala Sub bidang Pemberdayaan di Badan Pengelola Geopark Ciletuh.
c. Studi Literatur
Studi  literatur  adalah  desain  penelitian  untuk  mengumpulkan  data  terkait  suatu  topik.  Pengumpulan  data dilakukan melalui alat pencarian database sebagai langkah pencarian sumber literatur [15]. Data dikumpulkan melalui studi literatur dari buku, artikel, jurnal, dan laporan relevan untuk mendalami isu-isu terkait. Data destinasi wisata di Jawa  Barat  dikumpulkan  dari  Kaggle  melalui  searching  dan  web  scraping  menggunakan  Instant  Data  Scraper  di Google Chrome, kemudian diproses dengan Excel.
Dengan  demikian,  metodologi  penelitian  ini  dirancang  untuk  memastikan  bahwa  tujuan  penelitian  tercapai dengan cara yang sistematis dan efisien, menghasilkan data yang valid dan dapat dipercaya.
2.4 Analisa Kebutuhan

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Penelitian  ini  membutuhkan  spesifikasi  perangkat  keras  dan  perangkat  lunak  yang  tepat,  serta  dataset  wisata  dan UMKM, termasuk data dari Badan Pengelola Geopark Ciletuh Palabuhanratu. Adapun spesifikasinya adalah sebagai berikut:
a. Perangkat Keras
Adapun perangkat keras yang dibutuhkan untuk penelitian ini dapat di lihat pada Tabel 1.
Tabel 1. Kebutuhan Perangkat Keras No Perangkat Keras Keterangan 1 Laptop Huawei Matebook D14 2 Processor AMD Ryzen 7 3700U 3 RAM 8 GB 4 SSD 500GB 5 Smartphone Samsung A50
b. Perangkat Lunak
Adapun perangkat lunak yang dibutuhkan untuk penelitian ini dapat di lihat pada Tabel 2.
Tabel 2. Kebutuhan Perangkat Lunak No Perangkat Lunak Keterangan 1 Firebase (Auth & Firestore) Web server dan Database 2 Android Studio IDE Pengembangan Android 3 Brave/Chrome/Edge Browser

## 2.5 Analisa dan Pengembangan Aplikasi
Selama  pengembangan,  peneliti  menganalisis  sistem  menggunakan  diagram  UML  seperti use  case,  activity ,  dan sequence diagram . Schema digunakan untuk memodelkan hubungan antara entitas dalam basis data berbentuk objek. Berikut adalah rancangan diagram alur sistem untuk aplikasi mobile Android:
a. Use Case Diagram
Berikut merupakan representasi dari use case diagram dapat dilihat pada gambar 2.
Gambar 2. Use Case Diagram
Gambar 2 merupakan Use Case Diagram. Use Case adalah interaksi antara aktor dan sistem, sedangkan Use Case  Diagram adalah  representasi  visual  dari  interaksi  antara  satu  atau  lebih  aktor  [16].  Dalam  aplikasi  mobile pemandu  wisata  dan  UMKM,  terdapat  dua  aktor:  Admin  dan  pengguna.  Admin  mengelola  basis  data  layanan, sementara  pengguna  menggunakan  aplikasi  untuk  menemukan  lokasi  wisata  dan  tempat  oleh-oleh  terdekat  serta mendapatkan rekomendasi rute optimal.
b. Database Schema Firebase
Berikut adalah tampilan database yang digunakan pada firebase dengan bentuk schema pada gambar 3.

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Gambar 3. Database schema
Gambar 3 merupakan skema basis data yang digunakan peneliti. Database Schema JSON adalah representasi hubungan antar tabel dari suatu proses bisnis, yang mencakup simbol-simbol dan atribut entitas dengan relasi yang menghubungkan atribut-atribut tersebut [17]. Firebase adalah layanan dari Google yang memudahkan pengembang dalam mengembangkan aplikasi. Sebagai Backend as a Service (BaaS), Firebase menyediakan berbagai alat dan fitur untuk mempercepat proses pengembangan aplikasi [18]. Schema database Firebase yang digunakan adalah Firestore yang  dapat  mengatur  data  dalam  koleksi  dan  dokumen,  mendukung  subkoleksi  serta  field  seperti  string,  number, geopoint, dan timestamp. Firestore menyediakan skema fleksibel dan efisien untuk pengindeksan dan kueri. Berikut penjelasan singkat dari diagram pada Gambar 3 untuk schema database Firebase::
1. Places: Berisi dokumen dengan detail tempat dan subkoleksi image dan schedule.
2. Places_review: Berisi dokumen ulasan terkait places.
3. Umkm_review: Berisi dokumen ulasan terkait umkms.
4. Umkms: Berisi dokumen dengan detail UMKM dan subkoleksi schedule.
5. Users: Berisi dokumen informasi pengguna.
Hubungan  antar  koleksi  ditunjukkan  oleh  panah,  dengan  places_review  dan  umkm_review  terkait  dengan places dan umkms, serta users yang terkait dengan umkms untuk pengajuan UMKM.

## 2.6 Analisa Algoritma
Algoritma Branch and Bound adalah metode pencarian yang digunakan untuk menemukan solusi optimal dalam ruang pencarian. Langkah-langkahnya meliputi:
a. Inisialisasi:  Masukkan  simpul  akar  ke  dalam  antrian.  Jika  simpul  akar  merupakan  solusi  yang  diinginkan, pencarian selesai.
b. Seleksi:  Pilih  simpul  dengan  nilai  jalur  terkecil  dari  antrian.  Jika  simpul  tersebut  merupakan  solusi,  pencarian selesai.
c. Ekspansi: Kembangkan anak-anak dari simpul yang dipilih. Hitung nilai jalur untuk setiap anak dan masukkan mereka ke dalam antrian.
d. Penyaringan:  Evaluasi  setiap  simpul  untuk  menentukan  apakah  solusi  dari  simpul  tersebut  mungkin  lebih baik daripada solusi yang sudah ada. Jika iya, masukkan simpul tersebut ke dalam antrian.
e. Ulangi: Ulangi langkah-langkah di atas hingga solusi optimal ditemukan atau antrian kosong. [sitasi] Algoritma ini berguna untuk menyelesaikan masalah optimasi dengan membatasi ruang pencarian dan hanya mengeksplorasi solusi yang berpotensi lebih baik. Misalnya, seorang wisatawan ingin mengunjungi Bandung, Bogor, dan Garut sebagai destinasi wisata, serta mencari oleh-oleh di UMKM di kota-kota tersebut. Algoritma Branch and Bound  dapat  membantu  merencanakan  rute  terpendek  untuk  mengunjungi  ketiga kota  tersebut  dan  membeli  oleh- oleh. Nilai estimasi lintasan terpendek dari simpul i ke tujuan diwakili oleh ĉ(i). Selanjutnya, fungsi pembatas pada matriks ditentukan melalui persamaan:
ĉ (S) = ĉ (R) + A (i,j) + r (1)
Keterangan : ĉ (S)= jarak minimum melalui S ĉ (R)= jarak minimum melalui R, R adalah orangtua dari S

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
A (i,j)= bobot sisi (i,j) pada graph berkoresponden dengan R,S r = matriks tereduksi simpul S
Dengan  memanfaatkan  persamaan  ini,  jarak  minimum  melalui  simpul  S  dapat  dihitung  dengan mempertimbangkan jarak minimum yang melewati simpul R, bobot antara R dan S, serta matriks tereduksi dari simpul S.  Persamaan  ini  sering  diterapkan  dalam  algoritma  Branch  and  Bound  untuk  menghitung  jalur  terpendek  atau mengoptimalkan rute.

## Gambar .4 Graf Simpul Objek Wisata
Gambar  4  menunjukkan  lima  lokasi  wisata  sebagai  simpul  dalam  graf:  Kota  Bekasi,  Gunung  Tangkuban Perahu,  Kawah  Putih,  Green  Canyon  (Cukang  Taneuh),  dan  Pantai  Pangandaran.  Algoritma  Branch  and  Bound digunakan  untuk  mencari  solusi  lebih  efisien  dengan  mengurangi  jumlah  kemungkinan  yang  harus  diuji.  Proses dimulai  dengan  menggambarkan  graf  dalam  matriks  simetris,  yang  meminimalkan  kompleksitas  pencarian  dan meningkatkan efisiensi dalam menemukan rute terpendek dari Kota Bekasi ke setiap destinasi dan kembali lagi ke Kota Bekasi.

## Gambar 5. Hasil Graf ke Matriks Reduksi
Gambar  5  menunjukkan  penempatan  nilai  jarak  antara  simpul-simpul  dalam  matriks  M.  Nilai  Mij  dalam  matriks tersebut menunjukkan jarak antara simpul ke-i dan ke-j. Misalnya, pada baris pertama, M11 menandakan jarak dari dan ke simpul yang sama, yaitu S1, dengan nilai tak terhingga (∞). Jarak dari S1 ke S2 direpresentasikan oleh nilai M12, yaitu 144, dan seterusnya. Proses ini diulangi untuk setiap baris dalam matriks, mencatat jarak antara setiap pasangan simpul [19].

## 2.7 Analisa Pengujian
Penelitian  ini  menggunakan  metode  BlackBox  Testing  untuk  memeriksa  apakah  sistem  berfungsi  sesuai spesifikasinya.  BlackBox  Testing  fokus  pada  pengujian  kebutuhan  fungsional  perangkat  lunak.  Dalam  proses  ini, penguji menetapkan serangkaian kondisi input dan memverifikasi kinerja perangkat lunak sesuai dengan input tersebut [20]. Beberapa skenario pengujian menggunakan metode BlackBox Testing termasuk pengujian algoritma, preferensi pengguna, login, registrasi, beranda, daftar wisata, detail wisata, maps (detail UMKM dan rute), fitur favorit, profil pengguna, dan pendaftaran UMKM.

## 3. HASIL DAN PEMBAHASAN
Hasil penelitian ini adalah pengembangan aplikasi pemandu wisata dan dukungan UMKM bernama Chillgo. Aplikasi ini mengimplementasikan algoritma Branch and Bound untuk menyelesaikan permasalahan optimasi rute kunjungan yang mencakup destinasi wisata dan kunjungan ke UMKM, menggunakan teknologi Google Maps. Penelitian ini tidak hanya  menghasilkan  perhitungan  optimal  menggunakan  algoritma  Branch  and  Bound,  tetapi  juga  menerapkannya dalam  aplikasi  berbasis  Android.  Selanjutnya  dilakukan  pengujian  fungsional  untuk  membandingkan  hasil perhitungan manual dengan sistem, yang menunjukkan efisiensi dan akurasi yang lebih tinggi dari aplikasi Chillgo. Penerapan algoritma ini tidak hanya mempermudah perencanaan kunjungan wisata, tetapi juga memungkinkan para pengguna  untuk  mengunjungi  dan  mendukung  UMKM  lokal  dengan  cara  yang  terstruktur  dan  efisien.  Dengan integrasi  Google  Maps,  aplikasi  ini  memberikan  solusi  yang  komprehensif  dan  berkesinambungan  bagi  pengguna untuk  menikmati  pengalaman  wisata  yang  lebih  baik  sambil  mendukung  pertumbuhan  ekonomi  UMKM  di  area kunjungan wisata.

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359

## 3.1 Perhitungan Algoritma
Perhitungan algoritma yang digunakan yaitu branch and bound, dapat dilihat pada gambar 6.
Gambar 6. Flowchart Analisa Algoritma
Pada gambar 6 tedapat alur sebelum melakukan pencarian rute, tahap awal mencakup penyimpanan data jalur ke dalam basis data, sebagaimana ditunjukkan dalam gambar di atas. Algoritma Branch and Bound digunakan untuk menghasilkan  semua  jalur  dari  titik  awal  perjalanan  ke  titik  akhir,  dalam  hal  ini,  destinasi  wisata  dan  UMKM  di Geopark Ciletuh. Titik awal perjalanan adalah Pantai Tenda Biru Ujung Genteng, dengan kunjungan ke empat UMKM terdekat, termasuk Anday’s Cake dan Pawon Moghes (G-Opak). Berikut adalah jarak antar lokasi yang diperoleh dari Google Maps untuk menentukan rute terpendek menuju tujuan. Jarak antar titik ini tercantum dalam Tabel 5.
Tabel 3. Jarak Jalur Objek Wisata ke UMKM Titik Awal Titik Tujuan UMKM Jarak Pantai Tenda Biru Ujung Genteng Anday’s Cake 4,24 km Rosmadiana food 16,08 km Nuansa Fruits 19,49 km Pawon Moghes (G-Opak) 24,51 km Anday’s Cake Rosmadiana food 11,84 km Nuansa Fruits 15,25 km Pawon Moghes (G-Opak) 20,27 km Rosmadiana food Nuansa Fruits 8,76 km Pawon Moghes (G-Opak) 12,75 km Nuansa Fruits Pawon Moghes (G-Opak) 5,21 km
Tabel 5 menyajikan data yang akan disusun menjadi matriks berukuran 5x5, di mana setiap elemen matriks mewakili jarak antara berbagai titik tujuan. Indeks i dan j menunjukkan titik-titik tujuan dalam matriks ini. Setelah matriks dibentuk, jarak antar titik akan direpresentasikan dalam bentuk graf berbobot. Berikut adalah bentuk matriks tersebut serta gambar representasi graf berbobot dari jarak-jarak yang ada dalam matriks.

## Gambar 7. Graf berbobot hasil representasi matriks Mij
Setiap  simpul  dalam  graf  yang  ada  pada  gambar  5  mewakili  titik  awal  dan  tujuan  kunjungan,  seperti PTBUG(WISATA)  sebagai  titik  awal  ke  UMKM2,  AC(UMKM2)  sebagai  titik  tujuan ke  UMKM3,  RF(UMKM3) sebagai titik tujuan ke UMKM4, NF(UMKM4) sebagai titik tujuan ke UMKM5, dan PMG(UMKM5) sebagai titik

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
kembali ke PTBUG(WISATA). Penentuan rute terdekat dari satu simpul ke simpul lainnya dimulai dari titik awal dan berakhir kembali ke titik awal tersebut. Jarak antar titik direpresentasikan dalam graf sebagai nilai cost. Di bawah ini adalah graf berbobot yang merepresentasikan matriks Mij.
𝑗1         𝑗2        𝑗3        𝑗4          𝑗5
M ij = 𝑖1 𝑖2 𝑖3 𝑖4 𝑖5 [ ∞ 4,24 16,08 19,49  24,51 4,24 ∞ 11,84 15,25  20,27 16,08 11,84 ∞ 8,76 12,75 19,49 15,25 8,76 ∞ 5,21 24,51 20,27 12,75 5,21 ∞ ]
Matriks di atas memiliki sifat simetri, artinya jarak dari titik i ke j sama dengan jarak dari titik j ke i. Untuk menyederhanakan matriks tersebut, dilakukan reduksi.
Reduksi baris :
[ ∞ 0 11,84 15,25 20,27 0 ∞ 7,6 11,01 16,03 7,32 3,08 ∞ 0 3,99 14,28 10,04 3,55 ∞ 0 19,3 15,06 7,54 0 ∞ ]
Hasil matriks diperoleh dengan mengurangkan setiap nilai dalam baris dengan nilai terkecil di baris tersebut. Misalnya, nilai terkecil untuk baris 1 adalah 4,24, jadi semua nilai dalam baris tersebut dikurangi dengan 4,24. Ini juga dilakukan untuk baris-baris berikutnya.
Reduksi kolom :
[ ∞ 0 8,29 15,25 20,27 0 ∞ 4,05 11,01 16,03 7,32 3,08 ∞ 0 3,99 14,28 10,04 0 ∞ 0 19,3 15,06 3,99 0 ∞ ]
Hasil matriks diperoleh dengan mengurangi nilai terkecil dari tiap kolom. Misalnya, kolom ke-3 dikurangi nilai terkecil 3,55, sementara kolom ke-1,2,4,5 dikurangi 0, sehingga nilainya tetap. Proses reduksi ini menghasilkan nilai batas simpul akar atau c(root), yaitu jumlah pengurangan semua elemen baris dan kolom. Dengan demikian, ĉ(root) = 4,24 + 4,24 + 8,76 + 5,21 + 5,21 + 3,55 = 31,21. Nilai 31,21 ini merupakan penjumlahan nilai terkecil dari reduksi baris dan kolom, yang membentuk pohon ruang status baru dengan bobot 31,21.Selanjutnya, hitung simpul-simpul lain untuk membentuk pohon ruang status, mengacu pada persamaan dan proses yang telah dijelaskan sebelumnya.
a. Simpul 2 (lintasan 1,2)
Tahapan perhitungan simpul 2 dari lintasan baris 1 ke kolom 2 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 4,05 11,01 16,03 7,32 ∞ ∞ 0 3,99 14,28 ∞ 0 ∞ 0 19,3 ∞ 3,99 0 ∞ ] = [ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 6,96 11,98 7,32 ∞ ∞ 0 3,99 14,28 ∞ 0 ∞ 0 19,3 ∞ 3,99 0 ∞ ] = [ ∞ ∞ ∞ ∞ ∞
∞ ∞
0 6,96 11,98 0 ∞ ∞ 0 3,99 6,96 ∞ 0 ∞ 0 11,98 ∞ 3,99 0 ∞ ]
Matriks di atas berasal dari lintasan baris 1 diubah menjadi ∞, kolom 2 diubah menjadi ∞, dengan baris 2 posisi pertama  diubah menjadi ∞.  Perubahan ini diterapkan untuk mencerminkan jarak yang tak terhingga, menandakan bahwa  tidak  ada  lintasan  langsung  antara  simpul  tersebut  dalam  konteks  perhitungan  rute.  Pengurangan dilakukan pada baris ke-2 dengan nilai terkecil 4,05 dan kolom ke-1 dengan nilai terkecil 7,32. Sehingga ĉ(2) = 31,21 + 0 + 11,37 = 42,58. Angka 0 sesuai dengan rumus A(i,j), di mana A adalah matriks tereduksi untuk simpul R pada reduksi terakhir. Nilai 0 dijelaskan dalam matriks berikut:

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
A(1,2)
[ ∞ 𝟎 8,29 15,25 20,27 0 ∞ 4,05 11,01 16,03 7,32 3,08 ∞ 0 3,99 14,28 10,04 0 ∞ 0 19,3 15,06 3,99 0 ∞ ]
b. Simpul 3 (lintasan 1,3)
Tahapan perhitungan simpul 3 dari lintasan baris 1 ke kolom 3 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 11,01 16,03 ∞ 3,08 ∞ 0 3,99 14,28 10,04 ∞ ∞ 0 19,3 15,06 ∞ 0 ∞ ]
=
[ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 11,01 16,03 ∞ 0 ∞ 0 3,99 14,28 6,96 ∞ ∞ 0 19,3 11,98 ∞ 0 ∞ ]
Matriks di atas berasal dari lintasan baris 1 diubah menjadi ∞, kolom 3 diubah menjadi ∞, dengan baris 3 posisi pertama diubah menjadi ∞. Proses pengurangan dilakukan pada kolom ke 2 oleh nilai terkecil yaitu 3,08. Sehingga ĉ(3)  = 31,21+ 8,29 + 3,08 = 42,58.
c. Simpul 4 (lintasan 1,4)
Tahapan perhitungan simpul 4 dari lintasan baris 1 ke kolom 4 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ 0 ∞ 4,05 ∞ 16,03 7,32 3,08 ∞ ∞ 3,99 ∞ 10,04 0 ∞ 0 19,3 15,06 3,99 ∞ ∞ ]
=
[ ∞ ∞ ∞ ∞ ∞ 0 ∞ 4,05 ∞ 16,03 4,24 0 ∞ ∞ 0,91 ∞ 10,04 0 ∞ 0 15,31 11,07 0 ∞ ∞ ]
Matriks di atas berasal dari lintasan baris 1 diubah menjadi ∞, kolom 4 diubah menjadi ∞, dengan baris 4 posisi pertama diubah menjadi ∞. Proses pengurangan dilakukan pada baris ke-3 oleh nilai terkecil yaitu 3,08, dan baris ke- 5 oleh nilai terkecil yaitu 3,99. Sehingga ĉ(4)  = 31,21+ 15,25 + 7,07= 53,53.
d. Simpul 5 (lintasan 1,5)
Tahapan perhitungan simpul 5 dari lintasan baris 1 ke kolom 5 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ 0 ∞ 4,05 11,01 ∞ 7,32 3,08 ∞ 0 ∞ 14,28 10,04 0 ∞ ∞ ∞ 15,06 3,99 0 ∞] = [ ∞ ∞ ∞ ∞ ∞ 0 ∞ 4,05 11,01 ∞ 7,32 0 ∞ 0 ∞
14,28 6,96 0 ∞ ∞ ∞ 11,98 3,99 0 ∞]
Matriks di atas berasal dari lintasan baris 1 diubah menjadi ∞, kolom 5 diubah menjadi ∞, dengan baris 5 posisi pertama diubah menjadi ∞. Proses pengurangan dilakukan pada kolom ke-2 oleh nilai terkecil yaitu 3,08. Sehingga ĉ(5)  = 31,21 + 20,27 + 3,08 = 54,56. Hasil dari proses tahapan reduksi pada simpul-simpul diatas menjadi bentuk pohon status adalah sebagai berikut :

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Gambar 8 Pohon Status Simpul 1
Gambar  8  menunjukan  penomoran  pada  pohon  status  diatas  sesuai  dengan  simpul  sebelumnya  yaitu (1)PTBUG, (2)AC, (3)RF, (4)NF, (5)PMG. Tahap selanjutnya memilih simpul yang memiliki nilai bobot terkecil dan jarak terdekat pada pohon status yaitu simpul ke-2 dengan nilai terkecil yaitu 42,58. Berikut adalah proses peningkatan simpul 2 :
e. Simpul 6 (lintasan 1,2,3)
Tahapan perhitungan simpul 6 dari lintasan baris 1, baris 2 ke kolom 2, dan kolom 3 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 3,99 6,96 ∞ ∞ ∞ 0 11,98 ∞ ∞ 0 ∞ ] = [ ∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 3,99
0 ∞ ∞ ∞ 0 5,02 ∞ ∞ 0 ∞ ]
Matriks di atas berasal dari lintasan baris 1 dan 2 diubah menjadi ∞, kolom 2 dan 3 diubah menjadi ∞, dengan baris 3 posisi pertama diubah menjadi ∞.  Proses pengurangan dilakukan pada kolom ke-1 oleh nilai terkecil yaitu 5,02. Sehingga ĉ(6)  = 31,21 + 0 + 5,02 = 36,23.
f. Simpul 7 (lintasan 1,2,4)
Tahapan perhitungan simpul 7 dari lintasan baris 1, baris 2 ke kolom 2, dan kolom 4 dapat dilihat pada matriks dibawah ini.
[
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 3,99
∞ ∞ 0 ∞ 0 11,98 ∞ 3,99 ∞ ∞ ] = [ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ 3,99
∞ ∞ 0 ∞ 0
7,99 ∞ 0 ∞ ∞ ]
Matriks di atas berasal dari lintasan baris 1 dan 2 diubah menjadi ∞, kolom 2 dan 4 diubah menjadi ∞, dengan baris 4 posisi pertama diubah menjadi ∞. Proses pengurangan dilakukan pada baris ke-5 oleh nilai terkecil yaitu 3,99. Sehingga ĉ(7)  = 31,21 + 6,96 + 3,99 = 42,16.
g. Simpul 8 (lintasan 1,2,5)
Tahapan perhitungan simpul 8 dari lintasan baris 1, baris 2 ke kolom 2, dan kolom 5 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 0 ∞ 6,96 ∞ 0 ∞ ∞ ∞ ∞ 3,99 0 ∞]
Matriks di atas berasal dari lintasan baris 1 dan 2 diubah menjadi ∞, kolom 2 dan 5 diubah menjadi ∞, dengan baris 5 posisi pertama diubah menjadi ∞. Proses pengurangan tidak dilakukan pada baris dan kolom karena terdapat

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
nilai nol. Sehingga ĉ(8)  = 31,21 + 11,98 + 0 = 43,19. Proses reduksi diatas dari simpul 6 sampai simpul 8 memperoleh bentuk pohon status sebagai berikut :

## Gambar 9 Pohon Status Simpul 2
Gambar 9 merupakan tahap selanjutnya memilih simpul yang memiliki nilai bobot terkecil pada pohon status yaitu simpul ke-6 dengan nilai terkecil yaitu 36,23. Berikut adalah proses peningkatan dari simpul 6 :
h. Simpul 9 (lintasan 1,2,3,4)
Tahapan perhitungan simpul 9 dari lintasan baris 1, baris 2 ke kolom 2, kolom 3 dan kolom 4 dapat dilihat pada matriks dibawah ini.
[
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ 3,99 ∞ ∞ ∞ ∞ 0 5,02 ∞ ∞ ∞ ∞ ] = [ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 ∞ ∞ ∞ ∞]
Matriks di atas diperoleh dari lintasan pada baris 1 dan 2 diubah menjadi ∞, kolom 2, 3, dan 4 diubah menjadi ∞, serta dari kolom pertama pada posisi ke-4 yang dikosongkan. Proses pengurangan dilakukan pada baris ke-3 oleh nilai terkecil yaitu 3,99 dan baris ke-5 yaitu 5,02. Sehingga ĉ(9)  = 31,21 + 0 + 9,01 = 40,22.
i. Simpul 10 (lintasan 1,2,3,5)
Tahapan perhitungan simpul 10 dari lintasan baris 1, baris 2 ke kolom 2, kolom 3 dan kolom 5 dapat dilihat pada matriks dibawah ini.
[ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞]
Matriks di atas diperoleh dari lintasan pada baris 1 dan 2 diubah menjadi ∞, kolom 2, 3, dan 5 diubah menjadi ∞, serta dari kolom pertama pada posisi ke-5 yang dikosongkan. Proses pengurangan tidak dilakukan karena tiap baris dan kolom memiliki nilai 0. Sehingga ĉ(10)  = 31,21 + 3,99 + 0 = 35,2. Proses reduksi diatas dari simpul 9 sampai simpul 10 memperoleh bentuk pohon status sebagai berikut :

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Pohon status pada gambar 10, dapat disimpulkan bahwa rute dengan cost minimum adalah rute terpendek yang berhasil ditemukan melalui simpul 1-2-6-10 dan kembali ke simpul 1 Jika fokus utama adalah meminimalkan biaya. Sehingga,  peneliti  memiliki  fokus  utama  adalah  meminimalkan  jarak  perjalanan  misalnya,  untuk  mengurangi kelelahan pengemudi atau waktu tempuh, maka harus memilih jalur dengan jarak terpendek meskipun bobotnya lebih besar dapat dilihat di simpul 9 dengan 10. Berarti melalui 1-2-6-9-1 (PTBUG-AC-RF-NF-PMG-PTBUG) dengan total jarak 54,57 km.

## 3.1 Implementasi Aplikasi
Hasil implementasi aplikasi yang menggunakan algoritma Branch and Bound berbasis android untuk menentukan rute terdekat dengan beberapa kunjungan dapat dilihat pada tabel 4.
Tabel 4. Hasil Implementasi Aplikasi No Gambar Nama Halaman Keterangan 1. Tampilan Halaman Maps
Tampilan halaman ini menggambarkan sebuah peta dari google maps dengan titik-titik lokasi  dan diberi garis polyline untuk memberikan rute  terdekat  untuk  mengunjungi  beberapa  tempat  UMKM  dengan keterangan warna biru lokasi wisata ke UMKM, warna kuning lokasi UMKM  ke  UMKM,  dan  warna  merah  lokasi  UMKM  kembali  ke wisata  awal.  Terdapat  tombol-tombol  yang  umum  ada  di  maps seperti tombol zoom-in, zoom-out , dan mendeteksi lokasi pengguna. Selain  itu,  tombol  tutup  pada  bagian  kiri  atas  berfungsi  untuk kembali  ke  halaman  sebelumnya  dan  tombol  lihat  rute  berfungsi untuk  menampilkan  deskripsi  lebih  lanjut  mengenai  rute  serta tombol  yang  mengandung  ikon  informasi  untuk  menampilkan  dan menyembunyikan keterangan pada polyline. 2. Tampilan Halaman Rute Tampilan rute menampilkan deskripsi rute perjalanan menggunakan algoritma Branch and Bound dari mulai jarak pengguna ke wisata, wisata  ke  umkm,  umkm  ke  umkm,  dan  menampilkan  rute rekomendasi  yang  terbaik  untuk  mengunjungi  semua  tempat  dari wisata  ke  umkm,  umkm  ke  umkm,  sampai  kembali  ke  wisata  asal dengan  total  keseluruhan  jarak  yang  ditempuh.  Pada  nilai  yang ditampilkan di tampilan halaman rute berbentuk kilometer.

## 3.2 Hasil Pengujian Sistem
Pengujian ini berfokus pada fungsionalitas perangkat lunak. Peneliti melakukan tahapan pengujian untuk memastikan apakah sistem berfungsi sesuai prosedur yang diharapkan atau belum memenuhi standar dapat dilihat pada Tabel 5.
Tabel 5. Hasil Pengujian Sistem Kasus dan Hasil Uji Kasus yang diuji Skenario uji Hasil yang diharapkan Hasil Simpul 1(PTBUG) menuju Simpul 2(AC) untuk jarak rute terdekat 4,24 Km Dapat menampilkan dari perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 4,24 Km dari wisata(PTBUG) ke UMKM(AC) Berhasil menampilkan perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 4,24 Km dari wisata(PTBUG) ke UMKM(AC) OK Simpul 2(AC) menuju Simpul 6(RF) untuk Dapat menampilkan dari perhitungan algoritma dengan perhitungan sistem Berhasil menampilkan perhitungan algoritma dengan perhitungan sistem OK

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
jarak rute terdekat 11,84 Km aplikasi pemilihan jarak rute terdekat 11,84 Km dari UMKM(AC) ke UMKM(RF) aplikasi pemilihan jarak rute terdekat 11,84 Km dari UMKM(AC) ke UMKM(RF) Simpul 6(RF) menuju Simpul 9(NF) untuk jarak rute terdekat 8,76 Km Dapat menampilkan dari perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 8,76 Km dari UMKM(RF) ke UMKM(NF) Berhasil menampilkan perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 8,76 Km dari UMKM(RF) ke UMKM(NF) OK Simpul 9(NF) menuju Simpul 10(PTBUG) untuk jarak rute terdekat 5,21 Km Dapat menampilkan dari perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 5,21 Km dari UMKM(RF) ke UMKM(NF) Berhasil menampilkan perhitungan algoritma dengan perhitungan sistem aplikasi pemilihan jarak rute terdekat 5,21 Km dari UMKM(RF) ke UMKM(NF) OK Total jarak  54,57 Km dengan rute 1-2-6-9-1 (PTBUG-AC-RF-NF- PMG-PTBUG) Dapat menampilkan dari perhitungan algoritma dengan perhitungan sistem aplikasi mengenai total jarak 54,57 Km Berhasil menampilkan total jarak 54,57 Km dari perhitungan ke proses perhitungan sistem aplikasi OK

## 4. KESIMPULAN
Penelitian  ini  berhasil  mengembangkan  aplikasi  pemandu wisata  berbasis  Android  yang  memanfaatkan  Algoritma Branch and Bound untuk mengoptimalkan rute terdekat. Implementasi algoritma ini efektif dalam menentukan rute kunjungan dari destinasi wisata ke berbagai UMKM di Jawa Barat. Hasil perhitungan menunjukkan bahwa aplikasi mampu memberikan solusi rute kunjungan yang optimal, seperti contoh rute dari Pantai Tenda Biru Ujung Genteng ke beberapa UMKM terdekat dengan total jarak 54,57 Km. Aplikasi ini memberikan informasi yang akurat dan efisien, meningkatkan  aksesibilitas  serta  promosi  bagi  UMKM  lokal.  Pengujian  sistem  menggunakan  metode Blackbox Testing menunjukkan bahwa semua fitur berjalan dengan baik dan sesuai dengan yang diharapkan. Dalam konteks penelitian  selanjutnya,  disarankan  untuk  menambahkan  fitur  penambahan  penanda  manual  pada  peta  untuk memungkinkan pengguna menandai lokasi spesifik. Hal ini akan meningkatkan kompleksitas dan akurasi pencarian rute terdekat. Selain itu, pengujian White Box Testing atau load testing perlu dilakukan untuk memastikan aplikasi dapat menangani jumlah pengguna yang besar dan tetap berkinerja baik. Di samping itu, pengumpulan umpan balik dari pengguna aplikasi sangat penting untuk mengevaluasi pengalaman mereka dan mengidentifikasi area yang perlu diperbaiki  atau  ditingkatkan  pada  aplikasi.  Dengan  menerapkan  saran-saran  ini,  diharapkan  penelitian  selanjutnya dapat menghasilkan aplikasi yang lebih baik dan memberikan manfaat yang lebih besar bagi pengguna serta UMKM di Jawa Barat.

## REFERENCES
[1] “UNDANG-UNDANG REPUBLIK INDONESIA.” Accessed: Apr. 25, 2024. [Online]. Available: https://jdih.kemenkeu.go.id/fullText/2009/10TAHUN2009UU.HTM
[2] BAPPEDA, “Rencana Besar Pengembangan Destinasi Wisata Kelas Dunia Provinsi Jawa Barat,” Badan Perenc. Pembang. Drh.  Provinsi  Jawa  Barat ,  pp.  1–66,  2017,  [Online].  Available:  http://bappeda.jabarprov.go.id/documents/rencana-besar- pengembangan-destinasi-wisata-kelas-dunia-provinsi-jawa-barat/
[3] “Open Data Provinsi Jawa Barat.” Accessed: Apr. 15, 2024. [Online]. Available: https://opendata.jabarprov.go.id/id/artikel/6-wisata-jawa-barat-populer-bagi-wisatawan-ada-hidden-gems-juga-lho
[4] “Siaran Pers: Wamenparekraf Paparkan Program Strategis Garap Peluang Sektor Parekraf di 2023.” Accessed: Apr. 15, 2024. [Online]. Available: https://kemenparekraf.go.id/berita/siaran-pers-wamenparekraf-paparkan-program-strategis-garap- peluang-sektor-parekraf-di-2023
[5] A. Agung and G. Oka, Protection of UMKM in Sustainable Creative Economy Development in Indonesia . Atlantis Press SARL, 2023. doi: 10.2991/978-2-494069-93-0.
[6] I.  Marliana,  A.  Ikhwan,  and  T.  M.  Fawaati,  “Implementasi  Mit  App  Inventor  Dalam  Game  Mengenal  Huruf  Berbasis Android,” J. Teknoinfo , vol. 17, no. 1, p. 244, 2023, doi: 10.33365/jti.v17i1.2369.
[7] Y. Fito, A. Saputra, and A. A. S. H, “Implementasi Google Maps API Berbasis Website,” no. September, pp. 1–6, 2021.
[8] F. D. Heraldi, “Penerapan Algoritma Branch and Bound dalam Menyelesaikan Travelling Salesman Problem ( TSP ) untuk Menentukan Rute Perjalanan 11 Kantor Camat di Kota Padang,” 2022.
[9] A. Pranata and H. Hutrianto, “Rekayasa Perangkat Lunak Penentuan Jarak Terdekat Dalam Pengiriman Darah di PMI Kota Palembang  Dengan  Algoritma  Branch  And  Bound,” J.  Inf.  Technol.  Ampera ,  vol.  3,  no.  2,  pp.  244–255,  2022,  doi: 10.51519/journalita.volume3.isssue2.year2022.page244-255.
[10]  B. H. dan S. Maudin, “PENCARIAN RUTE TERPENDEK MENUJU TEMPAT WISATA MENGGUNAKAN METODE ALGORITMA  GREEDY  PADA  DINAS  PEMUDA  OLAHRAGA  KEBUDAYAAN  DAN  PARIWISATA  KOTA CIREBON,” J. Ilm. Indones. , vol. 5, no. 5, 2020.
[11]  R.  K.  R,  A.  H.  Hasugian,  and  P.  Hanifah,  “Penentuan  Rute  Dan  Tarif  Perjalanan  Angkutan  Umum  Di  Kota  Medan Menggunakan Algoritma A*,” J-SISKO TECH (Jurnal Teknol. Sist. Inf. dan Sist. Komput. TGD) , vol. 6, no. 1, p. 135, 2023, doi: 10.53513/jsk.v6i1.7402.
[12]  A.  N.  A.  F.  Nafiah,  “Perancangan  Aplikasi  Pencarian  Rute  Terdekat  Jasa  Binatu  Online  Berbasis  Android  Dengan

## Building of Informatics, Technology and Science (BITS)
Volume 6, No 1, Juni 2024 Page: 265−2 78 ISSN 2684-8910 (media cetak) ISSN 2685-3310 (media online) DOI 10.47065/bits.v6i1.5359
Menggunakan Metode Dijkstra,” Ubiquitous Comput. its Appl. J. , vol. 3, pp. 99–106, 2020, doi: 10.51804/ucaiaj.v3i2.99- 106.
[13]  I. Sina, “Metodologi Penelitian,” Widina Bhakti Persada Bandung , pp. 12–26, 2022.
[14]  A. F. Rahmah, Dwi Sartika Simatupang, and Alun Sujjada, “Sistem Monitoring Dan Kontrol Tanaman Pada  Greenhouse Berbasis Android Menggunakan Fuzzy Sugeno,” J. CoSciTech (Computer Sci. Inf. Technol. , vol. 4, no. 2, pp. 332–340, 2023, doi: 10.37859/coscitech.v4i2.5088.
[15]  M. Syofian and N. Gazali, “Kajian literatur: Dampak covid-19 terhadap pendidikan jasmani,” J. Sport Educ. , vol. 3, no. 2, p. 93, 2021, doi: 10.31258/jope.3.2.93-102.
[16]  D.  Hardiyanti,  “Sistem  Informasi  Sekolah  Berbasis  Web  pada  Sekolah  Dasar  Negeri  (SDN)  Seriti,” Indones.  J.  Educ. Humanit. , vol. 1, no. 3, pp. 156–168, 2021, [Online]. Available:
http://ijoehm.rcipublisher.org/index.php/ijoehm/article/view/28
[17]  A. R. Firdaus and D. F. Suyanto, “Pengembangan Aplikasi Pembayaran Pulsa Telepon Seluler Dan Pulsa Listrik Berbasis Android Menggunakan Framework Xamarin,” J. Manaj. Inform. , vol. 8, no. 2, pp. 1–10, 2018.
[18]  B.  A.  Risna  Sari,  Asri  Asri,  “Rancang  Bangun  Sistem  Pelayanan  Administrasi  Desa  Menggunakan  Android  Studio  dan Database Firebase,” Pros. Semant. , vol. 3, no. 1, pp. 189–198, 2021, [Online]. Available: http://www.journal.uncp.ac.id/index.php/semantik/article/view/1618
[19]  E.  Retnoningsih  and  F.  N.  Khasanah,  “Rekomendasi  Objek  Wisata  Provinsi  Jawa  Barat  Dengan  Algoritma  Branch  and Bound,” PIKSEL  Penelit. Ilmu Komput. Sist. Embed. Log. , vol. 6, no. 1, pp. 29–40, 2018, doi: 10.33558/piksel.v6i1.1397.
[20]  M. Merawati, I. Yustiana, and S. Somantri, “Sistem Informasi Geografis Pemetaan Bencana Pergerakan Tanah Kabupaten Sukabumi,” JIPI  (Jurnal  Ilm.  Penelit.  dan  Pembelajaran  Inform. ,  vol.  7,  no.  3,  pp.  945–957,  2022,  doi: 10.29100/jipi.v7i3.3157.