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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Scheduling a Fleet of Drones for Monitoring Missions With Spatial, Temporal, and Energy Constraints




    Publication date :

    2022-09-01


    Size :

    2258016 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Modeling Energy Consumption of Small Drones for Swarm Missions

    Cabuk, Umut Can / Tosun, Mustafa / Dagdeviren, Orhan et al. | IEEE | 2024


    Using drones in fire-fighting missions

    Radkov, V. / Aleksandrova, V. / Guncheva, A. | TIBKAT | 2019

    Free access

    METHOD OF CONTROLLING FLEET OF DRONES

    KIM HWANG NAM / YOO SEUNG HO / JUNG JONG TACK et al. | European Patent Office | 2016

    Free access

    METHOD FOR CONTROLLING FLEET OF DRONES

    European Patent Office | 2016

    Free access