Power Line Maintenance Using Multi-Package Collaborative Drone-Truck System

This paper investigates a multi-package delivery problem where a drone, cooperating with a truck traveling along a main road, delivers tools (packages) for trellis maintenance along a high-voltage power line. Each delivery is identified by the target trellis, the tool weight, an urgency-based profit, and the launch and rendezvous points along the road designated for the drone to reach the target trellis. The drone, constrained by payload capacity and energy budget, can complete multiple deliveries per mission. A mission is associated with an interval along the road designated by the first and the last trellises to be served. Interval missions must be non-overlapping since the truck moves in a single direction. We formalize this problem as the Truck-drone Multi-package mission Problem (TMP), aiming to select drone's missions that maximize total profit while respecting energy and payload constraints. We prove that TMP is NP-hard and propose an Integer Linear Programming formulation for optimal solutions. We introduce two variants of TMP, considering unitary or arbitrary package weights. For both, we design algorithms to generate all the feasible multi-package missions, among which to select the optimal solution. We compare flight count and profit between multi-and single-package missions. Our approach doubles profit and almost halves flights in the unitary weights case, while in the arbitrary weights case, profit increases by 50% and flights are reduced to 80%.