An effective Memetic Algorithm for Multi-depot Weighted Vehicle Routing Problem

The weighted vehicle routing problem (WVRP) is a very important extended vehicle routing problem during post-disaster scenarios for it considers not only the arrival time but also the urgency for each customer. In this paper, we tackle the multi-depot WVRP (MDWVRP), a more practical WVRP since a customer can be assigned to an appropriate depot. For MDWVRP, the number of vehicles located at each depot is restrained, and the number of the total vehicles used for all depots is also limited. To address this problem effectively, we propose a novel memetic algorithm (MA), in which an initializing scheme, a contribution-based crossover operator, and a local search method with different sizes are developed. The designed crossover operator can adjust the proportion of the arcs inserted into offspring from parents according to their fitness. In this sense, the better parent contributes more arcs to child, and vice verse. Moreover, two repair operators are applied to infeasible solution with violation of the number constraints of used vehicles so that the search can be conducted in large space. To demonstrate the effectiveness of the proposed algorithm, it is compared with several state-of-the-art algorithms on two benchmark datasets. The results show that the algorithm outperforms the leading algorithms on all instances, and updates all best-known solutions with an exception which is yet reached by the proposed algorithm. It is noticeable that most best-known solutions are improved by the algorithm with a significant level, the largest gap is over 25%.