A Multi-objective Variable Tabu Neighborhood Search Algorithm for Multiple Depot Vehicle Routing Problem in Epidemics

During epidemics, the transportation of medical resources from storage places to communities plays a crucial role, which can be regarded as a vehicle routing problem (VRP). However, the traditional VRP primarily focuses on the transportation cost of vehicles and typically revolves around a single depot, limiting its applicability. Therefore, this paper extends the VRP model and introduces a multi-objective and multi-depot aspect of VRP for epidemic (MOMDVRP4E) model, which can effectively address the multi-depot scenarios and additional costs stemming from the preventive policies in high-risk regions. For this new model, existing multi-objective optimization algorithms still encounter the issues with low-quality initial solutions and incomplete searches. To address these challenges, this paper proposes a Multi-objective Variable Tabu Neighborhood Search algorithm named MOVTNS. Initially, the MOVTNS utilizes the fuzzy clustering to generate high-quality initial solutions. Subsequently, a new two-stage three-population algorithm framework is proposed to enhance the search coverage. In the first stage, two populations are deployed to seek optimal solutions for two objectives parallelly, which effectively explores the edge-part solutions. In the second stage, a new population is employed to pursue the cooperative objective based on two independent populations, which explores the central part of the Pareto front from the edge part solutions. Extensive experiments on benchmarks validate the effectiveness of MOVTNS, showcasing its superior performance over various state-of-the-art algorithms.