In an urban environment, multiple small unmanned aerial vehicles (UAVs) may be utilized to locate, surveil, or attack various targets. Whatever the task, the air vehicles must cooperate by efficiently communicating with each other and optimally assigning each UAV to the appropriate task at the appropriate target and at the appropriate time. In this paper, a vehicle assignment algorithm is developed using a mixed integer linear program (MILP) to find the global optimal scheduling solution. The MILP can accommodate both binary and continuous decision variables as well as a variety of constraints and objective functions; however, the NP-hard nature of the problem implies a dramatic increase in the computing complexity as the number of variables and constraints increase. This formulation accounts for an assortment of scenarios focused on the military necessity for precise intelligence, surveillance, and reconnaissance (ISR) by modifying the vehicle routing problem with time windows (VRPTW) formulation. The VRPTW is a type of capacitated vehicle routing problem which optimally assigns a designated number of delivery vehicles originating at a single depot to a known number of customers. Specifically, the VRPTW and network flow techniques account for various scenarios as well as operator imposed timing constraints such as precedence constraints. For example, certain targets may take precedence or require simultaneous arrival times where the targets are first hierarchically clustered according to their proximity to each other. Thus, this paper also focuses on methods of clustering targets and implements this information into the MILP to optimally assign UAVs to targets. Clustering targets that are near enough to alert each other of an attack will allow UAVs to recognize this potential and hence surveil these targets simultaneously to avoid early detection. This techn.
UAV Scheduling via the Vehicle Routing Problem with Time Windows (Preprint)
2007
17 pages
Report
No indication
English
Aircraft , Operations Research , Military Intelligence , Algorithms , Scheduling , Linear programming , Military intelligence , Delivery , Decision making , Targets , Solutions(General) , Urban areas , Reconnaissance , Surveillance , Arrival , Synchronism , Vehicles , Routing , Allocations , Precision , Network flows , Clustering , Time , Computer programming , Formulations , Global , Optimization , Detection , UAV(Unmanned aerial vehicle)
Vehicle Routing and Scheduling Problem with Time Windows and Stochastic Demand
Transportation Research Record | 2004
|Vehicle Routing and Scheduling Problem with Time Windows and Stochastic Demand
Online Contents | 2004
|UAV Scheduling via the Vehicle Routing Problem with Time Windows AIAA Paper
British Library Conference Proceedings | 2007
|Agents Toward Vehicle Routing Problem With Time Windows
Taylor & Francis Verlag | 2015
|