Implementation of Held-Karp Algorithm to Calculate Shortest Route Path

Yulianto Bayu Prasetyo, Moh. Ali Romli

Held-Karp Algorithm, Traveling Salesman Problem, Android, Google Maps.

Shipping goods has become a part of the current economic growth in society. In the digital era and the advancement of e-commerce, the demand for shipping services is increasing. However, the process of selecting an efficient and optimal delivery route remains a complex challenge. Currently, some couriers and delivery service providers still rely on manual methods or inaccurate estimates, resulting in inefficient deliveries and higher costs. Based on previous research, the Held-Karp algorithm produces better results than the Iterative Deepening Search algorithm in finding optimal delivery routes. Therefore, in this study, an Android application was developed using Google Maps services and integrating the Held-Karp algorithm. The Held-Karp algorithm is used to optimize the delivery route, considering the most efficient distance and delivery sequence. The results will be displayed in an interactive map, facilitating couriers in performing their delivery tasks. By using this application, it is expected to improve the efficiency of goods delivery, reduce delivery time, and optimize the utilization of courier resources. The development of this application requires knowledge of the Held-Karp algorithm, Android-based programming, and integration with map services such as the Google Maps API.

https://doi.org/10.31871/IJNTR.9.12.4