An Extended Savings Algorithm for UAS-based Delivery Systems

Abstract

This paper presents an extended savings algorithm for a package delivery system using unmanned aircraft systems (UAS). The savings algorithm as a heuristic method solves a vehicle routing problem (VRP) that is commonly formulated by an operational plan for each vehicle. In general, package delivery systems need to establish an operational plan based on demand and preferred time to be visited for each customer. In UAS-based delivery systems, however, capacity and traveling time constraints must be additionally considered to create their operational schedules because of limited payload capacity and short endurance of unmanned aerial vehicles (UAVs). Because of these limitations, UAVs should be reused during operation hours to reduce acquisition costs. Thus, a recharging strategy should be included in the operational planning process. However, conventional savings algorithms cannot capture those properties at once because they have mainly focused on delivery systems with conventional vehicles such as trucks and passenger/cargo aircraft that have different vehicle features and operational characteristics, such as the endurance/speed of a vehicle and recharging strategy. To overcome the limitations of the conventional approaches, this paper proposes the extended savings algorithm, which can concurrently reflect the characteristics of both delivery systems and UAVs. To demonstrate the proposed extended savings algorithm this paper preforms numerical simulations with two representative scenarios in Annapolis, MD and Macon, GA.