A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem

•Propose a bi-level Voronoi diagram-based metaheuristic for solving MDVRP.•Implement an algorithm to solve large-scale MDVRP instances up to 20,000 customers.•Demonstrate Voronoi diagrams’ benefits in generating high-quality MDVRP solutions.•An approach to handle tradeoffs between solution quality and computational demand.

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.