基于运行安全的停机位再分配问题研究

刘长有，曹 强

（中国民航大学空中交通管理学院，天津 300300）

基于运行安全的停机位再分配问题研究

刘长有，曹 强

（中国民航大学空中交通管理学院，天津 300300）

分析了基于运行安全的停机位再分配问题。首先，在该多目标优化问题中考虑了3个目标函数，即分配到停机坪的航班数量最少、停机位分配的扰动最小和停机位被占用时间均衡。然后在停机位再分配模型中引入了安全性约束以避免潜在的航班双推冲突，并采用粒子群遗传算法对问题进行优化求解。最后，结合算例分析，检验了模型和算法的有效性。

机场停机位；最优化；再分配；粒子群遗传算法

按照航班计划合理地分配停机位，是提高机场运行效率的重要途径。当发生航班延误时，则需要在停机位预分配优化方案的基础上进行动态调度，即需考虑停机位的再分配问题。

在停机位分配优化问题的研究中，主要是以旅客行走距离最小、停机位的空闲时间最小、近机位的使用率最大等为目标函数进行建模，并采用排序算法、遗传算法和禁忌搜索等算法进行优化[1-5]。这些研究对停机位的预分配计划考虑的比较完整，但没有考虑对航班延误应急处理的停机位再分配问题，并且仅考虑了运行效率问题，而没考虑运行安全问题。

文献[6]采用禁忌搜索算法研究了停机位的再分配问题，文献[7]在停机位分配中引入避免航班双推冲突的安全性约束，初步研究了兼顾运行安全和运行效率的停机位分配优化问题。本文则在上述研究的基础上，研究了避免双推冲突的停机位再分配问题，即在对航班延误应急处理的停机位再分配问题中，仍然考虑安全性约束以避免潜在的航班双推冲突。

1 数学模型

假设有M个停机位，在一段时间T内，有N架航班要进行停机位分配，已知航班的预计进离场时间、地面活动时间及机型大小信息。

1.1 目标函数分析

1）停机位被占用时间的均衡性

航班在停机位停留时间为

式（1）表示航班i在停机位k的停留时间。

如果近机位资源总体使用不均衡，那么是对停机位资源的浪费，从而函数为

其中：F1为飞机占用停机位总时间的平方和。minF1使得机位占用时间尽量均衡。

2）航班机位分配的扰动性

如果有航班延误或者取消，原有的机位分配将会被打乱，需要再分配停机位。若再分配时，又被分配到原来机位，则变量xi=0，否则xi=1。从而函数为

其中：F2为受扰动的航班数。minF2使停机位再分配时所受到扰动性最小。

3）分配到停机坪的航班数最少

当航班密度较大时，可能会出现部分航班被分配到停机坪的情况，从而导致旅客的满意度被降低，所以有必要将分配到停机坪的航班数量尽量减少作为优化计算的目标。如分配到停机坪，则变量pi=1；如果可分配到一个停机位，则pi=0。从而函数为

其中：F3为分配到停机坪上的航班数。min F3使分配到停机坪上的航班数最少。

1.2 基本约束条件

1）独占性约束

式（5）表示每个航班仅需分配一个停机位，yik是航班i被分配到停机位k，是一个二进制变量，当且仅当航班i被分配到停机位k时，yik=1，否则yik=0。

2）紧邻航班约束

安排同一停机位的航班像一个队列，有进有出。式（6）表示紧邻某个航班之前至多只能有一个航班，紧邻其后也至多只能有一个航班。当航班i和航班j被分配到停机位k而且航班i是航班j的直接前邻航班时zijk为1，否则为0。

3）航班-机位类型匹配约束

其中：gk为停机位k的属性值；fi为航班i机型属性值。式（7）表示航班机型与机位类型的匹配约束，停机位只能停放允许的航班机型。

4）安全间隔约束

其中：aj为航班j的计划进场时间；di为航班i的计划离场时间。式（8）表示分配到同一停机位k的相邻航班i和航班j必须要满足一定的时间间隔δ的约束，以保证地面安全有效的运行。

5）避免潜在的双推冲突安全约束

当被分配到相邻停机位的2个航班的离港时间过于接近时，则可能存在潜在的双推冲突。式（9）中β为相邻停机位的航班离港时间的最小间隔。

1.3 多目标规划模型

1）停机位初次分配模型的目标函数为

在基本约束条件（5）~（8）中，增加安全性约束条件（9）。

2）停机位再分配模型的多目标函数为

其中，Pi（i=1，2，3）为优先权。同样在基本约束条件（5）~（8）中增加安全性约束条件（9）。

对于多目标函数F＇，采用分优先级处理的方法，即先求解优先级数高的目标函数，然后再求解次优先级数的目标函数，以此类推。

2 算法设计

本文拟采用粒子群遗传算法[8]求解机场停机位再分配问题，以达到优化分配的效果。根据停机位分配的特点，本文设计了如下方案：初始化种群、设计适应度函数、更新粒子的速度和位置、选择、交叉、变异运算。

1）初始化停机位分配方案，确定粒子群中所有n=100个个体位置及其速度，搜索个体的最佳位置Pi，并将个体最佳位置的最优值设定为群体最佳位置Pg初始位置，设置迭代次数0

2）按公式更新每个粒子的速度和位置，并计算其个体最佳位置Pi和群体最佳位置Pg；

3）如果满足终止条件输出最优解Pg，终止程序，否则继续第4）步；

4）选出m个个体，对它们执行交叉操作，得到m＇个新个体，与选出m个个体比较，得到适度值大的m个个体；

5）对m-s个个体执行变异操作，得到（m-s）＇个新个体，与m-s个个体比较，选择适应度高的m-s个个体，则新的m-s个个体进入下一代，转第2）步。

3 仿真实验结果与分析

3.1 停机位初次分配

算例采用某机场的20个停机位对116个航班的机位再分配问题，其中1~15号为大机位，允许停放大机型或者中机型，16~20为小机位，允许停放中机型。航班数据见文献[6]中的航班计划信息。同一个机位相邻2架飞机的最小停机位时间间隔δ=30 min，β= 1 min。交叉概率为0.75，变异概率为0.25。航班机型属性值，数字1表示中机型，数字2表示大机型。用粒子群遗传算法得到停机位分配的结果，如图1所示。

3.2 停机位再分配

在上述116个航班中随机产生20%的延误航班和3%的取消航班，其中28、57、66号航班被取消，延误航班时刻信息如表1所示。

图1 停机位初次分配模拟图Fig.1 Simulation chart of initial gate assignment

表1 航班计划变动信息Tab.1 Changed flight information

采用粒子群遗传算法得到的停机位再分配结果，如图2所示。

在图2中，与图1有16处不同（包括3个取消航班），占总航班量的13.79%（其中延误或者取消航班有5个），其中有1个航班被分配到了停机坪上，与停机位初次分配结果不同，如表2所示。停机位再分配的结果兼顾了系统的运行安全和效率，优化效果较为理想。

表2 相同航班所分配的不同停机位Tab.2 Different gates between two assignments for same flights

图2 停机位再分配模拟图Fig.2 Simulation chart of gate reassignment

4 结语

基于运行安全的停机位再分配问题，既要考虑在航班延误或取消的情况下动态调度，又要考虑兼顾机场运行的安全和效率。本文通过在模型中引入安全性约束，将机场停机位再分配与避免潜在的航班双推冲突有机结合，并采用粒子群遗传算法进行问题求解。结合航班计划的算例表明了模型和算法的有效性，即在保证机场运行安全的前提下，尽量减少由航班延误带来的停机位预分配计划扰动，并提高系统的运行效率。

[1]文 军，孙 宏，徐 杰，等.基于排序算法的机场停机位分配问题研究[J].系统工程，2004，22（7）：102-106.

[2]常 钢.民航机场停机位分配与优化技术研究[D].西安：西北工业大学，2006.

[3]YAN S Y，HUO C M.Optimization of multiple objective gate assignments[J].Transportation Research Part A：Policy and Practice，2001，35（5）：413-432.

[4]文 军.机场停机位分配问题的遗传算法[J].科学技术与工程，2010，10（1）：135-139.

[5]尹嘉男，胡明华，赵 征.多跑道机场停机位分配仿真模型及算法[J].交通运输工程学报，2010，97（2）：187-203.

[6]卫东选，刘长有.机场停机位再分配问题[J].南京航空航天大学学报，2009，41（2）：257-261.

[7]刘长有，翟乃钧.避免航班双推冲突的多目标停机位优化[C]//第29届中国控制会议论文集，北京，2010：1082-1086.

[8]SHI X H，LU Y H，ZHOU C G，et al.Hybrid Evolutionary Algorithms Based on PSO and GA[C]//Proceedings of the 2003 Congress on Evolutionary Computation，Canberra，Australia，2003：2400-2405.

（责任编辑：杨媛媛）

On gate reassignment for aircraft based on operational safety

LIU Chang-you，CAO Qiang
（College of Air Traffic Management，CAUC，Tianjin 300300，China）

Gate reassignment for aircraft based on operational safety is researched.First，three objectives are proposed as following the minimization of flights assigned to the apron，the disturbance of airport gates and the nonbalance of gate utilization ratio.Then a safety restraint is introduced into the model of gate reassignment and the particle swarm genetic algorithm is applied to solve the model.Finally，an example with the realistic data is implemented to show the validity of the model and the algorithm.

airport gate；optimization；reassignment；particle swarm genetic algorithm

V351；TP18

：A

：1674-5590（2014）01-0015-04

2012-12-10；

：2013-02-25

：国家自然科学基金项目（60979007）

刘长有（1956—），男，河北卢龙人，教授，博士，研究方向为繁忙机场运行管理与调度优化.