Abstract: We propose a two-stage algorithm (TSA) for solving the multi-depots vehicle routing problem (MDVRP). The first stage of TSA is decomposition. The problem being considered has a large feasible solution region. To control the scale of the problem and reasonably guide the algorithm to search in the high-quality solution region, we design a hybrid Gaussian mixture clustering algorithm that employs a nearest neighbor strategy (HGMA) to decompose the MDVRP into a series of single-depot VRPs. The second stage of the TSA is problem solving. We propose an enhanced ant colony optimization (EACO) method for solving the decomposed subproblems (the VRPs) and obtaining the solution to the original problem. We add a control factor to dynamically adjust the pheromone decay parameter in the EACO to effectively control the volatilization of the pheromone and improve the global search ability of the ACO. We also design a two-stage variable neighborhood search (TVNS) based on multiple variable neighborhood operations to enhance its the local search ability. Simulation experiments and comparisons of instances with different scales demonstrate the effectiveness of the proposed TSA.