Perbandingan Metode Branch and Bound dan Metode Cheapest Insertion Heuristics dalam Penyelesaian Travelling Salesman Problem - Alfanadim, Andraya; Winarno, Winarno; Zahra, Shakila Divala; Nudin, Muhammad Ihsan (Industrika : Jurnal Ilmiah Teknik Industri, 2026)
This study aims to compare the efficiency of the Branch and Bound (B&B) and Cheapest Insertion Heuristics (CIH) methods in solving the Traveling Salesman Problem (TSP) for optimizing delivery routes at PT BT. The study was conducted to determine the shortest delivery route, which has implications for fuel cost savings. Primary data in the form of delivery routes to five customer locations were analyzed using manual calculations and validated using the WinQSB software. The results show that the B&B method produces a route with a total distance of 114.6 km and fuel cost savings of 13.444% compared to the original route, while the CIH method provides a distance of 114.8 km with savings of 13.293%. Although both methods show almost similar results, the B&B method is superior in minimizing distance and costs. This study provides recommendations for PT BT to implement the B&B method as an optimal solution in distribution management, in order to improve operational efficiency and customer satisfaction. Keywords: Branch and Bound; Cheapest Insertion Heuristics; Cost Savings; Route Optimization; Traveling Salesman Problem.