Routing and Scheduling in Multigraphs with Time Constraints -A Memetic Approach for Airport Ground Movement

Lilla Beke, Lourdes Uribe, Adriana Lara, Carlos A. Coello Coello, Michal Weiszer, Edmund K. Burke and Jun Chen 2023. Routing and Scheduling in Multigraphs with Time Constraints -A Memetic Approach for Airport Ground Movement. IEEE Transactions on Evolutionary Computation. Advanced online publication. https://doi.org/10.1109/tevc.2023.3262743

TitleRouting and Scheduling in Multigraphs with Time Constraints -A Memetic Approach for Airport Ground Movement
TypeJournal article
AuthorsLilla Beke, Lourdes Uribe, Adriana Lara, Carlos A. Coello Coello, Michal Weiszer, Edmund K. Burke and Jun Chen
Abstract

Routing and scheduling problems with increasingly realistic modelling approaches often entail the consideration of multiple objectives, time constraints, and modelling the system as a multigraph. This detailed modelling approach has increased computational complexity and may also lead to violation of the additivity property of the costs. In the worst scenario, increased complexity makes the problem intractable for exact algorithms. Even when the problem is solvable, exact algorithms may not provide solutions within the given time budget, and the found solutions are not guaranteed to be optimal due to the additivity property violation. Approximate solution methods become more suitable in this case. This paper focuses on one particular real-world application, the Airport Ground Movement Problem, where both time constraints and parallel arcs are involved. We introduce a novel Memetic Algorithm for Routing in Multigraphs with Time constraints (MARMT) and present a comprehensive study of its different variants based on diverse genetic representation methods. We propose a local search operator that enhances search efficiency and effectiveness. MARMT is tested on real data based on two airports of different sizes. Our results show that MARMT does not suffer from the non-additivity property problem as it outperforms the state-of-the-art exact algorithm when allowed to converge. When a time budget of 10 seconds is imposed on MARMT, it is able to provide solutions with quality comparable (within 1-5% degradation) to the ones given by the exact algorithm with respect to the aggregated objective values. MARMT can be adapted for other applications, such as train operations.

JournalIEEE Transactions on Evolutionary Computation
ISSN1941-0026
1089-778X
Year2023
PublisherIEEE
Digital Object Identifier (DOI)https://doi.org/10.1109/tevc.2023.3262743
Web address (URL)https://doi.org/10.1109/TEVC.2023.3262743
Publication dates
Published online10 Apr 2023

Related outputs

Extracting Multi-objective Multigraph Features for the Shortest Path Cost Prediction: Statistics-based or Learning-based?
Songwei Liu, Xinwei Wang, Michal Weiszer and Jun Chen 2024. Extracting Multi-objective Multigraph Features for the Shortest Path Cost Prediction: Statistics-based or Learning-based? Green Energy and Intelligent Transportation. 3 (1) 100129. https://doi.org/10.1016/j.geits.2023.100129

Mercury - An open-source platform for the evaluation of air transport mobility - presentation
Delgado, L., Gurtner, G., Weiszer, M., Bolic, T. and Cook, A.J. 2023. Mercury - An open-source platform for the evaluation of air transport mobility - presentation. 13th SESAR Innovation Days. Seville, Spain 27 - 30 Nov 2023 SESAR.

Mercury - An open pax & flight simulator
Delgado, L., Gurtner, G., Weiszer, M. and Bolic, T. 2023. Mercury - An open pax & flight simulator. 13th SESAR Innovation Days. Seville, Spain 27 - 30 Nov 2023 SESAR.

Mercury: an open source platform for the evaluation of air transport mobility
Delgado, L., Gurtner, G., Weiszer, M., Bolic, T. and Cook, A.J. 2023. Mercury: an open source platform for the evaluation of air transport mobility. 13th SESAR Innovation Days. Seville, Spain 27 - 30 Nov 2023 SESAR. https://doi.org/10.61009/SID.2023.1.36

A chance-constrained programming model for airport ground movement optimisation with taxi time uncertainties
Xinwei Wang, Alexander E.I. Brownlee, Michal Weiszer, John R. Woodward, Mahdi Mahfouf and Jun Chen 2021. A chance-constrained programming model for airport ground movement optimisation with taxi time uncertainties. Transportation Research Part C: Emerging Technologies. 132 103382. https://doi.org/10.1016/j.trc.2021.103382

Multi-objective routing and scheduling for airport ground movement
Michal Weiszer, Edmund K. Burke and Jun Chen 2020. Multi-objective routing and scheduling for airport ground movement. Transportation Research Part C: Emerging Technologies. 119 102734. https://doi.org/10.1016/j.trc.2020.102734

An online speed profile generation approach for efficient airport ground movement
Tianci Zhang, Meng Ding, Hongfu Zuo, Jun Chen, Michal Weiszer, Xiaoyan Qian and Edmund K. Burke 2018. An online speed profile generation approach for efficient airport ground movement. Transportation Research Part C: Emerging Technologies. 93, pp. 256-272. https://doi.org/10.1016/j.trc.2018.05.030

Preference-based evolutionary algorithm for airport surface operations
Michal Weiszer, Jun Chen, Paul Stewart and Xuejun Zhang 2018. Preference-based evolutionary algorithm for airport surface operations. Transportation Research Part C: Emerging Technologies. 91, pp. 296-316. https://doi.org/10.1016/j.trc.2018.04.008

Permalink - https://westminsterresearch.westminster.ac.uk/item/w415x/routing-and-scheduling-in-multigraphs-with-time-constraints-a-memetic-approach-for-airport-ground-movement


Share this

Usage statistics

45 total views
0 total downloads
These values cover views and downloads from WestminsterResearch and are for the period from September 2nd 2018, when this repository was created.