OPTIMALISASI RUTE DISTRIBUSI MENGGUNAKAN METODE EKSAK ALGORITMA BRANCH AND BOUND

CVRP (Capacitated Vehicle Routing Problem) is a problem of route and vehicle capacity in distribution. Based on distribution channels, the authors analyze the fuel costs that must be incurred to distribute the product by considering the distance traveled by each distributor served. On the other hand, vehicle capacity also needs to be taken into account to be able to deliver products according to distributor needs. In this study, the authors optimize the distribution route using the Exact Branch and Bound algorithm method. The goal is to distribute products and costs in one of the MSMEs in North Sumatra, namely Sunny Glass Home Industry. As the name implies, the Branch and Bound algorithm limits the solutions that will produce numbers, then branching decision variables that do not have integer solutions, branching is done continuously until it produces integers and optimal decision variables. Optimization of distribution routes is not only based on distribution mileage, but also on vehicle type, vehicle capacity, and current fuel prices. With various scenarios, the results of this study prove that distribution costs can be minimized up to 72.1% of initial costs with optimal distribution routes.