Scholarlink

<p>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, <i>exponential in the input size</i> of the problem. We develop a non-trivial search procedure, VLNS, which examines this neighborhood <i>entirely</i>, in a computational time that remains <i>polynomial</i> 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 <i>flexible improvement procedure</i>, 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月17日

查看全文
  • Catherine Lorenz,
  • Nicola Mimmo,
  • Alena Otto,
  • Daniele Vigo

摘要

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.