A Memetic Search for Multi-Depot Cumulative Capacitated Vehicle Routing Problem

Abstract

The cumulative capacitated vehicle routing problem (CCVRP) is a variant of the vehicle routing problem that aims at minimizing the sum of arrival times of the vehicles at customers to ensure efficiency and fairness. It has many practical applications such as natural disaster rescue and school bus routing. In this paper, we investigate a more practical extensive version of CCVRP, the multi-depot CCVRP (MDCCVRP), which is a challenging problem since a customer can be assigned to any capacitated depot where a given number of vehicles are located, and the number of the total vehicles used for all depots is limited. In this paper, we propose a memetic algorithm (MA) to solve MDCCVRP, in which the adaptive crossover operator based on Q-learning, the initializing procedure, and the local search method are designed and combined smartly so that the search can be conducted in a large space. Firstly, three different initialization methods are adopted to create a diverse population in which the constraints for vehicles are ignored. Then, the population undergoes crossover operator and the offspring are improved by local search. The newly generated individuals with constraint violations are updated once the violations are eliminated by two employed repair operators in a separate way. Compared with the state-of-the-art algorithms on five benchmark datasets, the proposed MA outperforms them in the vast majority of cases. Moreover, the best-known solutions to substantial numbers of instances are updated. Note to Practitioners—This work deals with the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP). Compared with traditional vehicle routing problem (VRP), MDCCVRP is hard to address due to its complex structure and vehicle constraints. A memetic algorithm (MA) is proposed in this paper to tackle MDCCVRP. The proposed algorithm consists of a novel adaptive multi-route crossover operator, an initializing procedure with different initialization methods, a repair procedure based on double repair mechanism, and a local search procedure. The proposed MA successfully identifies new best-known solutions for the majority of MDCCVRP instances. Experimental results demonstrate its effectiveness in addressing the MDCCVRP, highlighting its potential to support decision-makers in optimizing route planning for real-world applications.