考虑组合机位的停机位预指派问题研究

盛 政,蔡碧金,王岩华

(南京航空航天大学 民航学院，江苏 南京 211106)



考虑组合机位的停机位预指派问题研究

盛 政,蔡碧金,王岩华

(南京航空航天大学 民航学院，江苏 南京 211106)

针对现有停机位指派研究优化程度不高的问题，对停机位指派中组合机位的使用进行分析。以列生成算法为基础，通过为组合机位设计独立的飞机连接网络，建立了可考虑组合机位的停机位指派模型，算例分析表明，该模型的指派结果比传统停机位指派模型优化程度更高，在实际操作中是有效可行的。

停机位指派；组合机位；列生成算法

停机位指派问题是指在给定的作业时间窗内，考虑机型、停机位类型和航班时刻等因素，指派进港飞机到有限的停机位上实现停靠，以保证陆空运输的有效衔接[1]。

BRAAKSMA等在1971年最早采用定量的方法研究了停机位分配时旅客在航站楼内行走距离最小化的问题，建立了基于关键路径方法的仿真模型[2]；DREXL等研究了以最小化旅客行走距离、最小化未分配的航班数量和最大化航班的机位偏好为目标的多目标停机位分配优化模型，采用基于Pareto的模拟退火算法求得Pareto前沿优化解[3]；DORNDORF等将停机位指派看作一个集合划分问题来研究，对停机位分配策略的鲁棒性进行了优化，模型中考虑了相邻停机位间的飞机停靠限制[4]；NEUMAN等从机场和航空公司两方面利益角度出发，建立了以最大化停机位分配的鲁棒性、最大化停机位的空间利用率、最大化航空公司的机位偏好和最小化分配到远机位的航班数量为优化目标的多目标停机位分配模型，研究中采用阴影约束来描述停机位间的互相限制、组合及拆分[5]。国内对停机位分配问题的研究虽然起步较晚，但也取得了一定的成果。文军等按照先到先服务原则，建立了航班停机位分配问题的排序模型，并给出了求解该模型的标号算法[6]；卫东选等建立了以分配到远机位的航班数量最少、分配方式扰动性最小及相关旅客转移距离最小为优化目标的多目标停机位实时再分配优化模型[7]；卫东选等以最小化停机位各空闲时间段的离差平方和为优化目标，采用贪婪算法结合动态时间窗法对模型进行优化求解[8]；杨双双等引入客户评价体系，以客户满意度和停机位的保障能力为优化目标，研究停机位分配的优化策略[9]。

受限于约束规则的复杂性，现有停机位指派方面的研究多采用启发式算法或人工智能算法进行求解，并且很少考虑组合机位之类的复杂约束。这种优化方式虽然求解速度较快，但得到的指派方案通常质量不高，一般无法获得全局最优解，并且在应用时经常与实际情况脱节，降低了停机位的使用效率。

1 问题描述

停机位预指派的主要工作是根据现有的航班信息及各类资源，按照一定规则合理编制停机位预分配计划， 以达到提高机场资源利用率及旅客满意度的目的。

在机场实际运营过程中，停机位的组合与拆分使用是一种很常见的现象。每天的不同时刻，机场的到达航班流中不同机型所占的比例都在不断变化，但机场中停机位的比例却是固定的。因为停机位类型与飞机型号之间的匹配约束问题，若不进行停机位的组合与拆分，机场的停机位资源利用率会大大降低。

如图1所示为飞机占用机位时间示例图，停机位G1与G3分别为普通机位与组合机位，G1无法进行组合与拆分操作，只能停靠与机位类型相匹配的飞机；G3为组合机位，在不进行拆分操作的情况下，G3可停靠大型机(如F1)，而当机场中小型机位不够用时，G3也可被拆分成两个小型机位，分别停靠两架小型机(如F2与F3)。

图1 飞机占用机位时间示例图

2 停机位预指派列生成算法的数学模型

以列生成算法为基础建立停机位预指派模型，在子问题的设计中针对组合机位与非组合机位的特性分别构建不同的航班连接网络，使得模型能准确描述停机位的组合及拆分适用情况。列生成算法的数学模型分为主问题和子问题两部分，主问题用以求得目标解，子问题则作为辅助，负责生成主问题的决策变量(列)并判断主问题的解是否已达到最优。当主问题和子问题迭代求解时，主问题需要放松整数约束以向子问题传递对偶变量信息(整数约束不属于线性约束，无法计算其对偶变量)。限制主问题的最优解可能是非整数形式，最后需采用分支定界法求得整数解。

2.1 限制主问题 (RMP)

(1)决策变量xi。若停机指派方案i被采用，则xi等于1，否则为0。停机位指派方案的定义是指派给某一机位飞机队列。

(2)集合。I为停机位指派方案集合，i∈I；P为飞机集合，p∈P；G为停机位集合，g∈G。

(3)参数。agi表示若停机位方案i可被指派给机位g(一个方案只可被指派给一个机位)，则其等于1，否则为0；bpi表示若停机位方案i中包含飞机p，则其等于1，否则为0；neari表示若停机位方案i所指派的机位为近机位，则其等于1，否则为0；UAPp表示若飞机p未被指派，则其等于1，否则为0；Mp为未指派飞机的罚成本，笔者取Mp=10 000。

限制主问题的数学模型如下：

(1)

(2)

(3)

UAPp=0,1

(4)

模型目标函数式(1)为最大化近机位使用率；式(2)为停机位使用约束，每个停机位最多被指派一条停机方案；式(3)为飞机指派约束，每个飞机只能被指派给一个机位或不指派；式(4)限制了未被指派的飞机数量必须为整数，即飞机只能被指派或不被指派。

2.2 子问题的构造

列生成算法的关键是构造子问题模型，因为子问题模型在求解过程中需要被反复迭代计算，所以构造的子问题必须求解方便，并且能简洁地表达主问题的简约成本。因为限制主问题的目标函数为最大，取负转化为最小目标函数后限制主问题中非基变量的简约成本CRi=-neari-πpbpi-πgagi。若minCRi<0，则将子问题生成的CR值为负的停机位方案加入到限制主问题；若minCRi=0，则限制主问题求得最优解。

为求得minCRi，通过构建飞机连接网络来求解最短路径问题。每一个停机位对应着一个连接网络，网络中的每条路径表示一个该停机位的停机位方案，路径的长度则为对应的简约成本。组合机位因为其可拆分性，连接网络的结构与普通机位不同，笔者采用两种不同的规则分别对每个机位g构建连接网络Gg=(Vg,Eg)。

为方便起见，事先定义两种冲突参量。①Colid1p1,p2：当飞机p1和p2可被指派到同一普通机位而不冲突时(时间和空间上均不冲突),其值为0，否则为1。②Colid2p1,p2,g：当飞机p1和p2可同时停在机位g时，其值为0，否则为1。

2.2.1 非组合机位的飞机连接网络构建

网络中Vg为节点集合，包括所有可被指派到机位g上的飞机对应的节点vp、源节点s和汇节点t：

Vg={s,vp,t|p∈P}

Eg为连接边集合，若飞机p1和p2均可被指派到机位g且不冲突，则建立一条从p1指向p2的有向边(飞机p1的占用机位时刻早于p2)。此外还包括从s指向所有vp和从所有vp指向t的有向边：

Eg={(vp1,vp2)|Colid1p1,p2=0}∪

{(s,vp),(vp,t),(s,t)|p∈P}

2.2.2 组合机位的飞机连接网络构建

组合机位网络中的Vg不仅包括所有可被指派到机位g上的飞机对应的节点vp、源节点s和汇节点t，还额外加入了新的组合停靠节点：

因为组合停靠节点的加入，Eg也会添加新的指向边：

{(vp1,vp2,p3)|Colid1p1,p2=0∨Colid1p1,p3=0}∪

{(vp1,p2,vp3)|Colid1p1,p3=0∨Colid1p2,p3=0}∪{(vp1,p2,vp3,p4)|(Colid1p1,p3=0∧Colid1p2,p4=0)∨

(Colid1p1,p4=0∧Colid1p2,p3=0)}

假设飞机p1,p2,p3,p4间的冲突关系为：Colid1p1,p2=1，Colid1p2,p3=1，Colidp1,p4=0，Colidp2,p4=0，Colidp3,p4=0，Colid2p1,p2,g=0，Colid2p2,p3,g=0(见图2)。在不考虑组合机位的情况下和考虑组合机位的情况下它们的连接网络差别很大,分别如图3和图4所示。

图2 飞机占用机位时间示例图

图3 不考虑组合机位时连接网络图

图4 考虑组合机位时连接网络图

构建飞机连接网络的最后一步需要为网络中每条连接边赋权重值，以使每条从s到t的路径长度等于路径方案对应的简约成本。笔者为每条从s出发的边赋权重-neari-πg，每条从vp出发的边赋权重-πp(赋权重时组合停靠节点vp1,p2可拆分为两个子节点vp1和vp2，不影响计算结果)。赋值后能较容易地计算出每条路径的长度为-neari-πpbpi-πg。

此时，子问题的数学模型可表示为：

(5)

(6)

xmn=0,1m,n∈Va

(7)

式中：(m,n)∈Eg；dmn为边(m,n)的权值；xmn为0-1型的决策变量(路径选择变量)，边(m,n)被选中时xmn=1，否则xmn=0。

2.3 模型求解

整个数学模型求解过程如图5所示。

图5 模型求解步骤

限制主问题为线性规划问题，子问题为典型的最短路径问题求解，均不存在太大困难。值得注意的是当采用分支定界法求得整数解时很可能因为限制主问题的决策变量组成比较单一，而导致求解时间过长或求得的解质量较差的问题。为解决该问题，笔者在每回合迭代中不仅为限制主问题加入子问题求得的最优路径方案，还会加入一些CR值为负的次优方案，以保证分支定界时的求解速度和解的质量。

3 算例分析

笔者以国内某机场一个航站楼一天内的停机位及航班数据作为算例，将65个航班指派到10个停机位上。根据所获得的航班信息(见表1)和机位信息(见表2)，将65个航班分为5种机型，包括中小型飞机：4架B738的航班9个，4架A319的航班12个，6架A320的航班10个；大型飞机：7架A333的航班20个，4架A332的航班14个。10个机位中1～4号机位为普通近机位，11～14号机位为普通远机位，5、8号机位为组合近机位，其中5号机位可拆分为6号机位和7号机位(小型机位，不能与5号机位共存)，8号机位可拆分为9号机位和10号机位(小型机位，不能与8号机位共存)。

在航班信息表中航班属性有4种，其中始发航班表示前一天在该机场过夜的航班，出发航班及到达航班分别代表过站飞机的进港和离港，过夜航班表示今天在该机场过夜的航班。

表1 航班信息表

笔者在AIMMS平台下进行模型的建立和求解，AIMMS是以优化为目标的语言开发环境，其主要特点有：①多维的建模语言和先进的建模概念，如列生成、随机规划和现代化的集成开发环境(IDE)(包括诊断工具、PROFILER编辑器和数学规划检查器)。②集成的图形化用户界面创建器(GUI)用来创建与模型中多维标识符紧密关联的控件，如多维表格、图表、网络控件的流程和GIS地图。③连接针对不同数学规划的求解器(线性、整数、非线性等),AIMMS能把最优化的模型传送到世界级的求解器，如XA、CONOPT或CPLEX 等。

在考虑组合机位时，模型在CPU为Intel(R)Core(TM) i5-3210M，主频为2.5 GHz，内存为4 G的主机上求解时，23 s达到最优，列生成算法迭代次数为28次，最优指派方案的甘特图如图6所示，图中每一段长条为航班占用机位时间(通过飞机指派结果还原即可)，其中G5A、G5B、G6A和G6B为拆分后的小机位。

为进行对比，同时采用了不考虑组合机位的数学模型进行求解，求解结果如图7所示。

不考虑组合机位时65个航班中58个被分配到了近机位，靠桥率为89%；在加入组合机位后，65个航班中60个被分配到了近机位，靠桥率提升到了92%。通过对比两个指派结果图可以看出，F6、F55、F57、F38、F59、F61这6个航班的占用机位时间是冲突的，当机位不可拆分时，由于机位资源所限，必然有两个航班会被指派到远机位(见图7中F59和F61)，而若将大型机位G5拆分成两个小机位时，这6个航班均可被指派到近机位，从而提高停机位指派结果的整体靠桥率。

表2 停机位信息表

图6 考虑组合机位的指派结果

图7 不考虑组合机位的指派结果

因为算例数据较小，因此与实际停机位使用情况尚存在较大差距，但从算例分析结果中仍可看出，相较于普通停机位指派模型，所建立的模型可以更准确地模拟停机位的组合与拆分使用情况，在某一类型停机位资源达到饱和时，可以通过机位的组合与拆分对不同类型停机位的比例进行调整，从而使停机位资源的利用率达到最大。

4 结论

机位的拆分和组合是机场实际运营中常采用的一种手段，可以有效提高机场停机位的使用率。笔者在考虑6个停机位指派基本约束的基础上，引入了专有性约束、飞机拖曳约束、过夜航班约束及组合机位约束(前3个约束均在模型求解前的数据预处理中完成)，建立了更符合实际的停机位指派模型。通过建立特殊的飞机连接网络来产生组合机位的飞机停靠方案，并将其与列生成算法相结合，该算法可求得停机位指派模型的最优解。最后采用实际数据的算例分析表明，相较于未考虑组合机位的停机位指派模型，加入组合机位规则后模型的指派结果更优，且更加切合实际，对提高机场运行效率具有积极的意义。

[1] 朱金福.航空运输规划[M]. 西安:西北工业大学出版社，2009:136-177.

[2] BRAAKSMA J P, SHORTREED J H. Improving airport gate usage with critical path[J]. Transportation Engineering Journal, 1971,97(2):187-203.

[3] DREXL A, NIKULIN Y. Multicriteria airport gate assignment and Pareto simulated annealing[J]. IIE Transactions, 2008,40(4):385-397.

[4] DORNDORF U, JAEHN F, PESCH E. Modelling robust flight-gate scheduling as a clique partitioning problem[J]. Transportation Science, 2008,42(3):292-301.

[5] NEUMAN U M, ATKIN J A D. Airport gate assignment considering ground movement[J] .Computational Logistics, 2013(8197):184-198.

[6] 文军,孙宏,徐杰,等.基于排序算法的机场停机位分配问题研究[J].系统工程,2004,22(7):102-105.

[7] 卫东选,刘长有.机场停机位再分配[J].南京航空航天大学学报,2009,41(2):257-261.

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

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

SHENG Zheng:Postgraduate; School of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China.

[编辑：王志全]

Gate Assignment Problem under Consideration of Combined Gate Restriction

SHENGZheng,CAIBijin,WANGYanhua

The optimization degree of existing studies on gate assignment is not high enough. The application of combined gate to gate assignment was analyzed. Based on column generation, the gate assignment model suitable for combined gates was built by designing independent aircraft network for those gates. The example in reality shows that this model is effective and practical. The optimization degree of assignment result of the model is higher than that of traditional models.

gate assignment; combined gate; column generation methods

2015-04-03.

盛政(1989-)，男，湖南衡阳人，南京航空航天大学民航学院硕士研究生.

南京航空航天大学研究生创新基地(实验室)开放基金资助项目(kfjj201445).

2095-3852(2015)05-0616-05

A

V351.11

10.3963/j.issn.2095-3852.2015.05.020