Department of Electric and Electrical Engineering, Konkuk University, Seoul 05029, Korea.
Department of Electrical and Computer Engineering, University of Rochester, Rochester, NY 60521, USA.
Sensors (Basel). 2021 Feb 9;21(4):1219. doi: 10.3390/s21041219.
A delivery service using unmanned aerial vehicles (UAVs) has potential as a future business opportunity, due to its speed, safety and low-environmental impact. To operate a UAV delivery network, a management system is required to optimize UAV delivery routes. Therefore, we create a routing algorithm to find optimal round-trip routes for UAVs, which deliver goods from depots to customers. Optimal routes per UAV are determined by minimizing delivery distances considering the maximum range and loading capacity of the UAV. In order to accomplish this, we propose an algorithm with four steps. First, we build a virtual network to describe the realistic environment that UAVs would encounter during operation. Second, we determine the optimal number of in-service UAVs per depot. Third, we eliminate subtours, which are infeasible routes, using flow variables part of the constraints. Fourth, we allocate UAVs to customers minimizing delivery distances from depots to customers. In this process, we allow multiple UAVs to deliver goods to one customer at the same time. Finally, we verify that our algorithm can determine the number of UAVs in service per depot, round-trip routes for UAVs, and allocate UAVs to customers to deliver at the minimum cost.
使用无人机 (UAV) 的送货服务具有成为未来商业机会的潜力，因为它具有速度快、安全且对环境影响小的特点。为了运营无人机送货网络，需要一个管理系统来优化无人机送货路线。因此，我们创建了一个路由算法，为从仓库向客户送货的无人机寻找最佳往返路线。通过考虑无人机的最大范围和载重量，最小化送货距离来确定每架无人机的最佳路线。为了实现这一目标，我们提出了一个具有四个步骤的算法。首先，我们构建一个虚拟网络来描述无人机在运行过程中可能遇到的真实环境。其次，我们确定每个仓库的最佳服务无人机数量。第三，我们使用约束条件中的流变量消除不可行的迂回路线。第四，我们分配无人机到客户，使从仓库到客户的送货距离最小化。在这个过程中，我们允许多架无人机同时向一个客户送货。最后，我们验证我们的算法可以确定每个仓库的服务无人机数量、无人机的往返路线，并以最低成本分配无人机到客户进行送货。
