Collaborative Research: Arc Routing Problems in Combined Drone/Truck Fleets

This award contributes to national prosperity by advancing planning methods for combined drone/truck fleets to serve critical societal needs, such as energy transmission infrastructure monitoring, urban police patrolling, rural and suburban mail delivery, roadway pavement inspection, and traffic monitoring. Despite the significant opportunities offered by drones for remote operations, their limited flying time and small battery capacity hamper large-scale operations.

Coordination between drones and roadway-dependent motor vehicles, such as trucks, can help resolve these issues by providing batteries and payload required for continued drone services. This project will provide a novel approach to cover large service areas using combined drone/truck fleets. This award highlights the societal applications characterized by combined ‘arc’ routing, for which existing routing methods cannot provide adequate decision-making tools.

In particular, this project will validate the methods developed through a case study involving surveillance of electric power transmission lines, the backbone of the nation’s energy infrastructure. This project will train the future workforce in computational operations research and develop open-source software packages to support the further use of unmanned vehicles.

The project will advance our understanding of arc routing problems in combined drone/truck fleets by developing computational optimization models and algorithms. The combined drone/truck arc routing problem is fundamentally different and significantly more challenging than traditional arc routing problems because drones can fly directly from one point to another point in the network without following ground arcs.

In addition, a drone may serve only part of an arc due to its limited capacity and footprint, or potentially multiple distinct routes covering the entire arc. The optimal routing of mobile hubs served by trucks must also be incorporated into this already challenging problem. Furthermore, a drone may launch from one truck and return to another truck if beneficial; therefore, synchronization between drones and trucks plays a significant role.

This project will provide a novel mixed-integer linear programming formulation and adaptive heuristics based on decomposition, dynamic programming, partitioning, large neighborhood search, and machine learning for efficient operations of the combined fleets. The models and algorithms will be validated with actual data from power transmission line monitoring.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.