论文标题
扩展多个旅行推销员问题，以安排执行监控任务的无人机舰队
Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet of Drones Performing Monitoring Missions
论文作者
论文摘要
在本文中，我们将一组无人机的行程路径安排在图形上，需要在预定的时间点以多次访问节点。这是众所周知的多个旅行者问题的延伸。提出的公式可以应用于多个域，例如在运输网络中监视交通流，或监视远程位置以协助搜索和救援任务。为了找到最佳的时间表，该问题被提出为整数线性程序（ILP）。鉴于问题是高度组合的，因此最佳解决方案仅针对小型问题。因此，还提出了一种贪婪的算法，该算法使用一步前进的启发式搜索机制。在详细的评估中，观察到贪婪的算法的性能几乎是最佳的，因为它平均为最佳的92.06％，而它可以扩展到具有数百个无人机和位置的设置。
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.
