EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

The multidepot drone general routing problem with duration and capacity constraints

Teresa Corberán, Isaac Plana, José M. Sanchis, Paula Segura

International Transactions in Operational Research · 2025-11 · 32 (6) · 3756-3779

DOI: 10.1111/itor.13457 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Transactions in Operational Research, online erschienen am 23.03.2024. Verfasst von Teresa Corberán und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Ministerio de Ciencia e Innovación, European Regional Development Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This paper studies the multidepot drone general routing problem with duration and capacity constraints (MDdGRP), an extension of the classical general routing problem with several depots. A fleet of drones with limited flight time and payload, each one located in a different depot, must jointly perform the service. In this continuous optimization problem, a set of lines of a network has to be serviced and a set of nodes has to be visited to deliver a given commodity. The aim is to find a set of drone routes performing the complete service with the shortest total duration. Aerial drones can enter a line at any point, service a portion of that line, and exit through another point, without following the lines of the network. While this flexibility allows for potentially better solutions, it also adds complexity to the problem. To deal with this, we digitize the MDdGRP instances by approximating each line with a polygonal chain containing a finite number of points that can be used to enter and exit each line. Thus, an instance of a discrete multidepot general routing problem (MDGRP) is obtained. This paper proposes an integer formulation for the MDGRP, some families of valid inequalities, and a branch‐and‐cut algorithm based on the strengthened formulation. Two matheuristic algorithms are presented, focused on sequentially selecting (and adding) some promising intermediate points to enter and exit a line. Instances involving up to six depots, 22 delivery points, and 88 original lines have been generated to test the performance of the methods proposed.

Förderung

  • Ministerio de Ciencia e Innovación
  • European Regional Development Fund

Zitieren

APA

Corberán, T., Plana, I., Sanchis, J. M., & Segura, P. (2025). The multidepot drone general routing problem with duration and capacity constraints. International Transactions in Operational Research, 32(6), 3756-3779. https://doi.org/10.1111/itor.13457

Vancouver

Corberán T, Plana I, Sanchis JM, Segura P. The multidepot drone general routing problem with duration and capacity constraints. International Transactions in Operational Research. 2025;32(6):3756-3779. doi:10.1111/itor.13457

BibTeX
@article{Corbern2025,
  author = {Corberán, Teresa and Plana, Isaac and Sanchis, José M. and Segura, Paula},
  title = {The multidepot drone general routing problem with duration and capacity constraints},
  journal = {International Transactions in Operational Research},
  year = {2025},
  volume = {32},
  number = {6},
  pages = {3756--3779},
  doi = {10.1111/itor.13457}
}
Kostenlos starten →