基于一种改进的多目标进化算法求解多目标航空公司机组配对问题

doi:10.7523/j.ucas.2024.064

中国科学院大学学报

基于一种改进的多目标进化算法求解多目标航空公司机组配对问题

李聪, 姜志鹏, 杨文国

中国科学院大学数学科学学院,北京,100049

收稿日期:2024-01-24 修回日期:2024-06-12 发布日期:2024-06-24

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

LI Cong, JIANG Zhipeng, YANG Wenguo

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, 100049, China

Received:2024-01-24 Revised:2024-06-12 Published:2024-06-24
Contact: ^†E-mail: jiangzhipeng@ucas.ac.cn
Supported by:
^*Supported by National Natural Science Foundation of China (12071459)

摘要/Abstract

摘要： 具有多个目标的航空公司机组配对问题目的是寻找一个可行的任务环子集,使得寻找到的可行任务环子集覆盖所有航班,并且使得每个目标函数最小化。对于该问题,本文提出了两个不同的数学模型,其中一个是包含逻辑关系的模型,另一个是整数规划模型。为了解决该多目标问题,本文提出了一种改进的多目标进化算法,该算法是一种非支配排序遗传算法,它使用每个解对应的目标向量和自适应评估向量之间的距离区分种群个体。本文提出的这个算法主要使用自适应评估向量和帕累托方向作为搜索方向,以获得帕累托最优解。为了得到更好可行的帕累托解,本文还使用一种修复策略和一种局部优化策略。最后,在实验结果中,本文指出提出的改进的多目标进化算法优于传统的非支配排序遗传算法II和另一种多目标遗传算法。

关键词: 航空公司机组配对, 多目标优化, 帕累托最优解

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

中图分类号:

O221.4

李聪, 姜志鹏, 杨文国. 基于一种改进的多目标进化算法求解多目标航空公司机组配对问题[J]. 中国科学院大学学报, DOI: 10.7523/j.ucas.2024.064.

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.

参考文献

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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们

基于一种改进的多目标进化算法求解多目标航空公司机组配对问题

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价

访问统计

联系我们

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