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 to higher-quality solutions when the amount of computation time is limited. In this work, we extract known features of a capacitated VRP (CVRP) solution and we introduce additional features. 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.