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

This article focuses on the problem of planning drone delivery services within an urban unmanned aircraft systems traffic management (UTM) network, modeled as airspace above urban road networks with multiple flight levels. It formulates the drone delivery service planning as a dynamic network flow problem with time windows and capacity constraints, presenting both link-based and path-based integer linear programming models. The main contribution is the development of a branch-and-price (BP) algorithm enhanced by customized heuristics—including a primal heuristic and a reservation heuristic—to efficiently find near-optimal integer solutions despite the large problem size and complexity. Numerical experiments on the Sioux Falls network demonstrate that while direct integer programming solvers struggle with memory and scalability, the BP algorithm with the primal heuristic provides competitive solutions within reasonable computation times, especially in congested scenarios, whereas the reservation heuristic offers fast but often suboptimal feasible solutions. The study highlights challenges in scaling UTM optimization and suggests further research on airspace design and handling dynamic demand.