链接：https://pan.baidu.com/s/1zE0pxUR91vGAMReJhWXXow?pwd=4gv0
提取码：4gv0

机组排班是在遵守管理当局的机组适航条例和保证航班计划飞行任务的正常完成的
条件下， 通过科学合理地排班， 降低机组人力资源成本。 本文考虑到机组排班的合理性、
公平性和有效性， 构造了航班连接网络并根据网络建立了基于点边的多目标优化模型。 该
模型能显示表达赛题给出的航班衔接和飞行员工作限制等约束。 对于大规模的问题， 本文
基于机组排班的特点和所建立的数学模型的结构设计了加速求解的策略， 极大地降低了计
算时间。
问题一中考虑了常规的时空衔接约束和首尾基地约束。 为了简化航班连接约束， 本文
依据航班信息构造了航班对集合并基于航班连接网络建立了网络流模型。 模型中考虑到了
航班配置数、 乘机次数和替补资格使用数等指标， 同时需要满足时空衔接和基地约束。 在
模型求解的预处理上， 本文通过分析模型的结构去掉了冗余约束， 极大地降低了问题的规
模。 在求解方法上， 本文采用标量化的方法以处理该多目标问题， 获取 Pareto-最优解。 计
算实验表明， 数据集 A 能在 0.7 分钟内得到满足所有航班配置要求的排班方案， 此时乘机
人次为 8， 无人使用替补资格； 针对数据集 B， 采用分段策略处理， 每段长度三到四天，
结果表明不满足配置航班数为 35。
问题二考虑了机组排班中执勤相关的成本、 公平性和时间约束。 为处理累计执勤和飞
行用时的容量约束， 本文建立了非线性整数规划模型。 在模型的预处理阶段， 本文借助线
性化技术将二次变量代换为一次变量， 同时引进与被替换变量关联的线性约束以得到与原
模型等价的混合整数线性规划模型。 在模型的求解阶段， 基于数据集中航班普遍为中短航
程的特点， 本文采用“暂不考虑、 求解、 检验” 的策略， 结合调整权重处理飞行时间约束，
显著地节省了计算用时。 数值实验表明， 数据集 A 在 9 分钟内得到 Pareto-最优解， 其中不
满足配置航班数为 0， 总体乘机人次为 22， 替补资格使用次数为 23； 对于数据集 B， 不满
足配置航班数为 76。 针对数据集 A， 我们还给出了权重比例的灵敏度分析。
问题三考虑了与任务环相关的成本、 公平性和时间限制。 在模型上， 沿用线性化技术
处理建立的非线性模型。 在模型的求解阶段， 进一步使用“暂不考虑、 求解、 检验” 的策
略处理违反概率小的约束。 数值实验表明， 数据集 A 可以在 16 分钟得到 Pareto-最优解，
其中不满足配置航班数为 4， 总体乘机人次为 1， 替补资格使用次数为 15； 数据集 B 中不
满足配置的航班数为 152 个。
总体而言， 我们的模型可以有效地处理机组排班问题， 对于小规模数据能够给出满意
的解； 对于较大规模数据， 能够在较短的时间内给出一个可以接受的解。

关键词： 机组排班； 多目标规划； Pareto-最优； 混合整数线性规划； 线性化技术（RLT）