The multidepot drone general routing problem with duration and capacity constraints
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.
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}
}
EUVIMED