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

Download

2003.07124.pdf

Date

2020-4

Author

Semiz, Fatih
Polat, Faruk

Metadata

Show full item record

Item Usage Stats

260
views

73
downloads

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.

Subject Keywords

Control and Systems Engineering, Software, General Mathematics, Computer Science Applications, Vehicle Routing, Task Assignment, Area Covarage, Unmanned Aerial Vehicle

URI

https://hdl.handle.net/11511/35966

Journal

Robotics and Autonomous Systems

DOI

https://doi.org/10.1016/j.robot.2020.103435

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

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: https://hdl.handle.net/11511/35966.