基于相关机会约束规划的应急调度机型指派问题研究

朱博文，唐福玉，徐书娟，陈 静

（中国民航大学 理学院，天津 300300）

基于相关机会约束规划的应急调度机型指派问题研究

朱博文，唐福玉，徐书娟，陈 静

（中国民航大学 理学院，天津 300300）

为应对民航突发情况，保障民航运行安全，提出应急调度这一概念。本文阐述常规情况下航班调度的基本模型，分析其在应急情况下的弊端。引入相关机会约束，构建应对突发状况的应急调度模型。根据拟合数据，利用基于随机拟合的改进遗传算法，借用matlab软件求解模型。结果显示，基于相关机会约束规划的机型指派模型在考虑随机因素的情况下，比基本模型更符合实际动态环境要求。

相关机会约束；应急调度；机型指派；遗传算法

航空公司一般会提前1年制订出相应的航班计划，然而这些计划在安排时常被不确定事件打乱。利用恰当的模型与优化算法，提出应急调度方案，有利于保障航空公司快速恢复正常运营，减少航班延误。对此黄为 等论述了航空公司航班应急调度的目标、方法及对策。牟德一 等提出航班调度应急管理鲁棒调度与受扰恢复策略研究。本文引进相关机会约束，在传统的模型中加入随机变量，建立带有相关机会约束的航班调度模型。

1　应急情况下机型指派模型研究

1.1确定情况下航班调度问题的机型指派模型

机型指派管理对航空公司收益管理有较大影响，是整个航班计划管理的核心部分。以下是马苏德·巴扎尔甘提出的机型指派模型简化模式。

式中：C为到达机场集合，表示网络中所有结点或停场过夜机场；F为航班集合；Pi， j为由机型j飞航班i的成本；如果航班i用机型j执行，则xi， j=1，否则为0，M为网络中的机场（结点）数；J为机型集合。

1.2应急情况下的航班调度机型指派问题相关机会约束模型

在应急情况下，管理者期望在花费资金较少的情况下最大概率的实现预期的管理目标，由于在航班应急情况下，许多参量出现一定的随机型，原来的一部分确定型变量转化成为随机变量，传统的确定型数学规划模型无法很好地求解这类机型指派问题，相关机会约束模型，在根据具体条件情况要求下设定一定的优先等级，允许在一定情况一定置信水平下满足约束条件，其模型如下。

式中：ξ是个随机向量；x是个决策向量；α和β是管理者预先给定的置信水平。为航班实际的成本。其中ξj表示航班j的旅客量，是一个随机变量；Si表示机型i的座位数；Gk， j为机型j在机场k过夜的飞机数量。Nj为机型j的可用飞机数量；当结点k的航班i是进港航班，Sj，k=+1，当结点k的航班i是离港航班，Si，k=-1。

2　模型算法研究

2.1机会函数的计算机仿真拟合计算

设gj（x，ξ）≤0， j=1，2，…，P是事件Aj在点x的诱导约束，则机会函数式fj（x）由下式给出：

相关机会约束目标函数变化为Max（ f1（x）， f2（x），…， fp（x），其中x为管理变量；ξ为随机变量，其分布为φ（ξ）。

我们允许采用蒙特卡罗随机拟合方法估计机会函数fj（x）。具体思想是利用ξ为随机变量的分布φ（ξ），从中产生N个随机向量，分别记为ξ1，ξ2，…，ξN；设N次试验中gj（x，ξk）≤0（k=1，2，…，N）成立的次数为n，即随机变量中符合约束条件的个数。由中心极限定理和大数定理得出，机会函数允许用近似估计概率。

2.2随机拟合仿真的改进遗传算法

由于相关机会模型问题的复杂性，很难利用现有的理论方法求解，采用蒙特卡罗随机仿真拟合的改进遗传算法极大地方便求解模型。基于蒙特卡罗随机拟合的改进遗传算法求解步骤如下。步骤1：确定变异概率Pm，交叉概率Pc及种群数参数N；步骤2：编码优化问题，形成有N个染色体的初始群体，并借用随机拟合技术检验染色体的可行性；步骤3：借用随机拟合技术估算初始种群中每个染色体的适应值；若停止规则满足，则算法停止，否则转下一步；步骤4：估算概率；步骤5：以概率Pi从初始种群中随机选部分染色体构建新的种群；步骤6：按照给定的变异概率Pm与交叉概率Pc，对染色体实行变异与交叉操作，并借用蒙特卡罗随机拟合技术检验后代的可行性；步骤7：重复步骤2至步骤6，直到完成设定的循环次数；步骤8：给出方案结果最好的染色体作为最终最优解。

3　算例分析

A航空公司为应对由风暴等不确定因素引起的大面积航变，提前制定应急预案。该公司有2种机型，6架Ⅰ型飞机，3架Ⅱ型飞机，Ⅰ、Ⅱ机型的座位数分别为185、200。设A航空公司甲、乙城市之间的航班旅客需求为ξ1（去）、ξ2（返）分别为正态分布ξ1～N（150，352）、ξ2～N（160，472），首先来解2.1中的模型，根据算例的数据，得到F=｛1，2，3，4，5，6｝，J=｛1，2｝，M=｛1，2，3｝，N1=6，N2=9，由程序得到最优解确定性模型最小成本为115 608，甲乙往返满足旅客量需求置信水平分别是80%、52%。现引入相关机会约束，设定一定的优先等级，设定满足甲去乙为第一优先级，置信水平不低于90%，乙返回甲地为第二优先级，置信水平不低于80%，满足在相关基础模型参数基础上，求解的相关机会约束模型最小成本为121 956。并且误差不超过2%。结果显示，成本虽然有所增加，却能够以较高的置信度满足旅客需求，模型具有鲁棒性，往返置信水平分别提升到90%、80%以上，有效提升航空公司形象及顾客满意度，有利于长远发展。

4　结　语

在前人成果基础上构建相关机会约束的机型指派模型，并运用蒙特卡罗随机拟合与改进遗传算法等方法求解模型，结果显示模型的可行性及鲁棒性，一定程度上可为航空公司的应急机型调度提供相应参考。但模型仅考虑了不确定旅客需求的随机性，实际情况较为复杂，可以进一步研究同时包含模糊不确定性、随机不确定性的突发状况及应急调度。

主要参考文献

［1］赵秀丽.航空公司不正常航班恢复模型及算法研究［D］.南京:南京航空航天大学.2010.

［2］［美］马苏德·巴扎尔甘.航空公司运营规划与管理［M］.邵龙，王美佳，译.北京:中国民航出版社，2006:39-56，81-91.

［3］牟德一，王志新，夏群.基于机组延误概率的鲁棒性机组配对问题［J］.系统管理学报，2011，20（2）:207-212.

［4］刘宝碇，赵瑞清，王纲.不确定规划及应用［M］.北京:清华大学出版社，2003:84-91.

［5］黄为.国内航班的应急调度管理［J］.经济与管理，2009（3）:74-76.

10.3969/j.issn.1673 - 0194.2015.12.103

F224.3；V352

A

1673-0194（2015）12-0135-02

2015-04-13