Solving a Large-Scale Multi-Depot Vehicle Routing Problem Heuristically

This chapter focuses on the distribution plan of a large-scale distributor of care and cleaning products to its customers located in the eastern and south eastern regions of Turkey. The distribution network consists of three depots and 502 customers. The vehicle fleet consists of homogeneous vehicles. The problem is to determine which depot should serve which customers including the routing decisions, which is an instance of the well-known Multi-Depot Vehicle Routing Problem (MDVRP). The authors use a cluster-first, route-second approach to solve the model. To do so, we first use the capacitated p-median formulation for clustering and assignment of customers to each depot. Next, we use a single-depot VRP to solve the routing problem for each depot and its cluster of customers. For this, a Guided Local Search metaheuristic is implemented and Google-OR-Tool is utilized as a solver. Real data of the company including demands, vehicle capacities, exact coordinates of depots and customers is utilized. Detailed computational experiments and their results are presented.