Application of K-Means Clustering and OR-Tools to Optimize Rice Distribution: A Case Study of Perum Bulog Indonesia

Food security is one of the Indonesian government's priority policies aimed at maintaining economic and political stability. To ensure the nutritional needs of its population are met, the government requires sufficient food availability distributed nationwide at stable and affordable prices. Rice is the main staple food in Indonesia. According to data from the National Food Agency, rice consumption in Indonesia is very high, averaging 139 kilograms per capita per year, with a dependency rate of 97%. In response to food security challenges, the Indonesian government has entrusted the Food Supply and Price Stabilization Program (SPHP) for rice to Perum BULOG, a State-Owned Enterprise (SOE) specializing in food logistics. To optimize distribution to Perum BULOG’s retailers, called Rumah Pangan Kita (RPK), efficient routes and transport capacity are prioritized. Therefore, this paper proposes an approach using the Heterogeneous Capacitated Vehicle Routing Problem (HCVRP) to enhance distribution efficiency and reduce delivery costs. By employing the K-Means algorithm to cluster RPK addresses and Guided Local Search via OR-Tools to determine suitable transportation types, this study successfully identified optimal delivery routes for each cluster and corresponding vehicle types. The results demonstrated a reduction in delivery costs of up to 21%, significantly improving the efficiency of the SPHP rice distribution process. This outcome ultimately supports rice availability and price stability, crucial for maintaining food security in Indonesia.