孙成豪+王婉贞+周润

摘 要：航班计划是一个实时优化问题。诸多不确定因素会造成正常航班的扰动，包括航空器故障，恶劣天气，交通管制等。本文的目的是通过构建数学模型来得出不正常航班飞机恢复的优化方案。本文将航班的延误时间处理为随机变量，总延误时间作为优化目标，在可用的资源和航空公司估计成本的机会约束条件下，构建了一个随机机会约束规划模型。

关键词：航空公司运营；不正常航班；飞机恢复；机会约束规划；遗传算法

DOI：10.16640/j.cnki.37-1222/t.2017.12.238

0 引言

由于航空业的特点和竞争的需要，航空公司的航班运行控制对运筹学的许多分支理论和方法，特别是最优化技术有着非常迫切的需求。

在国外，文献[1]中，Yu提出了针对航空公司不正常航班调度问题的扰动管理策略，就航空公司常规和非常规航班调度问题进行了建模优化。文献[2]找到快速有效的算法和软件处理航班调度问题。Teodorobic ，Stojkovicd等人[3]为了使取消航班数量和旅客总延误时间最小，提出了一种基于Lexicographic动态规划模型。在我国，赵秀丽[4]把航班延误时间看作为常量，分别对不正常航班的取消航班问题、飞机路线恢复问题、机组恢复问题、一体化航班计划恢复问题进行了研究。文献[5]中就机组延误问题，建立了基于概率的鲁棒性机组配对问题和飞机排班问题的随机模型。本文针对不正常航班下的飞机恢复问题研究建立相应的优化模型及算法。后续内容安排如下：第2章是预备知识；第3章是问题描述和基本建模方法；模型及算法在第4章；全文的总结和展望放在了第5章。

1 随机机会约束规划

定义2.1[6]假设x是一个决策向量，ξ是一个随机向量，是目标函数，（j=1，2，…，p）是没有给出确定的可行集的随机约束函数。机会约束可以表示为如下的形式：

2 问题描述与基本方法

当恶劣天气或机械故障引起航班延误时，由于恶劣天气持续时间和故障机械修复时间都是不确定的，从而航班延误时间是不确定的。本文将总延误时间作为优化目标，而公司成本预算作为约束条件，建立问题的模型及算法。Argüello [7]提出了时间带近似模型相关理论，本文采用时空网络结构来调整航班安排。

3 飞机恢复问题的机会约束规划模型与算法

约束二：飞行的覆盖范围。每个航班都只有飞行或取消两种状态，因此，每个航班k对应的飞行和取消状态和为1。例如，航班34有两种可选飞行航线，一个取消状态，每个航班仅执行一次，可得以下公式：

同理，所有航班k均可表达为上述形式。

约束三：转送结点飞机流。结点中的飞机数量=在该结点起飞飞机数量-在该结点降落飞机数量+由该结点转移到同一城市沉落结点的飞机数量。

约束四：沉落结点飞机流。沉落结点需要的飞机数量=在该沉落结点降落的结束航班的飞机数量+从同一城市其他结点转移来过夜的飞机数量。

每个沉落结點都有相对应的约束条件：

由此得到模型：