论文标题
解决无人机的区域覆盖范围问题：随时间窗口变化的车辆路由
Solving Area Coverage Problem with UAVs: A Vehicle Routing with Time Windows Variation
论文作者
论文摘要
在现实生活中，通过用无人驾驶汽车（UAV）覆盖该地区，为一组大区域提供安全性是一个困难的问题，由多个目标组成。如果必须在特定的时间窗口中继续进行区域覆盖范围，那么这些困难就会更大。我们通过考虑使用时间窗口（VRPTW）变化的车辆路由问题来解决这一问题，在这种变化中，代理的容量是一个，每个客户（目标区域）必须同时提供多辆车，而不会违反时间窗口。在此问题中，我们的目标是找到一种方法，以覆盖所有无人机数量在时间窗口期间，最小化总距离的必要数量，并通过满足每个代理商的额外约束来提供快速解决方案。我们提出了一种新颖的算法，该算法依赖于目标区域的时间窗口，然后在每个群集和现成的无人机中逐渐产生运输问题。然后，我们解决了使用单纯形算法的运输问题来生成解决方案。在示例场景中评估了拟议算法和其他实施算法以比较解决方案质量的性能。
In real life, providing security for a set of large areas by covering the area with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consist of multiple objectives. These difficulties are even greater if the area coverage must continue throughout a specific time window. We address this by considering a Vehicle Routing Problem with Time Windows (VRPTW) variation in which capacity of agents is one and each customer (target area) must be supplied with more than one vehicles simultaneously without violating time windows. In this problem, our aim is to find a way to cover all areas with the necessary number of UAVs during the time windows, minimize the total distance traveled, and provide a fast solution by satisfying the additional constraint that each agent has limited fuel. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs. Then we solve transportation problems with the simplex algorithm to generate the solution. The performance of the proposed algorithm and other implemented algorithms to compare the solution quality is evaluated on example scenarios with practical problem sizes.
