The Truck–Drone Hurdle Relay Problem in a Euclidean space

In this work, we study the Truck–Drone Hurdle Relay Problem in a Euclidean space (TDHRP), which is particularly relevant in the context of disaster relief. In this problem, a drone is tasked with the delivery of relief supplies in a disaster-stricken area, while being supported by trucks along its way with transportation and battery exchanges. Trucks and drone need to work together, as the partially damaged road network prevents the trucks from reaching the destination, and as the distance from the depot to the destination is far too great for the drone to cover in one flight. We develop a mixed-integer linear program (MILP) for the TDHRP, where we apply a geometric approach that includes trajectory planning for the drone, as opposed to the common assumption in truck–drone delivery that the vehicles operate on a graph. The geometric approach allows the drone to be launched and recovered on any position along the roads, to model the drone velocities as continuous variables, and to ensure collision avoidance. To reduce computation times, we develop an exact row-generation solution method with six different strategies on adding rows. In an extensive computational study with instances with up to ten trucks and 300 obstacles or no-fly zones, two strategies are shown to yield faster median computation times then the complete MILP.