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

doi:10.7523/j.ucas.2024.064

Abstract

Abstract:

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.

Key words: airline crew pairing, multi-objective optimization, Pareto solutions

CLC Number:

O221.4

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.

Figures/Tables 10

Fig.1 An example of graph structure for crew pairing problem

Fig.2 Examples of fitness assignment for NSGA-AEV and crowded distance for NSGA-Ⅱ

Fig.3 An example of binary coding

Fig.4 Flowchart of NSGA-AEV

Fig.5 Number of non-feasible solutions derived by NSGA-AEV with or without repairing strategy

Fig.6 Minimum sum of all objective function values of NSGA-AEV with or without local optimization strategy

Fig.7 Number of iterations reaching convergence of NSGA-AEV with or without local optimization strategy （in 10 runs）

Table 1 Number of iterations reaching convergence and runtime of NSGA-AEV， NSGA-Ⅱ， and MMGA， respectively， in 20 runs

run number	NSGA-AEV		NSGA-Ⅱ		MMGA
run number	NIRC	CPU/s	NIRC	CPU/s	NIRC	CPU/s
average		1 328.8		1 289.1		1 276.3
1	923	1 349.1	923	1 294.4	672	1 275.9
2	633	1 331.3	800	1 294.0	701	1 283.7
3	494	1 335.3	651	1 272.8	931	1 280.4
4	551	1 330.4	396	1 292.8	867	1 266.5
5	604	1 331.3	915	1 278.0	813	1 268.8
6	861	1 335.4	318	1 307.2	814	1 281.1
7	726	1 300.7	995	1 279.4	910	1 282.8
8	670	1 331.7	720	1 292.0	888	1 257.8
9	553	1 346.4	527	1 315.2	831	1 283.5
10	493	1 335.3	632	1 294.6	793	1 278.1
11	471	1 323.7	518	1 282.8	830	1 274.3
12	352	1 346.2	434	1 309.3	692	1 277.9
13	769	1 328.3	632	1 268.9	534	1 280.7
14	566	1 295.0	837	1 274.1	690	1 277.3
15	562	1 335.5	444	1 286.8	892	1 272.2
16	925	1 349.7	623	1 291.6	666	1 285.1
17	735	1 322.0	712	1 271.5	976	1 267.3
18 19	586 458	1 307.3 1 337.1	671 544	1 280.5 1 314.8	868 814	1 273.1 1 273.8
20	685	1 305.3	794	1 282.1	696	1 285.6

Table 2 Results of performance measure by C(X',X″) approach for NSGA-AEV and NSGA-Ⅱ

run number	$C (X', X ″)$	$C (X ″, X')$	$C (X', X ″) > C (X ″, X')$	$C (X ″, X') > C (X', X ″)$
total better runs			11	3
1	1	1
2	1	0	True
3	1	1
4	1	0	True
5	1	0	True
6	1	0	True
7	1	0	True
8	1	1
9	1	0	True
10	0	1		True
11	0	1		True
12	1	1
13	0	1		True
14	1	1
15	1	0	True
16	0	0
17	1	0	True
18	1	0	True
19	1	0	True
20	1	0	True

Table 2 Results of performance measure by C(X',X″) approach for NSGA-AEV and NSGA-Ⅱ

run number	$C (X', X ″)$	$C (X ″, X')$	$C (X', X ″) > C (X ″, X')$	$C (X ″, X') > C (X', X ″)$
total better runs			11	3
1	1	1
2	1	0	True
3	1	1
4	1	0	True
5	1	0	True
6	1	0	True
7	1	0	True
8	1	1
9	1	0	True
10	0	1		True
11	0	1		True
12	1	1
13	0	1		True
14	1	1
15	1	0	True
16	0	0
17	1	0	True
18	1	0	True
19	1	0	True
20	1	0	True

Table 3 Results of performance measure by C(X',X″) approach for NSGA-AEV and MMGA

run number	$C (X', X ″)$	$C (X ″, X')$	$C (X', X ″) > C (X ″, X')$	$C (X ″, X') > C (X', X ″)$
total better runs			13	5
1	0	1		True
2	1	0	True
3	1	0	True
4	1	0	True
5	1	1
6	1	0	True
7	1	0	True
8	0	0
9	1	0	True
10	0	1		True
11	1	0	True
12	1	0	True
13	0	1		True
14	1	0	True
15	1	0	True
16	0	1		True
17	1	0	True
18	1	0	True
19	0	1		True
20	1	0	True

Table 3 Results of performance measure by C(X',X″) approach for NSGA-AEV and MMGA

run number	$C (X', X ″)$	$C (X ″, X')$	$C (X', X ″) > C (X ″, X')$	$C (X ″, X') > C (X', X ″)$
total better runs			13	5
1	0	1		True
2	1	0	True
3	1	0	True
4	1	0	True
5	1	1
6	1	0	True
7	1	0	True
8	0	0
9	1	0	True
10	0	1		True
11	1	0	True
12	1	0	True
13	0	1		True
14	1	0	True
15	1	0	True
16	0	1		True
17	1	0	True
18	1	0	True
19	0	1		True
20	1	0	True

References 23

[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 .