OPTIMALISASI CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) DAN BIAYA DISTRIBUSI DI PERUMDA AIR MINUM TIRTA SANJIWANI KABUPATEN GIANYAR BALI

Perumda Air Minum Tirta Sanjiwani Gianyar Bali is a bottled drinking water company that has 8 regular customers and has 2 types of Isuzu Traga Box fleet with a capacity of 400 cartons. Problems arise when distributing products, namely working time management regarding travel distance and travel time when fulfilling customer requests, which must be completed during the week. This research aims to determine the optimal route that a company must take to create minimum distribution costs. This research uses the savings matrix, nearest insertion, and nearest neighbor methods which will be compared. Next, demand forecasting was carried out using the exponential smoothing method in MS Excel, and the distance matrix was measured using Google Maps and Google Earth. The initial routes owned by the company were 8 routes with a total distance of 327.6 km. The results of the optimization calculations produce a percentage of distance savings in the saving matrix of 33.67%, the nearest neighbor of 32.74%, and the nearest insertion of 33.59%. The saving matrix method was chosen as the recommended method for companies that produce 4 optimal routes with a total distance of 220.35 km, in terms of delivery time it can save up to 2 working days with a total fuel savings of 33.67% and food cost savings of 60%.
Keywords: Route Optimization, Distribution Costs, Savings Matrix, Nearest Neighbor, Nearest Insertion