Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.14279/30809
Title: | Scheduling a Fleet of Drones for Monitoring Missions With Spatial, Temporal, and Energy Constraints |
Authors: | Rigas, Emmanouil S. Kolios, Panayiotis Mavrovouniotis, Michalis Ellinas, Georgios |
Major Field of Science: | Engineering and Technology |
Field Category: | Electrical Engineering - Electronic Engineering - Information Engineering |
Keywords: | ant colony optimization (ACO);drones;heuristic search;integer linear programming (ILP);metaheuristic;scheduling;Unmanned aerial vehicles (UAVs) |
Issue Date: | 1-Sep-2022 |
Source: | IEEE Transactions on Intelligent Transportation Systems, 2022, vol. 23, iss. 9, pp. 15133 - 15145 |
Volume: | 23 |
Issue: | 9 |
Start page: | 15133 |
End page: | 15145 |
Journal: | IEEE Transactions on Intelligent Transportation Systems |
Abstract: | In this work, the travel path of a set of drones is scheduled across a graph, where the nodes need to be visited multiple times at pre-defined points in time. The nodes can either be demand nodes requesting monitoring, or supply nodes that are used as take-off/landing locations for the drones and for battery replacement to cope with the limited flying range of the drones. This is an extension of the well-known multiple traveling salesman problem and the proposed formulation can be applied in several domains such as the monitoring of traffic flows in a transportation network, the monitoring of remote locations to assist search and rescue missions, or the monitoring of critical infrastructure facilities for security and surveillance purposes. Aiming to find the optimal schedule, the problem is initially formulated as an Integer Linear Program (ILP). However, given that the problem is highly combinatorial, the optimal solution scales only for small-size problems. Thus, a greedy algorithm is also proposed that uses a one-step look-ahead heuristic search mechanism, as well as an algorithm that is based on ant colony optimization (ACO). In a detailed evaluation, it is observed that both algorithms achieve near-optimal performance for small settings, while also scaling to larger settings, with the ACO being more suitable for medium-size settings and the Greedy for larger ones. A field experiment is additionally performed to demonstrate the practical implementation of the proposed system under real-world conditions. |
URI: | https://hdl.handle.net/20.500.14279/30809 |
ISSN: | 15249050 |
DOI: | 10.1109/TITS.2021.3137359 |
Rights: | © IEEE |
Type: | Article |
Affiliation : | University of Cyprus KIOS Research and Innovation Center of Excellence (KIOS CoE) |
Publication Type: | Peer Reviewed |
Appears in Collections: | Άρθρα/Articles |
CORE Recommender
Sorry the service is unavailable at the moment. Please try again later.
Items in KTISIS are protected by copyright, with all rights reserved, unless otherwise indicated.