Unmanned aerial vehicle routing in the presence of threats

We study the routing of Unmanned Aerial Vehicles (UAVs) in the presence of the risk of enemy threats. The main goal is to find optimal routes that consider targets visited, threat exposure, and travel time. We formulate a mixed integer linear program that maximizes the total number of visited targets for multiple UAVs, while limiting both the route travel time for each UAV and the total threat exposure level for all UAVs to predetermined constant parameters. The formulation considers a set covering vehicle routing problem where the risk of threat exposure and the travel time are modeled for each edge in a vehicle routing network. To reduce threat exposure, waypoints are generated within the network so routes can avoid high-risk edges. We propose several waypoint generation methods. Using the candidate waypoints, the UAV routes are optimized with branch-and-cut-and-price (BCP) methodology. Minimum dependent set constraints and a simple path heuristic are used to improve the computational efficiency of the BCP algorithm. Computational results are presented, which show that the BCP algorithm performs best when the number of waypoints generated a priori is about half the number of targets.