The KIOS CoE research team consisting of the Research Associate Dr. Emmanouil Rigas, the Research Assistant Prof. Panagiotis Kolios and Prof. Georgios Ellinas, has won the 2nd Best Conference Paper Award for the paper entitled “Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet of Drones Performing Monitoring Missions”.
In this paper researchers schedule the travel path of a set of drones across a graph where the nodes need to be visited multiple times at pre-defined points in time. This is an extension of the well-known multiple traveling salesman problem. The proposed formulation can be applied in several domains such as the monitoring of traffic flows in a transportation network, or the monitoring of remote locations to assist search and rescue missions. Aiming to find the optimal schedule, the problem is formulated as an Integer Linear Program. Given that the problem is highly combinatorial, the optimal solution scales only for small sized problems. Thus, a greedy algorithm is also proposed that uses a one-step look ahead heuristic search mechanism. In a detailed evaluation, it is observed that the greedy algorithm has near-optimal performance, while it can potentially scale up to settings with hundreds of drones and locations.
This paper was presented at the 23rd IEEE International Conference on Intelligent Transportation Systems, which welcomes papers and presentations in the field of Intelligent Transportation Systems, dealing with new developments in theory, analysis, simulation and modeling, experimentation, demonstration, case studies, field operational tests, and deployments.
The paper can be viewed here: https://ieeexplore.ieee.org/abstract/document/9294568
Link to the conference: https://www.ieee-itsc2020.org/
The research presented in this paper was undertaken within the context of the EU project CARAMEL, funded by the European Union’s Horizon 2020 Research and Innovation Programme.
