Reward Maximization in Last-Mile Delivery Using Truck-Carried Heterogeneous Drones

Last-mile delivery is the costliest part of the logistics chain, and pairing delivery trucks with drones is a promising way to reduce that cost. Most truck–Unmanned Aerial Vehicle (UAV) models, however, make two assumptions that rarely hold: that drones can serve every customer, and that the truck route can be reshaped to fit them. In practice, drone endurance and payload are limited, and freight trucks follow fixed routes. We therefore study a more realistic regime in which drones augment a truck that keeps its predetermined route: the question is no longer how to route the truck, but which deliveries to serve and how to schedule the drones. This setting combines four features that prior work does not capture together: a fixed truck route, reward-based selection of a delivery subset (drones need not serve all requests), heterogeneous UAVs with individual payload and battery limits, and multi-delivery sorties constrained by a mission-level energy budget. We formalize it as the Multi-drone Multi-delivery Scheduling Problem (MMSP), model it as a Mixed Integer Programming (MIP), prove it NP-hard, and design three scalable algorithms: the Iterative Single-Drone Knapsack (ISDK), the PTAS Multiple Knapsack with Interval Scheduling (PMKIS), and the On-the-fly Greedy Scheduling (OGS), which trade solution quality for runtime in different ways. In experiments, all three stay close to the exact optimum, and the truck–drone system is consistently cheaper than a truck-only baseline, with the largest savings when deliveries are sparse.