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

Michael W. Levin () and David Rey ()
Additional contact information
Michael W. Levin: Department of Civil, Environmental, and Geo-Engineering, University of Minnesota, Minneapolis, Minnesota 55455
David Rey: SKEMA Business School, Université Côte d’Azur, Sophia Antipolis, 06902 Valbonne, France

Transportation Science, 2023, vol. 57, issue 4, 843-865

Abstract: 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.

Keywords: unmanned aerial vehicles; airspace management; drone delivery; service planning; branch-and-price (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1175 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:4:p:843-865

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().