TY - JOUR
T1 - Routing and Scheduling in Multigraphs with Time Constraints -A Memetic Approach for Airport Ground Movement
AU - Beke, Lilla
AU - Uribe, Lourdes
AU - Lara, Adriana
AU - Coello, Carlos A.Coello
AU - Weiszer, Michal
AU - Burke, Edmund K.
AU - Chen, Jun
N1 - Publisher Copyright:
IEEE
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Aircraft
KW - Airport ground movement
KW - Airports
KW - Costs
KW - Memetic algorithm
KW - Metaheuristics
KW - Multigraphs
KW - Multiobjective routing and scheduling
KW - Routing
KW - Shortest path problem
KW - Time factors
KW - Time windows
UR - http://www.scopus.com/inward/record.url?scp=85153397909&partnerID=8YFLogxK
U2 - 10.1109/TEVC.2023.3262743
DO - 10.1109/TEVC.2023.3262743
M3 - Artículo
AN - SCOPUS:85153397909
SN - 1089-778X
SP - 1
JO - IEEE Transactions on Evolutionary Computation
JF - IEEE Transactions on Evolutionary Computation
ER -