In this paper, a bi-level Voronoi diagram-based metaheuristic is introduced to solve the large-scale multi-depot vehicle routing problem (MDVRP). The upper level of the Voronoi diagram, derived from the depots, is used to allocate customers to depots. The lower level of the Voronoi diagram, derived from the customers, limits the search space of reallocating customers among the depots and rearranging the customers among the routes from each depot to its Voronoi neighbors. The results of numerical experiments clearly indicate the benefits of this proposed bi-level Voronoi diagram approach for solving very large-scale MDVRPs while balancing the solution quality and the computational demand.