航站楼旅客行李提取转盘的指派优化分析

颜建影 石丽娜 黄自鹏

摘  要：我国机场旅客吞吐量的不断增长导致航站楼内运行资源越发紧张。为提高旅客行李提取转盘运行效率，将遗传算法用于行李提取转盘分配问题中，以行李提取转盘的均衡使用为目标函数，根据函数模型，设计遗传算法求解步骤，并采用MATLAB进行仿真分析。与采用蚁群算法的行李提取转盘指派方式的结果进行对比，表明在优化行李提取转盘分配和使用效率问题上，遗传算法比蚁群算法的指派方式更优，达到了目标要求，提供了一种为解决机场行李提取转盘指派问题的可行方法。

关键词：航空运输;行李提取转盘;遗传算法;指派

中图分类号：F560    文献标识码：A

Abstract： With the continuous increase of passenger through put of airports in China， the operating resources in the terminal are becoming more and more tight. In order to improve the operating efficiency of luggage claiming turntables， genetic algorithm was applied and the balanced use of luggage claiming turntables was taken as the objective function. According to function model， genetic algorithm solution steps were designed， and MATLAB was used for simulation analysis. The results show that the genetic algorithm was more efficient than the ant colony algorithm in optimizing the claiming turntables allocation and service efficiency. The target requirement was satisfied， and a feasible method to solve the problem of airport luggage claiming turntables assignment was provided.

Key words： air transportation; luggage claiming tables; genetic algorithm; assignment

0  引  言

我國民航经济的快速发展带动了机场客流的迅猛增长，2019年我国机场旅客吞吐量达到了12.6亿人次，作为到港旅客流程的重要环节——行李提取，未能合理、便捷、高效处理，已成为近几年影响机场运行和旅客满意度的重要因素。而且目前大多数机场行李提取转盘规模仍维持原有规模，吞吐量的增加不仅加剧了行李提取问题的难度和复杂性，而且降低了机场的运行效率。因此，优化行李提取问题，对于航空公司和机场都有着重要意义。Ascó等人对离港行李分拣站整体进行了研究，得出工作均衡和缓冲时间是影响行李分拣站效率的关键因素，然后使用进化算法以工作均衡和缓冲时间最短为模型进行求解，以获得优化分配方案[1]。蔡翔针对大型枢纽机场行李分拣站的实际运行需求，提出了一种行李分拣站的分配优化模型，并采用活动选择算法求解该模型，以获得优化的分配方案[2]。De Neufville和Odoni则通过对行李提取区域进行研究后发现，行李提取传送带的长度尤为关键，而且也是不可缺少的一项影响要素[3]。陆讯通过对离港行李提取区域进行研究，表明行李提取转盘的分配，是影响行李提取区域拥挤问题的关键，并设计了蚁群算法来解决行李提取转盘的分配问题[4-5]。

从上述研究成果不难发现，已有的研究主要针对行李分拣站方面，尽管国内外一些学者对离港行李提取区域进行过研究，但对行李提取转盘指派问题的研究却不多。事实上，行李提取转盘的分配问题是至关重要的，从某种程度上来看，将会对是否应用均衡以及运行效率产生重要影响，最后关系到总体的运营效率。所以，本文采用遗传算法对行李提取转盘指派问题进行仿真优化研究，并将计算结果与采用蚁群算法的指派方式结果进行比较，以验证本文设计遗传算法的有效性。

1  行李提取转盘问题

1.1  行李提取区域运行效率的影响因素

美国交通运输研究委员调查得出行李提取转盘的指派直接影响行李提取区域的运行效率，即主要影响行李提取区域等待旅客的拥挤程度与可用空间。因此对行李转盘的分配优化是有必要的。

当前，在指派行李转盘时，比较常见的方法有以下两种，即：1∶1模式，即一个行李提取转盘服务一个航班;1∶N模式，即一个行李提取转盘服务于多个航班。综上分析，基于实际大型枢纽机场考虑，当前机场航班和行李转盘的分配主要是这两种方式结合的形式。因此，本文指派模型的建立主要基于这两种方式。

1.2  模型目标函数的选择

通过上述对行李转盘区域进行分析后发现，由于各个转盘之间，相对距离比较小，一旦行李提取转盘使用不均，会使行李负担较大的提取转盘旁旅客拥挤，同时相比其他负担较少的转盘运行时间变长，而行李负担相对较少的转盘，则会造成闲置，造成整体效率降低。因此，模型的目标就是行李提取转盘的使用均衡，进而达到提高运行效率和旅客满意度，使区域内资源得到充分利用。

1.3  模型建立

经上文研究后可知，本文转盘指派问题采用的目标函数即为行李提取转盘的负荷均衡，也就是说，采取一系列的优化指派，使得行李最多的转盘行李件数尽可能小。

问题模型具体如下所示：

F=minmaxXV                                            （1）

s.t. x=1， ？坌i∈U                                           （2）

xv≤v， k∈U， j∈V                                        （3）

x∈0，1， i∈U， j∈V                                         （4）

式（3）內，I=p∈U|T-T<15， p≥15，Ti∈U指的是第i个航班的抵达时间，I指的是全部和第k个航班的抵达时间相差低于15min的全部航班的集合。设一个航班占用转盘的时间为15min。

式（1）表示使行李件数最多的转盘上的行李件数尽可能最小，以达到均衡每个提取转盘负荷的目的。

式（2）指的是各个到达航班仅可以在一个转盘上进行分配。

式（3）可知，在相同时段，一个转盘将会被很多航班占用，但是总体的行李件数应低于一个转盘的最大容量。

式（4）指的是参数值所取范围。

在这一模型中，所采用的符号与参数定义具体如下所述，即：

U：指派时间段T内进港航班集合，U>0，U=1，2，…，M;

V：指派时间段T内可以应用行李转盘集合，V>0，V=1，2，…，N;

T：第i个航班的到达时间，i∈U;

v：第i个航班托运行李件数，i∈V;

v：行李提取转盘在15分钟内可以同时提供服务的行李数的最大值，按照相关规定得出，本研究所设定的行李数为300件;

x：0-1型变量，基于第i个航班的行李考虑，如果被分配至第j个转盘，那么则等于1，不然则是0。

2  转盘指派问题算法设计

2.1  指派问题的遗传算法

遗传算法是当今所有进化计算的随机搜索和优化算法中最常用的。它不依赖于问题的某一特定领域，为解决复杂的系统优化问题提供了一个通用模式[6-7]。行李转盘分配问题在运筹学中属于NP难问题，NP难问题关于多项式时间的算法很难发现，若采用传统的算法，其计算量和计算难度将会成倍增加，因此运用更加快速有效的算法去解决这类问题变得越来越重要[8]。而遗传算法就具有解决此类问题的特有优势，通常直接选取目标函数做为适应度函数，并且对所研究的问题类型鲁棒性非常的强。其算法主要包括最优适应度的选择和遗传算子的选取，基于此将设计一种遗传算法用来解决该转盘的指派问题。

2.2  遗传算法实现

2.2.1  染色体编码和种群初始化

（1）染色体编码

本文染色体设计使用自然数编码，相比于二进制编码来说，该编码可以使各种问题得到有效解决，而且遗传算子操作也更加方便[9]。在对行李转盘进行编码的过程中，如果采用了非零自然数，基因则是行李转盘，按照每个航班抵达的时间次序，构成相应的染色体，其中第i位的取值表示第i架航班所分配的行李转盘。

例如：在一段时间内，按照航班到达时间顺序共有40个航班先后到达，行李提取转盘共有6个，按照自然数编码染色体，染色体的长度L为40，每一个基因的取值范围为1～6，如X染色体：

染色体X：3 2 4 5 3 2 4 1 6 3 2 5 4 1 6 2 1 3 1 5 6 4 2 3 1 3 1 4 5 6 4 1 5 6 4 1 3 1 6 5

其中：第1位的取值为3，就是表示第1架航班分配在第3个行李提取转盘上;第2位的取值为2，表示第2架航班分配在第2个行李转盘上，以此类推。

（2）种群初始化

初始种群的产生可通过计算机从可能解中以随机方式产生设定数量的染色体，即第一代种群。

从可能解中随机方式产生一个染色体，若该染色体满足模型中全部约束条件，则该个体称为解染色体，若该染色体不满足全部约束条件，则该染色体称为非解染色体。最初解染色体的全体称为初始种群，初始种群中解染色体的个体数称为种群规模[10]。

2.2.2  适应度函数及选择算子

（1）适应度函数

因为模型中目标函数为求最小值，而遗传算法适应度函数为求最大值，可采用取倒数的方式，故适应度函数为：

F=                                                 （5）

式中：f=xv，F表示每个染色体适应度的大小，F越大表示其可行解越好，越能够以较大概率遗传到下一代群体中。

在组合优化问题中，处理不可行解的一种常用方法即为惩罚函数法[11]，因此其适应度函数优化后设计如下：

F=                                               （6）

式中：ξ=ρPn为惩罚函数，本文中Pn=max0，xv-v，ρ为惩罚因子，本文中取ρ=4。

（2）选择算子

为了使种群的优良基因得到保证，选择算子增大父代适应度值大的个体遗传到下一代的几率，从而促使种群个体可以与最优解靠拢。本文在研究的过程中，采用了轮盘赌的方式进行处理。

P=                                                （7）

式中：P为染色体n被选择的概率;F为染色体n适应度函数值;n为染色体n=1，2，…，S;S为种群大小。

式中得出，如果适应度值比较高，那么遗传到下一代的几率也会随之加大。在此过程中，通过多次选择来选取迁移染色体，其中累计概率为：

Q=P    r=1，2，…，n                                        （8）

式中：Q为染色体n的累计概率;P为个体r被选择的概率。

算法每次选择时都会产生一个在0，1内的均匀随机数d，该随机数将作为确定被选染色体遗传到下一代的选择指针。若d

例如：设规模为pop=5的种群S=nnnnn，染色体适应度F=20，F=17，F=10，F=29，F=16，染色体的选择概率Pn=1，2，…，5，其计算结果如下：P=0.21，P=0.18，P=0.10，P=0.32，P=0.17。

則每个染色体的累加概率Q，结果如下：Q=0.21，Q=0.41，Q=0.52，Q=0.83，Q=1.0。

通过转动轮盘5次，每次在0，1之间产生一个均匀随机数，得到5个随机数为：d=0.23，d=0.57，d=0.79，d=0.93，

d=0.35。

先从d=0.23开始观察，位于Q与Q之间，因此选择染色体Q遗传到下一代;接着d=0.57位于QQ之间，因此选择染色体Q遗传到下一代;依次下去，新种群S=nnnnn。

2.2.3  交叉算子

在遗传算法中，通过交叉操作来模拟自然界生物进化过程中的基因重组，以此希望进化出更为优良的下一代个体，得到想要最优解的同时能够以更快更好的方式。

本文采用单点交叉进行交叉操作，如表1所示。两个父代染色体的交叉操作，首先通过随机方式产生一个整数i，0

2.2.4  变异算子

在种群规模一定下的遗传算法，其广度搜索能力越强，种群的多样性就要越大。因此增大群体多样性，扩展搜索空间，从而避免早熟，是变异算子的主要工作目标，本文采用适用于自然数编码的交换变异实现变异操作。随机产生两个变异变量i，ji，j≤L，交换第i个航班与第j个航班的基因位，如表2所示。

即首先对于需要变异操作的父代染色体W以一定的概率选取，再以随机方式选取该染色体的两个基因位i，j1≤i， j≤L，通过交换该两个基因位上的基因，新的染色体W从而形成。

2.2.5  运行参数

编码长度L：L=40。

种群规模S：规模大小的选取，既要考虑种群多样性也要考虑运行时间，本文取S=200。

交叉概率P：既要保证以较快的速度发现新个体，也要兼顾保护种群中已形成的优良个体，一般取值为0.40～0.99，因此本文取P=0.90。

变异概率：较小的变异概率对于避免早熟现象和增加新个体的能力会较差，较大的变异概率随机性过高，一般取值范围为0.005～0.100，本文取0.010。

迭代代数：算法运行结束的条件之一，一般取100～1 000，本文最大迭代次数为200次。

2.3  遗传算法的步骤

在进行操作的过程中，全部航班以及转盘，根据前文的算法进行设计，具体步骤如下所述，即：

Step1：将航班的基本信息输入至其中，行李提取转盘信息，算法参数;

Step2：编码染色体，采用随机的方式，形成初始种群，设置最大迭代次数及迭代计数器[12]。令遗传代数初始化，初始令g

=1;

Step3：计算染色体适应值，对种群染色体适应值进行评价;

Step4：判断终止条件：满足，将会得到相应的群体适应值，将最优结果输出之后，完成算法：不满足，则令g=g+1，继续执行以下步骤;

Step5：对算法群体执行遗传操作：采用轮盘赌方法选择算子，选择出适应度较大的个体，进行交叉变异，产生新一代种群群体，返至Step3。

遗传算法具体流程图如图1所示。

3  算例仿真与分析

本文采用的算例以文献[5]中的数据为原始数据，机场航站楼共有旅客行李提取转盘6个，根据航班时刻表，40个航班先后从10：00到11：00到达，各个航班到达时间和行李件数如表3所示。

该文献采用的蚁群算法指派方式，得到的结果如表4所示。

与本文设计的遗传算法相结合，通过对MATLAB 求解程序进行编写之后，解本实例。设置种群规模为200，交叉概率P

=0.90，变异概率P=0.01，最大迭代次数为200次，得到遗传算法最优点变化趋势图，如图2所示。对行李提取转盘指派的结果如表5所示。

对遗传算法和蚁群算法两种结果进行对比分析后，结果如表6所示。

根据表6中的对比结果，采用遗传算法得到的服务行李件数的极差为20，比蚁群算法缩小了约2.5倍。均方差是334，比蚁群算法缩小了约5.5倍，均低于蚁群算法指派结果。表明各个行李提取转盘的行李数量更均衡，达到了预期的目标。说明了本文对行李提取转盘指派问题的优化采用遗传算法是可行的。

4  结  论

本文为机场旅客行李提取转盘指派问题的优化研究，依据相应的指派模型，其目标以均衡使用行李提取转盘，对遗传算法求解步骤进行了设计。通过实例结果分析，表明遗传算法对于优化行李提取转盘分配的可行性和优越性，提出了一种对解决机场旅客行李提取转盘指派问题的可行方法，为机场服务质量的提升提供了参考。

参考文献：

[1]  Ascó A， Atkin J A D， Burke E K. The airport baggage sorting station allocation problem[C] // Proceedings of the 5th Multidisciplinary International Conference on Scheduling： Theory and Application （MISTA 2011）. USA： [s.n.]， 2011：419-444.

[2] 蔡翔. 机场行李分拣站的分配优化研究[J]. 机械工程与自动化，2017（5）：37-39.

[3] Neufville D， Odoni. Airport Systems： Planning， Design， and Management[M]. McGraw-Hill Professional， 2000：63-68.

[4] 陆迅，朱金福，唐小卫. 多航班多行李提取模型[J]. 交通运输工程学报，2008，8（5）：104-108.

[5] 陆迅. 机场旅客与行李流程的规划和仿真研究[D]. 南京：南京航空航天大学（博士学位论文），2008.

[6] 李险峰. 基于改进遗传算法的汽车装配生产线平衡问题研究[D]. 北京：北京科技大学（博士学位论文），2017.

[7] 陈宵. DNA遗传算法及应用研究[D]. 杭州：浙江大学（博士学位论文），2010.

[8] 黄文奇，许如初. 近世计算理论导引：NP难度问题的背景、前景及其求解算法研究[M]. 北京：科学出版社，2004：87-88.

[9] 李明. 遺传算法的改进及其在优化问题中的应用研究[D]. 长春：吉林大学（硕士学位论文），2004.

[10]  TAO Y， TANG D， SHEN H. Design and implementation of USB key-based Java EE dual-factor authentication system[C]

// Proceed-ings of the 2009 International Conference on Information Manage-ment， Innovation Management and Industrial Engineering. Wash-ington， DC： IEEE Computer Society， 2009：443-446.

[11]  Kalyanmoy Deb. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics and Engineering， 2000，186（2）：311-338.

[12] 雷英杰，张善文. MATLAB遗传算法工具箱及应用[M]. 西安：西安电子科技大学出版社，2014.