Declarative UAVs Fleet Mission Planning: A Dynamic VRP Approach

In this paper, we study the problem of dynamically routing Unmanned Aerial Vehicles (UAVs) taking into account not only the known requests, their type, pick-up, and delivery locations, and time windows, but also considering traffic, i.e., collision avoidance, and changing weather conditions as well as the arrival of new customer requests or request cancellation by impatient consumers and emergency departures caused by low battery. This problem can be viewed as the dynamic version of the well-known Vehicle Routing Problem with Time Windows (VRRTW), where current routings are subject to change at any time. Its NP-hard character following the vehicle routing and deadlock-avoidance problems implies the need to use a constraint programming based framework that has proven to be effective in various contexts, especially related to the nonlinearity of system characteristics. The approach has been tested on several examples, analyzing customer satisfaction, i.e., service level, throughput (number of serviced requests). Revenue maximization is influenced by different values of the mission parameters, such as the fleet size, travel distance, wind direction, and wind speed. Computational experiments show the results that allow assessing alternative strategies of UAV mission planning.