An improved multi-objective evolutionary algorithm for the multi-objective airline crew pairing problem*

doi:10.7523/j.ucas.2024.064

Abstract

Abstract: The multi-objective airline crew pairing problem finds a subset of feasible pairings so that all flights are covered and each objective function is minimum. For the problem, we propose two mathematical models: a novel mathematical model that contains logical relationships and an integer programming model that is based on all feasible pairings enumerated by a depth-first search method. To solve the problem, we propose an improved multi-objective evolutionary algorithm, where this algorithm is a nondominated sorting genetic algorithm with the distance between the objective vector corresponding to each solution and an adaptive evaluation vector. The proposed algorithm uses the direction of the adaptive evaluation vector and the Pareto orientation for guidance to derive Pareto-optimal solutions. We also uses a repairing strategy and a local optimization strategy for deriving feasible and better solutions. For this problem, in our experimental results, the performance of the proposed algorithm is superior to that of the conventional nondominated sorting genetic algorithm II and another multi-objective genetic algorithm, respectively.

Key words: Airline Crew Pairing, Multi-objective Optimization, Pareto-optimal Solutions

CLC Number:

O221.4

LI Cong, JIANG Zhipeng, YANG Wenguo. An improved multi-objective evolutionary algorithm for the multi-objective airline crew pairing problem^*[J]. Journal of University of Chinese Academy of Sciences, DOI: 10.7523/j.ucas.2024.064.

References

[1] Wen X, Sun X T, Sun Y G, et al.Airline crew scheduling: Models and algorithms[J]. Transportation Research Part E: Logistics and Transportation Review, 2021, 149: 102304. DOI: 10.1016/j.tre.2021.102304.
[2] Aydemir-Karadag A, Dengiz B, Bolat A.Crew pairing optimization based on hybrid approaches[J]. Computers & Industrial Engineering, 2013, 65(1): 87-96. DOI: 10.1016/j.cie.2011.12.005.
[3] Crawford B, Castro C, Monfroy E.A hybrid ant algorithm for the airline crew pairing problem[M]//Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006: 381-391. DOI:10.1007/11925231_36.
[4] Zeren B, Özkol İ.An improved genetic algorithm for crew pairing optimization[J]. Journal of Intelligent Learning Systems and Applications, 2012, 4(1): 70-80. DOI: 10.4236/jilsa.2012.41007.
[5] Çetin Demirel N, Deveci M.Novel search space updating heuristics-based genetic algorithm for optimizing medium-scale airline crew pairing problems[J]. International Journal of Computational Intelligence Systems, 2017, 10(1): 1082-1101. DOI: 10.2991/ijcis.2017.10.1.72.
[6] Deveci M, Çetin Demirel N.Evolutionary algorithms for solving the airline crew pairing problem[J]. Computers & Industrial Engineering, 2018, 115: 389-406. DOI:10.1016/j.cie.2017.11.022.
[7] Srinivas N, Deb K.Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2(3): 221-248. DOI:10.1162/evco.1994.2.3.221.
[8] Chen C H, Chou F I, Chou J H.Multiobjective evolutionary scheduling and rescheduling of integrated aircraft routing and crew pairing problems[J]. IEEE Access, 2020, 8: 35018-35030. DOI: 10.1109/ACCESS.2020.2974245.
[9] Schaffer J D.Some experiments in machine learning using vector evaluated genetic algorithms[D]. Nashville, USA: Vanderbilt University, 1985.
[10] Horn J, Nafpliotis N, Goldberg D E.A niched Pareto genetic algorithm for multiobjective optimization[C]//Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence. Orlando, FL, USA. IEEE, 1994: 82-87. DOI: 10.1109/ICEC.1994.350037.
[11] Deb K, Pratap A, Agarwal S, et al.A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI: 10.1109/4235.996017.
[12] Fonseca C M, Fleming P J.Genetic algorithms for multiobjective optimization: FormulationDiscussion and generalization[C]//Proceedings of the 5th International Conference on Genetic Algorithms. ACM, 1993: 416-423. DOI:10.5555/645513.657757.
[13] Zitzler E, Thiele L.Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257-271. DOI:10.1109/4235.797969.
[14] Li H, Zhang Q F.Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 284-302. DOI: 10.1109/TEVC.2008.925798.
[15] Deb K, Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. DOI: 10.1109/TEVC.2013.2281535.
[16] Zhang X Y, Tian Y, Cheng R, et al.A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 97-112. DOI: 10.1109/TEVC.2016.2600642.
[17] Chen C H, Liu T K, Chou J H.Integrated short-haul airline crew scheduling using multiobjective optimization genetic algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 43(5): 1077-1090. DOI:10.1109/TSMC.2012.2234943.
[18] Chou T Y, Liu T K, Lee C N, et al.Method of inequality-based multiobjective genetic algorithm for domestic daily aircraft routing[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38(2): 299-308. DOI: 10.1109/TSMCA.2007.914784.
[19] Haouari M, Mansour F Z, Sherali H D.A new compact formulation for the daily crew pairing problem[J]. Transportation science, 2019, 53(3): 811-828. DOI: 10.1287/trsc.2018.0860.
[20] Du Xiangbing.Research on Integrated Optimization of Airline Crew Scheduling[D]. Beijing: Beijing Jiaotong University, 2020.
[21] Liu T K, Chen C H, Chou J H.Optimization of short-haul aircraft schedule recovery problems using a hybrid multiobjective genetic algorithm[J]. Expert Systems with Applications, 2010, 37(3): 2307-2315. DOI: 10.1016/j.eswa.2009.07.068.
[22] Park T, Ryu K R.Crew pairing optimization by a genetic algorithm with unexpressed genes[J]. Journal of Intelligent Manufacturing, 2006, 17(4): 375-383. DOI: 10.1007/s10845-005-0011-z.
[23] Beasley J E, Chu P C.A genetic algorithm for the set covering problem[J]. European Journal of Operational Research, 1996, 94(2): 392-404. DOI: 10.1016/0377-2217(95)00159-X.

An improved multi-objective evolutionary algorithm for the multi-objective airline crew pairing problem^*

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments