Optimization of the Capacitated Vehicle Routing Problem (CVRP) and Distribution Costs in a Drinking Water Company

Abstract

This study examines the optimization of bottled water distribution logistics at a water company that serves eight regular customers using two Isuzu Traga Box fleets, each with a capacity of 400 cartons. The study addresses the Capacitated Vehicle Routing Problem (CVRP) by comparing three proven route optimization methods: the Saving Matrix Algorithm, the Nearest Insertion Heuristic, and the Nearest Neighbor Algorithm. The research methodology integrates exponential smoothing techniques for demand forecasting and utilizes Google Maps and Google Earth for precise distance measurements and route planning. The initial distribution system operated with 8 separate routes covering a total distance of 327.6 km, resulting in inefficient resource utilization and high operational costs. Through comprehensive optimization analysis, all three methods demonstrated significant efficiency improvements with varying performance levels. The Saving Matrix algorithm achieved the highest distance reduction of 33.67%, followed by Nearest Insertion at 33.59%, and Nearest Neighbor at 32.74%. The Saving Matrix method, selected as the optimal solution based on comprehensive performance evaluation, successfully redesigned the distribution network into 4 consolidated routes with a total distance of 220.35 km. This optimization resulted in substantial operational improvements, including: reducing delivery time from several days to 2 working days, reducing fuel consumption costs by 33.67%, and an extraordinary 60% reduction in driver meal allowances. This implementation also improved vehicle utilization efficiency and enhanced customer service reliability. The study concluded that the Saving Matrix Algorithm provides the most effective and practical solution for improving distribution logistics efficiency in the bottled water industry, offering significant cost savings while maintaining service quality standards.