PENERAPAN ALGORITMA BRANCH AND BOUND UNTUK JALUR TERPENDEK DAN MAKSIMALISASI KEUNTUNGAN

Abstract

Optimizing distribution costs is the main key for companies to achieve maximum profits. One method that can be used to solve problems related to distribution is the Traveling Salesman Problem (TSP). Traveling Salesman Problem (TSP) is a problem in finding the shortest route for a salesman by visiting all places in an area exactly once in each city and returning to the starting city. The branch and bound method is an algorithm method that is commonly used to determine the optimal solution to optimization problems, especially in discrete and combinatorial optimization. As the name suggests, this method consists of 2 steps, namely Branch, which means building all possible tree branches leading to the solution, and Bound, which means calculating which nodes are active nodes (E-nodes) and which nodes are dead nodes (D-nodes) using constraint boundary conditions. The results of calculations and processing carried out on distances between locations using the method used by the Traveling Salesman Problem with the Branch and Bound algorithm produce the best and optimal route, namely the 1-4-3-5-2-1 route with a Z or optimum value of 231.