宋阿妮 包贤哲

(湖北工业大学电气与电子工程学院 湖北 武汉 430068)

0 引 言

随着人民收入水平的提高和旅游业的蓬勃发展,机场客机数量开始迅速增长,各大机场登机口资源都面临着严峻考验。机场登机口的合理分配将会大幅度降低机场运营成本和旅客登机时间,减少支出的同时提升乘客服务质量,所以如何合理分配机场登机口资源是所有大型机场亟待解决的重要问题[1-3]。

目前机场分配登机口方案往往根据日常经验,没有理论依据,导致登机口数量无法满足机场飞机的正常使用,而盲目新建航站楼和登机口又会造成资源浪费并增加乘客登机时间降低服务质量。

国内外学者针对登机口分配问题进行了大量研究,但到目前为止仍然没有一套非常完整的处理方案和体系。其中文献[4-6]运用遗传算法求解登机口分配问题,但由于遗传算法所需设置参数过多,模型建立复杂很难在实际情况中得到运用。Drex等[7]的模型中加入了机场对登机口的人为偏好因素,建立了多目标优化数学模型,最后通过帕累托模拟退火算法求解其分配序列,但如何确定人为偏好因素的相关参数却是一个难题。文献[8-9]设计了以乘客转机时间为优化目标的分配模型,利用禁忌搜索算法以及混合的禁忌搜索算法求解登机口分配问题,虽然得到了登机口分配最优解,但其数学模型和算法只适用于无约束的登机口分配问题,难以运用在复杂的现实登机口问题中。黄帮菊等[10]用贪心算法对机场登机口进行多目标优化求解,获得了较好的分配结果,但是却出现了登机口分配不均匀的现象造成登机口闲置的资源浪费问题。衡红军等[11]利用最邻近算法构建了由出港航班和到港航班组成的车辆行驶总路程最短的子路径集合,再依据子路径间的时间衔接关系将子路径进行优化组合,将所有子路径任务合理分配给行李运输车,并同时保证了所需车辆数最少和车辆任务量均衡的目标,这一规划机场运输车的调度问题与航班在某个登机口出发或降落有着密切的关系,提出的算法对机场登机口分配问题有一定的参考价值。该算法虽然能够提供较为合理的分配方案,但其模型及实现较为复杂,对于大型机场而言,实际运用性不高,且仍然存在着算法结果收敛缓慢等问题;Bouras等[12]则尝试用启发式算法解决机场登机口分配问题,但在分配登机口的时间流程上依然存在不足。

因此本文对大型机场登机口分配问题进行了研究,提出了一种多种群变异非线性动态粒子群算法(Multi-population Mutation Nonlinear Dynamic Particle Swarm Algorithm, PMNDPSO)求解该模型。首先对机场登机口与飞机起落时间进行合理分类以简化模型优化相关参数,然后以分配的登机口数量最少作为优化目标,设立多个粒子种群进化、变异并寻找最优个体放入优质种群,然后用典型线性递减策略和动态策略相结合的复合方式改进的进化公式对优质种群再次进行迭代进化,最终求解得到机场登机口的分配序列。

1 问题分析与模型建立

机场设有两个航站楼分别为航站楼T与航站楼S,航站楼T拥有m个登机口,航站楼S拥有n个登机口,每个登机口负责接纳固定机型的飞机,拥有供飞机停靠的所有技术设备,航站楼登机口情况如图1所示。

图1 机场航站楼和登机口示意图

图2 飞机分配方法框图

1.1 模型假设

为了能够让研究问题时更加方便,作出以下假设:

(1) 航站楼T与航站楼S所有的登机口除了型号以外完全相同,统筹分配。

(2) 每个登机口都拥有着国际出发/国际到达,国内出发/国内到达,宽体机/窄体机等固定属性,每个登机口只能停靠对应属性的飞机。

(3) 同一架飞机起飞与降落必须在同一登机口期间不能改变其停靠位置。多架飞机停靠于同一登机口时,间隔时间不得小于45分钟,用于登机口故障检修和清洁工作。

(4) 在登机口位置不足或两架停靠同一登机口的飞机间隔小于45分钟时,飞机被安排到临时登机口,临时登机口的数量不限。

1.2 模型建立

设某大型机场在一天内一共有k架飞机停靠,按照时间前后顺序为全部飞机进行编号,分别为V=(V1,V2,…,Vk),即飞机的到达时间满足:

TIV1

(1)

式中TIVi(i∈1,…,k)表示在该机场停靠的飞机到达时间。然后将机场登机口也按顺序进行编号,T航站楼的登机口编号为T=(T1,T2,…,Tm),S航站楼的登机口编号为S=(S1,S2,…,Sn)。

将飞机按照属性进行分类:I表示国际出发/国际到达,D表示国内出发/国内到达,W代表宽体机,N代表窄体机,共可以分成IIN、IIW、IDN、IDW、DIN、DIW、DDN、DDW8个类别,对应相同属性的登机口。其中如IDN型飞机表示国际出发国内达到的窄体机。分类的方式如表1所示。

表1 飞机登机口分类示意表

在同一登机口停靠的飞机必须满足后一架飞机到达时间与前一架飞机的起飞时间间隔45分钟及以上,即:

(2)

(3)

式中:Ω用以记录被分配到航站楼中的登机口停靠的飞机数量,当飞机满足式(2)时,Ωi=1。

另外考虑到服务质量问题,为了让乘客得到更好的登机旅行体验,要尽可能保证乘客从候机室到达目的登机口的时间最短,这里假设所有乘客的步行速度相同,所以即要求乘客从候机厅到达登机口的距离最短,乘客的平均步行距离Lall为:

(4)

式中:Rj表示第j个乘客到达目的登机口的距离,一天之内一共有m位乘客在某机场登机出行;Rmax表示所有乘客中步行的最长距离。

机场每天会对登机口进行维护,在两架飞机到达该登机口的登机间隙会让工作人员对登机口进行基本清洁检查维护称为基本维护。另外,在一天的航班结束之后,会对当天启用的登机口进行全面的检查维修维护称为启用维护,这两者都会产生一定的维护费用,为了让机场每天的运维成本最低,要保证在安排时尽量少启用登机口数目,并将飞机尽量安排在基本清洁检查维护费用较低的登机口,产生的总体成本费用为:

(5)

式中:Si表示第i个登机口的每日的启用维护费用;Ci表示第i个登机口每次的基本维护费用;wi则表示一共有第i个登机口当天的基本维护次数,当天一共启用了y个登机口;Sall表示所有登机口全部启用所需的启用维护总费用;Cmax则表示所有登机口中的最大基本维护费用。

(6)

式中:Gpub为惩罚因子,表示所有未被分配到航站楼进入临时登机口的飞机总数。

按照表1所示方法,将飞机按照不同的类别一一进行分类,并依据时间先后排序。

最终模型所需优化的目标函数为:

(7)

式中:Gpub为惩罚因子,表示α1为惩罚因子的系数,可以根据实际需要更改该参数的数值,d表示分配所有飞机所使用的机场登机口总数。

2 改进的粒子群算法

2.1 经典粒子群算法

粒子群算法(Particle Swarm Optimization, PSO)是模仿鸟类觅食行为的一种群体协助的随机搜索算法,最早是由Eberhart和Kennedy于1995年提出。

经典粒子群算法模仿鸟类捕食,在一定空间内存在许多鸟,但只有一块食物,所有鸟不知道食物的具体位置,但却知道和食物的距离。通过不断地改变自身的方向和前进的速度最终让所有鸟找到该食物的位置即得到最优解。

首先设置最大迭代次数tmax表示种群搜索次数,设置粒子个数N,粒子的维数P,初始化所有粒子全部维数的前进速度,第n个粒子第p维的初始速度为Vnp,粒子速度的更新公式为:

Vnp=ωVnp+C1random(0,1)(Hnp-Xnp)+

C2random(0,1)(Hgd-Xnp)

(8)

式中:ω为惯性权重,为非负固定常数,通过调整ω的大小可以改变算法的前期和后期的搜索能力。C1、C2为加速常数,一般当C1=C2∈[0,4]时,算法有较好的搜索能力,Hnp表示第n个粒子进化过程中历史最优个体的第p维数值,Hgd则表示全局最优解的第p维数值。全部粒子的所有维数随着迭代次数的增加,其速度也在发生变化。每一次迭代,粒子就按照当前速度向全局最优解和历史最优解的方向改变自身位置,其位置更新公式为:

Xnp=Xnp+Vnp

(9)

所有粒子在不停的迭代过程中不断向着全局最优解和个体历史最优解靠近,最终收敛于最优值附近,这就是经典粒子群的搜索原理。

2.2 多种群非线性动态粒子群算法

2.2.1 多种群变异进化策略

经典粒子群算法很容易陷入局部最优导致早熟情况,为了能够保证粒子群算法在前期的搜索范围能够覆盖最优解,设定初始种群m+1个,其中前m个种群中粒子数都为N,最后一个种群为无任何粒子的空种群,将此空种群称为优质群,前m个粒子群按照式(8)的进化方式单独搜索最优解,当种群陷入局部最优解后将其当前全局最优解Higk放入第m+1个空种群中作为该优质群的新粒子xik,陷入局部最优解的粒子群开始变异并重新搜索下一个局部最优解,变异公式为:

xinpk=xinp(k-1)+random(0,1)×

(fmax(xinpk)-fmin(xinp))×(tmax-t)/tmax

(10)

式中:xinpk表示第i个种群第n个粒子第p维第k次变异的值,fmax(xinpk)即该粒子第p维第k次变异的历史最大值,fmin(xinpk)即该粒子第p维第k次变异的历史最小值, random(0,1)为(0,1)之间的随机数,tmax为最大迭代次数,t为当前迭代次数。其搜索变异过程如图3所示。

图3 多种群搜索变异过程图

粒子按照此方式依次将每个种群第k次变异的最优粒子放入优质群中,k是可以根据解的最终解的情况设定的变异次数,当所有种群已经达到最大变异次数并再次陷入局部最优时,优质群粒子成熟,此时该种群的优质个体的整体搜索范围将会覆盖所有可能的最优解,按照改进的进化公式可以快速准确地找到全局最优解,有效防止粒子群陷入早熟情况。

2.2.2 非线性动态惯性权重策略

经典粒子群算法以其搜索速度快,效率高且算法简单等优势很快被运用于各种优化问题上,但随着对粒子群算法了解的逐步深入,也发现了其容易陷入局部最优解的缺点。

为了能够使得登机口分配中粒子群算法不陷入局部最优解,提出一种非线性动态粒子群的改进方式,其惯性权重将典型非线性递减策略和动态策略相结合,能够有效地提高粒子群在后期的搜索准确性和速度。

(1) 非线性递减策略。粒子群算法的搜索过程是一个非线性搜索过程,在搜索前、中、后期的位置移动速度和收敛快慢都有所不同,所以为了能够尽可能符合粒子群的搜索规律,设定其非线性部分的惯性权重ω为:

(11)

式中:当ωmax=0.9,ωmin=0.4时,整个非线性部分的搜索效果较好,在计算式中加入指数函数,在算法前期即迭代次数较小时,算法前期的惯性权重较大、搜索步长较长,保证了算法前期的搜索范围,在搜索后期,t较大时,惯性权重跟随着算法的搜索规律快速减小,能够有效减小步长以缩小搜索域在局部范围内精确搜索找到最优结果。

(12)

(13)

(14)

式(14)中的ωq=1,ωp=0.5,ωu=0.13时,其搜索效果最好,进化速度因子小时,表明进化速度快,此时应适当降低粒子的进化速度不至于过快而导致部分粒子无法收敛,当进化速度因子逐渐增大时,表明算法进化速度在逐渐减慢,说明算法开始接近最优解附近,此时应逐渐减小惯性权重以保证算法的局部搜索精度,聚集度因子作为算法的另一特征参数,其功能与进化速度因子类似,聚集度因子较低时,表明粒子的搜索范围较广,搜索速度较快,聚集度因子较高时,粒子进入局部搜索,搜索速度减慢。将两个特征参数进行组合,使粒子群算法进化过程中不断根据自身规律更新惯性权重以满足当前迭代条次数下的搜索精度要求。

(3) 复合惯性权重。根据上述给出的动态策略部分的惯性权重式(14)和非线性递减策略部分惯性权重式(11)可以得到最终的复合惯性权重ωN为:

(15)

式中:λ1,λ2∈[0,1],根据式(15)得到的复合惯性权重综合了粒子迭代非线性变化过程以及其进化状态对算法的影响,相对于单独的惯性权重设定,前期能够保证足够大的搜索范围防止早熟,后期能够根据粒子的进化状态迅速收缩搜索范围得到局部精确解。

最终得到的复合惯性权重粒子群算法的速度更新公式为:

Vnp=ωNVnp+C1random(0,1)(Hnp-Xnp)+

C2random(0,1)(Hgd-Xnp)

(16)

优质群按照改进后的进化式(16)继续迭代进化,最终得到最优解。算法的整体运算过程如图4所示。

图4 MNPDPSO框图

3 实例验证

3.1 改进效果测试

为了测试改进策略的效果,现将提出的不同改进策略加在原先的算法上,分别得到采用多种群变异进化策略粒子群算法(PMPSO)、采用非线性动态复合策略粒子群算法(NDPSO),以及三者同时采用的本文提出的PMNDPSO,并采用Rastrigin’s、Ackley’s、Easom、Eggholder四种典型测试函数对这四种算法进行测试,粒子个数N=200,其他各参数设置全部采取实际问题中的变量取值,四种函数求解函数得到的最终各项信息数据如表2所示。

表2 改进策略测试效果表

表2中Min表示算法得到的最优解数值,Time则表示得到最优解所用的时间,Rate表示收敛到最优解的粒子个体数占总个体数的比例,可以看到采用多粒子群变异策略的粒子群算法(PMPSO)由于优化了初始粒子群,提高了粒子的多样性和优质性,前三个函数都能得到最优解且收敛率较高,但整体的搜索速度却较慢。加入了非线性动态复合策略的粒子群算法(DPSO)得到了前两个函数的最优解,但因为前期搜索范围和初始粒子多样性不足,导致在搜索后面两个较复杂的函数时其精度不高,由于其缩小了后期搜索范围改善了算法后期的搜索速度,所以找到最优解的时间较短,两种改进后的算法相对于传统PSO在搜索精度和搜索速度上都有显著提升,证明了上述改进策略的有效性,将所有改进策略同时引入PSO即本文提出的PMNDPSO,其改进效果如表3所示。

表3 整体改进效果信息表

根据表3数据可以得到看到,相对于传统PSO,改进后的PMNDPSO四个函数都能够搜索到最优解,且粒子收敛率相对于PSO有了显著提升,但是由于多种群进化方式提升了系统的时间复杂度,所以求解得到最优解的速度下降了,但由于机场登机口分配系统会提前安排次日的飞机登机口顺序,所以对时间响应度要求不高,影响可以忽略。根据上述函数测试表明,改进后的PMNDPSO在精度和收敛率上较传统PSO都有显著提升,也证明了算法改进的有效性。取最具代表性的Eggholder函数的迭代过程图如图5所示。

图5 Eggholder函数测试迭代图

3.2 求解登机口分配实例

设某国内机场有航站楼T与航站楼S,其中航站楼T一共拥有15个飞机登机口分别为T=(T1,T2,…,T15),航站楼S一共拥有22个飞机登机口分别为S=(S1,S2,…,S22),在某一天内一共有295架飞机在该机场降落,按照时间先后顺序给所有飞机排序分别表示为V=(V1,V2,…,V295)。

首先将登机口与飞机按属性进行分类匹配,一共可分为8种类型的登机口和飞机,每个型号的登机口以及该登机可以停靠的飞机数量等信息如表4所示。

表4 登机口与飞机匹配图

根据表4中登机口与飞机的匹配情况,将不同属性的飞机按照时间前后进行排序,该顺序就是飞机进入特定登机口的顺序序列,部分匹配相应登机口的飞机起飞降落时间表如表5所示。

表5 不同登机口匹配飞机起飞降落时刻表

该机场22个登机口的每次的基本维护费用以及启用维护费用和距离候机厅的距离信息如表6所示。

表6 登机口维护费用与位置信息表

为了能够验证PMNDPSO的运用效果,用传统粒子群(PSO)、蚁群算法(AG)、萤火虫算法以及PMNDPSO三种算法求解分类后的机场登机口匹配最佳方案。设粒子迭代次数t=250,粒子个数N=20,由于一共有295架飞机,所以粒子的维数P=295,进化粒子表示为x=(xi1,xi2,…,xi295),初始粒子进化速度Vnp=1,惯性权重式(10)中参数取值分别为ωq=1,ωp=0.5,ωu=0.13,最终得到的算法迭代结果如图6所示。

图6 算法迭代图

由图6中可以看到,改进后的PMNDPSO在迭代次数达到40次左右时收敛到最优解,而传统粒子群算法、萤火虫算法、蚁群算法的收敛相对较慢,且PMNDPSO能够得到更好的优化结果。四种算法求解得到的最终结果参数如表7所示。

表7 四种算法结果对比表

由表5可看出,PMNDPSO求解飞机登机口的综合效果要更好,其最优目标求解精度相对于FA、GA、PSO分别提高了23.13%、14.94%、8.01%,一共只启用了33个登机口就能基本满足所有飞机的降落起飞停靠需求并成功分配了276架飞机。但由于改进策略增加了算法的时间复杂度,所以计算解决方案的平均迭代时间相对下降了13.56%、27.03%、37.45%,不过机场登机口分配系统对时间响应度要求并不高,且算法之间时间差距并不大,所以此时间差对系统影响可以忽略。除此之外,相对于另外三种算法,PMNDPSO能够为机场节省更多预算,分配的方案所需成本最低,相对于另外三种算法分别提高了21.62%、22.52%、10.33%。且在该算法分配的方案下,乘客到达目标登机口的距离最短,距离相对于另外三种算法分别提高了52.43%、36.74%、23.90%,能够显著提升乘客的出行体验,提升机场服务质量。所以综合上述多个特性可以看出,PMNDPSO算法相对于GA、FA以及PSO,其各方面性能提升较为显著,在机场登机口分配问题上有着更好的适应性。用PMNDPSO计算所得飞机停靠登机口的匹配顺序结果如表8所示。

表8 飞机停靠登机口匹配顺序表

当日在该机场停靠的295架飞机中有276架飞机成功匹配,进入临时登机口的飞机仅为19架,匹配成功率达到93.56%,使用33个登机口,其中T6、T11、S5、S8四个登机口可以闲置不需要安排航班。

为了能够更为直观地看出每个登机口的飞机停靠时间的相对情况,将得出的匹配结果绘制成甘特图,如图7与图8所示。

图7 T航站楼飞机匹配登机口停靠时间甘特图

图8 S航站楼飞机匹配登机口停靠时间甘特图

4 结 语

本文针对机场登机口分配问题提出了一种PMNDPSO,该算法在初期设立多个种群进化变异,将每次变异迭代得到的每个种群的最优个体放入优质种群中,有效避免了粒子群前期陷入局部最优解,并让其搜索范围变得更广、更精确。优质种群进化公式中的惯性权重考虑到了粒子搜索的非线性过程以及粒子进化自身的状态,能够在搜索前期根据算法自身特性调整参数避免陷入早熟,在搜索后期也能够快速减小搜索范围在局部范围内找到更精确的结果,通过在传统PSO中逐步加入不同的策略进行测试,证明了上述改进的有效性。将其运用到登机口分配实例中,新提出的算法能够很好地为机场找到最佳的登机口分配方案并节省运营成本避免登机口资源的浪费和航班受阻并大幅度缩短旅客的登机时间,提升机场的整体服务质量。研究机场中途新增、取消相关航班的动态登机口优化系统问题将是下一步研究的目标。