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. 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.
    2. 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).
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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).
    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. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Michael E. Fragkos & Vasileios Zeimpekis & Vasilis Koutras & Ioannis Minis, 2022. "Supply planning for shelters and emergency management crews," Operational Research, Springer, vol. 22(1), pages 741-777, March.
    11. Luo, Ying & Schonfeld, Paul, 2007. "A rejected-reinsertion heuristic for the static Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 41(7), pages 736-755, August.
    12. Adria Soriano & Margaretha Gansterer & Richard F. Hartl, 2018. "The two-region multi-depot pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1077-1108, October.
    13. Schaumann, Sarah K. & Bergmann, Felix M. & Wagner, Stephan M. & Winkenbach, Matthias, 2023. "Route efficiency implications of time windows and vehicle capacities in first- and last-mile logistics," European Journal of Operational Research, Elsevier, vol. 311(1), pages 88-111.
    14. Mikkel Sigurd & David Pisinger & Michael Sig, 2004. "Scheduling Transportation of Live Animals to Avoid the Spread of Diseases," Transportation Science, INFORMS, vol. 38(2), pages 197-209, May.
    15. Biao Yuan & Ran Liu & Zhibin Jiang, 2015. "A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements," International Journal of Production Research, Taylor & Francis Journals, vol. 53(24), pages 7450-7464, December.
    16. Z. Al Chami & H. Manier & M.-A. Manier, 2019. "A lexicographic approach for the bi-objective selective pickup and delivery problem with time windows and paired demands," Annals of Operations Research, Springer, vol. 273(1), pages 237-255, February.
    17. Vincent F. Yu & Hadi Susanto & Yu-Hsuan Yeh & Shih-Wei Lin & Yu-Tsung Huang, 2022. "The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers," Mathematics, MDPI, vol. 10(6), pages 1-22, March.
    18. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Chris T., 2013. "Designing vehicle routes for a mix of different request types, under time windows and loading constraints," European Journal of Operational Research, Elsevier, vol. 229(2), pages 303-317.
    19. Diana, Marco & Dessouky, Maged M. & Xia, Nan, 2006. "A model for the fleet sizing of demand responsive transportation services with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 40(8), pages 651-666, September.
    20. Bohan Hu & Feng-Jang Hwang, 2026. "Supermarket-chain grocery delivery optimization through courier coordination," Annals of Operations Research, Springer, vol. 359(3), pages 2829-2868, 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.