Advanced Search
Volume 48 Issue 12
Dec.  2022
Turn off MathJax
Article Contents
Journal of Beijing University of Aeronautics and Astronautics  > 2022  >  48(12): 2345-2355.
XING Zhiwei, HOU Xiangkai, LI Biao, et al. Civil aviation luggage cart stacking algorithm based on dynamic quadtree search[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(12): 2345-2355. doi: 10.13700/j.bh.1001-5965.2021.0144(in Chinese)
Citation: XING Zhiwei, HOU Xiangkai, LI Biao, et al. Civil aviation luggage cart stacking algorithm based on dynamic quadtree search[J]. Journal of Beijing University of Aeronautics and Astronautics, 2022, 48(12): 2345-2355. doi: 10.13700/j.bh.1001-5965.2021.0144(in Chinese)
shu

Civil aviation luggage cart stacking algorithm based on dynamic quadtree search

doi: 10.13700/j.bh.1001-5965.2021.0144
  • 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
  • Received Date: 25 Mar 2021
  • Accepted Date: 05 Sep 2021
  • Publish Date: 16 Sep 2021
    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.

     

    • FullText(HTML)
  • loading
    • References(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
    • Relative Articles
    • Supplements(0)
    • Cited By
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(15)  / Tables(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views(264) PDF downloads(32) Cited by()
    Proportional views
    Related

    Copyright © Journal of Beijing University of Aeronautics and Astronautics

    Address: Editorial Department of Journal of Beijing University of Aeronautics and Astronautics, 37 Xueyuan Road, Haidian District, Beijing Post Code: 100191 Email: jbuaa@buaa.edu.cn

    Supported by: Beijing Renhe Information Technology Co., Ltd.    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return