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.