Travel application itinerary using the traveling salesman problem method and the held-karp algorithm

Abstract

The Kapuas Hulu Regency is home to several fascinating tourist spots, yet finding directions inside the regency can be challenging for visitors. The Held-Karp Algorithm can be used to find the fastest route between any two cities with only one stop, which is known as the Traveling Salesman Problem (TSP). Bellman, Held, and Karp created this dynamic program in 1962 with the goal of minimizing travel time and expenses. The number of cities to be visited (forming nodes in the graph), the point of origin (the starting node in the graph), and the distances between the cities (weights between the nodes) must all be specified in the model of the TSP problem before the Held-Karp Algorithm can be applied. The focus of this study will be tourist destinations in West Kalimantan's Kapuas Hulu Regency. A system that uses the Held-Karp Algorithm to find the shortest paths between different tourist spots in Kapuas Hulu Regency will be built as part of this project. As a result, this technology will help tourists plan their trips effectively and minimize their expenditures for both time and transportation