0 引言
随着航空运输的蓬勃发展，旅客对高效完成进港、离港相关程序的需求愈加强烈，对于航班选择的基础也从价格演变至便捷、体验。乘机时，行李码放装机工作的完成时间直接影响着旅客登机的等待时间，其运输质量也直接影响着航班的运行安全及旅客的飞行体验。
目前，旅客行李的装机、码垛仍然以人力搬运的模式进行，少部分较为先进的机场采用了真空吸盘式抓取装置来提高效率［1］，行李装箱算法是码垛机器人领域关键性问题之一，它的解决可以改善装卸人员工作模式，提高旅客满意度，进而增加航空公司收益。
航空行李码垛问题实质上是三维装箱问题，属于NP-Complete问题。目前，国内外学者对于装箱问题的研究主要有学术、应用两个侧重点。在学术方面，多数学者的研究目标是填充率与计算时间，如张德富等［2］，刘胜等［3］，李孙寸等［4］，Elhedhli S等［5］，Zheng J N等［6］，Gon
alves J F 等［7］；在应用方面，1995年Bischoff E E等［8］首次提出了十二种不同的约束，推动了装箱问题由理论到实际的转化。此外，那日萨等［9］、Ramos A G 等［10］，Lurkin V［11］也都考虑到问题的现实性，针对不同应用背景提出了不同的装箱策略。不过，从学术角度对三维装箱问题的研究虽然具有空间利用率高的优势，但当问题的异构性增强时，求解时间将急剧增加，导致其工程应用性较弱；从应用角度对三维装箱问题的研究虽然考虑了较多现实性约束，具有较高工程应用价值，但集中在铁路、公路方面的研究较多，航空运输领域仅有零星成果。
因此，本文针对航空运输背景下旅客行李码垛问题，为保证航班密集情况下旅客行李按时装机，重点研究如何克服传统算法在行李强异构时解算时间过高的弱点，同时辅以较为合理的空间布局。将K-means聚类引入装箱算法，从体积、质量两方面综合考察每件行李，结合“砌墙式”布局思想，设计了“面填充”与“箱填充”两阶段码放策略。并通过BR1～BR7经典算例与实际旅客行李数据，验证了聚类算法对解算速度的贡献和砌墙算法的布局效果，证明了算法的高效性和实用性。
1 数学模型
1.1 约束条件
相比较公路、铁路、水路货物运输，航空行李运输与之既密切联系，又有其独有的特点。例如，飞机货舱空间较为充裕，旅客行李体积、质量、材质差异大，平均价值高，旅客对于运输损失的容忍度低。针对强异构旅客行李的装箱运输问题，可以定义为：有大量形状各异、质量不等的旅客行李及多个航空集装箱，求其装载方案，在稳定装载所有行李的前提下，使利用的航空集装箱数量最少。
根据问题定义，提出以下约束条件：（1）行李体积和质量约束。单个行李的体积、质量不能大于航空集装箱的最大装载容积、最大承载能力；（2）集装箱体积和质量约束。装载行李的总体积、总质量不能超过航空集装箱的最大装载容积、最大承载能力；（3）完全支撑约束。码放时每件行李都必须有完全的支撑面，即行李不能悬空码放；（4）重心约束。码放完成后，航空集装箱重心应低于或等于其几何中心。
1.2 假设条件
由于此类现实问题的复杂性，航空行李码放算法的提出基于以下假设条件：（1）行李形状为长方体。综合考虑航空行李运输实际，旅客行李以各尺寸拉杆箱、硬纸板箱为主，并且，许多复杂的形状也可拆分为多个小长方体；（2）行李密度均匀，重心位于几何中心；（3）行李承重性良好，能满足多层叠装，且由挤压产生的微小形变可忽略；（4）所有航空集装箱为同种规格。
1.3 模型建立
以航空集装箱底面为XY平面，垂直底面向上方向为Z轴，集装箱左、后、下角为坐标原点建立空间直角坐标系。
建立航空行李码垛布局优化数学模型：
式中 n、N —— 行李的总数量、可装载的航空集
装箱总数量；
wj、hj、dj、mj ——第 j号行李的宽、高、深、质量；
W、H、D、M —— 航空集装箱的宽、高、深、最大承重能力；
（xlj，ylj，zlj）—— 第j号已完成码放行李的左、后、下角坐标，j=1，2，…，n；
（xrj，yrj，zrj）—— 第 j号已完成码放行李的右、前、上角坐标，j=1，2，…，n；
Lij —— 第j号行李在第i号箱子中的层号，j=1，2，…，n，i=1，2，…，N；
gi —— 第i号航空集装箱内垛型重心高度，i=1，2，…，N；
Pi —— 0/1变量，表征第i号行李是否被装载，若已装载则Pi =1；
Qi —— 0/1变量，表征第i号航空集装箱是否被使用，若使用则Qi =1。
其中，式（1）、（2）为目标函数，即在完成装载全部行李的同时，最小化航空集装箱的使用数量；式（3）、（4）表示每个航空集装箱内装载行李的总体积、总质量小于集装箱的体积、最大承重能力；式（5）表示每件行李必须被下方行李（或集装箱底面）完全支撑；式（6）表示码放完成后，垛型的重心应当等于或低于航空集装箱的几何中心。
2 基于K-means的航空行李码放算法
2.1 K-means聚类预处理算法
K-means聚类算法可以将相似度较高的对象归类至同一个簇中。其中，K代表簇的个数，簇中所有对象的均值为聚类中心。具体分以下3个步骤：
（1）数据预处理。考虑到航空行李的差异性主要集中在质量、体积两方面，故将质量、体积进行离差标准化，去除量纲后作为聚类准则对行李数据进行聚类。
（2）首次分配数据点。随机确定k个初始点作为质心，计算数据集中每个点到k个质心的距离，并将该点分配至距离最近的质心所在的簇。
（3）更新数据点分配结果。更新质心的坐标为该簇所有点的平均值，并重复计算距离、分配数据点，当连续多次分配结果不发生改变时，视为聚类完成。
聚类算法的作用在于将一组强异构行李数据拆分为多组弱异构数据，后续装箱布局算法将根据聚类结果分别对每组行李数据进行布局计算，最终生成合理的码放结果。
2.2 启发式装箱布局算法
装箱流程如图1所示。
图1 装箱流程
基于航空行李码放的特殊应用背景，结合较为经典的“砌墙”式布局思想，并在其基础上拓展，设计两阶段码放策略，第一阶段将单个行李组合成不同宽度的“条”，再将“条”拼接为垂直面（简称“面填充”）；第二阶段将各个垂直面码放入箱（简称“箱填充”）。
第一阶段“面填充”算法的思路。首先选取一件行李作为“条”内最下一层行李，上层所有行李的宽不能超过它的宽度，上层行李的总高度也不能超过集装箱的箱高。其次，若当前“条”受箱高限制无法继续装填，且横向宽度尚未达到箱宽，则开启新“条”继续码放。最终，当所有的行李都被填入各垂直面面的“条”内时，算法结束。
“面填充”算法：
//定义s为“条”变量，i为行李变量，rw为集装箱剩余宽度变量
第二阶段“箱填充”实质上是一维装箱问题。算法利用bop记录已用的集装箱数量，t与tmax为当前面号与总面数，垂直面深度td定义为面内深度最大的行李的深度。算法运行时，首先开启一个集装箱，填入一个垂直面。随后以集装箱深度为限定值，考察每个垂直面对已打开的所有箱子的适应度，将其填入首个适合的集装箱中。若没有合适的集装箱选择，则开启新箱，并将该面填入新箱内。最终，当所有面都被填入各自集装箱内时，算法结束。
“箱填充”算法：
3 实例验证
本文将基于K-means的启发式航空行李码放算法以C语言编程实现，采用某机场自助行李托运设备采集的真实行李数据验证算法的布局效果，利用国际上被引用最多的算例对比验证算法的时间性能，进行试验计算机处理器的型号为Intel（R）Core（TM）i5-6500CPU@3.20GHz。
3.1 装箱效果验证
目前，国内部分机场已有自助行李托运设备投入运行，该设备在旅客托运行李时利用激光扫描仪扫描该件行李，配合多种传感器，采集包括行李长、宽、高、重量及各个角度图像在内的各种信息。本文试验数据来自于某机场自助行李托运系统，从大量实际运行数据中随机选取100组进行试验，限于篇幅，表1仅列出其中部分航空行李数据。
表1 航空行李试验数据
本次试验中，首先利用聚类算法将行李数据划分为四类，即k=4，分别为：大体积大质量、小体积大质量、大体积小质量、小体积小质量。当连续3次分配结果不改变时确定为聚类完成，并将每个簇中的行李按体积顺序排序，形成待码放行李列表。图2为各聚类簇特性示意图，图3为聚类结果图，图中五角星为最终的聚类中心，横、纵轴为标准化后的质量、体积值。
图2 聚类簇特性
图3 聚类结果
在实际航空运输中，受货舱空间限制，大型客机的行李运输通常采用航空集装箱，而中小型客机则在货舱内设置隔离网，采用分块隔离的方式保证行李的水平稳定性，如图4所示，隔离网所分割的区域亦可视为航空集装箱。为直观评价算法的装箱布局效果，采用MATLAB软件编程实现码放方案的可视化。通过建立飞机货舱模型，输入行李的特征信息与位置坐标，即可生成货舱内行李装载的三维效果图。图5给出了对表1中数据进行测试后的装箱布局效果。
图4 飞机货舱结构图
图5 装箱布局效果图
可见，首先以聚类算法综合判断旅客行李的体积、质量，再利用码放算法将每簇行李安放于各个区域内的思路是可行的。对于个别区域（如右上侧）的填充率较低，其原因主要是各聚类簇的内部元素数量不平均，即测试数据中大件行李较少、中小件较多，为保持行李运输的稳定性而牺牲了一部分填充率。并且，采用聚类算法后，较为类似的行李均集中于同一个区域内，也避免了人工装载过程中行李随机进入货舱，各个区域内行李种类混杂，造成装卸难度大的问题。总体看来，针对较强异构性的真实旅客行李，算法的布局效果是令人满意的。
3.2 装箱效率验证
对于带质量约束的三维装箱问题，国际上大多数学者采用Bischoff和Ratchliff在1995年提出的算例［8］来验证算法的性能。算例共分为7组，依次为BR1，BR2，…，BR7，每组含有100件待码放物体，异构型自BR1至BR7逐渐增强，集装箱尺寸为587 cm×233 cm×220 cm，用来进行比较的是Ramos A G等［10］在2018年提出的一种典型码放算法，试验结果如表2所示。
表2 本文算法与现行研究（Ramos A G等）的比较
由表2可以发现，当待码放物体的异构性逐渐增强时，算法的解算时间总体呈下降趋势，且在BR2至BR3时产生明显跳变。这一点恰好印证了应用K-means聚类算法预处理的优势，当待码放物体异构性较弱时，聚类结果很大可能出现某一簇内元素数量远多于其他类的情况，导致解算速度变慢；当待码放物体异构性增强后，各个簇内元素分配较为平均，解算速度得到显著提升。还可以发现，算法的解算时间在跳变前后基本保持平稳，这是因为在各个簇内元素数量差异较大时，解算时间主要取决于元素最多的簇；而当各个簇内元素数量分配较为平均后，解算时间取决于所有簇解算时间之和。
通过观察Ramos A G等提出的算法可以发现，随着异构性的增强，算法的解算时间呈递增趋势，这一规律与本文码放算法是相同的，也是装箱问题的一般规律。但是，本文利用K-means算法对待码放物体进行预处理，化整为零，将一个强异构问题拆散为多个弱异构问题，在显著降低了解算时间的同时，令算法的解算时间具有了随异构性的增强不升反降的优良特性。
4 结语
本文提出了基于K-means的航空行李快速装箱算法，通过实际旅客行李、国际经典算例两项试验，结果表明，算法给出的布局方案不仅可以保证强异构性航空行李的合理、快速码垛，而且具有解算时间随异构性的增强而降低的优良特性。同时，将机器学习领域的聚类算法引入装箱问题，为今后装箱算法的设计提供了一条新思路。探索更优的聚类、码放策略，弥补算法在行李弱异构时计算较慢的不足是将来的研究工作。
参考文献：
［1］ 苗登雨，周新，张志伟，等.真空吸盘式多功能抓取装置的设计［J］.包装与食品机械，2016，34（6）：39-42.
［2］ 张德富，彭煜，张丽丽.求解三维装箱问题的多层启发式搜索算法［J］.计算机学报，2012，35（12）：2553-2560.
［3］ 刘胜，朱凤华，吕宜生，等.求解三维装箱问题的启发式正交二叉树搜索算法［J］.计算机学报，2015，38（8）：1530-1543.
［4］ 李孙寸，施心陵，张松海，等.基于多元优化算法的三维装箱问题的研究［J］.自动化学报，2018，44（1）：106-115.
［5］ Elhedhli S，Gzara F，Yan Y F.A MIP-based slicing heuristic for three-dimensional bin packing［J］.Optimization Letters，2017，11（8）：1547-1563.
［6］ Zheng J N，Chien C F，Gen M. Multi-objective multipopulation biased random-key genetic algorithm for the 3-D container loading problem［J］.Computers &Industrial Engineering，2015，89：80-87.
［7］ Gon
çalves J F，Resende M G C.A biased random key genetic algorithm for 2D and 3D bin packing problems［J］.International Journal of Production Economics，2013，145（2）：500-510.
［8］ Bischoff E E，Ratcliff M S W.Issues in the development of approaches to container loading［J］.Omega，1995，23（4）：377-390.
［9］ 那日萨，崔雪莲，韩琪玮.基于实际约束的三维装箱问题优化算法［J］.工业工程与管理，2017，22（4）：10-16.
［10］ Ramos A G，Silva E，Oliveira J F. A new load balance methodology for container loading problem in road transportation［J］.European Journal of Operational Research，2018，266（3）：1140-1152.
［11］ Lurkin V，Schyns M. The airline container loading problem with pickup and delivery［J］.European Journal of Operational Research，2015，244（3）：955-965.
