Design and Implementation of the Shortest Path Navigation in Samosir District using Branch and Bound Algorithm

Rudy Chandra; Tegar  Arifin Prasetyo

doi:10.29207/resti.v8i2.5585

Rudy Chandra Institut Teknologi Del https://orcid.org/0000-0002-2267-6365
Tegar Arifin Prasetyo Institut Teknologi Del https://orcid.org/0000-0001-8058-7961

DOI: https://doi.org/10.29207/resti.v8i2.5585

Keywords: Branch and Bound, Map, Samosir, Shortest Path, Tourist

Abstract

Samosir has a large area and several tourist attractions, making it difficult for visitors to explore the island. Unknowing the route can make the journey less fun and waste time. In general, tourists seek to know the fastest way to a tourist location to save time and money while on vacation. As a result, we require an application that will offer directions to the shortest path. This research aims to develop a web-based application that may display a map of the shortest travel to a tourist site. This website will display a map that marks the route from the origin point to the destination point. The Branch and Bound algorithm is used to determine the shortest path. The Python libraries OSMnx, Folium, and NetworkX modify paths and show a route map with OpenStreetMap. The error value of the distance between the branch, the bound algorithm, and Google Maps is used to obtain the RMSE accuracy value. The RMSE value is 3.02 and the MAPE value is 0.0023 indicating that the application produced already has a good implementation prototype. Furthermore, there is no significant distinction between the appearance of maps that implement OpenStreetMap and Google Maps.

Downloads

Download data is not yet available.

References

D. W. V. Napitupulu, F. Rahmafitria, and R. Rosita, “The Effect of Tourism Accessibility Perception Towards Tourists Visiting Intention to Toba Lake in Samosir District,” Journal of Indonesian Tourism, Hospitality and Recreation, vol. 4, no. 1, pp. 39–52, 2021, doi: 10.17509/jithor.v4i1.32410.

“Pariwisata | Kabupaten Samosir.” Accessed: Apr. 02, 2023. [Online]. Available: https://samosirkab.go.id/pariwisata/

H. M. P. Simarmata and R. S. Saragih, “The influence of tourism imagery on tourist visits in lake toba tourism object north sumatera,” Proceedings of the International Conference on Industrial Engineering and Operations Management, no. August, pp. 3848–3855, 2020.

S. Saraniemi and M. Kylänen, “Problematizing the concept of tourism destination: An analysis of different theoretical approaches,” J Travel Res, vol. 50, no. 2, pp. 133–143, 2011, doi: 10.1177/0047287510362775.

S. Hajar, B. Supriyono, M. R. Khairul Muluk, and A. Said, “Tourism Potential Planning Based Governance in the Lake Toba Area,” 2021.

A. Haryadi, E. Kusratmoko, and A. Karsidi, “Climate comfort analysis for tourism in samosir district,” in E3S Web of Conferences, EDP Sciences, May 2019. doi: 10.1051/e3sconf/20199405001.

S. Hajar, “Tourism Development Policy Through Economic Potential in Supporting Tourism and Creative Economy Programs in the Lake Toba Region,” International Journal of Health, Economics, and Social Sciences (IJHESS), vol. 4, no. 1, pp. 18–30, 2022.

N. Ginting and A. Sasmita, “Developing tourism facilities based on geotourism in Silalahi Village, Geopark Toba Caldera,” IOP Conf Ser Earth Environ Sci, vol. 126, no. 1, 2018, doi: 10.1088/1755-1315/126/1/012163.

R. Punmiya and S. Choe, “Energy theft detection using gradient boosting theft detector with feature engineering-based preprocessing,” IEEE Trans Smart Grid, vol. 10, no. 2, pp. 2326–2329, 2019, doi: 10.1109/TSG.2019.2892595.

M. E. Azhar, J. Jufrizen, M. A. Prayogi, and M. Sari, “The role of marketing mix and service quality on tourist satisfaction and loyalty at Samosir,” Independent Journal of Management & Production, vol. 10, no. 5, p. 1662, Oct. 2019, doi: 10.14807/ijmp.v10i5.937.

R. Perdana Sari, S. Rasio Henim, and P. Caltex Riau, “MEASUREMENT AND ANALYSIS OF TOURISM WEBSITE USER EXPERIENCE USING USABILITY TECHNIQUES.” [Online]. Available: https://pariwisata.pekanbaru.go.id/

S. Aggarwal and N. Kumar, “Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges,” Comput Commun, vol. 149, pp. 270–299, 2020, doi: 10.1016/j.comcom.2019.10.014.

F. Theurich, A. Fischer, and G. Scheithauer, “A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs,” EURO Journal on Computational Optimization, vol. 9, Mar. 2021, doi: 10.1016/j.ejco.2020.100003.

T. Arifin Prasetyo et al., “IMPLEMENTATION OF BRUTE-FORCE ALGORITHM AND BACKTRACKING ALGORITHM FOR FIREFIGHTING ROBOT SIMULATION,” Kumpulan jurnaL Ilmu Komputer (KLIK), vol. 10, no. 01, pp. 72–81, 2023.

Z. Zhang and Y. Han, “Discrete sparrow search algorithm for symmetric traveling salesman problem,” Appl Soft Comput, vol. 118, p. 108469, Mar. 2022, doi: 10.1016/J.ASOC.2022.108469.

Y. Shi and Y. Zhang, “The neural network methods for solving Traveling Salesman Problem,” in Procedia Computer Science, Elsevier B.V., 2021, pp. 681–686. doi: 10.1016/j.procs.2022.01.084.

D. Ferone, P. Festa, and F. Guerriero, “An efficient exact approach for the constrained shortest path tour problem,” Optim Methods Softw, vol. 35, no. 1, pp. 1–20, 2020, doi: 10.1080/10556788.2018.1548015.

D. Rachmawati and L. Gustin, “Analysis of Dijkstra’s Algorithm and A∗ Algorithm in Shortest Path Problem,” J Phys Conf Ser, vol. 1566, no. 1, 2020, doi: 10.1088/1742-6596/1566/1/012061.

T. Arifin Prasetyo, R. Chandra, B. Simamora, M. J. Christian, A. Rokyanto Silaban, and M. V. Siregar, “Pathfinding Solving in Maze Game using Backtracking Algorithms,” Jurnal CoreIT, vol. 9, no. 1, pp. 2599–3321, 2023, doi: 10.24014/coreit.v.

B. Appleton and C. Sun, “Circular shortest paths by branch and bound,” Pattern Recognit, vol. 36, no. 11, pp. 2513–2520, 2003, doi: 10.1016/S0031-3203(03)00122-5.

T. A. Prasetyo, “Particle Swarm Optimization and Genetic Algorithm for Big Vehicle Problem: Case Study in National Pure Milk Company,” 2021.

S. Poikonen, B. Golden, and E. A. Wasil, “A branch-and-bound approach to the traveling salesman problem with a drone,” INFORMS J Comput, vol. 31, no. 2, pp. 335–346, 2019, doi: 10.1287/ijoc.2018.0826.

S. Violina, “Analysis of Brute Force and Branch & Bound Algorithms to solve the Traveling Salesperson Problem (TSP),” 2021.

M. Dell’Amico, R. Montemanni, and S. Novellani, “Algorithms based on branch and bound for the flying sidekick traveling salesman problem,” Omega (United Kingdom), vol. 104, Oct. 2021, doi: 10.1016/j.omega.2021.102493.

S. Wahyuningsih and D. Retno Sari, “Study of the Brand and Bound Algorithm Performance on Traveling Salesman Problem Variants,” 2021.

W. Zhang and R. E. Korf, “An Average-Case Analysis of Branch and Bound with Applications: Summary of Results.” [Online]. Available: www.aaai.org

C. Agung and N. Christine, “PERFORMANCE ANALYSIS OF OPTIMIZATION METHODS FOR SOLVING TRAVELING SALESMAN PROBLEM,” Innovative Technologies and Scientific Solutions for Industries, no. 1 (15), pp. 69–75, Mar. 2021, doi: 10.30837/itssi.2021.15.069.

G. Zarpellon, J. Jo, A. Lodi, Y. Bengio, and P. Montréal, “Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies,” 2021. [Online]. Available: www.aaai.org

C. P. Tomazella and M. S. Nagano, “A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem,” Expert Systems with Applications, vol. 158. Elsevier Ltd, Nov. 15, 2020. doi: 10.1016/j.eswa.2020.113556.

D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, “Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning,” Discrete Optimization, vol. 19, pp. 79–102, Feb. 2016, doi: 10.1016/j.disopt.2016.01.005.

T. O. Hodson, “Root-mean-square error (RMSE) or mean absolute error (MAE): when to use them or not,” Geoscientific Model Development, vol. 15, no. 14. Copernicus GmbH, pp. 5481–5487, Jul. 19, 2022. doi: 10.5194/gmd-15-5481-2022.

D. Chicco, M. J. Warrens, and G. Jurman, “The coefficient of determination R-squared is more informative than SMAPE, MAE, MAPE, MSE and RMSE in regression analysis evaluation,” PeerJ Comput Sci, vol. 7, pp. 1–24, 2021, doi: 10.7717/PEERJ-CS.623.