Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet
  of Drones Performing Monitoring Missions
  In this paper we 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 (ILP).
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 as it is on average at 92.06% of the optimal, while it can
potentially scale up to settings with hundreds of drones and locations.
