欢迎访问中国科学院大学学报,今天是

中国科学院大学学报 ›› 2026, Vol. 43 ›› Issue (5): 590-602.DOI: 10.7523/j.ucas.2024.064

• 数学与物理学 • 上一篇    下一篇

面向航空公司机组配对问题的改进多目标进化算法

李聪, 姜志鹏(), 杨文国   

  1. 中国科学院大学数学科学学院,北京 100049
  • 收稿日期:2024-01-24 修回日期:2024-06-12 发布日期:2024-06-24
  • 通讯作者: 姜志鹏

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

Cong LI, Zhipeng JIANG(), Wenguo YANG   

  1. 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: Zhipeng JIANG
  • Supported by:
    National Natural Science Foundation of China(12071459)

摘要:

具有多个目标的航空公司机组配对问题目的是寻找一个可行的任务环子集,使其覆盖所有航班,同时每个目标函数最小化。针对该问题,构建2种不同的数学模型,一种是包含逻辑关系的模型,另一种是整数规划模型。为求解这一目标问题,提出一种改进的多目标进化算法,该算法基于非支配排序遗传算法框架,通过计算每个解对应的目标向量和自适应评估向量之间的距离区分种群个体。算法主要利用自适应评估向量和帕累托方向引导搜索,以获得帕累托解。为进一步提升解的质量和可行性,还引入修复策略和局部优化策略。实验结果表明,所提出的多目标进化算法性能上优于传统的非支配排序遗传算法Ⅱ及另一种多目标遗传算法。

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

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

中图分类号: