The problem that often occurs in the process of distributing goods is that the distribution route is not optimal so that the costs incurred are greater and the travel time is longer. This can be solved by finding the shortest path that can be passed or what is known as the Traveling Salesman Problem (TSP). This study aims to determine the optimal distribution route for goods using a combination of the Branch and Bound and Cheapest Insertion Heuristic algorithms. The data used are in the form of location names and distances between locations that have been collected by Putra BJ Bangun in his research entitled Solving the Traveling Salesman Problem (TSP) with the Branch and Bound Method (Application of the Palembang Post Office Goods Transportation Problem). The results of the study show that the optimal route for the distribution of goods at the Palembang City Post Office, using a combination of both algorithms, is: KPRK Palembang → KPC Kapt A. Rivai → KPC Pakjo → KPC Talang Ratu → KPC Sukarami → KPC Alang Lebar → KPC Sekip → KPC Cinde → KPRK Palembang, with a total distance of 24.3 km. This route can be an alternative for salesmen to visit several KPCs and return to KPRK, with more efficient costs and time because it is the shortest route. In addition, this combination of algorithms is more efficient and simpler in terms of processing steps and computing time compared to using the Branch and Bound algorithm.

Keywords: Traveling Salesman Problem (TSP), Branch and Bound, Cheapest Insertion Heuristic, Algorithm Combination, Optimal.