Implementation of the Branch and Bound Method to Optimize the Nearest Tourist Routes in Palembang City
DOI:
https://doi.org/10.58466/eqadem96Keywords:
Branch and Bound, Haversine, Travelling Salesman Problem, Palembang, OpenStreetMapAbstract
This study discusses the application of the Branch and Bound method to optimize the nearest tourist route in Palembang City using the Traveling Salesman Problem (TSP) approach. The problem raised is how to determine the most efficient tourist route from several tourist destinations with minimum travel distance. The study utilizes geographic coordinate data of tourist destinations obtained through OpenStreetMap, then the distance between locations is calculated using the Haversine Formula to obtain an accurate distance estimate based on latitude and longitude. Furthermore, the Branch and Bound Algorithm is used to find the optimal route solution through the process of branching, bounding, and pruning so that the solution search becomes more efficient than the brute force method. The results show that the system successfully produces an optimal circular tourist route with a total minimum distance of 40.47 km and an execution time of 12.84 seconds. The integration of the Haversine Formula and Branch and Bound is proven to be able to provide efficient, accurate, and adaptive tourist route recommendations to help tourists save travel time and transportation costs in Palembang City.
References
[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.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Jaysen Stephanus, Felix Gunawan, Yohannes Yohannes
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
