A last-mile drone-assisted one-to-one pickup and delivery problem with multi-visit drone trips

Online retailers and food delivery platforms are exploring last-mile package and food delivery using drones to reduce delivery time and improve customer experience. We investigate a novel and pioneering problem, the one-to-one pickup and delivery problem with multi-trucks and multi-visit drone (OPDP-MTMV). This problem involves multiple trucks, each of which is equipped with a single drone for pickup and delivery services. The drones are capable of carrying multiple packages per drone trip. Pickup and delivery requests can be served by either a truck or a drone, subject to the one-to-one precedence constraints of the requests, the capacity constraints of the truck and the drone, and the endurance constraints of the drone. The energy consumption of a drone is based on the flight time and the varying payload along the multi-visit drone trip. The objective is to minimize the sum of the fixed cost and the variable duration cost. We formulate this problem using a mathematical model and propose an iterated local search (ILS) algorithm based on the distinct features of the problem. Finally, we conduct comprehensive computational experiments using test instances of various sizes to analyze the characteristics of the solution, the applicability of the algorithm, and the impact of different drone configurations.