In a near future drones are likely to become a viable way of distributing parcels in a urban environment. In this paper we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to service all the customers. We present a set of matheuristic methods for the problem. The new approaches are validated via an experimental campaign on two sets of benchmarks available in the literature. It is shown that the approaches we propose perform very well on small/medium size instances. Solving a mixed integer linear programming model to optimality leads to the first optimality proof for all the instances with 20 customers considered, while the heuristics are shown to be fast and effective on the same dataset. When considering larger instances with 48 to 229 customers, the results are competitive with state-of-the-art methods and lead to 28 new best known solutions out of the 90 instances considered.

Matheuristic algorithms for the parallel drone scheduling traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - 289:(2020), pp. 211-226. [10.1007/s10479-020-03562-3]

Matheuristic algorithms for the parallel drone scheduling traveling salesman problem

Dell'Amico M.;Montemanni R.;Novellani S.
2020

Abstract

In a near future drones are likely to become a viable way of distributing parcels in a urban environment. In this paper we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to service all the customers. We present a set of matheuristic methods for the problem. The new approaches are validated via an experimental campaign on two sets of benchmarks available in the literature. It is shown that the approaches we propose perform very well on small/medium size instances. Solving a mixed integer linear programming model to optimality leads to the first optimality proof for all the instances with 20 customers considered, while the heuristics are shown to be fast and effective on the same dataset. When considering larger instances with 48 to 229 customers, the results are competitive with state-of-the-art methods and lead to 28 new best known solutions out of the 90 instances considered.
2020
289
211
226
Matheuristic algorithms for the parallel drone scheduling traveling salesman problem / Dell'Amico, M.; Montemanni, R.; Novellani, S.. - In: ANNALS OF OPERATIONS RESEARCH. - ISSN 0254-5330. - 289:(2020), pp. 211-226. [10.1007/s10479-020-03562-3]
Dell'Amico, M.; Montemanni, R.; Novellani, S.
File in questo prodotto:
File Dimensione Formato  
s10479-020-03562-3.pdf

Accesso riservato

Tipologia: Versione pubblicata dall'editore
Dimensione 314.33 kB
Formato Adobe PDF
314.33 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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