颜建影，石丽娜

(上海工程技术大学 航空运输学院，上海 201620)

0 引 言

随着中国经济持续稳定的增长，对基础设施的投资越来越大，使得人们的出行越发方便，越来越多的普通百姓把飞机作为一种交通方式的选择，但随着乘坐飞机旅客的持续增多，使得机场的运行配置资源越发紧张，运行管理变的越发重要。当前，国内开始不断增建新机场或扩建机场，这种方式虽可以解决燃眉之急，但要想根本的解决机场运行资源紧张的局面，还要更加合理的使用运行资源，并且随着智能化、高效机场建设，对值机柜台资源的动态配置，提高服务效率变得更加重要。机场航站楼中运行最为复杂的流程为值机流程，因此对于提高旅客满意度，实现资源的高效利用具有重要作用[1]。因此，确定所需值机柜台配置数量是机场和航空公司对于旅客到达机场航站楼所需解决的首要问题。

此前，关于值机柜台资源分配问题，相关人员也进行了多方面的研究。文献[2]提出把值机柜台的分配问题转换成多维放置问题，即在空间有限的情况下，尽可能多的放置值机柜台。但其中并没考虑高峰期旅客排队等候值机，在机场值机区域有限的情况下，每多放置一个柜台旅客排队等候值机的区域则会相应减少，使得原本就拥挤的值机区域越发拥挤，反而使旅客满意度降低。文献[3]通过调查机场旅客到达时刻以及航班离港时间数据，建立值机柜台的指派优化模型，该模型采用计算机仿真软件运行模拟，并未涉及具体算法。文献[4]提出了协助机场分配公用值机柜台的整数规划模型，但该模型考虑的参数过多，求解过于复杂，实际应用困难。文献[5]建立了在达到旅客满意度的条件下，使人工成本最小的模型。该模型将值机和安检都考虑在内，并不是单纯对值机成本的求解，且对旅客的到达过程假设为单纯的指数分布，而实际中值机旅客的到达曲线往往为上下浮动的曲线。同时，随着自动值机设备的发展，使用自助值机设备进行值机的旅客也逐年增多。文献[6]中以同时考虑租用柜台成本和顾客时间成本为前提，将自助值机柜台转化为人工值机柜台进行分析，但在旅客值机的选择时只是单纯的将有行李的旅客分为人工值机，而无行李的旅客选择自助值机。文献[7]为求算最佳的值机柜台排班策略，运用派迩值机柜台规划实验系统，将人工值机柜台和自助值机柜台分开进行分析，求解最小的人工值机柜台成本。通过计算机对值机流程进行仿真分析，没有涉及到具体的算法且值机柜台开放数量始终为一定值，而现实中各个时段开放的值机数都是变化的。文献[8]将人工值机柜台和自助值机柜台资源共同分析研究，以所有旅客行走距离之和最短为优化目标，实现对自助值机柜台和人工值机柜台的合理分配，但文中并未考虑旅客的到达分布以及值机排队等待时间。

当前机场值机柜台的分配，越来越重视自助值机设备的使用。因此，本文在求解值机系统所得净收益最大时，首先将满足一定条件的旅客满意度约束考虑进去，然后在分析人工值机柜台时，将自助值机设备的使用情况也进行了分析，最后将自助值机设备使用产生的收益考虑进去。通过实例分析，最终得到相应的动态值机柜台分配数量，为机场航站楼值机系统柜台的资源配置提供一定的参考。

1 机场值机流程的分析

旅客值机是机场离港流程中的一部分，分为人工值机和自助值机两种方式。旅客到达机场航站楼值机大厅，根据个人喜好选择人工值机或自助值机子系统，同时根据各系统的排队情况，选择最短的队列等候值机。

1.1 值机流程排队系统

值机流程作为航站楼旅客流程的子系统，其运行效率的高低，决定了旅客其它步骤的运行。其中，旅客到达的过程与航班时刻表、航班旅客人数以及旅客到达分布曲线有关。某一时刻t的旅客到达率γ(人/min)为各航班该时刻旅客到达率之和，如公式(1)。

(1)

式中，l表示t时刻内航班的个数，a={1,2,…,l}。

值机过程服从M/M/k的排队模型排队系统[9]，有k个服务台，各服务台服务率等于u(人/min)，总服务率为ku。因此，值机柜台的服务强度为值机系统总到达率与总服务率之比，值机柜台服务强度ρ应小于1。

(2)

(3)

(4)

其中，式(2)为服务强度计算公式；式(3)为旅客值机排队平均旅客数；式(4)为值机排队旅客平均排队时间(min/人)；k为开放的值机柜台个数。

1.2 基于服务标准的值机柜台资源配置

目前，机场一般要求航站楼的值机服务必须满足一定指标。见表1所列：中国民用航空局发布的民用运输机场服务质量标准[10]。因此，本文在求解值机柜台开放数量时，应以满足机场值机排队等待时间标准为前提。即：

Wt≤Wc

(5)

式中，Wc为某服务水平下，标准值机排队等待时间。

2 值机柜台分配模型的建立

2.1 假设条件

根据以上对值机流程的分析，为便于计算，对值机过程进行以下假设：

(1)机场到达旅客全部使用值机柜台进行值机，即人工值机柜台和一体化自助值机设备。

(2)值机过程满足先到先服务的原则。

(3)值机排队系统的各时段所需柜台数为正整数。

(4)值机方式为公用柜台，旅客到达时选择最短队列排队。

(5)旅客全为经济舱旅客。

(6)人工值机柜台配置服务人员，自助值机设备不配置服务人员。

2.2 不同时间段值机方式的选择

由于旅客选择值机方式具有很大的随机性，旅客选择偏好，受旅客个人特征、值机设备特征等影响[11]。根据文献[12]，得到某一机场早高峰时段值机排队系统。旅客对于人工值机柜台和自助值机柜台的预测选择偏好[12]，其选择比例见表2。

表2 旅客不同值机方式选择比例

由表2可知，在值机的早高峰时段，人工值机方式仍占据主导作用，但自助值机的占比相比平峰时段在高峰时段明显增大。说明高峰时段，由于旅客人数增多，值机排队时间变长，选择自助值机的旅客增多。因此，为了对机场繁忙时段值机柜台分配进行分析，本文选择早高峰时段的旅客到达进行问题分析。

2.3 值机柜台分配模型的建立

2.3.1 模型中符号含义

t：值机时间按照一定时间间隔，平分为n个时间段，t≥1,t={1,2,…,n}；

Xt：时间段t内，使用人工值机柜台旅客所占比例，0≤Xt≤1；

Yt：时间段t内，使用自助值机柜台旅客所占比例，0≤Yt≤1；

PU：人工值机柜台服务一位旅客产生的收益；

PV：自助值机柜台服务一位旅客产生的收益；

PW：开放一个值机柜台单位时间成本。

2.3.2 目标函数模型的确定

由上述分析可知，本文以满足IATA(International Air Transport Association)C级旅客排队等待时间为前提，以值机过程净收益最大为目标函数，来优化航站楼的值机柜台资源分配问题。即在得到值机系统最大净收益的同时，求得其分配的值机柜台数量，净收益越大表明值机系统的收益越高。

(6)

(7)

Wt≤Wc

(8)

kt≤C

(9)

式(7)表示值机工作人员的繁忙概率，应控制在一个合理的范围内。太大，服务员容易疲劳出错，导致效率下降；太小，值机工作效率降低，柜台使用率不高。另外，其取值范围应该大一些，否则可能使问题解不可行，约束不满足。

式(8)表示旅客值机排队平均等待时间，应满足服务标准。本文选取国内经济舱95%的旅客值机排队等待时间不超过14 min。

式(9)表示开放的值机柜台数，该数值不可超过机场可开放最大值机柜台数。其中C为可开放的最大值机柜台个数。

3 值机柜台动态分配参数设定

通过上述函数模型，选取某机场早高峰8：00-11：30值机区域的所有航班的实际旅客到达作为实例分析，可开放值机柜台总数C为30。

3.1 旅客到达率的确定

本文选取30 min作为时间间隔，如果间隔时间太短容易造成值机排班难度大，造成人员排班混乱[13]。根据实际旅客到达人数，由公式(1)得到早高峰各时间段内的旅客到达率，见表3。

表3 各时间间隔旅客到达率

3.2 值机工作人员繁忙概率取值区间的确定

由于人工和自助的值机服务时间没有显著差异[12]，因此本文设定人工值机柜台和自助值机柜台旅客服务率相等，各柜台的平均服务率u=23人/30 min。

首先，运用MATLAB对满足约束条件的值机柜台开放个数求解，得到各时段值机柜台可开放数量(如图1所示)，以及与之对应的值机人员繁忙概率(如图2所示)。

图1 各时间段值机柜台可开放数量

图2 值机柜台可开放数量对应值机人员繁忙概率

由图2可知，值机人员繁忙概率最大达到了8.127 2，导致值机工作人员极度疲劳，最小却仅为0.002 5，值机柜台工作效率极其低下，资源浪费。因此，应设定合理的取值范围。同时为防止出现问题的不可行解，设定值机人员的繁忙概率取值为[0.25,0.91]。

4 值机柜台动态配置的模拟退火算法设计

4.1 分配问题的模拟退火算法

模拟退火算法最早由Metropolis等[14]在1953年提出。其原理与固体的退火原理类似，如图3所示。即将固体温度加热后，再使其缓缓降温冷却，最后在常温时达到稳定基态内能最小。当算法终止时，保存的最小解即为所求的最优目标函数值[15]。值机柜台的分配问题，属于NP难问题，若采用传统方法，计算量和难度将会极大增加。因此，采用更加快速的方法来求解此类问题变得越发重要。1983年模拟退火算法第一次被引入优化领域，由于能有效的近似求解具有NP复杂性的难题，克服其它优化算法容易陷入局部最优的缺陷，并对初值没有强依赖关系。基于此，将设计模拟退火算法用来求解值机柜台动态分配问题。

图3 关系原理

4.2 模拟退火算法实现

4.2.1 初始解的生成

为扩大求解范围，本文初始解以随机数的方式产生。在MATLAB中运用随机数生成程序，随机生成一个一行七列取值为[1,29]的矩阵。

4.2.2 目标函数的确定

本文值机柜台分配问题的目标函数S，是在满足约束的前提下，得到的最大值机净收益。进而得到各时段分配的值机柜台数量，如公式(10)所示：

(10)

本文目标函数求解为最大值，而模拟退火算法求解的是最小值。因此，在判断是否接受新解时，改为当新解大于旧解目标函数时，则接受新解。

4.2.3 新解的产生

新解的产生应简单快速，以减少算法所用时间。基于此，本文新解的生成通过交换的方式，以随机概率的大小选择以下两种不同方式产生新解：

(1)二变换法

随机选择解中序号为u、v(设u

表4 二变换法

(2)三变换法

随机选择序号为u、v(设u

另外，由于目标函数本身带有约束条件，当新解生成后，还要判断是否满足约束，如果满足则进行算法下一步，否则根据新解服务强度的大小，进行相应改变。(具体过程在算法步骤Step3中介绍)

4.2.4 Metropoils新解接受准则

在模拟退火算法中，解的接受准则为Metropoils准则。因本文目标函数为求最大值，即新解的接受条件为：若ΔS>0，则接受新解kj作为新的当前解；如果ΔS<0，则新解kj按照接受概率P确定是否接受。如公式(11)、(12)所示。

ΔS=S(kj)-S(ki)

(11)

(12)

其中，ΔS为目标函数差;1≤i

4.3 运行参数

初始温度T0：控制参数初始温度T0=97。

衰减函数T：控制参数的衰减函数连续降温表达式T=T×φ。φ是衰减函数的一个常数，取值为[0.50,0.99]之间，本文取0.90。

终止温度Tf：终止温度即算法运行的停止准则。一般终止温度设为足够小的正数，取值为[0.01,5]之间，本文取3。

Markov链长度Lk：Lk即循环次数，应能在控制参数T的取值上达到平衡。取值一般为100 n，本文设Lk为700次。

4.4 模拟退火算法步骤

根据前文设计，算法步骤如下：

Step1令初始温度T=T0，并按照上述所述方式生成一个初始解k0。

Step2令T等于冷却进度表中的下一个值Ti。

Step3根据当前解ki进行扰动，即进行交换操作，从而产生新解kj。判断新解是否满足柜台分配的约束条件，如果满足进行下一步，否则根据新解的服务强度ρ。如果ρ≥1，则kj进行加1操作，如果ρ<1，则kj=1，直到找到一个满足约束条件的值机柜台开放数量，并计算新解相应的目标函数值S(xj)，进而得到ΔS。

Step5在温度为Ti值下，重复进行Lk次扰动和接受循环，即循环步骤3和4，直到满足要求。

Step6判断T是否达到终止标准。满足，则停止运算输出最优目标函数解，算法结束；否则，转到步骤2继续执行。

算法流程如图4所示。

图4 模拟退火算法流程

5 实例分析

设PU=10元/人、PV=5元/人、Pw=4元/min，通过MATLAB运用所设计的模拟退火算法求解目标函数，得到目标函数(值机系统)最大净收益为265.92元。最优利润为1.27元/min。最终得到各时间段最大净收益和配置的值机柜台数量(如图5所示)，以及与之对应的值机人员繁忙概率大小(如图6所示)。

图5 各时段最大净收益与值机柜台开放数量

图6 各时间段值机人员最终繁忙概率

将本文采用模拟退火得到的值机柜台分配数量，与以往采用启发式和枚举式相结合的方法对人工值机柜台进行分配的结果进行对比，值机开放总数基本相同。说明了算法的有效性，但启发与枚举结合的方法，往往需要运算经验，并且人工运算需要大量时间，且相比本文所用算法，难以在机场实际应用。同时本文计算在考虑使用自助值机设备的情况下，人工值机柜台开放总数量为113个，相比以往只对人工值机分配数量，本文人工值机柜台减少了18.7%的使用量，提高了值机系统资源的利用效率。同时，分配更加合理，为机场提供了不同的值机柜台资源分配方案，见表5。

表5 不同时间段值机设备动态开放数量

6 结束语

本文为机场航站楼内值机柜台资源的配置研究，在满足旅客满意度约束标准的前提下，考虑值机员的繁忙程度，以系统净收益最大为目标，通过设计的模拟退火算法，对值机柜台资源进行动态配置求解。运用MATLAB进行实例分析，在P4，i5,1.19 GHz算法平均运行11 s，得到最大的系统净收益，进而得到各时间段内值机柜台的分配数量。结果表明，相比只考虑对人工值机柜台的配置及采用启发式运算的方法，本文在考虑了自助值机柜台分配方式下，各时间段使用的值机柜台数量分配更加合理，同时运算所用时间大大减少，提高了值机系统运行效率和旅客满意度，为机场值机柜台的运行配置提供了可行参考。