IDEAS home Printed from https://ideas.repec.org/a/eee/jaitra/v129y2025ics0969699725001188.html

Multi-agent task allocation and path planning for autonomous ground support equipment

Author

Listed:
  • van der Zwan, Manouk
  • ErmiÅŸ, Gülçin
  • Sharpanskykh, Alexei

Abstract

We aim to contribute to the automation of ground handling tasks using autonomous ground support equipment (GSE) at airports. Automation of airside operations has recently become critical for the airports to achieve higher levels of safety and efficiency under growing traffic demand and requires solving a complex scheduling and path planning problem. To address this problem, we present a multi-agent task allocation and path planning model for handling airside operations on the apron. In the problem, the ground handling tasks are to be allocated to the equipment, the trips of vehicles should be scheduled within specific time windows considering the flight schedules, and the collisions of vehicles on the apron and service roads should be avoided. We present a centralized multi-agent task allocation and routing model which aims to optimize the allocation and routing of various types of ground handling tasks over a heterogeneous set of GSE vehicles. We convert the allocation and routing problem into vehicle routing problem with time windows, pick-ups, deliveries and solve the problem using a warm start mixed integer linear programming (MILP) model. We also introduce a nonlinear objective function which converts the MILP model into a mixed integer nonlinear programming (MINLP) model, to minimize the time service locations at the stands are occupied. Then, we solve the corresponding path finding problem to find collision free paths for the GSE, by the multi-agent path finding model. The proposed model outperforms the decentralized approach in previous research regarding the allocation rate of assigning tasks to vehicles and the performance indicators of finding conflict free paths, and in CPU time. The mean deviations from shortest paths were considerably small in path planning which means that the solution quality was high. Furthermore, the CPU time of allocating tasks has been reduced by 48% compared to the CPU time of decentralized allocation.

Suggested Citation

  • van der Zwan, Manouk & ErmiÅŸ, Gülçin & Sharpanskykh, Alexei, 2025. "Multi-agent task allocation and path planning for autonomous ground support equipment," Journal of Air Transport Management, Elsevier, vol. 129(C).
    • Handle: RePEc:eee:jaitra:v:129:y:2025:i:c:s0969699725001188
    DOI: 10.1016/j.jairtraman.2025.102855
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0969699725001188
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jairtraman.2025.102855?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Silvia Padrón & Daniel Guimarans, 2019. "An Improved Method for Scheduling Aircraft Ground Handling Operations From a Global Perspective," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-25, August.
    2. A Norin & D Yuan & T A Granberg & P V&aauml;rbrand, 2012. "Scheduling de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(8), pages 1116-1125, August.
    3. Alonso Tabares, Diego & Mora-Camino, Felix & Drouin, Antoine, 2021. "A multi-time scale management structure for airport ground handling automation," Journal of Air Transport Management, Elsevier, vol. 90(C).
    4. Liu, Ran & Xie, Xiaolan & Augusto, Vincent & Rodriguez, Carlos, 2013. "Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care," European Journal of Operational Research, Elsevier, vol. 230(3), pages 475-486.
    5. Bao, Dan-Wen & Zhou, Jia-Yi & Zhang, Zi-Qian & Chen, Zhuo & Kang, Di, 2023. "Mixed fleet scheduling method for airport ground service vehicles under the trend of electrification," Journal of Air Transport Management, Elsevier, vol. 108(C).
    6. Harold W. Kuhn, 2010. "The Hungarian Method for the Assignment Problem," Springer Books, in: Michael Jünger & Thomas M. Liebling & Denis Naddef & George L. Nemhauser & William R. Pulleyblank & (ed.), 50 Years of Integer Programming 1958-2008, chapter 0, pages 29-47, Springer.
    7. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    8. M. W. P. Savelsbergh & M. Sol, 1995. "The General Pickup and Delivery Problem," Transportation Science, INFORMS, vol. 29(1), pages 17-29, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yi He & Kenneth Kelly & Matthew Jeffers & Roberto Vercellino & Yanbo Ge & Monte Lunacek, 2026. "Energy, power, and infrastructure demands from electrifying airport ground support equipment at United States airports," Nature Communications, Nature, vol. 17(1), pages 1-14, December.

    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. Zhou, Peng & Shen, Yu & Zheng, Yujing & Zheng, Yuefeng & Guo, Binfeng & Du, Yuchuan, 2025. "A comprehensive review of ground support equipment scheduling for aircraft ground handling services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 203(C).
    2. Bao, Danwen & Chen, Zhuo & Kang, Di & Zhou, Jiayi, 2026. "Real-time disruption recovery method for apron vehicles based on stability," Journal of Air Transport Management, Elsevier, vol. 131(C).
    3. Lu, Quan & Dessouky, Maged M., 2006. "A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 175(2), pages 672-687, December.
    4. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    5. Zhang, Huili & An, Xuan & Chen, Cong & Wang, Nengmin & Tong, Weitian, 2025. "Data-driven robust two-stage ferry vehicle management at airports," Omega, Elsevier, vol. 133(C).
    6. Du, Yuchen & Yang, Hai & Chow, Joseph Y.J. & Le, Tho V., 2025. "Two-stage stochastic fleet and battery sizing with routing optimization for sidewalk delivery robots," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 201(C).
    7. Shaza Hanif & Shahab Ud Din & Ning Gui & Tom Holvoet, 2023. "Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem," Mathematics, MDPI, vol. 11(19), pages 1-25, September.
    8. Diana, Marco & Dessouky, Maged M., 2004. "A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 539-557, July.
    9. Xue Han & Peixin Zhao & Qingchun Meng & Shengnan Yin & Di Wan, 2020. "Optimal scheduling of airport ferry vehicles based on capacity network," Annals of Operations Research, Springer, vol. 295(1), pages 163-182, December.
    10. Fagui Liu & Lvshengbiao Wang & Mengke Gui & Yang Zhang & Yulin Lan & Chengqi Lai & Boyuan Zhu, 2023. "A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window," Journal of Heuristics, Springer, vol. 29(2), pages 269-311, June.
    11. Silvia Padrón & Daniel Guimarans, 2019. "An Improved Method for Scheduling Aircraft Ground Handling Operations From a Global Perspective," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(04), pages 1-25, August.
    12. Vis, Iris F.A., 2006. "Survey of research in the design and control of automated guided vehicle systems," European Journal of Operational Research, Elsevier, vol. 170(3), pages 677-709, May.
    13. Fu, Liping, 2002. "Scheduling dial-a-ride paratransit under time-varying, stochastic congestion," Transportation Research Part B: Methodological, Elsevier, vol. 36(6), pages 485-506, July.
    14. Han, Xue & Zhao, Peixin & Kong, Dexin, 2023. "Two-stage optimization of airport ferry service delay considering flight uncertainty," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1103-1116.
    15. Yi Zhang & Guowei Hua & T. C. E. Cheng & Juliang Zhang, 2020. "Cold chain distribution: How to deal with node and arc time windows?," Annals of Operations Research, Springer, vol. 291(1), pages 1127-1151, August.
    16. Mohamed Cissé & Semih Yalçindag & Yannick Kergosien & Evren Sahin & Christophe Lenté & Andrea Matta, 2017. "OR problems related to Home Health Care: A review of relevant routing and scheduling problems," Post-Print hal-01736714, HAL.
    17. Munjeong Kang & Chungmok Lee, 2021. "An Exact Algorithm for Heterogeneous Drone-Truck Routing Problem," Transportation Science, INFORMS, vol. 55(5), pages 1088-1112, September.
    18. Shi, Yong & Boudouh, Toufik & Grunder, Olivier, 2019. "A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 52-95.
    19. Mohsen Emadikhiav & David Bergman & Robert Day, 2020. "Consistent Routing and Scheduling with Simultaneous Pickups and Deliveries," Production and Operations Management, Production and Operations Management Society, vol. 29(8), pages 1937-1955, August.
    20. Margarita P. Castro & Andre A. Cire & J. Christopher Beck, 2020. "An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 263-278, April.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:jaitra:v:129:y:2025:i:c:s0969699725001188. 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.journals.elsevier.com/journal-of-air-transport-management/ .

    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.