基于动态四叉树搜索的民航行李车码放算法

民航行李智能化码放是未来行李处理的重要发展方向。为解决当前运输过程中劳动密集、效率低下等问题，提出了基于动态四叉树搜索的民航行李车码放算法。基于行李构型沿竖直方向动态规划组合成复合条，针对根节点空码放方案构造四叉树，设计动态最低利用率公式，在四叉树的每层生成复合层，4个分支为4种复合层放入后的新码放方案。设计了一种优化剩余空间的动态选择算法，在每层选择并保留n个最优码放方案继续搜索，当无法生成新码放方案时算法结束，取搜索过程中填充率最高者为最终码放方案。在现实算例的测试中，码放方案的平均空间利用率为91.63%，相对于选取的同类算法提升了16.83%，且算法稳定性更强，可多行李一次装载，并使用现实机械手码放平台验证码放结果。 

Civil aviation luggage cart stacking algorithm based on dynamic quadtree search

Intelligent baggage packing is an important trend of future civil aviation baggage processing. To solve the problems of labor intensiveness and inefficiency in the current transportation, a new algorithm based on dynamic quadtree search is proposed. Using the dynamic planning of luggage configuration in the vertical direction, the quadtree is constructed for the empty code placement scheme of the root node. A dynamic minimum utilization formula is proposed to generate a composite layer in each layer of the quadtree.After placing the composite layer, the branches become the new schemes. A dynamic selection algorithm is also designed to optimize the remaining space. n optimal code placement schemes are selected and retained at each layer to continue searching. When the new code placement scheme cannot be generated, the algorithm ends, and the final code placement scheme has the highest filling rate among all the schemes. In the test of practical examples, the average space utilization rate of the schemes is 91.63%, 16.83% higher than that of similar algorithms.Moreover, the proposed algorithm is more stable and can load multiple bags one time.The results are verified by using areal manipulator stacking platform.