Branch-and-Price for Drone Delivery Service Planning in Urban Airspace

Unmanned aerial vehicles or drones are increasing in use both for commercial and casual purposes. Although drone traffic management is mostly absent, as drone use increases, aerial conflicts are likely to also increase. This paper studies the problem of planning drone delivery service through an urban air traffic network space. The urban air traffic network is assumed to mostly be the airspace above existing roads and is modeled as a transportation network with multiple flight levels. Drone flights are modeled as individual trip requests with origins, destinations, and time windows. We present a novel integer linear programming formulation for this drone delivery service planning problem. The main contribution of this paper is developing a branch-and-price algorithm to solve the formulation, as the number of decision variables grows quickly with the problem size. We investigate three variations of branch-and-price, including branching on trajectory assignment variables, branching rules related to served requests, and a primal heuristic to quickly find integer feasible solutions. Numerical results show the limits of the integer linear programming formulation and the benefits of the primal heuristic in finding a good feasible solution.