The multiple flying sidekicks traveling salesman problem with variable drone speeds. (November 2020)

• Record Type: Journal Article
• Authors: Raj, Ritwik; Murray, Chase
• Is Part Of: Transportation research. Volume 120(2020)
• Publication Date: 2020-11
• Subjects: Unmanned aerial vehicle -- UAV speed -- Drone speed -- Traveling salesman problem -- Truck-drone -- Heuristics; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2020.102813
• Languages: English
• ISSNs: 0968-090X

Abstract

Abstract: This research considers unmanned aerial vehicles (UAVs) that may travel at varying speeds in a last-mile delivery system involving a single truck and a fleet of UAVs. In existing truck-and-UAV delivery models that assume constant or unlimited UAV endurance, the natural conclusion is that operating UAVs at higher speeds will either decrease, or have no adverse effect on, total delivery times. However, in reality, UAV power consumption is a nonlinear function of both speed and parcel weight; flying at high speeds can dramatically reduce flight ranges, thus limiting the effectiveness of these logistics systems. This paper addresses the tradeoffs between speed and range in a new variant of the combined truck/UAV delivery problem in which UAV speeds are treated as decision variables. A three-phased algorithm is provided that dynamically adjusts UAV speeds to achieve superior performance, with the goal of minimizing the total delivery time (or makespan). Results indicate that significant time savings can be achieved by operating UAVs at variable speeds. Furthermore, under certain conditions, optimizing UAV speeds also results in shorter truck travel distances, reduced UAV energy consumption per trip, and less UAV loitering while waiting to rendezvous with the truck. Highlights: A combined truck-UAV delivery problem in which UAV speeds are decision variables. A three-phased heuristic algorithm solves problems with 100 customers and 4 UAVs. Savings in delivery-time achieved with variable UAV speeds over fixed-speed UAVs. Optimizing UAV speeds results in shorter truck travel distances. Other benefits include reduced UAV energy consumption and less UAV loitering.