Clustering-Based Search in a Memetic Algorithm for the Vehicle Routing Problem with Time Windows

This paper addresses the vehicle routing problem with time windows (VRPTW), aiming to minimize the total travel time. A simple memetic algorithm (MA) is proposed for solving this problem. At the beginning of the search, a clustering procedure is applied to customers' spatial information. The search procedure consists of relocating customers between close routes, seeking to minimize detour costs associated with the relocations. The information gathered by the clustering procedure is used to identify which routes lie close to each other. Computational experiments on the Solomon's benchmark set show the effectiveness of the proposed approach, which produces competitive solutions and outperforms four out of six solution approaches considered for comparison regarding the travel cost attained over all the instances of the benchmark set.