Highlights A new extension to the flying sidekick TSP is presented. This problem assigns one truck and multiple heterogeneous drones to deliver parcels. Queueing of drone launch and retrieval activities is included in the formulation. A three-phase heuristic solves problems with 100 customers and 4 drones. Numerical analysis provides insights into system behaviors and heuristic performance.
Abstract This paper considers a last-mile delivery system in which a delivery truck operates in coordination with a fleet of unmanned aerial vehicles (UAVs, or drones). Deploying UAVs from the truck enables customers located further from the depot to receive drone-based deliveries. The problem is first formulated as a mixed integer linear program (MILP). However, owing to the computational complexity of this problem, only trivially-sized problems may be solved directly via the MILP. Thus, a heuristic solution approach that consists of solving a sequence of three subproblems is proposed. Extensive numerical testing demonstrates that this approach effectively solves problems of practical size within reasonable runtimes. Additional analysis quantifies the potential time savings associated with employing multiple UAVs. The analysis also reveals that additional UAVs may have diminishing marginal returns. An analysis of five different endurance models demonstrates the effects of these models on UAV assignments. The model and heuristic also support anticipated future systems that feature automation for UAV launch and retrieval.
The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones
Tramsportation Research, Part C: Emerging Technologies ; 110 ; 368-398
2019-11-02
31 pages
Article (Journal)
Electronic Resource
English
The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery
Online Contents | 2015
|Exact methods for the traveling salesman problem with multiple drones
Elsevier | 2021
|