A tabu search algorithm with variable cluster grouping for multi-depot vehicle routing problem

We herein present a tabu search algorithm with variable cluster grouping (TSVCG for short) to deal with Multi-depot vehicle routing problem (MDVRP for short). In TSVCG, we firstly adopt variable cluster grouping to convert a complicated MDVRP to typical single depot vehicle routing problem (SDVRP for short). And then we apply a tabu search algorithm to solve each SDVRP. In the grouping process, we discuss how to find a scale factor and minimum geometric semicircle correction factor to improve the customer points´ grouping, and thus get the different groups for further problem-solving. The experimental results shown that the proposed variable cluster grouping can reduce grouping blindness and improve the efficiency of grouping and viability of group results. The results also shown that the proposed TSVCG performed well compared with the previous work with the geometric grouping.