Premium
Modeling the flying sidekick traveling salesman problem with multiple drones
Author(s) -
Dell'Amico Mauro,
Montemanni Roberto,
Novellani Stefano
Publication year - 2021
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22022
Subject(s) - drone , travelling salesman problem , computer science , scheduling (production processes) , set (abstract data type) , operations research , truck , service (business) , order (exchange) , mathematical optimization , engineering , mathematics , aerospace engineering , business , algorithm , marketing , genetics , finance , biology , programming language
This article considers a version of the flying sidekick traveling salesman problem in which parcels are delivered to customers by either a truck or a set of identical flying drones. The flights of the drones are limited by the battery endurance and each flight is made of a launch, a service to a customer, and a return: launch and return must happen when the truck is stationary. These operations require time and when multiple drones are launched and/or collected at the same node, their order becomes relevant. The proposed model takes into account the order of these operations as a scheduling problem, because ignoring it could lead to infeasible solutions in the reality due to the possible exceeding of the drones endurance. We propose a set of novel formulations for the problem that can improve the size of the largest instances solved in the literature. We provide a comparison among the formulations, between the multiple drones solutions and the single drone ones, and among different variants of the model.