基于贪婪算法的无人机运输方案研究

侯志浩 吉林大学数学学院

引言

2017 年，美国波多黎各领土遭遇了最严重的飓风，对数百万居民造成了巨大的不利影响。由于许多高速公路已经中断，所以各地居民迫切需要救生医疗用品。在这种情况下，非政府组织提出了“Dronego”项目，将无人机的3 个医疗包转移到5 家选定的医院。我们需要设计一个从已确定的各种候选旋翼无人机中选出的“DroneGo”机队，以完成转移医疗包和检测道路状况的任务。

1 初步分析

我们利用经度作为横坐标，纬度作为Y 轴坐标来获得图1，因此我们可以直观地指出5 个位置的分布。当然，实际位置位于拱形，而我们的坐标图是平坦的。事实上，我们的地图是地球的一个横截面，因此可能与直觉中的真实地图有所不同，但距离，经度和经度都是准确的值。

图1 波多黎各的坐标图显示了5 个目的地

首先，我们给出以下定义：

独立需求（di）：相应中心每天对医疗包的需求。总需求（S）：每天医疗包5 个中心需求的总和。

随后，我们将医疗中心的比例系数定义为：

在我们看来，这个定义是合理的，因为每个中心需要的包裹数量与其接纳人口，各种医疗水平的指数正相关。该系数表明了相应医疗中心在紧急情况下的重要性。然后我们定义了另一个公式来比较任何两个灾害应对方案。首先，我们给出以下定义：

然后得到：

2 分类讨论

到目前为止，我们已经确定了车队，考虑到每个位置的最佳距离不是唯一的，我们将ISO 容器作为圆心，找到交叉区域后，覆盖道路，人口和地形做出选择。最佳位置是（见图2 和图3）

图2 最佳位置

图3 平面图中的最佳位置

如图3 所示，我们可以要求无人机可以从A 点出发，并在到达由A点和医院确定的椭圆的任何点后到达医院，如果可能的话，保持飞行剩余距离的一半到任何要求的地方，最后回到医院。（如（b）所示）

球场并不总是直的，无人机可以在曲线路线上飞行，只要它们可以返回（医院或集装箱）至于VRD（视频侦察无人机），可检测区域是如上所述的侦察圈（SC）。

草图仅显示两个不同的路线以给出简单的符号。坐标由经度和纬度组成，这使得性能不像现实那么直观。

3 结论

对于前往D1 的无人机，每架无人机B 最多可以满足D1 的2 天要求，所以我们只需要在两天内发送一架无人机B.对于支持D2 的无人机，每架无人机F最多可以满足一天的请求，并有足够的空间来携带MED包，比例为202/112/211，因此我们可以在前两天指定一架无人机F，然后发送其余要求的4 天（此外，无人机可以在一次飞行中提供D3 和D2，我们可以通过这种方式实现D1 和D2 的包装管理）。在考虑D3 时，每架无人机B 最多可以满足一天的要求。根据比例系数，我们只需在四天内分配一架无人机。