Algoritma Branch and Bound dengan Clustering Metode Sweep untuk Menyelesaikan Masalah Vehicle Routing Problem(VRP) (Studi Kasus: PT. Mitha Artha Keluarga)

Abstract

The vehicle routing problem is a combinatorial optimization problem that aims to determine the most efficient route for a number of vehicles to deliver goods to a number of bases. PT Mitha Artha Keluarga, as an authorized agent for the distribution of 3 kg LPG gas, ensures the smooth distribution of the subsidized product. One of the disbution problem is about delivery delays of shipment products. This research uses the Branch and Bound Algorithm to obtain the optimal route to travel from the origin point to the destination point and back to the origin point by exploring all possible routes for the distribution of 3 kg LPG gas by PT Mitha Artha Keluarga in the Pematangsiantar area using the Branch and Bound Algorithm. Because the bases visited route by Branch and Bound will take a very long time in determining the route, this research utilizes the Sweep Method in clustering where the bases are grouped based on their geographical location to facilitate distribution. This method found the shortest route of 244.58 km out of 408.8 km. This shows the results that the Branch and Bound Algorithm with clustering using the Sweep Method is able to provide efficient shortest route solutions, so that it can help improve the efficiency of LPG gas distribution.