Landing-Aware Multi-Drone Routing in Last-Mile Delivery Services

Abstract

We propose a framework to compute the optimal routes for multi-drones to minimize the delivery time in the last-mile delivery service. We mainly focus on a notion of the landing exclusion zone that appears during the landing phase; an area around the drop-off site is blocked until a drop-off is completed. Such zones affect the delivery time as other drones need to detour or hover around the site unnecessarily. We formulate the Mixed-Integer Linear Programming (MILP) problem by explicitly modeling the landing phase. Then, we present the heuristic algorithm that iteratively solves a sequence of single-drone delivery problems according to the delivery priorities. A delivery priority is determined according to the spatiotemporal occupancy that quantifies the significance of the size of the landing exclusion zone and its blocking period. We designed the experiment for 48 urban delivery scenarios with varying density and distribution of delivery destinations, departure points, and order quantities. Our experiment results show that the heuristic computes the routes significantly faster than the original MILP, and the delivery time is 5% higher from the optimal solution (lower-bound), and 60% lower from the general requirement of a single package per round-trip (upper-bound).