Solving the area coverage problem with UAVs: A vehicle routing with time windows variation

Semiz, Fatih
Polat, Faruk
In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. These difficulties are even greater if the area coverage must continue throughout a specific time window. We address this by considering a Vehicle Routing Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously without violating time windows. In this problem, our aim is to find a way to cover all areas with the necessary number of UAVs during the time windows, minimize the total distance traveled, and provide a fast solution by satisfying the additional constraint that each agent has limited fuel. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs. Then we solve transportation problems with the simplex algorithm to generate the solution. The performance of the proposed algorithm and other implemented algorithms to compare the solution quality is evaluated on example scenarios with practical problem sizes.
Robotics and Autonomous Systems


A Parallel Algorithm for UAV Flight Route Planning on GPU
Sanci, Seckin; İşler, Veysi (Springer Science and Business Media LLC, 2011-12-01)
Aerial surveillance missions require a geographical region known as the area of interest to be inspected. The route that the aerial reconnaissance vehicle will follow is known as the flight route. Flight route planning operation has to be done before the actual mission is executed. A flight route may consist of hundreds of pre-defined geographical positions called waypoints. The optimal flight route planning manages to find a tour passing through all of the waypoints by covering the minimum possible distanc...
Biobjective route planning of an unmanned air vehicle in continuous space
TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (2023-02-01)
We consider the route planning problem of an unmanned air vehicle (UAV) in a continuous space that is monitored by radars. The UAV visits multiple targets and returns to the base. The routes are constructed considering the total distance traveled and the total radar detection threat objectives. The UAV is capable of moving to any point in the terrain. This leads to infinitely many efficient trajectories between target pairs and infinitely many efficient routes to visit all targets. We use a two stage approa...
Modeling and simulation of a small-sized Tiltrotor UAV
Çakıcı, Ferit; Leblebicioğlu, Mehmet Kemal (2012-10-01)
Unmanned aerial vehicles (UAVs) are remotely piloted or self-piloted aircrafts that can carry cameras, sensors, communication equipment and other payloads. Tiltrotor UAVs provide a unique platform that fulfills the needs for ever-changing mission requirements, by combining the desired features of hovering like a helicopter and reaching high forward speeds like an airplane, which might be a force multiplier in the battlefield. In this paper, the conceptual design and aerodynamical model of a realizable small...
Improvement of routing protocols for unmanned flying ad hoc networks (UFANETS) by using crosslayer metrics
Alkış, Oğuz; Ulusoy, İlkay; Department of Electrical and Electronics Engineering (2019)
Unmanned Air Vehicles (UAV) have been used to perform different type of missions. Many of these civilian and military missions require information exchange between UAVs, which is performed by using routing protocols for wireless ad hoc networks. An efficient routing protocol for unmanned flying ad hoc networks (UFANETs) plays a critical role for data transmission during various applications. In the literature, there are many studies for mobile ad hoc networks (MANET) routing protocols. Due to high mobility ...
An Interactive Algorithm for Multi-objective Route Planning
Tezcaner, Diclehan; Köksalan, Mustafa Murat (Springer Science and Business Media LLC, 2011-08-01)
We address the route selection problem for Unmanned Air Vehicles (UAV) under multiple objectives. We consider a general case for this problem, where the UAV has to visit several targets and return to the base. We model this problem as a combination of two combinatorial problems. First, the path to be followed between each pair of targets should be determined. We model this as a multi-objective shortest path problem. Additionally, we need to determine the order of the targets to be visited. We model this as ...
Citation Formats
F. Semiz and F. Polat, “Solving the area coverage problem with UAVs: A vehicle routing with time windows variation,” Robotics and Autonomous Systems, 2020, Accessed: 00, 2020. [Online]. Available: