Multi-Start metaheuristics (MSM) are commonly used to solve vehicle routing problems (VRPs). These methods create different initial solutions and improve them through local-search. The goal of these methods is to deliver the best solution found. We introduce initial-solution classification (ISC) to predict if a local-search algorithm should be applied to initial solutions in MSM. This leads to a faster convergence of MSM and higher-quality solutions when computation time is limited. In this work, we extract features of a capacitated VRP (CVRP) solution, by transforming the structure of a solution into quantitative metrics (i.e.number of customers in each route, average compactness of a route, or number of intersections between routes). With these features and a machine-learning classifier (random forest), we show how ISC --significantly-- improves the performance of greedy randomized adaptive search procedure (GRASP), over benchmark instances from the CVRP literature. With the objective of evaluating ISC's performance with different local-search algorithms, we implemented a local-search composed of classical neighborhoods from the literature and another local-search with only a variation of Ruin-and-Recreate. In both cases, ISC significantly improves the quality of the solutions found in almost all the evaluated instances.