| dc.description.abstract | The use of Unmanned Aerial Vehicles (UAVs) and the importance of its role have evolved and increased recently in both civilian and military operations. In this research, we study the routing of Unmanned Aerial Vehicles (UAVs) in the presence of the risk of enemy threats. The main goal for this research is to find optimal routes that consider the targets visited, expected fuel burn, threat exposure, and travel time. We formulate two mixed integer linear programs. In first formulation, we minimize the total expected fuel burn for multiple UAVs in order to visit multiple targets while maintaining the total threat exposure level for all UAVs to a predetermined constant parameter. In the second formulation, we maximize the total number of visited targets for multiple UAVs while maintaining both the route travel time for a UAV and the total threat exposure level for all UAVs to predetermined constant parameters. Both formulations consider a set covering Vehicle Routing Problem (VRP), and some assumptions are made. The expected fuel burn, the risk of threat exposure, the travel time are modeled and calculated for each edge and for each route. Several waypoint generation methods are proposed. In this research, waypoints are considered targets that do not need to be visited. However, a UAV may or may not visit a waypoint while traveling from a target to another in order to reduce the threat level.The Branch and Cut and Price (BCP) methodology is used to solve the problem. In the BCP, first, the linear programming relaxation of the problem is solved at each node of the branch-and-bound tree. A cut generation step is called to try to find Minimum Dependent Set (MDS) cuts and add them to the Restricted Master Problem (RMP) in order to cut some fractional solutions and encourage integrality. If the MDS cuts do not exist, the pricing step is called. In the pricing step, routes, variables, with negative reduced costs are generated using a Delayed Column Generation (DCG) algorithm and added to the RMP. In our sub problem, the Integer Programming Shortest Path (IPSP) algorithm is used as an engine for the DCG algorithm. A simple path heuristic (HEU) is used with the DCG algorithm in order to generate simple paths from negative cost cycles. Finally, bounds are updated and branching is carried out using a variant of Ryan and Foster branching logic. A computational study for both formulations is done and results for different scenarios are presented. The results for the first formulation show that for the 10-target case, as the total threat level decreases, both the total expected fuel burn and the number of waypoints visited increase for both algorithms, the DCG-HEU and the DCG-HEU-MDS. In addition, only one UAV is used. Therefor, the problem is considered a Traveling Salesman Problem, but with waypoint generation. The results for the second formulation show that both algorithms, the DCG-HEU and the DCG-HEU-MDS, perform better when using fewer number of waypoints based on the 4-hour run time limit. For the small-sized problem, the DCG-HEU performs better than the DCG-HEU-MDS when using the same number of waypoints. For the large-sized problem, the DCG-HEU-MDS performs better than the DCG-HEU when using the same number of waypoints. | en_US |
