A Depth-First Branch and Bound Algorithm for Integer Knapsack Problem in Freight Transportation

Abstract

E-commerce growth so rapidly in Indonesia and giving great opportunity for logistics service in order to give easiness for customer to make deliveries. Pos Indonesia (Persero) is an Indonesian state-owned companies engaged in delivery of goods and letter. In sending a goods, its important to choose the right goods that will be lifted into the freight transportation. The more optimal load of goods, the more income will be gotten. To find an optimal selection of solution, it can be modeled as Integer Knapsack problem by optimizing the maximum capacity of knapsack. The purpose of the research is to get an optimal solution by selecting a right goods based from weight using Depth-First Branch and Bound in freight transportation of Pos Office Mataram. Total weight from 23-31 august 2022 is 11,563.3 kg and get Rp. 16,259,430.00 income can be delivered in 11 days using Depth-First Branch and Bound better than an actual shipment that need 12 days to distributed all of goods. Therefore, the accumulate of weight using Depth-First Branch and Bound more effective and it can be used as an alternative solution to get an optimal selection of goods in freight transportation.