Fleet and Routing Optimization for Drone Delivery
PhD research, 2019 - 2022
Overview
This project solved system-level design optimization of a delivery drone fleet. Our goal was to reduce the fleet-level acquisition cost and delivery energy consumption by simultaneously optimizing the following three decision variables:
- Fleet sizing and composition, i.e. how many and what kind of drones should we put in the fleet?
- Each drone’s design variables, e.g., takeoff weight, battery capacity, rotor size, motor size, etc.
- Delivery routing, i.e., allocation of customer to each drone.
Our project extended the fleet sizing and mix vehicle routing problem (FSMVRP), which has been studied for truck delivery in the operations research community, to drone delivery.
Example of optimization results
Here is an example of the optimized delivery routes. Each drone departs from the depot at the center, visits one or a few customers (black points), and returns to the depot.
And the following figure shows the optimized drone design and fleet composition. The x- and y-axes are the two fundamental design variables (takeoff weight and cruise speed) and each drone illustration shows the disk and wing areas. The colors of the drones correspond to the routing colors in the above figure. For example, the orange tailsitters fly the orange routes.
Overall, we can see that the multirotors tend to serve nearby customers with multiple customers on a route, whereas the tailsitters serve customers far away from the depot and only makes one or two stops per route. These optimization results well exploited the different characteristics of the two VTOL configurations in making the optimal routing assignments: The multirotors are more efficient in hover, therefore it is best for shorter-distance (and potentially multi-stop) delivery. Tn the other hand, tailsitters are tailored for cruise performance, thus they are more efficient for longer-distance deliveries.
Sequential heuristic algorithm
The concurrent optimization of delivery routing and drone design results in a mixed-integer nonlinear optimization problem, which is very difficult to solve efficiency. To tackle this challenge, we proposed an effective sequential heuristic algorithm. This algorithm combines three steps: routing heuristics using Google OR-Tools, gradient-based optimization for drone design variables using OpenMDAO, and an exploratory step to increase the change of finding the global optimal solution. The following figure shows the overview of the proposed heuristics.
The proposed algorithm is computationally efficiency, reasonably accurate, and can solve large-scale problems (i.e., problems with many customers and many drones). More detailed discussion can be found in our paper.
Relevant publication
Shugo Kaneko and Joaquim R. R. A. Martins, Fleet Design Optimization of Package Delivery Unmanned Aerial Vehicles Considering Operations, Journal of Aircraft, 2023.