The vehicle routing problem is a critical research issue in logistics because the strategies used may strongly impact its performance. A good strategy would allow the management to make a good decision to enhance the performance of logistics. In practice, we have to consider two or more factors in solving the vehicle routing problem at the same time. An effective hybrid search algorithm for the vehicle routing problem with time windows is presented in this study, which takes into account at the same time the number of vehicles and the total distance for vehicles based on a novel metaheuristic algorithm named coral reefs optimization algorithm with substrate layers (CRO-SL). The experimental results show that the proposed algorithm outperforms all the other state-of-the-art algorithms compared in this paper.