Drone-Based Package Delivery Logistics Systems: History
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:

Autonomous Drone Delivery (ADD) modes are expected to become an important pillar of the future logistics industry for small parcel delivery at the last mile, as well as meal delivery service for fast food (e.g., pizza, etc.) and restaurants.

  • autonomous drones
  • vehicle routing problem
  • drone-based package delivery system

1. State of Parcel Delivery through Drones in Logistics Industry

In recent years, several firms have started to pay more attention to the design of drones intended for package delivery in different industries, such as e-commerce and the medical sector. The giant of e-commerce, Amazon, took a significant step forward when they introduced their demo reel. In 2013, Amazon was one of the first players to deploy a delivery system, where the Prime Air from Amazon was designed to safely deliver packages to customers within a short period of time by employing fully automated drones [7,8]. Amazon Prime Air made its first official delivery in 2016 by transporting a package to a house 10 miles from the Cambridge fulfillment center. In 2020, after UPS and Alphabet’s Project Wing, the Federal Aviation Administration granted Amazon federal authorization to run its Prime Air project of drone package delivery for the purpose of delivering parcels to its costumers efficiently and safely [9]. Another project, named Parcelcopter, launched in 2013 by the giant German logistics company ‘Deutsche Post DHL’, involved aerial vehicles transporting medicine to the island of Juist in the North Sea [10]. Alphabet, though not an e-commerce company, also expects a big future for drones in shipping; in 2014, it revealed Project Wing, which developed drones intended to deliver packages larger than those by Prime Air of Amazon and Pacelcopter of DHL [11]. The online store Siroop, founded in 2015 by the retail distributor Coop and the cellular phone company Swisscom, developed a pilot project for online shopping delivery by drones using vans, in collaboration with the German automobile manufacturer Mercedes Benz [12]. In this project, the drone uses the roof of the delivery truck as a landing platform. The package is processed by the driver in order to deliver it to the recipient. Additionally, the restaurant industry has also started paying attention to the drone delivery mode. Indeed, some fast food giants, such as Domino’s Pizza and McDonald’s, are realizing the high potential of home delivery by involving drone delivery services in congested urban areas. They have already developed experimental tests for meal delivery in collaboration with drone technology startups such as Flytrex and Flirtey [3]. Additionally, the transportation of medicines through drones is feasible between hospitals [13]. In some countries in Africa, governments are obliged to maintain low drug inventories due to the high cost of storing drugs. A delivery of life-saving medicine, for instance, can take more than four hours to reach its destination by car. To solve this issue, drone-based logistics systems are being launched in some countries, such as Rwanda and Tanzania, for delivering vaccines to isolated villages. In addition to this, in April 2019, the Government of Ghana officially launched its drone delivery service in cooperation with the US startup Zipline to serve hospitals and medical centers [14]. The goal was to build an emergency on-demand delivery service for different vaccines, blood products, and drugs.
Despite all of the advancements in drone technology by large corporations, and even despite the boom of artificial intelligence and economic activities, many countries around the world have yet to define specific regulations and rules for involving civil drones in their airspace; this limits the evolution of such a promising logistics industry [15]. As a result, the feasibility of reliable deployments of drone delivery systems is still in its early stages, and more steps are required to develop and integrate drones into a true (last mile) logistics industry [16]. Furthermore, recharging stations or drone ports will be indispensable infrastructure for enabling e-commerce and logistics companies to deal with the limited energy autonomy issue of such systems, which represents another important technical and cost challenge for those logistics companies and other relevant stakeholders.

2. Literature Investigation on Current Research for Drone-Based Logistics

In this review paper, we classified the relevant related works under four major groups, which represent the main research avenues by including a series of related challenges and constraints faced by these drone-based logistics systems. Thus, the main research issues and challenges can be summarized under the following headings: (1) vehicle routing problem with drones; (2) drone assignment issue; (3) charging process and recharging station location; (4) fleet dimensioning. An review of the literature is provided for each of these issues, as well as an explanation of one or more proposed solutions.
When considering the Vehicle Routing Problem with Drones (VRPD), most of the literature has addressed hybrid delivery systems, which combine two delivery modes: the vehicle-based delivery system and the drone-based delivery mode. Most issues with last-mile delivery with drones suggest that the aerial vehicle is transported close to the destination of the package by ground vehicles. From here, while the drone is delivering a package, the van can serve other customers who are not reachable by drone. As a result, the drone will be able to continue serving all customers who are within its flight zone, increasing user-friendliness and making the schedule more flexible [8,17,18,19]. In the first conducted studies in this direction, Murray and Chu [20] addressed two issues related to drone-based delivery in conjunction with trucks in order to minimize the trip time for both the drone and the truck when returning to the depot. The flying sidekick travelling salesman problem was the first to be handled, based on a mixed integer linear programming (MILP) formulation to minimize the expected delivery time, whereby the drone is assigned to the truck to deliver parcels to customers. Regarding this problem, the authors proposed a heuristic approach called “Truck First, Drone Second”, where the truck path is designed to resolve the traveling salesman problem. The truck travels along a route that begins at a depot, serves customers along the way, then finishes at the depot. The second issue tackled was the traveling salesman problem with parallel drone scheduling. In contrast to the first problem, this problem considers that the drone and the truck perform deliveries independently. The heuristic approach proposed for this this issue assumes that the drones will serve all the customers within their maximum range, while the truck will serve the remaining customers. In contrast, many assumptions were later introduced to simplify the model, whereby the authors assumed that the number of drones is very limited, the velocity and duration of a drone’s flight are constant, the drone preparation is done by a person in the vehicle (drone not autonomous), and the depot is located near the center of all customers. However, the delivery problem is considered a stochastic problem and uses a large fleet of fully autonomous drones in the delivery system, thus making the modeling very challenging. Later, Jeon et al. [21] addressed the same routing problem by using MILP models and some heuristics based on the approach proposed by Murray and Chu. This proposed method involves reducing the number of empty flights in order to increase drone utilization; it is being tested on Jeju Island, using localization and tracking data. Dorling et al. [8] addressed two multi-trip vehicle routing problems that incorporate battery and payload weights into the energy consumption calculations; the first problem deals with the cost issue of a delivery time constraint, and the second problem seeks to optimize the delivery time subject to a cost limit. Furthermore, the proposed algorithms seek to optimize the drone fleet size as well as the trips for the delivery of the package. The authors assumed that the operator has enough fully charged batteries to satisfy the drone energy requirements before the deliveries can start and that the operator deploys only one depot (charging station) in the area. In contrast, it would be very challenging and costly for a delivery company to deploy multiple depots and battery swapping stations, as well as to manage battery swapping between trips to meet the daily demand. Wang et al. [22,23] addressed the vehicle routing problem with drones, where the fleet consists of multiple trucks equipped with multi-drones to minimize the completion time. Both vehicles can deliver the packages, and the trucks must wait for the drone after it has been deployed for a delivery. They proposed a routing strategy called “The Drone Vehicle Traffic Problem”, where the objective is to serve all customers within the shortest time duration. The authors show good results in terms of delivery cost reduction and delivery time when using drones and trucks instead of trucks alone, consolidating their results through simulations and the analysis of several worst-case scenarios. However, the authors did not take into consideration the automated landing of drones on the ground vehicle, which is very challenging for this hybrid delivery mode. Thereafter, Schermer et al. [24] proposed two heuristic algorithms for solving the same problem, supported with numerical experiments on large-scale traveling salesman problems. The first algorithm, named “Two-Phase Heuristic (TPH)”, initially creates the vehicle routing problem for the truck and then the vehicle routing problem for using drones. The second algorithm, named “Single-Phase Heuristic (SPH)”, computes routes that already include drones. A similar work by Ham [25] also addressed the vehicle routing problem; the author suggested a constraint optimization formulation in order to solve scheduling problems of multiple trucks, drones, and depots, subject to time, drop-off, pick-up, and multi-visit constraints. The proposed drone delivery schedule allows drones to fly back to the depot to deliver the next order after completing the preceding drop or to fly directly to another customer to collect a returned parcel. In contrast, incorporating new drone tasks, such as collecting returned packages, necessitates a greater extension of the drone’s flight range, making the delivery system modeling extremely difficult. In addition, Wang and Sheu [26] addressed the vehicle routing problem with drones in a real-world setting by employing an arc-based integer programming approach and developing a branch and price algorithm. In comparison to other studies where the number of customers was limited, they applied their approach to a large-scale system that included multi-drones and trucks, as well as several customers being served. They used the branch-and-price algorithm to find optimal solutions for a set of instances in an average of two hours. Bertolaso et al. [27] also tackled the hybrid delivery system, which combines a drone and a vehicle, where the drones’ landing task problem was addressed. To deliver the parcel, the drone can land on the vehicle’s roof while the vehicle is moving to the desired location. The authors developed a cooperative landing model by using Petri Nets plans, with a strategy that includes multiple phases.
Concerning the drone assignment to the customer, the decision system needs to determine which drone will be charged to deliver the parcel, which represents a significant challenge for the researchers in developing optimization techniques to deliver the parcel to the customer in the least amount of time, subject to several constraints, such as battery range limitations and the operational cost of the systems. After receiving the parcels, the drone assignment system assigns a drone from the available fleet to perform the mission according to the priority of customer requests. To the best of our knowledge, only a few works have addressed this issue. Grippa et al. [28] suggested a task assignment strategy (task means registered customer request) for assigning customer requests to drones in order to reduce the delivery time as much as possible. The proposed model is based on queuing theory, with Poisson processes generating the arrival of delivery requests for goods by drones. Two classes of job assignment policies have been proposed: the first is called nearest job first to random vehicles (NJR), and it chooses jobs based on the customer’s location, while the second is called first job first to nearest vehicles (FJN), and it chooses jobs based on the arrival time of the customer’s request. The FJN policy achieves a low expected average delivery time for low loads and performs well even for high loads. Park and Zhang et al. [29] addressed the battery and charger assignment problem in a discrete event simulation framework. The author proposed a solution algorithm capable of deciding where to assign batteries and chargers to the service by searching the best location, as well as computing charging and task dispatching schedules. Moreover, a scheduling model was formulated to determine the time at which a battery begins/stops charging or begins/stops discharging. Sawadsitang et al. [30] developed a suppliers’ cooperation policy to share the total cost of a drone delivery service. This means that suppliers can serve their customers collaboratively and share their drones in order to serve as many customers as possible; when a drone drops a package at the desired destination, it can return to any supplier depot that is part of the cooperation system. The proposed optimization model considers the parcel assignment problem as mixed integer programming. Murray and Chu [20] also tackled the customer assignment issue for drones working collaboratively with trucks, subject to the constraints of the launch points of trucks and drones, the depot node, and the rendez vous point of trucks and drones. However, only generated data were used to test the model’s performance, and the authors included several assumptions to simplify the model in terms of issues such as limited drone fleet size and limited number of trucks and customers. In addition, they did not consider the battery range issue in their modeling. To the best of our knowledge, no short-term assignment strategies have been proposed to improve the efficiency of an autonomous drone-based delivery service in real time. For instance, in fast-food meal delivery services, customers need to be served quickly, especially during peak hours, which represents a challenge for scheduling the drone fleet.
Considering the charging process and the location of recharging stations, recharging or swapping infrastructure will be required to extend the flight range of battery-powered drones. In this context, some studies proposed deploying charging infrastructure to expand the coverage range of drone delivery services. Hong et al. [31] addressed the issue of recharging infrastructure locations for drone-based commercial delivery services without truck cooperation in urban areas, where the fleet of drones is supported by the implementation of a network of recharging stations. The authors proposed a coverage location model to construct a delivery network that covers the maximum expected demand while minimizing average flight distance from depots to recharging stations. This approach was formulated using heuristic techniques combined with the Greedy algorithm. In contrast, this study did not investigate the potential impact of decision parameters such as recharging station configuration, charging time, number of batteries, and drone battery range on the performance of drone delivery services, which could more accurately reproduce the real nature of systems. Additionally, this study focused on the relocation problem but did not address the assignment problem. Yu et al. [32] addressed the drone coverage range issue by allowing the drone to be recharged along the way by landing on stationary or mobile recharging stations. Mobile recharging stations are small, unmanned ground vehicles that continue to recharge the drone while transporting it from one location to another. The proposed algorithm computes the optimal path for the drone to visit multiple locations while also determining when and where to land on charging stations. Furthermore, it determines the paths of unmanned ground vehicles as well as the optimal locations of recharging stations. Three scenarios were studied: multiple stationary stations, a single mobile station, and multiple mobile stations. A generalized traveling salesperson problem-based algorithm was proposed to solve the first two problems, and an integer linear programming algorithm was suggested to solve the third. Huang et al. [33] suggested a heuristic optimization deployment approach, addressing the issue of station location by proposing a method of deploying recharging stations throughout the city to recharge/or swap batteries. The authors consider that the charging station could be repositioned from one place to another to increase coverage. Shao et al. [34] proposed an optimization approach for drone delivery service, including battery swapping stations and maintenance checkpoints, based on the ant colony optimization algorithm, in order to increase the flight distance from depot to customer. Alyassi et al. [35] proposed an autonomous recharging system for fully autonomous drones, as well as conducted an empirical study to evaluate the impact of drone battery on system performance. Bacanli et al. [36] developed a charging station deployment solution for unmanned aerial vehicles based on a spiral-based scanning method. The problem of recharging station placement was also addressed in [37] by employing a back-and-forth method to find the optimal number of charging stations. Overall, we believe that the deployment of mobile recharging stations is feasible if we can understand the challenges of communication between the ground vehicle (mobile station) and the drone in the short term, such as vehicle trajectory prediction. Furthermore, the recognition of partner vehicles and the autonomous landing of drones on moving stations require further research and development based on advanced techniques such as artificial intelligence, image recognition, and virtual sensing. In this regard, Baca et al. [38] addressed the drone landing challenge on a moving van, proposing a computer vision algorithm to recognize the landing pattern on the roof of the van using a camera. An Unscented Kalman Filter was used to control the state of the vehicle by estimating position and velocity and predicting trajectory using a non-linear motion model. However, modeling the drone following of fast, dynamic vehicles on the road and predicting the motion of mobile stations in next short term is extremely difficult. Feng et al. [39] addressed the same issue, proposing an autonomous landing method based on a moving platform. The proposed approach consists of different combined models, including a Kalman filter for optimal target localization, a predictive control model, and integral control for robustness.
Alternatively, due to the flight range constraint, another strategy for expanding the delivery area of drone systems was proposed in the literature, which involves utilizing public transportation networks. In this context, Huang et al. [40,41] addressed the issue of limited flight range by proposing a round trip scheduling approach, utilizing public transportation networks, which allows the drone to deliver parcels to distant points from the warehouse. In contrast, the developed policy addressed a sample drone’s network of limited warehouses, drones, and customers; additionally, drone schedule synchronization with transportation network planning makes modeling of this hybrid dynamic system very challenging. Furthermore, the authors addressed the expected delivery time optimization using a Dijkstra-based algorithm, where the delivery system is supported by a public transportation network [42]. However, the proposed drone-vehicle delivery manner could increase the expected delivery time compared to the drone direct delivery mode. Furthermore, the communication technology of drones to vehicles, which allows the drone to collect vehicle trip information, is still in the early stages of use in the logistics industry. Other studies have also analyzed the logistics of drones for online meal delivery of fast food. In this respect, Liu [43] proposed a mixed integer programming (MIP) model to solve the dynamic pickup and delivery problem, assuming that the delivery system is reinforced by charging depots for swapping batteries when the drone’s battery is almost drained. Pinto et al. [44] also contributed to the literature on the recharging station deployment problem. The authors discussed drone meal delivery issues for restaurants, where a network of charging stations is proposed to support drones’ limited flight range. Under a set of constraints, a heuristic optimization model was proposed to determine the optimal placement and number of recharging stations to maximize coverage. In contrast to the parcel delivery business, the online meal delivery business faces significant delivery time challenges, particularly during peak hours, where the maximum waiting time of a customer is extremely limited in order to receive meals in a timely manner.
Nevertheless, during an autonomous drone missions to deliver a parcel to a customer in urban area, the drone navigation system might face unknown obstacles such as trees, power lines, trucks, and buildings. To overcome such challenges, more research on the sensing and perception of drones is required, based on new methods of artificial intelligence and computer vision to increase the precision of the recognition system. Additionally, newly developed artificial intelligence approaches for autonomous ground vehicles may be used to address challenges in using autonomous drones, transforming them into fully autonomous machines. In this regard, some recent works [45,46] have addressed recognition, automated detection, and navigation issues for autonomous drone delivery using machine learning, deep learning, and neural networks.
Concerning the issue of drone fleet dimensioning, studies have focused on estimating the required fleet size to meet a given demand and also on determining the initial position of the drone. Troudi et al. [47] proposed an approach that deals with vehicle routing problems to investigate the fleet dimensioning problems of drone delivery services. The authors developed an analytical model through two scheduling strategies, where the first one tries to schedule delivery operations while minimizing the flight distance, and the second attempts to strike a balance between distance and drone fleet size. Various analytical scenarios are being proposed in order to optimize the fleet cost by optimizing the number of drones, minimizing the flight drone distance, and reducing the number of batteries. However, the authors assume that the battery should be charged to 100% capacity for every mission, regardless of the remaining battery capacity after a mission, and that there are a limited number of customers served in urban area. Furthermore, the authors did not consider the battery swapping challenge for drone operators (when and where the swapping should be performed). Grippa et al. [28] conducted similar research, developing a method for dimensioning the drone delivery system that uses simulations and queuing theory. For dimensioning, two time horizons were proposed: long-term decisions about the number of depots to deploy in the service area and short-term decisions about the number of drones to use.
According to this review of the most relevant and most recent papers on drone-based parcel delivery systems, many drone delivery problems have been addressed, indicating the importance of drones in resolving many logistical problems, particularly in the last mile, and transforming the future of package delivery. However, in order to launch a drone delivery system in an urban area, the level of urban aerospace must be capable of dealing with high delivery drone traffic densities. Doole et al. [48] proposed a method for estimating the traffic demand for a typical dense European city’s drone-based delivery system. A case study was applied to the Paris metropolitan area. According to the outcome of their research, there will be an average of 63,596 hourly traffic density delivery drones of small express packages as well as fast-food meals in the urban airspace of Paris, an area of 12,012 km2, by 2035. However, the authors did not consider the battery charging issue in this study, which represents a challenge for the drone-based delivery process. Modeling of safety assessments has also been addressed. The work of Gonçalves et al. [49] highlighted the safety issue by proposing a safety model based on Petri nets to demonstrate evidence of drone safety and reliability, required for the airworthiness certification process. According to recent studies, by 2050, there will be 400,000 drones operating at a Very Low Level (VLL), which requires drones to fly between 0 and 500 ft. This corresponds to a high density of autonomous drone operations [50]. As a result, in order to successfully operate this system, there must be safe air navigation, as well as decision-making tools and obstacle data analysis methodologies, taking into account that flying closer to the ground also means being closer to manmade and natural obstacles.

This entry is adapted from the peer-reviewed paper 10.3390/su14010360

This entry is offline, you can click here to edit this entry!
ScholarVision Creations