Penerapan Metode Branch and Bound untuk Optimalisasi Rute Wisata Terdekat di Kota Palembang
DOI:
https://doi.org/10.58466/eqadem96Kata Kunci:
Branch and Bound, Haversine, Travelling Salesman Problem, Palembang, OpenStreetMapAbstrak
Penelitian ini membahas penerapan metode Branch and Bound untuk optimalisasi rute wisata terdekat di Kota Palembang dengan pendekatan Travelling Salesman Problem (TSP). Permasalahan yang diangkat adalah bagaimana menentukan jalur perjalanan wisata yang paling efisien dari beberapa destinasi wisata dengan jarak tempuh minimum. Penelitian memanfaatkan data koordinat geografis destinasi wisata yang diperoleh melalui OpenStreetMap, kemudian jarak antar lokasi dihitung menggunakan Haversine Formula agar memperoleh estimasi jarak yang akurat berdasarkan latitude dan longitude. Selanjutnya, Algoritma Branch and Bound digunakan untuk mencari solusi rute optimal melalui proses branching, bounding, dan pruning sehingga pencarian solusi menjadi lebih efisien dibandingkan metode brute force. Hasil penelitian menunjukkan bahwa sistem berhasil menghasilkan rute wisata sirkular optimal dengan total jarak minimum sebesar 40,47 km dan waktu eksekusi 12,84 detik. Integrasi Haversine Formula dan Branch and Bound terbukti mampu memberikan rekomendasi rute wisata yang efisien, akurat, dan adaptif untuk membantu wisatawan menghemat waktu perjalanan dan biaya transportasi di Kota Palembang.
Referensi
[1] Q. P. Mulya and G. Yudana, “Analisis Pengembangan Potensi Kawasan Wisata Sungai Musi sebagai Tujuan Wisata di Kota Palembang,” Jurnal Cakra Wisata, vol. 19, pp. 41–54, 2018.
[2] W. F. Mahmudy, “Optimasi Multi Travelling Salesman Problem (M-TSP) Menggunakan Algoritma Genetika,” in Seminar Nasional Basic Science V, Malang: FMIPA, Universitas Brawijaya, 2008, pp. 1–6.
[3] Y. D. Prasetyo, “Penyelesaian Travelling Salesman Problem dengan Algoritma Branch and Bound,” Jurnal MATEMATICS PAEDAGOGIC, vol. 1, no. 2, pp. 162–168, 2017, [Online]. Available: www.jurnal.una.ac.id/indeks/jmp
[4] E. Nurrohmah and D. Sulistioningrum, “OpenStreetMap sebagai Alternatif Teknologi dan Sumber Data Pemetaan Desa,” Seminar Nasional Geomatika 2018: Penggunaan dan Pengembangan Produk Informasi Geospasial Mendukung Daya Saing Nasional, pp. 787–796, 2018, [Online]. Available: https://www.openstreetmap.org/
[5] S. S. G. Witin, W. D. Permatasari, N. Aminah, P. Rande, F. D. T. Amijaya, and D. F. Putri, “Penerapan Algoritma Branch and Bound untuk Optimasi Rute Wisata di Kalimantan Timur Berdasarkan Traveling Salesman Problem,” Jurnal Ilmiah Matematika, vol. 13, no. 2, pp. 197–205, 2025.
[6] M. Mondal and D. Srivastava, “A Genetic Algorithm-Based Approach to Solve a New Time-Limited Travelling Salesman Problem,” International Journal of Distributed Systems and Technologies, vol. 14, no. 2, pp. 1–14, 2023, doi: 10.4018/IJDST.317377.
[7] F. S. Gharehchopogh, B. Abdollahzadeh, and B. Arasteh, “An Improved Farmland Fertility Algorithm with Hyper-Heuristic Approach for Solving Travelling Salesman Problem,” CMES - Computer Modeling in Engineering and Sciences, vol. 135, no. 3, pp. 1981–2006, 2023, doi: 10.32604/cmes.2023.024172.
[8] A. R. Putri and M. Widyastiti, “Penerapan Algoritma Branch and Bound untuk Jalur Terpendek dan Maksimalisasi Keuntungan,” INTERVAL: Jurnal Ilmiah Matematika, vol. 4, no. 2, pp. 86–98, Sep. 2024.
[9] I. F. Mutiara and M. Azalia, “Penerapan Algoritma Branch and Bound dalam Menyelesaikan Penjadwalan Flowshop,” TALENTA Conference Series: Energy & Engineering, vol. 6, pp. 171–176, 2023.
[10] I. M. D. Pratiyaksa, A. F. Setiawan, and D. Rudhistiar, “Sistem Penerapan Metode Haversine pada Aplikasi Pencarian Toko Vape Terdekat di Kecamatan Lowokwaru Berbasis Mobile Android,” JATI (Jurnal Mahasiswa Teknik Informatika), vol. 8, pp. 7486–7493, Aug. 2024.
[11] A. P. Irawan and R. Adawiyah, “Penerapan Metode Haversine dalam Pencarian Lokasi Penjualan Alkes di Kota Medan Berbasis Android,” JID (Jurnal Info Digit), vol. 2, pp. 1464–1477, Nov. 2024, [Online]. Available: http://kti.potensi-utama.ac.id/index.php/JID
[12] F. M. Gurnitowati, Rochmad, and Supriyono, “Penerapan Algoritma Branch and Bound untuk Menentukan Rute Objek Wisata di Kota Semarang,” UNNES Journal of Mathematics, vol. 3, no. 1, pp. 49–55, 2014, [Online]. Available: http://journal.unnes.ac.id/sju/index.php/ujm
[13] E. Retnoningsih and F. N. Khasanah, “Rekomendasi Objek Wisata Provinsi Jawa Barat dengan Algoritma Branch and Bound,” Jurnal Penelitian Ilmu Komputer, System Embedded & Logic, vol. 6, no. 1, pp. 29–40, Mar. 2018.
Unduhan
Diterbitkan
Terbitan
Bagian
Lisensi
Hak Cipta (c) 2026 Jaysen Stephanus, Felix Gunawan, Yohannes Yohannes
Artikel ini berlisensiCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
