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%.

翻译：DRP-E, 无人机必须访问一组节点, 通常需要来自( 潜在的) 移动补给站的电池交换。 与无人机路由文献的广泛限制相反, 几个目的地可以在连续两次电池交换之间访问。 在本文中, 我们提议DRP- E 的一小类非进取型非常大型的邻里, 它具有同步性, 利用两个大尺寸的多球性可溶性 DRP- E 子解决方案( SP1 和 SP2), 无人机必须访问一组节点, 并经常需要来自( 潜在的) 移动补给站( 移动站) 。 与无人机路段文献的广泛限制相反, 几个目的地可以在连续的两次电池交换中访问。 在本文中, 我们提议DRP- E 的两阶段动态程序算法VLSNSN, 以搜索该区间的额外交易可以灵活调整, 以适应准确性和计算时间之间的交易。 例如, 搜索程序可以转换成一个具有竞争力的DRPA 的当前测试方法, 。 进行相关的搜索程序, 正在测试, 正在测试一个具有竞争性的DRPRP 。