A Randomized Heuristic Algorithm for Cyclic Routing of UAVs
Cheng Siang Lim, Shell Ying Huang · 2018
Unmanned Aerial Vehicles (UAVs) have been increasingly used in military and civilian applications. Even though the UAV routing problems have similarities with Vehicle Routing Problems, there are still many problems where effective and efficient solutions are lacking. We propose a randomized heuristic algorithm for the cyclic routing of a single UAV. The UAV is required to visit a set of target areas where the time interval between consecutive visits to each area cannot exceed its relative deadline. The PSPACE-complete problem has a solution whose length may be exponential. Our algorithm tries to compute a feasible cyclic route while trying to keep short the cycle time. Our tests of 57 instances of the problem show that the algorithm has good effectiveness and efficiency.