This paper addresses the optimization of routing problems with drones. It analyzes the coordination of one mothership with one drone to obtain optimal routes that have to visit some target objects modeled as general graphs. The goal is to minimize the overall weighted distance traveled by both vehicles while satisfying the requirements in terms of percentages of visits to targets. We discuss different approaches depending on the assumption made on the route followed by the mothership: i) the mothership can move on a continuous framework (the Euclidean plane), ii) on a connected piecewise linear polygonal chain or iii) on a general graph. In all cases, we develop exact formulations resorting to mixed integer second order cone programs that are compared on a testbed of instances to assess their performance. The high complexity of the exact methods makes it difficult to find optimal solutions in short computing time. For that reason, besides the exact formulations we also provide a tailored matheuristic algorithm that allows one to obtain high quality solutions in reasonable time. Computational experiments show the usefulness of our methods in different scenarios.

Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs / Amorosi, L.; Puerto, J.; Valverde, C.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 136:(2021), pp. 1-22. [10.1016/j.cor.2021.105445]

Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs

Amorosi L.
Primo
;
2021

Abstract

This paper addresses the optimization of routing problems with drones. It analyzes the coordination of one mothership with one drone to obtain optimal routes that have to visit some target objects modeled as general graphs. The goal is to minimize the overall weighted distance traveled by both vehicles while satisfying the requirements in terms of percentages of visits to targets. We discuss different approaches depending on the assumption made on the route followed by the mothership: i) the mothership can move on a continuous framework (the Euclidean plane), ii) on a connected piecewise linear polygonal chain or iii) on a general graph. In all cases, we develop exact formulations resorting to mixed integer second order cone programs that are compared on a testbed of instances to assess their performance. The high complexity of the exact methods makes it difficult to find optimal solutions in short computing time. For that reason, besides the exact formulations we also provide a tailored matheuristic algorithm that allows one to obtain high quality solutions in reasonable time. Computational experiments show the usefulness of our methods in different scenarios.
arc routing problems; conic programming; drones; networks
01 Pubblicazione su rivista::01a Articolo in rivista
Coordinating drones with mothership vehicles: The mothership and drone routing problem with graphs / Amorosi, L.; Puerto, J.; Valverde, C.. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 136:(2021), pp. 1-22. [10.1016/j.cor.2021.105445]
File allegati a questo prodotto
File Dimensione Formato  
Amorosi_coordinating-drones_2021.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.62 MB
Formato Adobe PDF
1.62 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1569933
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact