基于延误油耗优化原则的停机位实时分配算法＊

（南京航空航天大学民航学院 南京 210016）

0 引 言

停机位是机场的重要资源，高效、合理的分配停机位是提高机场运行效率的重要途径之一．关于停机位分配问题，国内外很多学者已经做了很多研究．主要有两方面内容：（1）停机位预分配问题；（2）停机位实时分配问题．

Babic等［1］建立了以离港旅客和进港旅客的总步行距离最短为优化目标的停机位分配模型，对模型的求解采用了分枝定界法．文军等［2］将停机位分配抽象成为排序问题，采用“先到先服务”规则通过标号算法进行求解，通过模型优化提高了停机位使用效率．王力等［3］提出了以旅客登转机时间、机型与停机位类型匹配为优化目标，同时考虑航班性质、航班数量与密度、停机时间的多目标停机位分配的数学模型，并设计求解模型的禁忌搜索算法．熊杰等［4］在考虑跑道和滑行道的基础上，建立了飞机油耗总和最小的分配目标．

Yu等［5］针对航班大面积延误时进行实时调整，并采用了遗传算法进行求解．朱世群［6］设计了以旅客和机场地面服务人员的移动总距离最短为目标，并采用遗传算法进行求解的停机位实时调整策略．Tang［7］研究了停机位短缺和航班随机延误下的停机位实时调整．

停机位实时分配的研究还比较少，大部分研究都是通过模型和算法达到高效合理利用资源的目的［8－12］．然而，从延误油耗和从航空公司相同机型所承担延误油耗均衡的角度来考虑停机位实时分配问题的文章还未曾发现．航空运输业是一个高风险、高投入的资金密集型行业，平均利润只有3%～6%，降低成本对于每个航空公司都具有非常重要的意义，而飞机的油耗成本占到总成本的1／3左右．由于航空公司规模各不相同，并且各航空公司在某一段时间内涉及的航班架次和机型大小也各不相同，不能笼统的要求各航空公司的耗油均衡，因此本文建立了以延误油耗最低和各航空公司相同机型所承担延误耗油均衡为目标的停机位适时调整模型，采用遗传算法进行求解，所得结果表明此模型和算法在停机位实时分配中是合理而可行的．

1 模型描述

延误油耗优化原则：降低由于航班延误所产生的延误油耗，并使各航空公司相同机型所承担的延误油耗基本均衡．由于调整之后个别航班延误油耗可能有增有减，因此，在降低油耗的同时使各航空公司的油耗变化基本均衡．

1.1 模型的数据定义

Pmn为n公司m型飞机油耗变化占所有公司m型飞机油耗变化的百分比；COi为航班i每分钟的耗油量；CTi为飞机滑行到停机位i所消耗的时间；COmn为n公司m型飞机的耗油量；Bmn为n公司m型飞机分配到的停机位集合；Xij的意义为，若航班i分配到停机位j则Xij为1，否则Xij为0；Rij为航班到达停机位时间；Lij航班离开停机位时间；K1i为停机位i空闲的开始时间；K2i为停机位i空闲的结束时间；Gj为停机位；Qi为航班机型；Di为航班i初始分配到的停机位；D′i为航班调整后的停机位；ΔT为同一停机位2架航班的最小间隔．

1.2 模型的目标分析

1）延误产生的总油耗最低 要求停机位的实时调整使航班由于延误增加的油耗降到最低，通过最小化航班调整前后增加的滑行时间来实现．

式中：（CTD′i－CTDi）为航班i增加的滑行时间．三项相乘的结果为延误增加的油耗，求其最小值即可满足延误增加的总油耗最低的目标．

2）延误油耗均衡 要求各航空公司相同机型油耗的均衡．通过最小化各公司相同机型油耗变化的百分比与平均值之间的差距来实现延误油耗的均衡．

3）多目标优化模型

约束条件：式（1）是每个航班都只分配一个停机位；式（2）满足停机位与机型相匹配；式（3）表示停机位的空闲时间大于最低安全时间；式（4）表示停机位空闲的开始时间要早于航班的到港时间并且空闲的结束时间要晚于航班离港时间．

2 模型求解

根据停机位分配的特点，采用遗传算法对多目标优化模型进行求解．

2.1 初始解的产生

采用如下方法产生初始可行解：

1）读取航班信息，停机位信息，读取初始航班可停靠的停机位集合．

2）对于第一个航班，随机选取集合中的一个停机位，作为该航班的停机位，然后更新该停机位的空闲开始时间，使该停机位的空闲开始时间等于该航班的离港时间．

3）对于第二个航班，重新调整其可停靠的停机位集合，然后从中选取某一停机位，更新停机位空闲开始时间，若无进停机位可分，跳转到2）．

4）以此类推，输出可行解．

2.2 适应度函数的设计

采用基于目标优劣表现的排序法［12］确定个体适应度．适应度计算如式（5）所示．

式中：n为目标函数个数；N为种群个体总数；Xj为种群的第j个个体；Ri（Xj）为种群所有个体对目标i优劣排序后个体j在序列中的序号；Fi（Xj）为Xj对目标i所得的适应度；k为（1，2）区间的常数，用于加大个体的函数值表现最优时的适应度．

2.3 遗传操作

1）基于航班交换的变异：采用交换变异的方式，对航班基因串进行变异：即在航班基因串中随机选择两位置，交换该位置处的两航班基因．

2）Pareto最优解更新策略．算法执行过程中采用Pareto最优解作为选择判断条件，最终得到多目标优化问题的最优解集．

3 实验分析

采用首都机场实际运行的22个航班数据（见表1）．涉及到国航、东航、南航和海航4个航空公司．根据实际操作，得到大型飞机耗油46kg／min，中型飞机耗油28kg／min，小型飞机耗油12kg／min．

表1 航班信息表

采用首都机场11个典型的近停机位进行实验，其中1，2，3，5，6，11号停机位为大型停机位；8，9，10号停机位为中型停机位；4，7号停机位为小型停机位．预先分配的停机位见表2．

表2 停机位预分配结果

飞机从跑道滑行到停机位所消耗的时间见表3．现第7个航班延误到10：15到港，根据文献［6］选取10：00～11：00内航班作为实时调整的区间．停机位空闲时间如表3所列，对于此前没有使用的停机位设置停机位开始时刻为08：00，对于此后没有使用的停机位，设置停机位空闲结束时刻为14：00．

表3 停机位预分配结果

程序在Matlab7．8．0环境下进行实验，参数设计如下：交叉概率Pc＝0．8；变异概率Pm＝0．08；初始种群数量N＝50；进化代数T＝300．结果见表4．

表4 实时分配结果

结果分析：

图1 航空公司油耗变化图

因为小型飞机只有1架，可将其调整到4号停机位，也可调整到7号停机位，由于7号停机位的滑行时间比4号停机位少4min，因此搜索出7号停机位作为最优解，使总油耗降低．

3）特殊航班保障 本例选择4号和11号航班为特殊航班，调整后其分配到的停机位未发生变化，满足此前设定的目标．因此本文的模型，在航班发生延误时，能在满足油耗优化原则的前提下，通过调整少量航班使机场运行恢复正常，满足机场实际运行的要求．

4 结 论

在航班发生延误时，为降低油耗成本，本文建立了以延误油耗最小以及各航空公司所承担延误油耗成本均衡为目标的停机位实时调整策略，并通过遗传算法进行求解．通过实验证明，该停机位实时调整策略是一种合理可行的调整策略，其在兼顾特殊性质航班的同时，能很好降低延误油耗，均衡各航空公司之间的成本．

［1］BABIC O，TEODOROVIC D，TOSIC V．Aircraft stand assignment to minimize walking［J］．Joumal of Trans－Portation Engineerin，1984，110（3）：55－66．

［2］文 军，孙 宏，徐 杰，等．基于排序算法的机场停机位分配问题研究［J］．系统工程，2004，22（7）：103－105．

［3］王 力，刘长有，涂奉生．民用机场停机位优化配置［J］．南京航空航天大学学报，2006，38（4）：434－437．

［4］熊 杰，张 晨．基于飞机滑行油耗的枢纽机场停机位分配研究［J］．交通运输系统工程与信息，2010，10（3）：166－170．

［5］YU Gu，CHRISTOPHER A．Genetic algorithm approch for airport gate assignments for stochastic flight delays［J］．Journal of Transportation Engineering，2000，125（5）：385－389．

［6］朱世群．大型机场停机位实时调配问题的研究［D］．南京：南京航空航天大学，2007．

［7］TANG Chinghui．Real－time gate assignments under temporary gate shortages ans stochastic flight delays［C］／／2009IEEE International Conference on Service Operation，Logistics and Informatics，2009：267－271．

［8］孔佳玉．机场停机位分配建模及其遗传算法研究［D］．南京：南京理工大学，2008．

［9］戴顺南．机场停机位分配模型构建及算法实现［D］．北京：北京交通大学，2008．

［10］鞠姝妹，许 俐．基于GSAA的停机位指派优化问题的研究［J］．交通运输系统工程与信息，2008，8（1）：139－143．

［11］常 钢，魏生民．停机位分配问题优化技术［J］．中国民航学院学报，2006，24（2）：25－29．

［12］游进军，纪昌明，付 湘．基于遗传算法的多目标问题求解方法［J］．水利学报，2003（7）：64－69．