Very large-scale neighborhood search for drone routing with energy replenishment

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