复杂约束下航空行李码放算法研究

发布时间：2020-05-26 15:30

【摘要】：旅客行李处理作为机场的核心业务之一,实现其全流程自动化对推进“智慧机场”建设意义重大。论文针对当前行李拖车码放和飞机货舱码放环节中存在的劳动密集、效率低下问题,开展了航空行李码放算法研究。通过对其学术内涵“三维装箱问题”研究现状的全面梳理,发现已有算法的约束条件及优化目标与实际需求匹配度较低。为此,引入了机器学习领域聚类算法和飞机货舱特殊空间约束,确定了与码放环节相契合的两类装箱问题,并提出了求解方案。具体包括以下内容:构建了两类装箱问题的数学模型。基于对行李拖车码放问题、飞机货舱码放问题特点的分析,提出了包含拖车车厢约束的多箱布局模型与包含货舱特殊空间约束的单箱布局模型,并将之用数学语言表达,为算法设计提供支撑。针对行李拖车码放问题,设计了一种含聚类预处理的高效求解算法。算法将K-means聚类与“砌墙”启发式算法有机结合,将一个强异构问题划分为多个弱异构问题,再逐个求解。采用真实旅客行李数据进行实验,验证了算法的可行性;以国际经典算例(BR1~BR7)进行测试,证明了解算时间相比同类算法下降62.3%的突出优势。并且,K-means聚类的引入使算法具有了解算时间不易受异构性影响的优良特性。针对飞机货舱码放问题,设计了一种满足货舱特殊空间约束的行李布局算法。算法基于“关键点”思想,降维计算与升维码放交叉配合,逐件确定行李位置。采用偏大型、偏小型、混合型三组真实旅客行李数据进行实验,证明了算法在多种工况下算法具备快速、合理给出布局方案,完成飞机货舱行李码放任务的能力。课题将机器学习算法、不规则空间约束引入传统装箱问题,既弥补了传统装箱算法难以应用于航空行李处理的不足,又为空间多约束、物品强异构、时间高敏感条件下装箱问题的求解开辟了一条新思路。
【图文】：

行李,处理环,人力

作停留的不足，目前大多数机场已引入更为先进的“五级集中安检”模式。该模式分为机器自动判读、工作人员工作站判读、CT 机两次判读、开包判读共五次安全检查。其中，除第二、第五两个环节外几乎不需要人工干预，并且仅有少数经过前四级仍存在疑问的行李需要进行开包判读，极大的减轻了地服人员的工作压力。分拣系统方面，由民航第二研究所研发的高速行李自动分拣系统已在北京、重庆、天津等多座机场使用[7]，系统分拣速度的峰值高达 6000 件/小时，曾经较为繁琐、容易出错的分拣过程正逐渐被自动化的机器代替。可以看出，民航科研人员为提高离港旅客行李处理流程的自动化水平做了大量努力。然而，在将以上分析与图 1-1 对照时，不难发现仍然有两个环节采用传统的人力劳动。如图 1-2（a）、（b）所示，其中一个环节是分拣结束后，将行李由行李分拣机末端站点搬运至拖车车厢中；另一个为牵引拖车靠近飞机后，，将行李从拖车车厢中取出，运送并码放至飞机货舱。

行李,车厢

中国民航大学硕士学位论文2.2 行李拖车码放问题2.2.1 问题分析与假设条件行李拖车是机场常用的特种车辆，分为牵引车头与拖车车厢两部分。如图 2-2（a）、（b）所示，牵引车头由机场工作人员驾驶，由蓄电池提供必要的动力以拖动整个行李拖车前进。车头与车厢、车厢与车厢之间靠金属材质的拖钩相连，车厢的尺寸与包围形式没有固定的标准，一般依照各机场的实际需求确定。
【学位授予单位】：中国民航大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：V354

【相似文献】