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

邢志伟; 侯翔开; 李彪; 张涛; 文涛

doi:10.13700/j.bh.1001-5965.2021.0144

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

doi: 10.13700/j.bh.1001-5965.2021.0144

邢志伟^{1, 2, ,},
侯翔开¹,
李彪¹,
张涛³,
文涛³

1.
中国民航大学航空工程学院, 天津 300300
2.
中国民航大学电子信息与自动化学院, 天津 300300
3.
中国民用航空局第二研究所工程技术研究中心, 成都 610041

基金项目:

国家重点研发计划 2018YFB1601200

四川省科技计划 2019JDTD0001

详细信息

通讯作者:
邢志伟, E-mail: cauc_xzw@163.com

中图分类号: V219; TP311
计量
- 文章访问数: 317
- HTML全文浏览量: 87
- PDF下载量: 36
- 被引次数: 0
出版历程
- 收稿日期: 2021-03-25
- 录用日期: 2021-09-05
- 网络出版日期: 2021-09-16
- 整期出版日期: 2022-12-20

Civil aviation luggage cart stacking algorithm based on dynamic quadtree search

XING Zhiwei^{1, 2
, ,},
HOU Xiangkai¹,
LI Biao¹,
ZHANG Tao³,
WEN Tao³

1.
College of Aeronautical Engineering, Civil Aviation University of China, Tianjin 300300, China
2.
College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
3.
Engineering Technology Research Center, The Second Research Institute of Civil Aviation Administration of China, Chengdu 610041, China

Funds:

National Key R & D Program of China 2018YFB1601200

Sichuan Science and Technology Program 2019JDTD0001

More Information

Corresponding author: XING Zhiwei, E-mail: cauc_xzw@163.com

摘要

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

HTML全文

图 1 民航行李车示意图

Figure 1. Schematic diagram of luggage cart for civil aviation

下载: 全尺寸图片幻灯片

图 2 行李摆放姿态

Figure 2. Luggage placement

下载: 全尺寸图片幻灯片

图 3 复合条生成示意图

Figure 3. Schematic diagram of compound bar generation

下载: 全尺寸图片幻灯片

图 4 四种复合层示意图

Figure 4. Schematic diagram of four types of composite layers

下载: 全尺寸图片幻灯片

图 5 四叉树搜索

Figure 5. Quadtree search

下载: 全尺寸图片幻灯片

图 6 算法嵌套图

Figure 6. Nesting diagram of algorithm

下载: 全尺寸图片幻灯片

图 7 算法2流程

Figure 7. Flow chart of algorithm 2

下载: 全尺寸图片幻灯片

图 8 算法3流程

Figure 8. Flow chart of algorithm 3

下载: 全尺寸图片幻灯片

图 9 算法4流程

Figure 9. Flow chart of algorithm 4

下载: 全尺寸图片幻灯片

图 10 两种浪费体积示意图

Figure 10. Schematic diagram of two waste volumes

下载: 全尺寸图片幻灯片

图 11 算法5a流程

Figure 11. Flow chart of algorithm 5a

下载: 全尺寸图片幻灯片

图 12 DQS算法与HOBTS算法结果对比

Figure 12. Comparison of results between DQS and HOBTS algorithms

下载: 全尺寸图片幻灯片

图 13 DQS算法码放的4个结果

Figure 13. Four results of DQS algorithm stacking

下载: 全尺寸图片幻灯片

图 14 HOBTS算法码放的4个结果

Figure 14. Four results of HOBTS algorithm stacking

下载: 全尺寸图片幻灯片

图 15 现实码放结果

Figure 15. Real-world stack result

下载: 全尺寸图片幻灯片

表 1 航空行李实验数据

Table 1. Experimental data of air luggage

行李箱尺寸/寸	长/cm	宽/cm	高/cm	数量	比例/%
22	56~60	37~41	23~24	20	29
24	62~65	40~44	26~27	24	34
26	66~71	43~47	28~29	21	30
28	75~81	45~49	28~29	3	4
32	85~91	51~55	30~32	2	3

下载: 导出CSV

表 2 DQS算法参数

Table 2. Parameters in DQS algorithm

参数	说明	数值
fr5a/%	算法5a中复合条最低空间利用率	97
fr5b/%	算法5b中复合条最低空间利用率	93
fr₀/%	复合层最低空间利用率上限	90
n	保留码放方案数目(当n≥4时结果开始不再变化)	4

下载: 导出CSV

表 3 DQS算法30次运算结果

Table 3. 30 operation results in DQS algorithm

统计参数	空间利用率/%
最小值	90.1
第一四分位数	90.7
中位数	91.7
第三四分位数	92.5
最大值	93.6
平均值	91.63
注：标准差为0.010 557。

下载: 导出CSV

表 4 HOBTS算法30次运算结果

Table 4. 30 operations results of HOBTS algorithm

统计参数	空间利用率/%
最小值	68.9
第一四分位数	71.0
中位数	72.6
第三四分位数	77.8
最大值	86.7
平均值	74.8
注：标准差为0.046 709。

下载: 导出CSV

表 5 多样性数据集运算结果

Table 5. Operation results of diverse dataset

异构等级	行李箱所占比例/%					平均填充率/%
异构等级	22寸	24寸	26寸	28寸	32寸	平均填充率/%
1	100					85.8
		100				93.5
	30				70	84.6
2	50	50				91.2
		50	50			89.7
		20		40	40	84.3
3	33	33	34			92.3
		40	40	20		87.7
	40		10	10	40	89.1
4	25	25	25	25		89.2
	30	10		30	30	85.7
	30	30	30	5	5	91.3
5	20	20	20	20	20	88.8
		10	10	40	40	84.3
	20	40	20	10	10	86.4
注：异构等级越高，行李箱异构性越强，异构性强弱受行李箱种类和占比影响，种类越多，占比越平均，异构性越强。

下载: 导出CSV

表 6 标准测试集BR1~BR7运算结果比较

Table 6. Comparison of operation results between standard tests of BR1-BR7

算法	约束	填充率/%
算法	约束	BR1	BR2	BR3	BR4	BR5	BR6	BR7
HSA^[9]	C1 & C2	93.8	93.9	93.7	93.6	93.2	92.7	92.0
CLTRS^[4]	C1 & C2	94.5	94.7	94.7	94.4	94.1	93.9	93.2
MLHS^[24]	C1 & C2	94.5	94.9	95.2	95.0	94.8	94.5	94.0
MLTrS^[18]	C1 & C2	93.5	93.4	93.8	93.9	93.4	93.7	93.6
DQS	C1 & C2 & C3	92.5	95.1	93.4	93.0	92.6	92.8	92.2
注：C1为方向约束，C2为稳定性约束，C3为完全切割约束。

下载: 导出CSV

参考文献(24)

[1]	DYCKHOFF H, FINKE U. Cutting and packing in production and distribution[M]. Heidelberg: Physica-Verlag, 1992.
[2]	WÄSCHER G, HAUNER H, SCHUMANN H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109-1130. doi: 10.1016/j.ejor.2005.12.047
[3]	BORTFELDT A, WÄSCHER G. Constraints in container loa-ding-A state-of-the-art review[J]. European Journal of Operational Research, 2013, 229(1): 1-20. doi: 10.1016/j.ejor.2012.12.006
[4]	FANSLAU T, BORTFELDT A. A tree search algorithm for solving the container loading problem[J]. Informs Journal on Computing, 2010, 22(2): 222-235. doi: 10.1287/ijoc.1090.0338
[5]	GEORGE J A, ROBINSON D F. A heuristic for packing boxes into a container[J]. Computers & Operations Research, 1980, 7(3): 147-156.
[6]	CRAINIC T G, PERBOLI G, TADEI R. TS(2)PACK: A two-level tabu search for the three-dimensional bin packing problem[J]. European Journal of Operational Research, 2009, 195(3): 744-760. doi: 10.1016/j.ejor.2007.06.063
[7]	张德富, 魏丽军, 陈青山, 等. 三维装箱问题的组合启发式算法[J]. 软件学报, 2007, 18(9): 2083-2089. https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200709005.htm ZHANG D F, WEI L J, CHEN Q S, et al. Combinatorial heuristic algorithm for three dimensional packing problem[J]. Journal of Software, 2007, 18(9): 2083-2089(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200709005.htm
[8]	CHEKANIN V A, CHEKANIN A V. Multimethod genetic algorithm for the three-dimensional orthogonal packing problem[J]. Journal of Physics Conference Series, 2019, 1353(11): 012109.
[9]	张德富, 彭煜, 朱文兴, 等. 求解三维装箱问题的混合模拟退火算法[J]. 计算机学报, 2009, 32(11): 2147-2156. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200911006.htm ZHANG D F, PENG Y, ZHU W X, et al. Hybrid simulated annealing algorithm for solving three dimensional packing problem[J]. Chinese Journal of Computers, 2009, 32(11): 2147-2156(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200911006.htm
[10]	EROZAN I, CALISKAN E. A multi-objective genetic algorithm for a special type of 2D orthogonal packing problems[J]. Applied Mathematical Modelling, 2020, 77(1): 66-81.
[11]	FENG X, MOON I, SHIN J. Hybrid genetic algorithms for the three-dimensional multiple container packing problem[J]. Flexible Services and Manufacturing Journal, 2015, 27(2-3): 451-477. doi: 10.1007/s10696-013-9181-8
[12]	张钧, 贺可太. 求解三维装箱问题的混合遗传模拟退火算法[J]. 计算机工程与应用, 2019, 55(14): 32-39. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201914006.htm ZHANG J, HE K T. Hybrid genetic simulated annealing algorithm for 3D bin packing problem[J]. Computer Engineering and Applications, 2019, 55(14): 32-39(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201914006.htm
[13]	张长勇, 翟一鸣. 基于改进遗传算法的航空集装箱装载问题研究[J]. 北京航空航天大学学报, 2021, 47(7): 1345-1352. doi: 10.13700/j.bh.1001-5965.2020.0197 ZHANG C Y, ZHAI Y M. Research on air container loading problem based on improved genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(7): 1345-1352(in Chinese). doi: 10.13700/j.bh.1001-5965.2020.0197
[14]	KOCH H, SCHLGELL M, BORTFELDT A. A hybrid algorithm for the vehicle routing problem with three-dimensional loading constraints and mixed backhauls[J]. Journal of Scheduling, 2019, 23(4): 71-93.
[15]	ZHAO C, JIANG L, TEO K L. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem[J]. Journal of Industrial and Management Optimization, 2017, 13(5): 1-21.
[16]	LIU S, WEI T, XUN Z Y, et al. A tree search algorithm for the container loading problem[J]. Computers & Industrial Engineering, 2014, 75: 20-30.
[17]	刘胜, 朱凤华, 吕宜生. 求解三维装箱问题的启发式正交二叉树搜索算法[J]. 计算机学报, 2015, 38(8): 1530-1543. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201508003.htm LIU S, ZHU F H, LV Y S. Heuristic orthogonal binary tree search algorithm for three-dimensional packing problem[J]. Chinese Journal of Computers, 2015, 38(8): 1530-1543(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201508003.htm
[18]	刘胜, 沈大勇, 商秀芹, 等. 求解三维装箱问题的多层树搜索算法[J]. 自动化学报, 2020, 46(6): 1178-1187. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO202006008.htm LIU S, SHEN D Y, SHANG X Q, et al. A multi-layer tree search algorithm for 3D packing problem[J]. Acta Automatic Sinica, 2020, 46(6): 1178-1187(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO202006008.htm
[19]	FONTAN F, LIBRALESSO L. An anytime tree search algorithm for two-dimensional two and three-staged guillotine packing problems[J]. Computer Science, 2020, 4(2): 1-20.
[20]	PEJIC I, VAN DEN BERG D. Monte Carlo tree search on perfect rectangle packing problem instances[C]//Proceedings of the 2020 Genetic and Evolutionary Computation Conference, 2020: 1697-1703.
[21]	TOFFOLOT A M, ESPRIT E, WAUTERS T, et al. A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem[J]. European Journal of Operational Research, 2017, 257(2): 526-538.
[22]	HARRATH Y, BOUOUDINA H E, QASIM A T, et al. Toward smart logistics: A new algorithm for a multi-objective 3D bin packing problem[C]//Smart Cities Symposium, 2018.
[23]	郑斐峰, 梅启煌, 刘明. 基于遗传算法与贪婪策略的多港口集装箱配载研究[J]. 运筹与管理, 2018, 27(5): 1-7. https://www.cnki.com.cn/Article/CJFDTOTAL-YCGL201805002.htm ZHENG F F, MEI Q H, LIU M. Research on multiport container stowage based on genetic algorithm and greedy strategy[J]. Operations Research and Management Science, 2018, 27(5): 1-7(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-YCGL201805002.htm
[24]	张德富, 彭煜, 张丽丽. 求解三维装箱问题的多层启发式搜索算法[J]. 计算机学报, 2012, 35(12): 2553-2561. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201212011.htm ZHANG D F, PENG Y, ZHANG L L. Multilevel heuristic search algorithm for solving three-dimensional packing problem[J]. Chinese Journal of Computers, 2012, 35(12): 2553-2561(in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201212011.htm