Unmanned Aerial Vehicle Routing With Limited Risk

Abstract

Due to safety and uninhabitable surrounding environments, long range Unmanned Aerial Vehicles (UAVs) have become an increasingly popular option in both scientific and military applications. With troubling oil prices, a logistic planner requires an efficient method to identify an optimal routing solution. The solution should not only optimize the bottom line objective but must also control variations in an operation.We study the UAV routing problem with limited risk (URPR) in which the considered risk is a fuel burn variance caused by wind variation. The URPR determines the optimal route that minimizes total expected fuel burn to visit all assigned targets while maintaining the variability to a constant parameter. The URPR is modeled as a set-partitioning problem with a quadratic variance constraint (SPQC). However, the quadratic variance constraint is simplified to a single linear variance constraint. In this study, we discuss two types of the URPR, which are the classical URPR and the URPR with time windows (URPRTW). We present algorithms in a Branch-and-Cut-and-Price methodology to solve the URPR, and the URPRTW. Within the BCP methodology, variables with negative reduced costs are generated to be added to the restricted master problem (RMP) in the pricing step, and minimum dependent set (MDS) constraints are generated in the cutting step to encourage integrality of a solution. Minimum-cost path algorithms such as the Dynamic Programming Shortest Path (DPSP) and the Integer Programming Shortest Path (IPSP) were implemented as column generation engines in the pricing step. Although, the DPSP algorithm quickly found optimal solutions for the URPRTW, it is not applicable in the URPR due to computational complexity. The generating of MDS constraints shows competitive results in the URPRTW and impressive results in the URPR in terms of a computational time. In the conducted computational experiments, medium-sized URPRTWs and small-sized URPRs were optimally solved.Furthermore, we discuss a special case of SPQC with a different variation model where the quadratic constraint is irreducible. We propose the Delayed Columns-and-Cuts Generation algorithm (DCCG) to solve the special case SPQC. The algorithm solves the continuous relaxation of special case SPQC in branch-and-bound nodes. A cut selection strategy adds two types of cuts to cut off infeasible solution. Finally we discuss future extensions of this research.