A Branch-and-Price Algorithm for the Urban Aerial Delivery Problem With Energy Constraints

In this paper, an urban aerial delivery problem (UADP) is investigated, where the parcel transportation service is accomplished by drones in an urban setting. The aim of the problem is to minimize the total service completion time, by taking into account of the flow balance, the energy consumption, and the response time window. To fully explore the structure of the UADP, a mixed integer linear programming (MILP) model is constructed based on an arc-flow scheme. However, directly handling the UADP with commercial solvers is time consuming. In order to enhance the responsiveness of urban courier services and speed up the solving process, a set-covering model (UADP-SC) is proposed with a linear programming based relaxation. Then a branch-and-price algorithm is designed with pricing accelerating strategies based on heuristics. The computational experiments show that the proposed branch-and-price algorithm outperforms the off-the-shelf commercial solvers in terms of computation efficiency. In the mean time, the proposed algorithm can also serve to obtain optimal battery swapping and path planing decisions in face of the large-scale urban aerial delivery problem with energy constraints. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Note to Practitioners</i>—With the intensification of the aging population issue, the manual labor costs in logistics have sharply increased. Simultaneously, advancements in drone technology enable uncrewed aerial vehicles to participate in logistics distribution systems, addressing the last-mile delivery challenge. In the planning of drone delivery routes, the constraint of drone batteries cannot be ignored. This constraint not only affects delivery safety but also impacts delivery efficiency—both crucial considerations for decision-makers. Consequently, we propose a model considering the energy constraints. We introduce a branch-and-pricing algorithm to expedite the problem solving. The results show that the proposed algorithm performs well across various problem scales. Moreover, adopting a strategy of replacing batteries only when necessary can save approximately 17% to 23% of the total completion time. We also conducted performance comparisons under different ratios of orders to drones, providing decision-makers with a useful benchmark.