Optimasi Rute Pendistribusian Barang Menggunakan Kombinasi Algoritma Branch and Bound dan Cheapest Insertion Heuristic - Oeitama, Whennie Youngger; Oeitama, Whannie Youngger; Sitandi, Flora Frisilia; Mas'ud, Syamsuddin (UIN Walisongo Semarang, 2024)
The problem that often occurs in the process of distributing goods is that the distribution route is not optimal which results in higher costs and longer travel times. This can be solved by finding the shortest path that can be passed or widely recognized 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 research indicate 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, spanning a total 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.