The multi‐purpose K ‐drones general routing problem
Networks · 2023-12 · 82 (4) · 437-458
DOI: 10.1002/net.22176 ↗At a glance
Journal article in Networks, published online on 2023-07-22. Written by James Campbell and 4 co-authors. Cited 15 times so far (Crossref); 41 references. The full text is freely available (open access, CC BY-NC-ND 4.0). Funded by: European Regional Development Fund, European Social Fund, Ministerio de Ciencia e Innovación.
Abstract (original language)
In this article, we present and solve the multi‐purpose ‐drones general routing problem (MP ‐DGRP). In this optimization problem, a fleet of multi‐purpose drones, aerial vehicles that can both make deliveries and conduct sensing activities (e.g., imaging), have to jointly visit a set of nodes to make deliveries and map one or more continuous areas. This problem is motivated by global healthcare applications that deploy multipurpose drones that combine delivery trips with collection of aerial imaging data for use in emergency preparedness and resilience planning. The continuous areas that have to be mapped may correspond to terrain surfaces (e.g., flooded areas or regions with a disease outbreak) or to infrastructure networks to be inspected. The continuous areas can be modeled as a set of lines so that each area is completely serviced if all the lines covering it are traversed. Thus, given a set of nodes and a set of lines, the problem is to design drone routes of shortest total duration traversing the lines and visiting the nodes, while not exceeding the range limit (flight time) and capacity (loading) of the drones. Unlike ground vehicles in classical routing problems, drones can enter a line through any of its points, service only a part of that line and then exit through another of its points. The possibility of flying directly between any two points of the network offered by drones can lead to reduced costs, but it increases the difficulty of the problem. To deal with this problem, the lines are discretized, allowing drones to enter and exit each line only at a finite set of points, thus obtaining an instance of the ‐vehicles general routing problem (‐GRP). We present in this article an integer programming formulation for the ‐GRP and propose a matheuristic algorithm and a branch‐and‐cut procedure for its solution. Results are provided for problems with up to 20 deliveries and up to 28 continuous areas.
Funding
- European Regional Development Fund
- European Social Fund
- Ministerio de Ciencia e Innovación
- Ministerio de Ciencia, Innovación y Universidades
Cite
APA
Campbell, J., Corberán, Á., Plana, I., Sanchis, J. M., & Segura, P. (2023). The multi‐purpose K ‐drones general routing problem. Networks, 82(4), 437-458. https://doi.org/10.1002/net.22176
Vancouver
Campbell J, Corberán Á, Plana I, Sanchis JM, Segura P. The multi‐purpose K ‐drones general routing problem. Networks. 2023;82(4):437-458. doi:10.1002/net.22176
BibTeX
@article{Campbell2023,
author = {Campbell, James and Corberán, Ángel and Plana, Isaac and Sanchis, José M. and Segura, Paula},
title = {The multi‐purpose K ‐drones general routing problem},
journal = {Networks},
year = {2023},
volume = {82},
number = {4},
pages = {437--458},
doi = {10.1002/net.22176}
}
EUVIMED