Location routing problem with interdependent mobile depot operations for post-disaster relief

When a disaster occurs, a sound and timely response is essential to reduce casualties and losses. Since rescue vehicles are mostly powered by electricity, the endurance of them is not comparable to that of traditional vehicles. Therefore, it is of great significance to study how rescue vehicles can execute multiple tasks quickly and efficiently with limited energy in cooperation with fuel-driven transportation platforms, called depots. Based on the characteristics of disaster rescue, a new variant of location routing problem (LRP), called location routing problem with interdependent mobile depot operations (LRPIMD), is introduced, considering the cooperation among transportation platforms and rescue vehicles. The mobility of the transportation platforms and the introduction of the interdependent depot operation bring challenges to solve the problem, as the complex coupling relationships among the task sets of various locations need to be considered. An improved memetic algorithm with novel heuristics (IMA-NH) is proposed to efficiently solve LRPIMD. Firstly, a heuristic-assisted initialization rule (HaIR) is designed taking into account the cooperation among transportation platforms and rescue vehicles. Then, a novel sequence-based crossover operator (NSC) is suggested, which effectively utilizes the excellent genes in parents and explores the solution space in three dimensions, including depot configuration, task selection and execution sequence. Finally, a variety of smart neighborhood structures are introduced to improve the effectiveness of the local search. A comparison about the proposed algorithm against several state-of-the-art algorithms and the commercial solver Gurobi is constructed. Computational results indicate that IMA-NH has a satisfactory performance in solving LRPIMD and is a competitive algorithm. It is also verified that the introduction of interdependent mobile depot operations can reduce the unnecessary energy consumption of rescue vehicles on travelling, thereby improving the efficiency of task execution.