Collision-free trajectory planning for drones with velocity dependent energy consumption and moving piggyback vehicles

Abstract In this work, we challenge the common assumption in truck-drone last-mile delivery that trucks and drones operate on a graph. Instead, we adopt a geometric approach, allowing the vehicles to operate in Euclidean space. Our proposed mixed-integer linear program determines a collision-free trajectory for a drone in the Euclidean space with obstacles, where the drone is launched and recovered by moving vehicles. Compared to graph-based approaches, the advantages are: (a) Flexible launching and recovery: The drone can be launched and recovered from any position along the streets, rather than being limited to discrete points (i.e., nodes of a graph). (b) Continuous drone velocity: The drone velocity is a continuous variable, and the drone energy consumption depends directly on its velocity. (c) No-fly zones and obstacles: Trajectory planning is incorporated to ensure a collision-free flight (rather than considering detours as a predefined parameter). To the best of our knowledge, such a geometric approach is new in truck-drone last-mile delivery. In our computational study we prove the usefulness of our geometric approach, as even large instances with up to 300 obstacles can be solved within reasonable computation time. In comparison to graph-based approaches, our geometric approach yields faster delivery times and enables the drone to reach customers that are out of its reach in graph-based approaches.