基于K-means与关键点的组合行李码放算法

Combined Luggage Stacking Algorithm Based on K-means and Key Points

目的为了解决当前航空行李码放流程中存在的劳动密集、效率低下的问题,开展行李码放算法研究。方法搭建含有重量、体积和货舱空间约束的航空行李码放数学模型,采用聚类、排序、关键点构建策略,设计一种K-means聚类与"关键点"思想相结合的组合式算法。结果采用100件真实旅客行李数据进行了实验,结果表明算法给出的布局方案规划合理,垛型左右两侧质量之差低于1%,满足了货舱的空间约束与载重平衡约束。结论算法具备在复杂环境下得到优良布局方案的能力,K-means聚类的引入也将机器学习领域的聚类算法引入装箱问题,架起了机器学习算法与传统装箱算法的桥梁,为今后装箱问题算法的设计提供了一条新思路。

The paper aims to study the luggage stacking algorithm to solve the labor-intensive and inefficient problems in the current flight luggage stacking process for check-in. In this paper, a mathematical model of flight luggage with weight, volume and cargo compartment constraints was built. By using clustering, ranking and key point construction strategy, a new algorithm combining K-means clustering and "key point" idea was designed. Experiments on 100 pieces of real passenger baggage showed that the layout plan given by the algorithm was reasonable. The difference of mass between the left and right sides of the stack was less than 1%, which satisfied the space constraint and load balancing constraint of the cargo compartment. The algorithm has the ability to obtain excellent layout scheme in complex environment. The introduction of K-means clustering algorithm establishes a bridge for machine learning algorithm and traditional packing problems, and provides a new idea for design of bin-packing problem algorithm in the future.