王笑天　田　勇　万莉莉　杨　晔

(南京航空航天大学民航学院　南京　210016)

基于列生成算法的停机位指派的鲁棒性研究*

王笑天田勇万莉莉杨晔

(南京航空航天大学民航学院南京210016)

摘要：引入停机位计划的概念来描述指派到同一机位上的一系列的航班，将停机位指派问题转化为选择符合相应的停机位类型的最佳停机位计划，建立增大停机位指派鲁棒性的数学模型.应用列生成算法求解该模型.算例分析表明，该停机位指派模型和算法在计算时间和指派结果上具有一定的优势，在实际操作中是有效可行的.

关键词：停机位指派；鲁棒性；停机位计划；列生成算法

王笑天(1988- ):硕士生，主要研究领域为空中交通管理

0引言

停机位指派的鲁棒性是指机位预指派自身具有一定的“抗干扰能力”.目前机场停机位资源紧缺，当进出机位的航班发生随机延误时，会影响到其他航班，重新指派耗时耗力.因此，建立增大停机位指派鲁棒性的模型并采用高效的算法快速生成指派方案势在必行.国内外学者对停机位指派的鲁棒性进行了一定的研究.Hassounah等[1]首次对停机位指派的鲁棒性进行了研究.ABolat等[2]研究了以最小化机位空闲时间段的方差为目标的机位指派问题，用分支定界法进行求解.尔后又对该问题进行了进一步的研究，并设计启发式算法求解[3].田晨等[4]采用遗传算法对停机位指派的鲁棒性问题进行了研究.卫东选等[5]以最小化停机位各空闲时间段的离差为优化目标，采用贪婪算法结合动态时间窗法对模型进行优化求解.杨双双等[6]基于客户评价体系，对停机位分配优化技术进行了研究.本文将具有相同特性的停机位划分为一种停机位类型，从而将停机位指派问题转化为选择符合相应的停机位类型的最佳停机位计划，在此基础上建立了增大停机位指派鲁棒性的数学模型，并应用列生成算法求解该模型.

1停机位指派的数学模型

1.1鲁棒性评价函数的设计

鲁棒性评价函数应具有2个特点：(1)它应该指派给较小的空闲时间间隔以较高的成本来作为惩罚，而对于较大的空闲时间间隔则设置适当的成本进行略微的惩罚；(2)函数在较小的空闲时间间隔时应非常陡峭，后趋于平缓，以反映在小的时间间隔范围内时间间隔的增加是有利且明显的.相关参数是由我国机场航班历史统计数据拟合得到的.基于以上特点，设计评价函数如下.

(1)

式中：t为指派到同一机位上相邻2架航班之间的时间间隔，即机位缓冲时间，根据机位指派人员经验，最小取值为20min.

1.2停机位类型划分

本文提出一种比较细致地划分停机位类型的方法，具体分类标准参见表1，那么根据停机位所能停放机型的大小，最多可将停机位划分成A,B,C,D,E,F6种类型.

表1　飞机分类标准

1.3停机位计划的概念

将研究时间段内可以指派到同一机位上的一系列的航班定义为一个停机位计划，因而可能的停机位计划有无数种.在列生成算法中，停机位计划起着联系主问题和子问题的重要作用，它在主问题中是决策变量，同时子问题产生的结果是一个新的停机位计划.

1.4整数线性规划模型

定义航班集合V，停机位类型集合A，停机位计划集合N，并引入以下符号.

1) 下标号记号i,停机位计划下标；v,航班下标；a,停机位类型下标.

2) 参数ci,停机位计划i的成本，可通过停机位计划i中相邻2架航班之间的空闲时间间隔成本求和得到；Qv,一个非常大的成本系数，本文取1 000 000；gvi,当航班v包含在停机位计划i中时等于1，否则等于0；eia,当停机位计划i可指派到a类型的停机位上时等于1，否则等于0；Sa,a类型的停机位数量.

3) 决策变量xi,执行停机位计划i时等于1，否则等于0；UAFv,存在未指派的航班v时等于1，否则等于0.若存在未指派航班，则将其指派至远机位.

应用以上符号，建立如下增大停机位指派鲁棒性的数学模型.

(2)

(3)

(4)

(5)

(6)

式(2)为目标函数，要求停机位指派成本最低；式(3)为航班指派约束，表示每个航班仅且仅能被指派到一个停机位计划中；式(4)为停机位类型个数约束，表示指派到a类型停机位上的停机位计划数必须等于a类型停机位数；式(5)和(6)为变量取值约束.

2列生成算法求解过程

具体求解步骤如下.

步骤1初始化.由指派人员根据经验给定初始解，生成限制主问题.

步骤2求解限制主问题.

步骤3计算航班约束和停机位类型约束的对偶变量的值，分别用πv(v=1,2,…，V)和λa(a=1,2,…,A)表示.

步骤4利用上述对偶变量值对子问题网络图中边的权值进行调整.

步骤5对子问题进行求解(求得主问题非基变量的最小简约成本).

步骤6若最小简约成本小于0，则将其所对应的停机位计划作为新的列加入到初始解中，转至步骤2；否则，转至步骤7.

步骤7若限制主问题的解为非整数，则利用分支定界法求得整数解；否则，当前解即为最优解.

2.1限制主问题

将式(5)和(6)表示成约束松弛便得到松弛线性规划问题，可作为列生成算法的主问题。从所有停机位计划中选择符合各类停机位类型且与其数目相等的停机位计划构建停机位指派模型的限制主问题。

2.2子问题的构造

列生成算法的关键是构造子问题.为求得所有实际可行的停机位计划的最小简约成本，本文构建这样一个网络，在该网络中，每个可行的停机位计划等价于网络中的一条路径，反之亦然.并且，路径的长度等于相应的停机位计划的简约成本，从而将求解最小简约成本的问题转化为求解网络中的最短路径问题.

图1　有向网络图

最后，对每种停机位类型下的最小简约成本再求最小，即得最终的停机位计划i的最小简约成本.

3算例分析

本文对国内某机场一个航站楼20个停机位1d内的110架航班进行指派.根据航班和机位信息，将停机位划分为E类国内航班停机位、D类国内航班停机位、C类国内航班停机位、E类国际航班停机位、D类国际航班停机位和C类国际航班停机位6种类型，对应的个数分别为4,2,6,2,2,4.航班信息见表2.表中No为航班序号；Arr为进场时刻；Dep为离场时刻；S为机型；Cat为航班类型.航班从早上08：00(表中以08：00为0时刻)开始到晚上22:35结束.

表2　航班信息

运用AIMMS软件进行求解,得到如图2所示的最优指派方案.其中，Gatetype1对应E类国内航班停机位，Gatetype2对应D类国内航班停机位，Gatetype3对应C类国内航班停机位，Gatetype4对应E类国际航班停机位，Gatetype5对应D类国际航班停机位，Gatetype6对应C类国际航班停机位.

图2　最终指派方案甘特图

在所有相邻2架航班之间的空闲时间中，最长空闲时间为275min，最短空闲时间为20min，平均空闲时间为81.833min.由于航班进离场存在高峰时段和相对空闲时段，因而机位空闲时间段的跨度比较大.对各个机位上相邻2架航班之间的空闲时间段及个数进行统计，得到如图3所示的空闲时间段分布图.由图3可见，空闲时间段集中在55～95min内，这是由于空闲时间段较小时不利于增大停机位指派的鲁棒性，而空闲时间段较大时则会导致一些航班无法指派到机位上.

图3　空闲时间段分布图

采用本文设计的算法对文献[5]中的算例进行求解，得到的优化目标值，即所有机位空闲时间段的平方和为773 024min2，而禁忌搜索算法得到的优化目标值为798 485 min2，遗传算法得到的优化目标值为776 210 min2，可见本文设计的算法较启发式算法能够得到更为优越的解.同时，本文算法的求解时间为204.4 s，而经典算法一般无法在多项式时间内求解出该NP难问题，所以该算法的求解速度明显快于经典算法.

4结束语

在机场实际运行过程中，航班的随机延误普遍发生，因此，提高停机位预指派方式的鲁棒性对保障航班计划执行率尤为重要.未来还可进一步考虑不同类型航班对应不同的单位时间延误成本，从而根据航班类型合理分配缓冲时间，使停机位指派的鲁棒性研究更具现实意义.

参 考 文 献

[1]HASSOUNAHM,STEUARTG.Demandforaircraftgates[J].TransportationResearchRecord,1993,1423:26-33.

[2]BOLATA,AS-SAIFANK.Proceduresforaircraft-gateassignment[J],Mathematical&ComputationalApplications,1996,1(1):9-14.

[3]BOLATA.Assigningproceduresforprovidingrobustgateassignmentsforarrivingaircrafts[J],EuropeanJournalofOperationalResearch,2000,120(1):63-80.

[4]田晨,熊桂喜.基于遗传算法的机场机位指派策略[J].计算机工程,2005,31(3):186-189.

[5]卫东选,刘长有.机场停机位指派问题研究[J].交通运输工程与信息学报,2009,7(1):57-63.

[6]杨双双,田勇,万莉莉,等.基于客户评价体系的停机位分配优化研究[J].武汉理工大学学报：交通科学与工程版,2013,37(1):167-171.

[7]白凤,朱金福,高强.基于列生成算法的不正常航班调度[J].系统工程理论与实践,2010,30(11):2036-2045.

中图法分类号：U8

doi:10.3963/j.issn.2095-3844.2015.01.039

收稿日期：2014-00-00

ResearchonRobustnessofGateAssignmentBasedon
ColumnGenerationMethods

WANGXiaotianTIANYongWANLiliYANGYe

(School of Civil Aviation,Nanjing University of

Aeronautics and Astronautics,Nanjing 210016,China)

Abstract：It is very significant to study the robustness of gate assignment scheme in the process of airport operation. The concept of gate plan is introduced to describe a series of flights which are assigned to the same gate, then the gate assignment problem boils down to selecting the best subset of gate plans which conform to the corresponding gate type, so a mathematical model of increasing gate assignment robustness is established. Column generation methods are introduced to solve this model. Finally, a given instance shows that the model and algorithm of gate assignment have certain advantages in computation time and assignment result, which are effective and feasible in practice.

Key words：gate assignment;robustness;gate plan;column generation methods

*中央高校基本科研业务费专项资金资助(项目编号：NJ20140017)