XYZ Ltd. is a daily newspaper company, one of which is located in Kartasura, Sukoharjo. Newspapers were distributed to 11 locations around Kartasura and Klaten. In the delivery process, there are limitations such as the number of vehicles and vehicle capacity. The company wants to find a better or shorter route in distributing its products to agents to minimize transportation costs. This issue can be considered a Capacity Vehicle Routing Problem. In this study, the sweep algorithm was first used to find the initial solution. The local search procedure is used for the solution obtained by the sweep and nearest neighbor algorithm. The new first route is Depot-A2-A4-A5-A6-A10-A1-Depot, while the second route is Depot-A7-A3-A8-A9-A11-Depot. Those routes are found using local search combination of 1-insertion intra route, and swap intra route. After that, the minimum cost is calculated. The results are a decrease in the distance, time, and fuel costs from the previous route. The improvements are saving IDR 1,119,323 per year, 8 minutes faster, and 4.3 km shorter than the previous route for route 1 and IDR 728,862 per year, 6 minutes faster and 2.8 km shorter than the previous route for route 2.