IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v193y2025ics1366554524004502.html
   My bibliography  Save this article

Air Corridor Planning for Urban Drone Delivery: Complexity Analysis and Comparison via Multi-Commodity Network Flow and Graph Search

Author

Listed:
  • He, Xinyu
  • Li, Lishuai
  • Mo, Yanfang
  • Sun, Zhankun
  • Qin, S. Joe

Abstract

Urban drone delivery, a rapidly evolving sector, holds the potential to enhance accessibility, address last-mile delivery issues, and alleviate ground traffic congestion in cities. Effective Unmanned Aircraft System Traffic Management (UTM) is essential to scale drone delivery. A critical aspect of UTM involves planning a city-wide network with spatially-separated air corridors (air routes). Most existing works have focused on routing problems or air traffic management. Compared to these problems, the air corridor planning problem requires much higher spatial and temporal resolutions and presents computational challenges due to the scale, complexity, and density of urban airspace, along with the coupling issues of multi-path planning. Therefore, we conducted this research to understand the complexity and computational resources required to optimally solve the air corridor planning problem. In this paper, we use a minimum-cost Multi-Commodity Network Flow (MCNF) model, a mathematical model, to model the problem and demonstrate the complexity of air corridor planning through the complexity of MCNF. We then apply Gurobi’s and GLPK’s integer programming (IP) solvers to find optimal solutions. Additionally, we present two existing multi-path graph search algorithms, the Sequential Route Network Planning (SRP) algorithm and the Distributed Route Network Planning (DRP) algorithm, to address this corridor planning problem. Numerical experiments conducted at various scales and settings using IP solvers and graph search algorithms indicate that finding an optimal solution requires significant computational resources and yields only a slight improvement in optimality compared to graph search algorithms. Thus, air corridor planning is complex both theoretically and numerically, and graph search algorithms can provide a feasible solution with good enough optimality for corridor planning in real-world scenarios. Moreover, the multi-path graph search algorithms can easily incorporate side constraints that are known to be impossible to solve with polynomial algorithms, making it more practical for real-world applications. Finally, we demonstrate the application of SRP and DRP in real-world 3D urban scenarios.

Suggested Citation

  • He, Xinyu & Li, Lishuai & Mo, Yanfang & Sun, Zhankun & Qin, S. Joe, 2025. "Air Corridor Planning for Urban Drone Delivery: Complexity Analysis and Comparison via Multi-Commodity Network Flow and Graph Search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 193(C).
    • Handle: RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004502
    DOI: 10.1016/j.tre.2024.103859
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554524004502
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2024.103859?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Morton Klein, 1967. "A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems," Management Science, INFORMS, vol. 14(3), pages 205-220, November.
    2. Wang, Lizhong & Fang, Liping & Hipel, Keith W., 2008. "Basin-wide cooperative water resources allocation," European Journal of Operational Research, Elsevier, vol. 190(3), pages 798-817, November.
    3. Mesquita, Marta & Moz, Margarida & Paias, Ana & Pato, Margarida, 2015. "A decompose-and-fix heuristic based on multi-commodity flow models for driver rostering with days-off pattern," European Journal of Operational Research, Elsevier, vol. 245(2), pages 423-437.
    4. Paola Cappanera & Maria Paola Scaparra, 2011. "Optimal Allocation of Protective Resources in Shortest-Path Networks," Transportation Science, INFORMS, vol. 45(1), pages 64-80, February.
    5. Naoto Katayama, 2019. "A combined fast greedy heuristic for the capacitated multicommodity network design problem," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 70(11), pages 1983-1996, November.
    6. Lemardelé, Clément & Estrada, Miquel & Pagès, Laia & Bachofner, Mónika, 2021. "Potentialities of drones and ground autonomous delivery devices for last-mile logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    7. Pentico, David W., 2008. "The assortment problem: A survey," European Journal of Operational Research, Elsevier, vol. 190(2), pages 295-309, October.
    8. He, Xinyu & He, Fang & Li, Lishuai & Zhang, Lei & Xiao, Gang, 2022. "A route network planning method for urban air delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    9. Dimitris Bertsimas & Sarah Stock Patterson, 2000. "The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach," Transportation Science, INFORMS, vol. 34(3), pages 239-255, August.
    10. Goldbeck, Nils & Angeloudis, Panagiotis & Ochieng, Washington Y., 2019. "Resilience assessment for interdependent urban infrastructure systems using dynamic network flow models," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 62-79.
    11. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    12. Elbert, R. & Müller, J. P. & Rentschler, J., 2020. "Tactical network planning and design in multimodal transportation – A systematic literature review," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 120617, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Houshan Zhang, 2025. "A Graph-Induced Neighborhood Search Heuristic for the Capacitated Multicommodity Network Design Problem," Mathematics, MDPI, vol. 13(4), pages 1-23, February.
    2. Lienkamp, Benedikt & Schiffer, Maximilian, 2024. "Column generation for solving large scale multi-commodity flow problems for passenger transportation," European Journal of Operational Research, Elsevier, vol. 314(2), pages 703-717.
    3. Khodakaram Salimifard & Sara Bigharaz, 2022. "The multicommodity network flow problem: state of the art classification, applications, and solution methods," Operational Research, Springer, vol. 22(1), pages 1-47, March.
    4. Thomas W. M. Vossen & Michael O. Ball, 2006. "Slot Trading Opportunities in Collaborative Ground Delay Programs," Transportation Science, INFORMS, vol. 40(1), pages 29-43, February.
    5. Chunlong Li & Jianzhong Zhou & Shuo Ouyang & Chao Wang & Yi Liu, 2015. "Water Resources Optimal Allocation Based on Large-scale Reservoirs in the Upper Reaches of Yangtze River," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 29(7), pages 2171-2187, May.
    6. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    7. He, Xinyu & He, Fang & Li, Lishuai & Zhang, Lei & Xiao, Gang, 2022. "A route network planning method for urban air delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    8. Zhongwen Xu & Liming Yao & Yin Long, 2020. "Climatic Impact Toward Regional Water Allocation and Transfer Strategies from Economic, Social and Environmental Perspectives," Land, MDPI, vol. 9(11), pages 1-17, November.
    9. Naoto Katayama, 2020. "MIP neighborhood search heuristics for a service network design problem with design-balanced requirements," Journal of Heuristics, Springer, vol. 26(4), pages 475-502, August.
    10. Jiang, Yangsheng & Huangfu, Junjie & Xiao, Guosheng & Zhang, Yongxiang & Yao, Zhihong, 2025. "Energy-efficient trajectory design of connected automated vehicles platoon: A unified modeling approach using space-time-speed grid networks," Energy, Elsevier, vol. 314(C).
    11. Karakose, Gokhan & McGarvey, Ronald G., 2018. "Capacitated path-aggregation constraint model for arc disruption in networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 225-238.
    12. Ana Paias & Marta Mesquita & Margarida Moz & Margarida Pato, 2021. "A network flow-based algorithm for bus driver rerostering," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 543-576, June.
    13. Lu, Qing-Chang & Xu, Peng-Cheng & Zhao, Xiangmo & Zhang, Lei & Li, Xiaoling & Cui, Xin, 2022. "Measuring network interdependency between dependent networks: A supply-demand-based approach," Reliability Engineering and System Safety, Elsevier, vol. 225(C).
    14. Sina Mohri, Seyed & Ghaderi, Hadi & Van Woensel, Tom & Mohammadi, Mehrdad & Nassir, Neema & Thompson, Russell G., 2024. "Contextualizing alternative delivery points in last mile delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 192(C).
    15. Martin Durbin & Karla Hoffman, 2008. "OR PRACTICE---The Dance of the Thirty-Ton Trucks: Dispatching and Scheduling in a Dynamic Environment," Operations Research, INFORMS, vol. 56(1), pages 3-19, February.
    16. Lorenzo Castelli & Paola Pellegrini & Raffaele Pesenti, 2012. "Airport slot allocation in Europe: economic efficiency and fairness," International Journal of Revenue Management, Inderscience Enterprises Ltd, vol. 6(1/2), pages 28-44.
    17. Mühlhofer, Evelyn & Koks, Elco E. & Kropf, Chahan M. & Sansavini, Giovanni & Bresch, David N., 2023. "A generalized natural hazard risk modelling framework for infrastructure failure cascades," Reliability Engineering and System Safety, Elsevier, vol. 234(C).
    18. João Barreiro & Ruth Lopes & Filipa Ferreira & Rita Brito & Maria João Telhado & José Saldanha Matos & Rafaela Saldanha Matos, 2020. "Assessing Urban Resilience in Complex and Dynamic Systems: The RESCCUE Project Approach in Lisbon Research Site," Sustainability, MDPI, vol. 12(21), pages 1-15, October.
    19. Shen, Yi & Yang, Huang & Ren, Gang & Ran, Bin, 2024. "Model cascading overload failure and dynamic vulnerability analysis of facility network of metro station," Reliability Engineering and System Safety, Elsevier, vol. 242(C).
    20. Transchel, Sandra, 2017. "Inventory management under price-based and stockout-based substitution," European Journal of Operational Research, Elsevier, vol. 262(3), pages 996-1008.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004502. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.