市区行李值机服务移动站点优化方法*

胡小兵 张雪梅 周 航 马一鸣

（1.中国民航大学体系安全和智能决策实验室 天津 300300；2.中国民航大学安全科学与工程学院 天津 300300；3.中国民航大学中欧航空工程师学院 天津 300300）

0 引 言

机场是为乘客提供出行便利的复杂交通枢纽，由于机场与城市市区之间的距离较远，大多数乘客需要携带行李赶赴机场，使得航空出行非常繁琐。为此，机场在市区范围建造城市候机楼（city air terminal,CAT）来改善乘客的体验，其主要功能是为乘客提供行李托运和值机服务。目前，根据中国已运营的CAT实际情况分析，已经出现了一些弊端：①运营效率和服务覆盖面不足；②投资和运营成本较高，经济效益低；③在选址上有诸多限制，乘客不方便到达。

考虑以上问题，本文提出1 种新型城市行李值机服务模式，即市区移动站点（urban mobile stations,UMS）服务模式。UMS是在市区内提供行李值机服务的专用车辆。UMS 模式基于乘客的实时位置分布情况确定UMS站点位置，最大程度地提高服务覆盖率和效益，并降低运营成本。UMS模式的服务模式具有智能化、灵活化、个性化等优点，既有传统城市候机楼的优势，又克服了其弊端，为乘客的出行提供精准便捷的服务。

要实现UMS服务模式，所需解决的主要问题是在每个服务时段内基于乘客的实时动态分布情况来实时解算UMS 位置分布，因此需要研究1 种有效方法，在复杂的城市道路网中优化UMS 的位置分布。资源配置优化问题中的方法可用于UMS 位置优化问题，主要包括确定性算法（如分枝定界算法[1]）和启发式算法（如模拟退火算法[2]、禁忌搜索算法[3]和p-中值加韦伯算法[4]）。Hakimi[5]在优化单1 设施位置时定义p-中值问题模型，并将其扩展到多个设施位置优化；Mladenović等[6]根据经典的仓库选址问题，运用元启发式规则解决多设施位置布局问题；李军等[7]通过建立网格索引对DBSCAN 算法的高时间复杂度进行了改进，基于此算法来确定班车的停留站点位置；魏明等[8]从时间和空间等方面考虑，以极小化所有公交车的行驶里程为目标来优化选址布局；程一一等[9]通过分析站点服务范围内的兴趣点特征，利用指标值和权值的方法来计算多设施位置的合理度；鲍文仓等[10]提出了1种共享电动汽车服务站点布局的改进模型，利用“连续逼近”模型和混合整数规划来确定多设施的位置；刘嘉文等[11]基于联合覆盖选址思想，考虑了多种影响因素以及各需求点应具备不同的权重，建立了多时段、多目标共享单车停放点选址优化模型来解决多设施优化选址问题。研究者还提出了许多混合算法，如模拟退火法和随机下降法的混合算法[12]，以及基于拉格朗日松弛法和遗传算法的混合算法[13]，Brimberg等[14]提出了可变邻域搜索，主要解决同时定位多设施位置优化问题。

这些方法通常针对位置选址的战略优化问题，对计算时效性要求不高，需要花较长时间（例如，几天甚至数周）来完成优化计算，最终得到1 个最优解。然而，在UMS 模式下，对于每个服务时段内UMS位置分布需要实现实时动态优化，优化过程必须在较短时间（甚至几分钟）内完成。因此，计算效率低的优化方法难以适用于解决UMS 模式实时位置分布问题。

笔者提出了1 种混合优化方法，该方法采用改进的涟漪扩散算法求解多对多路径优化问题，采用自适应遗传算法求解多站点位置优化问题。新方法能很好地满足UMS优化问题对计算时效性的要求，从而为UMS 这种全新服务模式的实际应用提供了技术支撑。

1 市区移动站点服务模式

针对传统的城市候机楼服务模式的缺点和不足，提出1种全新的市内行李值机服务模式，即UMS服务模式。UMS 模式主要由服务商运营的智能平台、乘客使用的移动应用程序和服务车辆3 个模块组成。新模式的操作见图1。将1 d 分为几个服务时段，每个服务时段的运行过程如下：①乘客通过移动应用程序提前填写行李托运和值机需求；②平台收集乘客数据，根据乘客位置优化UMS 位置分布；③平台将优化结果发送至服务车辆，这些车辆出发前往指定地点，并在服务期间停留在指定地点，同时，乘客从平台内接收信息，包括UMS 位置及其最短路线；④乘客在服务期间到对应的服务车辆办理行李值机手续。每个服务时段的运行过程重复上述步骤。

以服务时段13：00—15：00为例，见图2，乘客通过APP 预订值机服务，主要信息包括行李托运的预计时间、住址、航班信息等，预订必须早于服务启动时间，例如，设置时间提前参数tadv=1 h，即必须在12:00 之前预订13：00—15：00 期间的服务，参数tadv应根据乘客需求和机场或航空公司的限制条件确定；平台在12：00 基于服务时段13：00—15：00 的城市路网和乘客分布位置对UMS位置分布进行优化；平台将提供从每个乘客到最近的服务车辆的最短路径；优化必须在有限的时间（例如几分钟）内完成，预留足够的时间让车辆到达指定地点，并尽早向乘客发送相关服务信息；乘客可以按照移动应用程序上显示的路线到达最近的服务车辆。至少需要2组服务车辆轮流提供服务，考虑车辆故障、交通堵塞和其他意外情况，还需要1组备用车辆。

UMS 模式的服务车辆安装有符合民航标准的行李安检设备、值机设备和足够的行李存储空间。车载监控系统和乘客应用程序进行数据传输，以便相互交换相关信息，包括UMS 位置分布（向顾客提供服务车辆的当前位置；向平台提供所有服务车辆位置和状态）、乘客信息（对智能平台和服务车辆可见）、指令和服务状态更新等。

与传统城市候机楼模式相比，UMS服务模式有以下优点：①以服务车辆代替城市候机楼，极大程度地降低投资和运营成本；②针对每个服务时段，根据乘客的实时分布优化服务车辆的位置分布；③大大缩短乘客到达UMS的平均路径长度，实现灵活的服务模式，便于吸引更多乘客使用，从而提升民航运输的竞争力。

2 市区移动站点位置优化数学模型

市区移动站点（UMS）是1种全新的市内行李值机服务模式，传统的城市候机楼服务模式的数学模型不能对其进行有效描述UMS。因此，本文基于UMS 服务模式的基本思想和模式架构，介绍1 种基于路网的优化数学模型，以便实现在各个时段内对UMS位置的动态优化。

UMS 模式是以人为本，以乘客为导向，如何方便乘客出行是我们考虑的重要原因。UMS 模式重点考虑2个因素：乘客到服务车辆的平均路径长度、乘客最大可接受距离。

其次，优化UMS位置的动态优化可以被描述为以下最小化问题。

式中：xij为连接节点i,j的链路是否属于最短路径的指示变量；k为起点；n为终点；l为中间点，当xij属于最短路径的指示变量时为1，否则为0。式（7）约束的意义为寻找k到n的最短路径，即第1 个约束保证k一定可以走出去；第2 个约束保证一定有路径通往点n；第3个约束为路径可以通过约束1中创造的路径延续下去，直至点n。

笔者提出了UMS服务模式的理论概念，并针对这一服务模式建立了数学模型，该模型主要考虑了2个目标：①从乘客到UMS 的平均路径长度；②超出乘客可接受路径长度的路程。在将来的实际应用中，该模式还可以进一步改进，以考虑更多的目标，包括UMS 的数量、各站点UMS 的工作负荷均衡、UMS的总服务时长最短等。

3 基于涟漪扩散算法与遗传算法的混合优化算法

本文所提出的市区移动站点服务模式中，保证其有效运行的难点在于必须实时优化站点位置，即在短时间内给出位置方案。现有方法大都针对静态位置优化问题，算法时效较差，不适合UMS 场景。为大幅提升优化效率，本文在算法层面开展研究，提出了1 种混合智能优化方法，包含2 个部分：①改进涟漪扩散算法，有效计算乘客与UMS之间的平均路径长度，解决多对多路径优化问题；②引入定制化设计的自适应参数调整方法以提高遗传算法搜索效率，加快进化算法的收敛速度，从而快速得到服务车辆的最优位置。

图3 RSA计算多对多路径优化问题流程图Fig.3 Flowchart of RSAfor calculating many-to-many optimization problem

UMS 位置分布优化是1 个NP 难度的组合优化问题，为了获得更好的计算效率，本文提出1种改进的遗传算法。首先，介绍染色体的设计和遗传操作。然后重点介绍1种具有自适应调节的遗传算法

图4 RSA求解多对多路径优化问题的过程Fig.4 The process of RSAsolving many-to-many path optimization problem

图5 1条染色体结构图（例如：=3 并且选择6、9和21标记的节点作为UMS位置）Fig.5 Structure of one chromosome(e.g. =3 and the nodes marked by 6,9,and 21 are chosen as the UMS locations)

本文遗传算法的进化操作包括：精英遗传（操作发生概率pd）、变异（pm）、均匀交叉（pc）随机重新初始化（prg）、随机遗传（1-pd-pm-pc-prg）。

为了提高遗传算法的优化能力和收敛速度，通常可以在遗传算法中采用了自适应的参数调整方法[19]。本文根据自适应遗传算法（adaptive genetic algorithm,AGA）的思想，结合UMS问题的特点，对遗传算法的参数采用如下针对性设计的自适应调整方法。

首先，每一代ng∈[1,NG]的最大适应度值记为

引入1个指标knc，它为适应度最大值保持不变的世代数。它满足

式中：ncg为当前世代的指标。此外，knc反映了优化过程的现状，影响pm和pc的调整。

然后，根据Fmax和knc，分两阶段自适应调整变异概率pm和交叉概率pc，见图6。具体步骤如下：①突变和均匀交叉的初始可能性设为pm0和pc1；②如果knc1代的Fmax保持不变，则染色体可能处于局部最优区域。遗传算法将突变和交叉的可能性改变为pm1和pc1，使pm1＞pm0和pc1＜pc0，有助于遗传算法跳出局部最优区域；③如果knc2世代的Fmax不变(knc2＞knc1)，则设突变可能性为pm2(pm2＞pm1)，交叉可能性为pm2(pc2＜pc1)。也就是说，经过②的调整后，效果不明显，方法仍处于局部最优区域。因此，需要更多的随机性；④当对操作可能性进行调整时，一旦Fmax发生变化，即找到了更好的解，则将操作可能性改变为pm0和pc0，以便遗传算法可以探索与新Fmax相关的区域并迅速收敛。图7 为自适应调整遗传算法参数的流程图。

图6 两阶段自适应遗传算法的结构Fig.6 Illustration of the two-stage adaptive genetic algorithm

图7 改变突变和均匀交叉可能性的两阶段自适应遗传算法的流程图Fig.7 Flowchart of the two-stage adaptive genetic algorithm varying the mutation and uniform crossover possibilities

4 实例分析

为验证市区移动站点服务模式和优化模型算法的有效性，利用天津市路网（基于真实地图建立城市路网）和乘客分布（来自于2019 年4 月25 日对天津机场乘客的调查）的真实数据，采用本文提出的混合算法对不同服务时段的UMS位置分布进行优化。

首先，将GA与3种不同的多对多路径优化算法（RSA、A*算法和Dijkstra 算法）分别结合，进行测试，重点比较它们的计算效率。混合算法分别表示为RSA-GA、A*-GA 和D-GA。设置参数NUMS=3,Dacc=5km，Vmax=1.2Wtot/NUMS。随机生成1 000个不同的乘客分布，采用上述3种混合算法对服务站点位置进行优化。为了避免随机性，对每种情况进行了500次测试，平均计算时间见表1。从表1中可以得到各算法的计算时间，D-GA的计算时间是RSA-GA 的3.67 倍，A*-GA 的计算时间是RSA-GA 的7.18 倍，故RSA-GA 的计算速度最高。从表1 中还可以看出，多对多路径优化求解所用的平均计算时间远高于遗传算法。所以，在UMS优化问题中，选择1 个高效的多对多路径优化算法至关重要。

表1 3 种混合方法的平均计算时间Tab.1 Average calculation time of the three hybrid methods

然后，本节比较了自适应遗传算法和模拟退火算法（SA）的效率和有效性。对SA 进行大量测试后，选取最佳参数的SA 用于比较实验。同理，通过对AGA参数的不同组合进行试验，选择如下最佳参数用于计较实验。

对2种算法进行对比实验，表2是自适应遗传算法与模拟退火算法在不同乘客分布情况下进行100次试验的结果（乘客位置从网络节点中随机选取）。从表2中可以看出，AGA的最佳目标函数值的平均值比SA 小13.1%，其平均路径长度C1比SA 略小，其总超出距离C2的平均值比SA小32.8%，SA的优化过程要比AGA慢3倍左右。结果表明无论是优化解还是计算速度，自适应遗传算法都要优于模拟退火算法。

表2 AGA 和SA 在不同乘客分布情况下进行100 次试验结果Tab.2 Results of AGA and SA with 100 different passenger source distributions

图8 2019年4月25日天津市路网及客源位置示意图Fig.8 Schematic diagram of Tianjin's urban route network and passenger source location onApril 25,2019

对2 种服务模式的服务质量（即目标C1、C2、和计算时间）进行比较。在对比实验中设置参数NUMS=3，Dacc=5km，Vmax=1.2Wtot/NUMS，AGA的参数与上述相同，采用混合方法进行优化，优化结果见表3。表4 是不同站点数量情况下城市候机楼模式的结果，并且AGA 的参数与上述相同。将表3的优化结果与表4 的结果进行了比较，得到在相同站点数NUMS=NCAT=3 的情况下，UMS 的平均路径长度比CAT 小30.9%，超出乘客的可接受路径长度比CAT 小43.7%。因此，在相同站点数的情况下UMS 服务模式更符合乘客的需求。当某些时段的乘客分布明显分散时，可以灵活分配更多的服务车辆，以更好地服务乘客、提高服务覆盖率。设置＜3 km 和C1＜2 km 为判断UMS 模式的服务车辆是否满足某个时段的乘客需求，当满足＜3 km和C1＜2 km时，则其正常运行，否则将增加服务车辆的数量。

表3 具有恒定数量的UMS（NUMS=3）的结果Tab.3 Results with a constant number of UMS( NUMS=3)

表5为不同NUMS的结果，与表4中不同NCAT的情况进行比较，结果表明，UMS 的平均路径长度比CAT显著降低，故乘客到达它的平均时间也就更短，且其位置分布优化的平均计算时间为377 s，满足UMS模式运行的要求。

表4 CAT 不同站点数量情况下的结果Tab.4 Results of cases with different station numbers of CAT

表5 UMS 可变数量的结果（ ＜3 km 和C1＜2 km）Tab.5 Results with a variable number of UMS( ＜3 km and C1 ＜2 km)

表5 UMS 可变数量的结果（ ＜3 km 和C1＜2 km）Tab.5 Results with a variable number of UMS( ＜3 km and C1 ＜2 km)

服务时间段05：00—07：00 07：00—09：00 09：00—11：00 11：00—13：00 13：00—15：00 15：00—17：00 17：00—19：00 19：00—21：00站点数量Cf 64343445 BOF/km 1.94 1.93 2.36 1.96 2.20 1.71 2.10 1.91 C1/km 1.92 1.81 1.79 1.58 1.94 1.42 1.77 1.91 C2/km 16 115 569 384 261 288 329 0计算时间/s 369 353 382 411 396 393 362 347

在成本方面对2种模式的运营成本进行比较见表6。从中可以得到，UMS 的估算成本低于CAT。表6中费用的估算基于参考文献[20]，中项目投资和效益分析主要考虑硬件建设、购买和租赁成本。因此，上述仅对2种模式的成本进行了粗略比较，只是对成本问题提供了初步的财务观点。

表6 UMS 和CAT 的调查和运营成本Tab.6 Investigation and operation costs of UMS and CAT

为进一步验证UMS服务模式的有效性，随机生成100个路网，每个路网均匀分布有Nn=600 个节点，每个节点的连接数不超过6个，故最大链路数约为1 800 条。每个路网随机假设500 组乘客分布数据，每组乘客分布数据包含约20 000 名乘客，将20 000名乘客随机分布在8个时段内。设NUMS=NCAT=3，其他参数与上述实验相同。图9绘制了随机测试案例的部分优化结果,其中红色圆点为UMS位置，蓝色圆点为当前时段需要托运行李乘客位置，绿色圆点为其他时段旅客位置，图中还给出了乘客到达UMS的最短路径。

图9 随机生成网络和乘客分布的测试中UMS和CAT的最佳站点位置Fig.9 Optimal station locations of UMS and CAT in a test with randomly generated network and passenger distribution

表7 为100 个路网基于各自500 组乘客分布数据的模拟结果平均值。结果表明，乘客到UMS之间的平均路径长度要略小于CAT，这是由于乘客的分布是随机选择的，总体上非常分散，因此2种服务模式的差异并不明显。但是对于UMS来说，超过可接受距离的情况明显减少。由此可见，在随机生成数据的实质性测试中，UMS 的服务效率明显优于CAT。

表7 具有恒定数量的UMS 和随机乘客分布的结果(N=3)Tab.7 Results with constant number of UMS with random passenger distributions(N=3)

5 结束语

为充分发掘城市候机楼概念的优势并克服其不足，本文提出1 种适用于市区行李值机服务的市区移动站点服务模式；介绍UMS 模式组成和运行方式；提出1种新型混合优化方法，以满足其布局实时优化的时间要求；以天津市的乘客市区值机需求为例，从服务质量和成本2个方面对2种服务模式进行了比较研究；最后，在随机生成路网和乘客分布的情况下，进一步证明UMS 模式相对于传统CAT 的优势，证明了新型服务模式有助于提高民航的服务质量，增强航空运输的竞争力。

在将来的应用研究中，UMS 模式尚有可改进的空间：例如，UMS 服务模式是基于互联网平台进行的，乘客需要在网络上预约，因此对一些需要托运行李而不熟悉上网的老年人存在使用不便问题；可引入更现实的考虑因素，采用多目标优化模型，如考虑UMS 数量的动态变化、各站点的工作负荷均衡、UMS 的总服务时长最短，网络节点是否符合UMS 的位置要求等；还需要在不同城市和国家进行更多的实际案例研究，以进一步评价UMS服务模式和所提出的优化算法的有效性；对于已经建立城市候机楼的地区，若直接将CAT 废弃经济损失较大，因此，如何将城市候机楼服务模式与市区移动站点服务模式有效结合，需要进一步开展相关研究。