Track: Operations Research
PT. Rariza Putra is a company engaged in the distribution of Liquefied Petroleum Gas (LPG) 3 kg. The distribution route starts from the Oil Fuel Filling Station (SPBE) to each customer venue. In the distribution method, the company determines the route only by decisions made by the driver, because the company does not have a fixed distribution route. It means that the resulting route is not an optimal route. With the existing problems, the company needs a problem-solving method that would provide a solution to calculate the shorter route to reduce transportation and fuel costs. This research was conducted on the Vehicle Routing Problem (VRP) with the Capacitated Vehicle Routing Problem (CVRP) approach, which determines the route by taking into account the capacity of the vehicle, and also Vehicle Routing Problem with Multiple Trips (VRPMT), which determines the route for each vehicle to make more than one delivery, and Vehicle Routing Problem with Split Delivery (VRPSD), where each base can be visited more than once. The method used in solving this problem is the Saving Matrix and also the Nearest Neighbor methods. These two methods will be compared to the initial route that exists in the company, and the method that gives the optimal results will be chosen. Based on the processing that has been carried out with the both methods, the Nearest Neighbor method is chosen which gives more optimal results in determining the route and also affects the fuel costs incurred. The route generated by the nearest neighbor method in one week is 283,37 km with a comparison of the initial route length of 391,17 km. While the total fuel cost savings that occur every week on the nearest neighbor method is Rp. 208.475 with a cost comparison on the initial route of Rp. 289.773 with a difference of Rp. 81.298. The new distribution route provides 28% savings compared to the initial route in the company.