基于贪婪-遗传算法的机场登机口分配策略

胡 杰, 鲍 帆, 石潇竹

(1. 中国电子科技集团公司第二十八研究所, 江苏 南京 210007;2. 空中交通管理系统全国重点实验室, 江苏 南京 210007)

0 引 言

随着航空运输业的快速发展,航班量也随之日益增长,使得部分机场登机口出现严重不足的情形,登机口资源冲突频发,影响机场运营效率与安全,同时也降低了旅客出行满意度。为解决该问题,大型枢纽机场通过在现有航站楼T的基础上新增卫星厅S,以缓解机场登机口不足的压力,提高过站飞机靠桥率。通常,航站楼T与卫星厅S有一段间隔距离,这对过境旅客的航班衔接产生了一定的负面影响,增加了中转旅客换乘失败的机率。因此,如何解决具有卫星厅的机场登机口分配问题,最大限度地优化登机口配置,已成为当前大型机场运营亟待解决的问题之一[1-2]。

机场航班-登机口分配属于运筹学多目标优化问题,其求解目标函数由机场决策者根据运营情况决定。国内外学者从乘客和机场运营两个层面建立并求解了诸多登机口分配优化模型。

首先,从乘客角度考虑,Braaksma等[3]首次提出了航班-登机口分配优化模型,并以最小化旅客航站楼内行走距离为目标函数实现登机口资源最优化分配。随后,Babic等[4]建立了机场登机口分配0-1整数规划模型,该模型以最小化旅客航站楼内的行走总距离为优化目标,并基于分支定界算法求解优化模型,但其未考虑中转旅客航班衔接问题。Mangoubi等[5]在文献[4]研究基础上,将中转旅客的步行距离作为优化目标建立了机场登机口分配模型,采用线性松弛法和启发式算法求解该模型,结果表明,启发式算法的性能接近最优。冯程等[6]基于传统滑行路径理念,建立了降低旅客进出机场空侧时间的登机口分配模型,采用启发式算法求解模型,取得了较好的分配效果。Jiang等[7]从乘客服务质量角度出发,建立了以缩短乘客步行总距离和均衡各航空公司的旅客平均步行距离为目标的登机口指派模型,采用Lingo软件进行仿真验证。上述研究表明,合理指派机场登机口位置可以有效降低乘客步行距离,提高机场服务满意度。

然后,从机场运行角度出发,Liu等[8]以最小化登机口空档间隔时间方差为优化目标建立了具有运行安全约束的鲁棒登机口分配模型,采用遗传算法求解该问题。Kim等[9]通过分析主要机场航班延时数据,建立了以最小化同一登机口的前后航班冲突率为目标的登机口分配模型,采用启发式贪婪算法求解模型。Yu等[10]在顾忌机场运营成本基础上,提出了鲁棒登机口分配模型,设计了一种自适应大规模领域搜索算法求解该模型。王岩华等[11]在考虑航班属性、机位尺寸等约束条件下,以航班靠桥率和廊桥周转率为优化目标建立了繁忙机场登机口分配模型,并利用混合集合规划方法求解算法模型,结果表明混合集合规划方法有效提升了航班靠桥率。Tan等[12]针对非正常抵达航班导致的登机口分配不确定性问题,提出了一种基于航班到达时间分析的鲁棒登机口分配方案,并利用遗传算法实现模型求解,从而减小了航班计划变化对初始分配结果的影响。刘君强[13]等对多航站楼机场登机口分配问题进行了研究,建立了基于协同决策并考虑航司时隙交换公平性的登机口实时分配模型,采用混合集合规划进行模型求解。随着机场登机口分配模型研究的不断深入,基于多目标优化的登机口分配模型成为研究热点,多目标情况下的登机口分配模型求解较为困难[14-15]。Zhu等[16]建立了机场登机口分配多目标0-1线性规划模型,考虑了乘客航站楼内行走总距离和航班延误成本两个优化目标。Deng等[17]建立了机场登机口多目标优化模型,该模型综合考虑了旅客行走距离、登机口空挡间隔时间方差、分配在固定登机口航班数量和宽登机口使用率4个优化目标,并采用线性加权法实现多目标优化向单目标优化的转变,然后采用粒子群算法求解该模型。Zhang等[18]在考虑机型、相邻登机口冲突等约束条件基础上,以最小化航班延迟数、登机口变更比例和中转失败乘客数为优化目标,建立了基于多商品流网络模型的登机口重分配模型,利用两种启发式算法完成真实数据验证。

由上述国内外研究现状可知,单纯的机场登机口分配问题已经得到了较好的解决,且有成熟的产品满足航司和地勤服务公司的应用需求,但是在实现登机口优化分配的同时考虑中转旅客行走时间和距离的研究有限[19]。针对大型枢纽机场新建卫星厅,本文在考虑航班类型、机体类型和转场时间间隔等约束条件基础上,建立了以成功分配航班数至固定登机口最多、中转旅客的总体最短流程时间最小以及固定登机口使用数量最少为优化目标的机场登机口分配模型,利用贪婪算法计算生成初始种群,并利用遗传算法实现模型求解,最后用一组大型枢纽机场的实际运营数据对本文所提出的登机口优化分配模型和算法进行验证。

1 问题描述

由于城市建设规模的快速发展,该市机场现有航站楼T的旅客流量已经达到饱和状态,为了应对未来的发展,在航站楼T附近新建了卫星厅S,航站楼T和卫星厅S之间有捷运线相通,其布局设计如图1所示。新建卫星厅后原有航站楼的运营保障压力得到了极大缓解,同时航班靠桥率也相应得到了提升,但是新建卫星厅对于部分中转旅客的航班衔接产生了较大的负面影响[20]。将中转旅客换乘因素作为登机口分配优化目标之一,实现机场登机口多目标优化是目前大型枢纽机场亟待解决的问题之一。本文研究以中转旅客的总体最短流程时间最小、分配至固定登机口的航班数量最多以及登机口使用数量最少为目标的航班-登机口分配问题,在有效提高机场登机口资源使用率的同时,提升中转旅客的出行满意度。

航站楼T具备完整的国际机场航站楼功能,包括出发、到达、出入境和候机,而卫星厅S仅可以提供出发、到达和候机功能,无出入境功能。对于中转旅客来说,换乘航班时需要有一定的时间办理相关手续,定义该时间为中转旅客最短流程时间。对于任一中转旅客,其最短流程时间由到达航班类型、登机口区域以及出发航班类型决定,共有16种不同组合场景,表1给出了16种不同组合场景下的最短流程时间。

表1 最短流程时间

2 航班-登机口分配模型

2.1 模型假设

为构建机场登机口多目标优化模型,航班-登机口的分配需要考虑如下规则。

(1) 机场临时停机位数量满足该时段内所有未分配到固定登机口的航班停靠,且对停靠的飞机无约束。

(2) 由同一架飞机执行的到达和出发两个航班只能分配在同一停机位,飞机停靠期间不可挪移至其他位置。

(3) 飞机转场信息、旅客信息和登机口信息等均已知,且不考虑当天退票情况。

(4) 机场所有登机口的功能属性不能改变,且转场航班只能停靠在与之属性相匹配的登机口。

(5) 分配在同一登机口的相邻两个航班之间的空档间隔时间不小于45 min。

2.2 模型建立

2.2.1 约束条件

假设机场在某时间段内需要安排的转场航班数为M,机场固定登机口数为N,在该段时间内有效的中转旅客组数为P,令i、j、l分别表示第i个转场航班、第j个登机口和第l组旅客(i=1,2,…,M;j=1,2,…,N;l=1,2,…,P)。

令xi,j为航班-登机口分配问题的决策变量,定义该变量取值为

(1)

根据机场实际运营情况,并考虑模型假设,建立如下的决策变量约束条件。

(1) 唯一性约束为

(2)

式(2)保证一架飞机只能安排在一个固定登机口,且中途不会被挪移。

(2) 到达航班类型约束为

|(T1,i-T2,j)xi,j|≠1

(3)

式中:T1,i表示转场航班i的到达航班类型;T2,j表示登机口j接受的到达航班类型。

T1,i=0表示转场航班i来自国外,T1,i=1表示转场航班i来自国内;T2,j=0表示登机口j接受来自国外的航班,T2,j=1表示登机口j接受来自国内的航班,T2,j=3表示登机口j能接受来自国外和国内的航班。式(3)保证航班的到达类型与登机口可接受的类型相匹配。

(3) 出发航班类型约束为

|(T3,i-T4,j)xi,j|≠1

(4)

式中:T3,i表示转场航班i的出发航班类型;T4,j表示登机口j接受的出发航班类型。

T3,i=0表示转场航班i目的地为国外,T3,i=1表示转场航班i目的地为国内;T4,j=0表示登机口j接受发往国外的航班,T4,j=1表示登机口j接受发往国内的航班,T4,j=3表示登机口j能接受发往国外和国内的航班。式(4)保证航班的出发类型与登机口可接受的类型相匹配。

(4) 机体类型约束为

(T5,i-T6,j)xi,j≥0

(5)

式中:T5,i表示转场航班i的机体类型;T6,j表示登机口j接受的机体类型。

T5,i=1表示转场航班i为宽体机,T5,i=2表示转场航班i为窄体机;T6,j=1表示登机口j可接受宽体机,T6,j=2表示登机口j可接受窄体机。式(5)保证航班的机体类型与登机口可接受的类型相匹配。

(5) 间隔时间约束

(6)

2.2.2 目标函数

根据机场运营情况,航班-登机口分配问题在满足上述约束条件下,需要尽可能地优化如下3个目标,以高效利用机场资源,同时提高换乘旅客的舒适度。由上述定义可知,机场固定登机口数为N,同时根据模型假设可知,临时停机位对停靠的飞机无约束,因此可以定义所有的临时停机位为第N+1个登机口,应用本文所定义的符号,可建立如下目标函数。

优化目标1为

(7)

式中:xi,N+1表示航班i分配在临时停机位的决策变量;J1表示被分配到临时停机位的飞机数量,即没有分配到固定登机口的飞机数量,该优化目标为尽可能多地将航班安排至固定登机口。

优化目标2为

(8)

式中;J2为中转旅客的总体最短流程时间;pl表示第l组中转旅客随行人数;τl表示第l组中转旅客的最短流程时间,其数值如表1所示,该优化目标为最小化中转旅客的总体最短流程时间。

优化目标3为

(9)

根据以上3个优化目标的定义可知,这3个目标之间是互相拮抗的,无法同时满足。目标函数的优先级为:尽可能多地将航班安排至固定登机口(minJ1)>最小化中转旅客的总体最短流程时间(minJ2)>最小化被使用登机口的数量(minJ3),即首先满足优化目标1,其次满足优化目标2,最后满足优化目标3。实现多目标优化问题求解的第一步是将多目标优化问题转化为单目标优化问题,线性加权是多目标优化广泛使用的一种模型,通过给不同的目标函数制定相应的权重,将多目标优化问题转化为单目标优化问题[21-22]。因此,多目标优化模型可以写成如下形式:

minJ=w1·J1+w2·J2+w3·J3

(10)

式中:J表示总体优化目标综合效用函数;w1、w2和w3分别表示优化目标1～3的权重值,且w1+w2+w3=1,其权重具体分配一般通过多次实验确定。

综上分析,可以建立如下的多目标多约束机场登机口优化分配模型:

(11)

3 算法设计

将航班抽象为物体,将航班在机场转场的时间抽象为物体体积,则该问题就转化为典型的背包问题,即如何使用最少的背包装入最大的价值。求解背包问题有多种算法,比如遗传算法、贪婪算法、粒子群算法和禁忌搜索算法等[23-25]。贪婪算法以自顶而下的方式进行搜索,在问题求解的每一个阶段都做出一个在一定标准下看似最优的决策,能快速求得可行解,但通常不是全局最优解,是求解最优化问题最简便的方法之一。遗传算法对登机口分配问题没有太多的数学要求,搜索过程中不需要问题的内在性质,其在牺牲一定时间代价的情形下可以获得全局最优解。传统遗传算法的初始种群设置具有较强的随机性,其个体适应度不高,降低了算法收敛速度。为此,本文借鉴贪婪算法局部寻优的特点,设计贪婪策略,利用贪婪算法得到的航班-登机口分配方案赋值遗传算法初始种群,并利用遗传算法求解最优航班-登机口分配方案。

3.1 初始种群获取

贪婪算法的核心是选择一种适合的贪婪策略[26-27],在航班-登机口优化目标中,最大化航班靠桥率,即将航班尽可能多地安排至廊桥登机口,符合贪婪算法的基本特性。因此,基于贪婪算法求解初始种群在一定程度上可以提高遗传算法求解效率,本文选择如下贪婪策略。

贪婪策略:转场航班依次到达机场,按照“先到先分配”的原则对航班计划进行排序。对于每个到达航班,优先指派航班至空闲时间间隔最小的登机口,具体实现步骤如下。

步骤 1初始化参数。将航班按照到达时间进行排序,先到达的航班优先分配登机口。设定登机口的空闲时间为上一架飞机的离港时间。

步骤 2求解局部最优解。对于每个到达航班,寻找其与登机口空闲时间间隔最小的登机口作为局部最优解,若转场航班i占用登机口j,则xi,j=1,否则xi,j=0。

步骤 3若某一转场航班经过多次尝试仍然无法分配到适合的登机口,则将该航班安排至临时停机位。

步骤 4遍历待分配航班,为所有计划内的航班分配适合的登机口。

用于生成初始种群的贪婪算法流程图如图2所示。

图2 贪婪算法流程图

3.2 遗传算法

根据上述分析可知,航班-登机口分配问题属于多目标动态规划问题,且含有多个约束条件,是一个典型的NP(nondeterministic polynomially)-hard问题。遗传算法是一种典型的智能优化算法,通过模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程实现模型求解,被广泛应用于求解NP-hard问题[28-29]。针对多目标、多约束的航班-登机口分配优化问题,本文利用带精英策略的遗传算法求解该问题。遗传算法从一组随机生成的初始解,也称为“种群”开始搜索,由上文分析可知,本文利用贪婪算法得到的航班-登机口分配结果赋值遗传算法初始种群。染色体是一串符号,这些染色体在后续迭代中进化就是遗传,其后代根据前一代染色体的“交叉”和“变异”运算形成,并且在每一代进化中通过计算个体的适应度来评价染色体的“好坏”,算法经过若干次迭代后,将收敛于最优染色体,即为问题的解。本文采用的遗传算法中一条染色体表示一个航班-登机口分配方案,每条染色体中包含若干个基因(基因个数由需要转场的航班对数量决定),第i个基因表示第i个转场航班对,基因上的数字表示对应航班停靠的登机口序号。在该染色体中,每个基因能选择的登机口序号除简易临时机位外,必须满足对应飞机和登机口在机型(宽/窄)、航班到达或出发类型(国内/国外)等约束条件上的完全匹配,染色体示意图如图3所示,本文使用带精英策略的遗传算法进行求解,算法流程如图4所示,算法实现过程如算法1所示。

算法 1 遗传算法(1) Begin(2) t=0;(3) Initialize P(t);(4) Evaluate P(t);(5) While not finished do(6) Begin(7) t←t+1;(8) Genetic operate P(t);(9) Evaluate P(t);(10) End(11) End

图4 遗传算法流程图

算法1中P(t)表示遗传算法更新第t代种群,结合图4和算法1,带精英策略的遗传算法具体实施步骤可表述如下。

步骤 1初始化遗传算法参数。设定种群大小为NP,染色体长度即需要转场的航班对数量为M,最大遗传代数为G。

步骤 2根据飞机转场信息、旅客信息以及机场登机口信息,利用贪婪算法生成遗传算法初始种群。

步骤 3根据第2节建立的登机口分配模型目标函数计算个体适应度,并对每代群体按照适应度值降序排序,取适应度值最大的个体染色体作为精英保留,适应度函数表达式为

(12)

式中:w1取值为0.7;w2取值为0.2;w3取值为0.1;Fit表示登机口优化分配适应度函数变量;Fmax为极大的正数使得Fit恒大于零,并根据个体适应度值分配计算个体被遗传到下一代群体的概率及其累积概率:

(13)

(14)

式中:ii=1,2,…,NP,fii表示第ii个个体的适应度值;pii和qii分别表示第ii个个体被遗传到下一代群体的概率和累积概率。

步骤 4对染色体进行选择操作,首先采用轮盘赌算法选择染色体,若所有的染色体具有相等的适应度值,则通过服从均匀分布的随机数对染色体进行随机性选择。

步骤 5对染色体进行交叉操作,生成两个随机正数t1和t2,将其作为需要截取的染色体片段,并采用双点杂交策略进行染色体交叉操作,染色体交叉操作过程示意图如图5所示。

为了提高遗传算法收敛速度,在遗传进化后期引入自适应交叉算子,本文在Srinvias等[30]提出的自适应遗传算法基础上对遗传算子计算公式进行了改进,使得交叉算子恒大于零,减小遗传进化走向局部最优解的概率,本文提出的改进自适应交叉算子计算公式为

(15)

式中:Pc表示交叉算子;fmax表示种群中个体最大适应度值;favg表示每一代种群平均适应度值;k1>k2,本文通过多次调整参数进行实验,设置k1为0.7,k2为0.4。

而在遗传进化初期,为提升种群的多样性,依然采用较大的固定交叉概率进行算法迭代,因此,设置交叉算子Pc为常数0.7。

步骤 6对染色体进行变异操作,生成随机正数作为需要变异染色体的基因位置,并将该位置登机口变异为1～N间随机正整数。

和自适应交叉算子设置类似,本文提出的改进自适应变异算子计算公式为

(16)

式中:Pm表示变异算子;k3>k4,本文通过多次调整参数进行实验,设置k3为0.1,k4为0.05。在遗传进化初期,采用较大的固定变异概率进行算法迭代,设置变异算子Pm为常数0.1。

步骤 7计算经选择、交叉和变异后的种群个体适应度,按照适应度值进行降序排序,淘汰适应度值最小的个体,并使用上一代精英补充,更新精英个体。

遗传迭代后期为提高个体间的竞争,本文通过扩大个体适应度值的差异程度提高算法最优解搜索能力,因此进化后期调整适应度函数为

(17)

式中:n为大于零的正整数,本文根据实际数据验证取值为2。

步骤 8重复执行步骤4至步骤7共计G次,获得最优航班-登机口分配结果,停止演化,取演化最后适应度值最高的个体作为最后遗传算法求得的全局最优解。

4 实例验证及分析

4.1 基于贪婪-遗传算法的登机口分配结果

实验数据来源于国内某大型枢纽机场,其中航站楼T有28个登机口,卫星厅S有41个登机口。登机口的属性包括:所在终端厅(T/S)、区域位置(North/Center/South/East)、能接受的航班到达类型(国际I/国内D)、能接受的航班出发类型(国际I/国内D)以及能停靠飞机的宽窄类型(宽W/窄N)。登机口属性不可修改,且只能接受航班到达类型、出发类型、机体宽窄类型以及适合的转场计划。根据统计,当天转场航班架次为303次,在该机场共有1 649组中转旅客,飞机转场信息、旅客信息以及登机口信息示例如表2～表4所示。

表2 飞机转场信息

表3 旅客信息

表4 登机口信息

根据待分配登机口的航班计划初始化遗传算法基本参数,其中,种群数量NP为60,染色体长度M为303,最大遗传代数G为600,当遗传代数大于480时表示遗传进化进入后期。

编写航班-登机口分配算法程序进行模型求解,登机口航班占用时间分配如图6所示,图7为航站楼T和卫星厅S各登机口分配航班数量及其使用率统计,图8为中转旅客最短流程时间占比统计。

图7 各登机口分配航班数量统计

图8 中转旅客最短流程时间占比统计

分析图6～图8,可以得到以下主要结论:

(1) 根据图6统计可知,本文所提出的算法成功为524架次航班(262架飞机)分配了登机口,占航班总数的86.47%,共使用了67个登机口,成功分配宽体机航班架次为82,分配成功率为83.67%,成功分配窄体机航班架次为442,分配成功率为87.01%。

(2) 由图7可以看出,航站楼T共有28个登机口被使用,其平均使用率为61.09%,卫星厅S共有39个登机口被使用,其平均使用率为56.22%。由此可知,在20日一天时间内,航站楼T登机口的平均使用率略高于卫星厅S,主要原因是卫星厅在一定程度上会增加旅客的换乘时间,从而导致算法在优化登机口分配方案时,更倾向于将飞机优先安排至航站楼T的登机口。

(3) 由图8可以看出,中转旅客最短流程时间为20 min的旅客数占比最大,为20.07%,最短流程时间为45 min的旅客占比相对较小,为11.34%,这说明大部分旅客有充足的时间用来换乘,验证了模型和方法的有效性。

4.2 登机口指派结果比较分析

为进一步说明本文基于贪婪-遗传算法的机场登机口优化模型求解方法的有效性,将本文登机口分配方案与采用相同数据的航班“先到先分配”随机指派结果、基于贪婪算法的登机口指派结果以及基于禁忌搜索算法[31]的登机口指派结果进行比较,结果如表5～表7所示。

表5 中转航班登机口分配结果对比

表6 航站楼T和卫星厅S的登机口使用情况

表7 中转旅客总体最短流程时间统计

由表5～表7可以看出,基于航班计划,按“先到先分配”随机指派策略的航班分配成功架次为478,登机口使用数量为69,其中航站楼T和卫星厅S的登机口平均使用率分别为64.76%和46.72%,中转旅客的总体最短流程时间为75 170 min。在贪婪算法实现登机口预分配结果基础上,使用遗传算法进行迭代优化后,成功分配航班架次为524,航班-登机口成功分配率提高了9.62%,登机口使用数为67个,且登机口平均使用率得到提高,中转旅客总体最短流程时间为63 156 min,相比“先到先分配”随机指派分配结果降低了15.98%。进一步对比文献[31]中基于禁忌搜索算法得到的登机口分配结果可以看出,本文所提出的登机口分配算法能够将更多的中转航班分配至固定登机口,且旅客总体最短流程时间相比禁忌搜索算法降低了2.44%。由此可知,基于贪婪-遗传算法的登机口优化方法能够有效提高航班-登机口分配成功率,显著减小中转旅客换乘时间,且登机口的使用效率得到提升,验证了模型和算法的有效性。

5 结 论

(1) 本文对具有卫星厅的枢纽机场登机口分配问题进行了研究,以提升中转旅客换乘满意度为优化目标,提出在最大化分配航班至固定登机口的基础上,最小化中转旅客总体最短流程时间和固定登机口使用数量,建立了适用于具有卫星厅的机场登机口分配优化模型。

(2) 设计了遗传算法染色体表现形式,给出了基于贪婪-遗传算法的登机口分配模型求解流程和算法实现过程,并利用带精英策略的遗传算法实现登机口优化模型求解。

(3) 利用一组实例数据对所提出的模型和算法进行了验证,结果表明本文提出的航班-登机口分配模型和算法能够有效为过站航班指派适合的登机口。