Abstract:This paper focuses on a multi-visit vehicle-drone collaborative routing problem with simultaneous pickup and delivery (MV-VDCRP-PD), in which constraints such as multi-visit per flight, time windows, simultaneous pickup and delivery, and vehicle’s varying speeds influenced by road networks are considered. Taking minimizing the delivery cost as the optimization objective, we first formulate a mathematical model for the MV-VDCRP-PD. Then, to effectively solve the problem, a memetic algorithm (MA) based on the genetic algorithm and adaptive large neighbourhood search algorithm is proposed. In the MA, an individual is encoded as containing two sequences, a customer sequence and a customer visiting pattern sequence. To check whether the individual violates the problem constraints and ensure its feasibility, a penalty function and a modification method are proposed. To guarantee the exploration ability of the MA, a customer-based crossover operator is presented to generate new individuals. Meanwhile, based on the problem characteristics, four destroy operators and four repair operators are developed with the purpose of finding better individuals. In addition, a population update strategy is proposed to guarantee the population quality and the proportion of feasible solutions. Finally, experimental tests and comparisons are carried out on different instances to verify the effectiveness of the proposed MA.