Implementasi Metode Hill Climbing untuk Mencari Rute Terbaik Saat Pengantaran Air Galon pada Usaha Galon Isi Ulang Nada Cinta

The use of route optimization in distribution processes has become an essential requirement for refillable gallon water businesses to improve operational efficiency. Nada Cinta Refill Gallon Water Business still determines delivery routes manually, resulting in ineffective travel time and fuel consumption. This study aims to implement the Hill Climbing algorithm to find optimal distribution routes using the Open Traveling Salesman Problem (Open TSP) approach. The Hill Climbing algorithm works heuristically by performing gradual solution improvements through an adjacent swap mechanism (neighbor position exchange) until reaching a local optimum condition. The system was developed as a web-based application using the Laravel framework and MySQL database to manage customer data, distance between locations, and optimal route calculation processes. Distance data were obtained using the FieldCalc application. System testing results show that the Hill Climbing algorithm successfully optimized delivery routes with significant travel distance reduction compared to manual routes, thereby improving operational distribution efficiency. The accuracy of the algorithm implementation was validated through comparison with manual calculations using Microsoft Excel, which showed consistent results. Black Box Testing demonstrates that all system functions operate according to functional requirements. The implementation of this system improves delivery time efficiency, saves fuel, reduces operational costs, and enhances customer service quality.