Truck and drone routing problem with synchronization on arcs
Hongqi Li, Jun Chen, Feilong Wang, Yibin Zhao
Abstract
Abstract Truck–drone technology that enables drones to launch from or land on a moving truck without the need for the truck to stop is the focus of this study. We define the truck and drone routing problem with synchronization on arcs (TDRP‐SA). The TDRP‐SA is characterized by synchronization on arcs, time windows, classified customers, direct delivery, multiple trucks, and multiple drones carried by each truck. The TDRP‐SA involves synchronization on arcs to permit trucks to dispatch and retrieve drones at suitable moving‐LRLs (drone launch/retrieval locations) on arcs of truck routes. A moving‐LRL is essentially a drone launch/retrieval location with a moving truck, and the drone launch/retrieval operations do not need special parking for the trucks. We develop a mixed integer nonlinear programming model to address the TDRP‐SA. We propose a mathematical analysis method to locate moving‐LRLs and to estimate the drone's arrival time at the customers. We develop boundary models through introducing linear piecewise functions to locate moving‐LRLs. We provide an adaptive large neighborhood search (ALNS) heuristic. Through computational experiments, the effectiveness of the boundary models, the TDRP‐SA model and ALNS‐based heuristic are evaluated.