In this paper, we investigate the symbiosis between a truck and multiple drones in a last-mile package delivery scenario, introducing the Scheduling Conflictual Deliveries Problem (SCDP). From the main depot, a truck takes care of transporting a fleet of drones that will be used to deliver packages to customers. The route of the truck is predefined. Each delivery is associated with the energy cost of a drone, a reward that characterizes the priority of the delivery, and an interval between two points of the truck’s route: the point from which the drone departs (launch point) and the point at which the drone returns to the truck (rendezvous point). The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward subject to the drone’s battery capacity while ensuring that the same drone performs deliveries whose delivery intervals do not intersect. After showing that SCDP is an NP-hard problem, we devise an Integer Linear Programming (ILP) formulation for it. Furthermore, we devise a pseudo-polynomial time optimal algorithm for the single drone case and additional approximation algorithms for both the single and multiple drones case. Finally, we thoroughly compare the performances of our presented algorithms on different synthetic datasets.

On the Scheduling of Conflictual Deliveries in a last-mile delivery scenario with truck-carried drones / Betti Sorbelli F.; Coro F.; Das S.K.; Palazzetti L.; Pinotti C.M.. - In: PERVASIVE AND MOBILE COMPUTING. - ISSN 1574-1192. - STAMPA. - 87:(2022), pp. 0-0. [10.1016/j.pmcj.2022.101700]

On the Scheduling of Conflictual Deliveries in a last-mile delivery scenario with truck-carried drones

Betti Sorbelli F.;Palazzetti L.
;
2022

Abstract

In this paper, we investigate the symbiosis between a truck and multiple drones in a last-mile package delivery scenario, introducing the Scheduling Conflictual Deliveries Problem (SCDP). From the main depot, a truck takes care of transporting a fleet of drones that will be used to deliver packages to customers. The route of the truck is predefined. Each delivery is associated with the energy cost of a drone, a reward that characterizes the priority of the delivery, and an interval between two points of the truck’s route: the point from which the drone departs (launch point) and the point at which the drone returns to the truck (rendezvous point). The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward subject to the drone’s battery capacity while ensuring that the same drone performs deliveries whose delivery intervals do not intersect. After showing that SCDP is an NP-hard problem, we devise an Integer Linear Programming (ILP) formulation for it. Furthermore, we devise a pseudo-polynomial time optimal algorithm for the single drone case and additional approximation algorithms for both the single and multiple drones case. Finally, we thoroughly compare the performances of our presented algorithms on different synthetic datasets.
2022
87
0
0
Betti Sorbelli F.; Coro F.; Das S.K.; Palazzetti L.; Pinotti C.M.
File in questo prodotto:
File Dimensione Formato  
PMC_2022___Extension_ICDCN___OPT___APX.pdf

Accesso chiuso

Tipologia: Preprint (Submitted version)
Licenza: Tutti i diritti riservati
Dimensione 526.17 kB
Formato Adobe PDF
526.17 kB Adobe PDF   Richiedi una copia

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

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1288751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact