基于粒子群算法的航班座位自动分配系统

李方方 蒋理 戴胜 秦胜男

摘   要：航班座位的分配有一系列的规则，但由于物理座位限制，一般无法满足所有旅客的个性化需求;一般自动分配座位通常采取“先到先得”的方式，但是这样的方式只能解决前一部分旅客的座位要求。此外，由于航班变更，机械故障，航线计划调整等原因，机型会发生变更，因此如何根据用户已有的需求进行座位自动分配算法是个需要解决的问题。本文主要采用了改进的粒子群算法为已购票旅客自动分配航班座位，尽可能满足旅客的个性化需求。

关键词：自动分配  粒子群  航班座位

目前民航旅客在預定航班后，一般都可以提前自助选择座位。如果不提前选择座位，旅客到达机场后，在柜台值机或自助设备上值机时，可以选择一个座位，或者由后台系统随机分配一个座位。

航班座位的分配有一系列的规则，但由于物理座位限制，一般无法满足所有旅客的个性化需求。由于大多航班都具备提前选座功能，想要预留好的座位要提前“下手”。而自动分配座位通常采取“先到先得”的方式，只能解决前一部分旅客的座位要求。

1  旅客的不同的座位需求

飞机机舱内的座位本身具备多种属性，包括：靠窗座位、靠过道座位、腿部宽敞座位、紧急出口座位、VIP旅客预留座位（一般是前排）等。不同旅客的座位需求是不同的。有人喜欢靠窗座位看风景;有人喜欢过道座位，方便去卫生间;VIP旅客一般分配前排座位;登机口边上座位不会分配给残疾人旅客，一般分配给男性，以便于突发事件时可以协助机组打开安全出口门;结伴同行的旅客尽可能分配在一起，在前后排或同一排;婴儿旅客不占座位，但是携带婴儿的旅客如果申请婴儿摇篮可以分配到有婴儿摇篮挂载点对应的位置，方便照看婴儿。

本系统主要涉及到的座位属性有很多，主要包括靠窗、中间、靠过道、安静、平稳、安全感高、VIP、登机口、残疾人、孕妇、婴儿摇篮、飞机平衡、票价、年龄等。

2  系统的设计与实现

航班座位自动分配系统整体是基于MVVM模式设计的，根据软件开发中前后端模式的基本历程，采用了前后端分离的基本结构。前端完全负责View层和ViewModel层。View是视图层，也就是所谓的用户界面;ViewModel是生成和维护的视图数据层，是对后端获取的Model数据完成数据转换的功能;两者完成封装，来生成视图数据模型。后端负责Model层，主要实现各种业务逻辑和数据库操作。

3  粒子群算法简介及其改进

3.1 粒子群算法

本文主要采用粒子群算法实现航班座位的自动分配，在计算机科学中，粒子群优化（PSO）是一种计算方法，可以通过迭代来改进候选方案的优化问题。它通过粒子的位置和速度根据数学公式得到一组候选解决方案，并在搜索空间中移动这些粒子来解决问题。

3.2 粒子群算法的改进

由于PSO操作简单、收敛速度快，因此在函数优化、 图像处理、大地测量等众多领域都得到了广泛的应用。 随着应用范围的扩大，PSO算法存在早熟收敛、维数灾难、易于陷入局部极值等问题需要解决，本文针对航班座位分配主要对粒子群算法进行了如下的改进：

3.2.1 参数选择与优化

（1）参数w代表惯性部分，c1代表社会部分，c2代表自身部分 这三个部分决定了搜索的作用。惯性权重w主要是代表粒子上一代速度对当前代速度的影响。w较大，说明全局寻优能力越强，而局部寻优能力则越弱;所以为了在达到搜索速度和搜索精度之间平衡，要对w进行了改进。随着迭代次数的增加，惯性权重w应不断减少，从而使得粒子群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。

（2）学习因子c1，c2都不为0，即为完全型粒子群算法，完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较好的选择。

（3） 群体大小m是一个整数，m很小时陷入局部最优解的可能性很大;m很大时PSO的优化能力很好，但是当群体数目增长至一定水平时，再增长将不再有显著作用，而且数目越大计算量也越大。

（4）粒子群的最大速度Vmax对维护算法的探索能力与开发能力的平衡很重要，Vmax较大时，探索能力强，但粒子容易飞过最优解;Vmax较小时，开发能力强，但是容易陷入局部最优解。Vmax一般设为每维变量变化范围10%～20%。

3.2.2 极值扰动的引入

粒子会出现“聚集”现象，当搜索到一定程度，算法就会处于进化停滞，粒子停留在一个较小的范围内搜索，容易使算法陷入局部最优。因此，可以在公式中引入扰动因子r3和r4，对个体极值pbest和全局极值gbest进行随机调整，从而扩大粒子的搜索范围，帮助粒子跳出局部最优。

4  座位自动分配过程

该系统实现单个旅客座位分配、一组旅客分配、整机旅客分配。根据分配结果展示单个旅客分配的位置，一组旅客的位置和整机旅客分配的位置;实现了算法分配过程的展示，计算出旅客的满意度。实现了旅客信息的展示、编辑添加旅客的信息、添加多人的信息、查看所有旅客的信息;展示了旅客的年龄分布图;展示了旅客的个人的属性偏好和一组的旅客的关系偏好。根据随机分配的算法与智能分配算法的对比展示出智能分配算法的优势，能展示随机分配的满意度、预分配的满意度、算法的执行时间和分配的失败的人数。

4.1 单个旅客自动分配

单个旅客的自动分配主要采用“先来先服务算法”。系统首先生成航班每位旅客的可选座位集合，采用先来先服务算法模拟航班旅客值机过程中的座位分配算法。

4.2 一组旅客自动分配

一组旅客的自动分配主要满足结伴同行的旅客，通过采用算法让他们尽可能自动分配在一起，比如分配在前后排或同一排。

4.3 整机旅客自动分配

整机旅客自动分配，就是根据用户提交的需求，实现一种自动分配座位的算法，为旅客分配合理的座位，尽可能满足旅客的个性化需求，提高旅客出行的用户体验。用户提交的需求主要包括前面介绍的靠窗等30多种属性。

5  算法的实现

本文主要通过抽取20组数据，分配采用改进的粒子群算法、贪心+匈牙利算法，朴素算法和先到先得算法这4种算法，从算法分配的满意度、算法分配的时间、算法分配涉及到的主要因素进行分析。得出结论如下。

（1）朴素算法分配满意度最高（人工消耗大量时间进行置换，将不满意的人交换，直到分配到满意的位置，得到最大满意度）

（2）先来先得算法分配结果满意度相对较低，为20%～40%，不能满足大多数旅客。

（3）贪心+匈牙利算法分配结果满意度比人工分配满意度相近，接近人工分配最大满意度，相对于粒子群算法满意度要低一点。

（4）粒子群算法分配结果满意度接近于人工分配满意度，最接近于人工分配结果。相对于贪心+匈牙利算法满意度更高。

6  结语

旅客对个体性化服务水平的需求对航空公司的服务提出了更高的要求，改造现有业务模式、提升服务品质、提高运营效率成为了民用航空业的重要目标。航班座位自动分配系统主要基于旅客的各种个性化需求，通过改进的粒子群算法实现为整机旅客分配最大满意度座位的需求，同时满足旅客个性化的需求。该算法将应用于中国航信的座位预分配业务系统，预期将会显著缓解柜台值机压力、提升旅客出行的座位满意度，航班旅客座位预分配算法将会对航空的业务流程产生重要的影响。

参考文献

[1] 王琨琨.一种航班座位分配算法[J].现代计算机：专业版，2015（14）：37-39.

[2] 张雁茹，赵志刚，李永恒.基于扰动的自适应粒子群优化算法[J].广西科学，2017，24（3）：258-262.

[3] 董文永，康岚兰，刘宇航，等.带自适应精英扰动及惯性权重的反向粒子群优化算法[J].通信学报，2016，37（12）：1-10.