Locating Platforms and Scheduling a Fleet of Drones for Delivering Perishable Items
Project Type: Research
LoDI Team: Monica Gentili, Pitu Mirchandani, Alessandro Agnetis, Zabih Gelichi
Overview
In many disaster scenarios like earthquakes, avalanches, and explosions, the first few hours are crucial. Commonly, that disaster can render roads inaccessible for some time. During these hours when people are stranded without means of transport, Unmanned Aerial Vehicles (UAVs), also known as drones, can deliver the emergency aid packages. In this humanitarian assistance scenario, we consider the people that will be served are either individuals or small groups/families, who are spatially dispersed.
Purpose and Need
When a disaster strikes, the road transportation networks might be heavily impacted. Due to the damages to road networks, fast and timely delivery of urgently needed medical packages to people trapped in disaster areas by traditional transportation modes like trucks faces a legion of logistical challenges. Examples of such challenges include but not limited to hard to access locations, the short shelf life of the urgent medicines, scarcity of human and facility resources. In this case, drones are considered as a promising solution to provide emergency support for people trapped in the disaster area. Advantages of using delivery drones include (1) vertical takeoff from and landing in small places, (2) low capital and operating costs, (3) no requirements of a pilot on-board, and (4) no need for a costly expansive infrastructure for takeoff/landing.
In this problem, we have p delivery drones to serve remote m demand points that need delivery of emergency medical supplies such as blood units. These demand points are reachable only by drones where each of the drones is constrained by a limited distance range to service a demand point. The drones operate out of mobile platforms which may be moved on useable roads. Each demand point requires a single package of the product whose utility decreases with delivery time due to product perishability. Furthermore, a customer’s demand may have a delivery time deadline. The main problem addressed is to locate platforms, and their associated drones, so that the p total disutility for delivery times are minimized. Each demand point requires a single package of the product whose utility decreases with delivery time due to product perishability.
Methodology
We considered two variants for this problem. First, we look at the case when perishable items need to be sent in a single day to the demand point. Then, we study other cases where delivery may take place over several days and platforms can be moved from day to day. We first, developed a continuous-time variant of the proposed problem. It can be easily proved that continuous-time version of these problems are NP-Hard. Then, a practical “time-slot” version of the problem, where time is discretized into slots, is developed which can be solved by standard optimization software. To evaluate the effectiveness and performance of the proposed model, we designed various experiments and analyses.
Results and Impacts
We analyzed the effects of using a different homogeneous fleet of drones (i.e., short-range vs long-range drones), having uniform disutility functions vs non-uniform disutility functions, allowing multiple drones per platform and a fleet of multi-type drones. The results of this study show that employing more than one drone per platform is not always beneficial. Also, the outcomes unveil that the flight range of drones is a decisive key to determine the number of required platforms and delivery time.