This study focuses on gasoline and diesel fuel distribution process at Boyolali fuel terminal, Indonesia. This terminal is responsible to deliver fuel to more than 290 fuel stations in Central and East Java provinces. The distribution area is divided into three zones, utilizing both single and multi-destination methods. Since the deliveries are done based on order priority and time windows, single-destination method is preferable, especially when delivering fuel to 47 gas station in Zone 3, causing a not optimal distribution scenario. Thus, a more effective and efficient distribution process for Zone 3 is needed. Creating an optimized distribution cost is started by clustering gas stations using P-Median, considering the distance between points. The optimization model is Multi Compartment Vehicle Routing Problem (MCVRP) with split delivery and multi product with the objective function of minimizing total distribution costs (considering tank truck’s fuel cost and carbon emission cost). Branch and Bound (B&B) algorithm is applied to solve the exact method of distribution route optimization, using LINGO software. The results show that by clustering Zone 3 gas stations into 9, the total daily distribution costs are reduced from IDR 12,712,435.20 to IDR 9,179,116.80, resulting to 28% reduction.