Journal of University of Chinese Academy of Sciences >
An improved multi-objective evolutionary algorithm for airline crew pairing problem
Received date: 2024-01-24
Revised date: 2024-06-12
Online published: 2024-06-24
Supported by
National Natural Science Foundation of China(12071459)
The multi-objective airline crew pairing problem tries to find a subset of feasible pairings such that all flights are covered and each objective function is minimized. For this problem， we propose two mathematical models： a novel mathematical model that contains logical relationships， and an integer programming model based on all feasible pairings enumerated by a depth-first search method. To solve the problem， we propose an improved multi-objective evolutionary algorithm， which is a non-dominated sorting genetic algorithm that distinguishes individuals using 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 solutions. We also use 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 those of the traditional nondominated sorting genetic algorithm Ⅱ and another multi-objective genetic algorithm.
Cong LI , Zhipeng JIANG , Wenguo YANG . An improved multi-objective evolutionary algorithm for airline crew pairing problem[J]. Journal of University of Chinese Academy of Sciences, 2026 , 43(5) : 590 -602 . DOI: 10.7523/j.ucas.2024.064
| [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. Multiobjective 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： formulation discussion 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-Ⅱ［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 Ⅰ： 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 X B. 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 . |
/
| 〈 |
|
〉 |