The Capacitated Vehicle Routing Problem (CVRP) is a well-known NP-hard problem where multiple vehicles must collect goods from customers and deliver them to a depot while respecting a capacity constraint. A common approach for solving the VRP is the Large Neighborhood Search (LNS) algorithm, which iteratively improves solutions by partially destroying and repairing them using various removal and insertion operators. In our study, we evaluated the use of fitness-based, density-based, proximity-based, and randomness operators, and we analyzed their individual and combined effects on solution quality. Our algorithm first generates an initial solution by applying k-means clustering, followed by the cheapest insertion heuristic that routes each cluster in dependently. This process that generates the initial solution is implemented in a deterministic manner to always have the same initial solution for the same in stance. This initial solution is then improved using LNS. We evaluated our method on four maps from the classic Solomon benchmark.