© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.This paper presents a case study that addresses the problem of vehicle routing to improve the distribution services of a newspaper distributor operating in Istanbul, Turkey. It is the priority of newspaper distribution companies to improve the distribution activity, to reduce the number of personnel, to reduce the cost incurred in the distribution process, and to provide services with the least number of vehicles in order to address the problem of newspaper distribution (NDP), which has become even more costly with the increase in the rate of reading electronic newspapers. The purpose of this study is to examine the capacitated vehicle routing problem (VRP) with heterogeneous vehicles and to evaluate the results through case analysis. K-means were used for clustering the customers and simulated annealing (SA) and particle swarm optimization (PSO) based metaheuristic approaches were proposed to solve this real-world problem. Finally, the performance of the proposed approaches was evaluated. The numerical results showed that the proposed SA based approach with k-means performed better than PSO and can find the most suitable solutions within reasonable computation time in large-scale problems.