A Note on Integer Programming Formulations of the Real-Time Optimal Scheduling and Flight Path Selection of UAVs

In recent years, considerable attention has been given to research on various aspects of unmanned aerial vehicles (UAVs) applications. UAVs are currently used for various military and civilian missions in the air, sea, space, and on the ground. In two recent papers, Shima et al. (2007) and Kim et al. (2007) considered closely similar m-UAV problems. In Shima et aL (2007), the problem is considered with each target being served by only one UAV to minimize the total travel distance across all UAVs (called load balancing), however, in Kim et al. (2007), the problem is considered with maximum number of targets that each UAV can serve with the objective of minimizing load balancing. Kim et aL presented mixed integer linear programming (MILP) formulations of the load balancing problem both for when the UAVs return to their original depot and when they do not. Shima et al. presented a combinatorial optimization formulation of their model with a branch-and-bound solution procedure. The MILP formulation of the load balancing problem is also adaptable to Shima et al.'s problem. However, there are major inefficiencies with the MILP formulation presented in Kim et al.'s model. In fact, The MILP formulations presented in Kim et al. are highly complicated with huge number of variables and constraints making them impractical for applications. The purpose of the present note is to provide explicit MILP formulations that dramatically reduce the number of variables and the number of constraints for variety of UAV tour assignment problems including the two models mentioned above and via simulation we show significance of these new formulations.