Application of hierarchical facility location problem for optimization of a drone delivery system: a case study of Amazon prime air in the city of San Francisco

Abstract

In the last decade, aerial delivery system has been considered as a promising response to increasing traffic jams and incremental demand for transportation. In this study, a distance-constrained mobile hierarchical facility location problem is used in order to find the optimal number and locations of launch and recharge stations with the objective of minimizing the total costs of the system. System costs include establishment cost for launching and recharge stations, drone procurement, and drone usage costs. It is supposed that the demand occurs according to Poisson distribution, distributed uniformly along the network edges and is satisfied by the closest open facility. Since the flying duration of a drone is limited to its endurance, it may visit one or more recharge stations to reach to the demand point. This route is calculated by the shortest path algorithm, and the Euclidean distance is considered between nodes and facilities. It is proved that facility location problems are NP-hard on a general graph. Accordingly, heuristic algorithms are proposed as solution method. To illustrate the applicability of the algorithms, a case study is presented and the results are discussed.