论文标题
非常大规模的邻里搜索无人机路由和能量补充
Very large-scale neighborhood search for drone routing with energy replenishment
论文作者
论文摘要
带有能量补充的无人机路由问题（DRP-E）属于带有中间停止和同步约束的一般路由问题类别。在DRP-E中，无人机必须访问一组节点，并通常需要（可能）移动补货站的电池掉期。与无人机路由文献中的广泛限制相反，可以在两个连续的电池掉期之间访问几个目的地。在本文中，我们为DRP-E提出了一个非平凡的非常大的社区，该社区协同利用了两个大型多项式可解决的DRP-E子问题（SP1和SP2）。所得邻域中可行解决方案的数量是SP1和SP2中的倍数，因此在问题的输入大小中指数级，而搜索的计算时间仍然是多项式。提出的多项式两阶段动态编程算法VLSN可以灵活地调整到准确性和计算时间之间所需的权衡。例如，可以将搜索过程转换为DRP-E的竞争运行时的精确算法。在计算测试中，开发的解决方案方法的表现优于DRP-E的当前最新启发式方法。基于对失踪人员的搜索的案例研究表明，VLSN可以轻松适应其他相关功能，并在灾难缓解方面的最先进解决方案的效果超过20％。
The Drone Routing Problem with Energy replenishment (DRP-E) belongs to a general class of routing problems with intermediate stops and synchronization constraints. In DRP-E, the drone has to visit a set of nodes and routinely requires battery swaps from a (potentially) mobile replenishment station. Contrary to widespread restrictions in the drone routing literature, several destinations may be visited in between two consecutive battery swaps. In this paper, we propose a nontrivial very large-scale neighbourhood for DRP-E, which synergetically leverages two large-sized polynomially solvable DRP-E SubProblems (SP1 and SP2). The number of feasible solutions in the resulting neighborhood is a multiple of those in SP1 and SP2, and, thus, exponential in the input size of the problem, whereas the computational time to search it remains polynomial. The proposed polynomial two-stage dynamic programming algorithm VLSN to search this neighborhood can be flexibly adjusted to the desired trade-off between accuracy and computational time. For instance, the search procedure can be converted into an exact algorithm of competitive runtime for DRP-E. In computational tests, the developed solution methods outperform current state-of-the art heuristics for DRP-E by a significant margin. A case study based on a search for missing persons demonstrates that VLSN easily accommodates additional practice relevant features and outperforms the state-of-the-art solution in disaster relief by 20%.
