A reactive GRASP algorithm for the multi-depot vehicle routing problem with time windows

Abstract

The vehicle routing problem (VRP) is a well know hard to solve problem in literature. In this work, we describe a reactive greedy randomized adaptive search procedures algorithm, for short, reactive GRASP, using a variable neighborhood descent (VND) algorithm as local search procedure to solve the multi-depot vehicle routing problem (MDVRP) and multi depot vehicle routing problem with time windows (MDVRPTW). This algorithm, called RGRASP+VND, combines four distinct local search procedures and a clustering technique. The Cordeau et al. dataset, a widely well known MDVRP benchmark, is considered for the experimental tests. RGRASP+VND achieves better results on most small instances and a lower average solution cost for all instances on the experimental tests when compared to the earlier GRASP approaches in the MDVRP literature. RGRASP+VND results are also compared with the state-of-the-art of MDVRP and MDVRPTW.