2006 NIP Award Recipient
Uninhabited Aerial Vehicle Routing with Limited Wind Risk
Jay M. Rosenberger - University of Texas at Arlington
NASA and the military are using uninhabited aerial vehicles (UAVs) for many scientific and combat activities. Monitoring ozone depletion, carbon dioxide levels, and inclement weather, such as hurricanes and tropical storms, are some potential uses of UAVs. Although the general vehicle routing problem (VRP) for transportation and logistics networks is well-studied in the optimization literature, only minimal research has considered optimally routing UAVs. Moreover, recent advances to limit risk in ship scheduling provide an invaluable research foundation for reducing the uncertain effects of wind on UAVs, which is an enormous obstacle in UAV path finding. The objective of the proposed research is to formulate and implement solution methods to solve UAV routing problems with limited wind risk. Moreover, the solution methods will be generalized so they may apply to many other industrial, military, and NASA applications. The proposed methods are based upon a branch-and-price-and-cut algorithm developed by the PI for ship-scheduling. Although the PI's previous research will provide a foundation of the proposed research, the two primary goals of this project are: (1) develop a branch-and-price-and-cut methodology to solve the UAV routing with limited wind risk, and (2) improve the computational efficiency of the branch-and-price-and-cut algorithm for both the UAV routing problem and the traditional VRP with limited risk.