2024/02/01 by Danny Kriz̧anc, Krizanc, Danny, Lata Narayanan +5
Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2402.00829
openalex publication_date 2024/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the truck-drone cooperative delivery problem in a setting where a single truck carrying a drone travels at constant speed on a straight-line trajectory/street. Delivery to clients located in the plane and not on the truck's trajectory is performed by the drone, which has limited carrying capacity and flying range, and whose battery can be recharged when on the truck. We show that the problem of maximizing the number of deliveries is strongly NP-hard even in this simple setting. We present a 2-approximation algorithm for the problem, and an optimal algorithm for a non-trivial family of instances.