Very large-scale neighborhood search for drone routing with energy replenishment
针对带能量补充的无人机路径规划问题，提出一种超大规模邻域搜索方法，通过结合两个可多项式求解的子问题，在多项式时间内穷举指数级邻域，显著优于现有启发式算法。
Abstract The drone routing problem with energy replenishment (DRP-E) describes 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, energy- or payload replenishment from mobile or stationary replenishment stations. Thereby, the drone may visit several destinations between two replenishments, and mutual waiting at the rendezvous locations may occur. In this paper, we propose a very large-scale neighborhood that synergistically 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. We develop a non-trivial search procedure, VLNS, which examines this neighborhood entirely , in a computational time that remains polynomial in the problem size. The desired trade-off between accuracy and runtime of the proposed two-stage dynamic programming approach can be flexibly adjusted with just a single parameter. For large parameter values, it converts to an exact approach. VLNS is a flexible improvement procedure , which is easy to implement. It can be straightforwardly adapted to many DRP-E variants and may be embedded in any algorithmic scheme, meta- or math-heuristic. In computational tests, we demonstrate that a lean local-search-based implementation of VLNS already outperforms state-of-the-art heuristics for several DRP-E variants by a significant margin. We furthermore propose a well-performing exact approach for DRP-E.