This study was conducted to help PT XYZ reduce its distribution costs, which have been considered relatively high. PT XYZ is a mung bean distribution company based in Bekasi. In this research, two approaches were applied: first, determining a new strategic warehouse location using the Center of Gravity method, and second, optimizing delivery routes using the Saving Matrix method. The analysis showed that relocating the warehouse to a new location (in the Jakamulya area, Bekasi City) would actually increase the total distribution distance by 101.9 km, from 284.19 km to 386.1 km. Consequently, the distribution cost would rise from IDR 5,100,140 to IDR 5,581,600, an increase of IDR 481,460. This indicates that the current warehouse location remains more efficient than the proposed new one. However, by optimizing the delivery route using the Saving Matrix method, significant cost savings were achieved. Operational costs were reduced from IDR 2,712,340 to IDR 1,756,830, resulting in a cost reduction of 35.26%. This shows that even without relocating the warehouse, efficiency can still be achieved through route optimization. In conclusion, the Center of Gravity method is less suitable for PT XYZ's case as it increases costs, where as the Saving Matrix method proves to be effective in significantly reducing distribution expenses.