Collaborative Drone-Truck Routing for Power Line Maintenance with Multi-Package Deliveries

We study a coordinated delivery problem where a drone, operating in tandem with a truck traveling along a road, delivers tools to pylons on a high-voltage power line. Each delivery is defined by a target pylon, package weight, urgency-based profit, and feasible launch and rendezvous points. The drone faces payload and energy constraints, can serve multiple deliveries in a mission, and can perform several missions before recharging. The objective is to maximize total urgency profit across all executed missions. We formalize this as the Power line Maintenance Problem (PMP), which requires selecting a subset of feasible missions that jointly respect energy limits and individually satisfy payload capacity. We prove that PMP is NP-hard and propose a two-phase solution: Generate Missions Phase (GMP), which generates multi-delivery missions, and Truck-drone multi-package Mission Problem (TMP), which selects the most profitable subset. An Integer Linear Program (ILP) formulation is provided for computing optimal solutions. We further study four variants of PMP with different weight models and energy costs. Complexity analysis shows that GMP is polynomial or pseudo-polynomial, while TMP remains NP-hard. Experiments show that GMP greatly reduces candidate missions, while allowing multiple deliveries per mission improves energy efficiency by up to 4 ×.