The Drone Delivery Problem

Researchers from Bilkent University and University of Liverpool have authored a paper that deals with what they call the ‘Drone Delivery Problem’ (DDP). Drone delivery is increasingly being used worldwide to make deliveries to a number of customers and the drones themselves are transported by traditional vehicles that act as launch points.

The authors describe the DDP as consisting of (i) selected launch points from a potential set of sites from where drones will take off to serve a number of customers, (ii) the assignments of customers to each launch points, and (iii) the physical speed at which these drones are able to travel between customers and aunch points.

The authors make three main contributions. They first introduce and formally define a delivery problem in which drones are used, where the speed of the actual drone is treated as the main decision variable. Second, they describe a nonlinear model for the problem and show that it can be reformulated as a second order cone programming function. Lastly, they present extensive computational experiments on the DDP on a realistic data set, quantifying the impact of using drones in making deliveries.

An illustration of the proposed drone delivery system

Reformulating The Model To Address The Authors’ Specific Needs

The model is also reformulated in the paper, using second order cone programming and subsequently strengthened by the use of perspective cuts, allowing the use of an off-the-shelf optimization software which solves the problems.

The authors explain how in such delivery systems the drone needs to be prepared either at a depot on a truck, ensuring efficient delivery depending on the network configuration of the cargo company.

“The drone takes off vertically from a given location, or a ‘pad’, and upon reaching a certain altitude, it cruises horizontally towards the direction of the customer. Upon arrival to the customer, it detects and lands on the drop-off point. After leaving the cargo at the drop off point, it travels in a reverse manner to return to the initial point of departure, finalizing the delivery,” the authors describe.

A Two-Echelon Delivery System

Motivated by these developments, the authors propose a two-echelon delivery system that uses drones in combination of traditional means of transport. In the model, trucks operate at the first echelon acting as dispatch points for drones that travel at the second echelon to actually make the delivery.

“Drones can either take off from a central depot or are transported by trucks to a parking area from where they are launched. In the latter case, each truck carries one drone to a designated parking area, from which the drone serves one customer and returns to the truck to be prepared for any subsequent delivery, as described above. The distance that a drone traverses is limited to a given range that is a function of battery capacity depending on the drone speed. Once all deliveries are made, the trucks return to the depot with their drones on board,” the authors describe.

The authors also formulate the drone energy consumption and range, calculating everything in detail and forming a lot of mathematical formulations for the DDP. They also focus on second order cone programming and do a computational study to present the detailed analyses on the solutions of the DDP.

Conclusion

After thorough analysis, the authors conclude that the Drone Delivery Problem (DDP) was properly introduced – using drones as the only mode of transportation to make deliveries to a number of customers.

“The proposed problem includes explicit calculations of drone energy consumption and the drone range, both of which depend on the drone speed, which itself is considered as a decision variable in the DDP,” the authors conclude.

• Although the use of the depot as a launch point incurs no operational truck cost, the depot may not always be the best launch point for a drone.
• A reduction in the delivery time bound does not always imply an increase in the drone speed for minimizing total cost, mainly due to the range constraints. Altering customer assignments and launch point locations instead may be a better means to cope with the tighter time bounds.
• The drone speed can be set to the same value for both legs (forward and return) of a given journey as using two different speed values does not save too much money.
• Deploying more than one drone from a launch point does not always reduce energy consumption due to the range constraints. One should instead consider either launching drones from new launch points or extending the capacity of the drone battery.

Citation: Dukkanci, Okan and Y. Kara, Bahar and Bektas, Tolga, The Drone Delivery Problem (January 10, 2019). Available at SSRN: https://ssrn.com/abstract=3314556 or http://dx.doi.org/10.2139/ssrn.3314556