Implementation of Branch and Bound Algorithm to Solve the Travelling Salesman Problem at PT Jasa Harapan Barat

Abstract

In the industrial world, every industrial company wants to get maximum profit. One way to increase profits is to minimize distribution costs. PT Jasa Harapan Barat is one of the bottled beverage distributor companies Cap Badak which is not only known in the city of Pematang Siantar, but throughout North Sumatra, even outside North Sumatra. So, the right minimum trajectory is needed so that distribution becomes faster. This minimum path problem is included in the Traveling Salesmen Problem (TSP). One way to solve TSP is by using the Branch and Bound algorithm. With data obtained from interviews and direct observations, it was obtained that solving TSP with the Branch and Bound algorithm obtained minimum paths and the total minimum path was 25.49 km. The search for the minimum path is done with the help of WINQSB software, where the length of the path of each distributing vertex is taken from google maps. And if you apply the Branch and Bound Algorithm to solve the Traveling Salesman Problem at PT Jasa Harapan Barat, the distribution cost will be cheaper for Rp. 15,093 for each distribution of Cap Badak drinks.