引用本文

李孙寸, 施心陵, 张松海, 董易, 高莲. 基于多元优化算法的三维装箱问题的研究. 自动化学报, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381

LI Sun-Cun, SHI Xin-Ling, ZHANG Song-Hai, DONG Yi, GAO Lian. Multi-variant Optimization Algorithm for Three Dimensional Container Loading Problem. ACTA AUTOMATICA SINICA, 2018, 44(1): 106-115. doi: 10.16383/j.aas.2018.c160381

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160381

关键词

三维装箱问题，多元优化算法，随机放置，局部调整，逐步逼近 

摘要

用多元优化算法（Multi-variant optimization algorithm，MOA）实现三维装箱问题的求解.算法通过随机放置和局部调整从而逐步逼近最优解.随机放置是将随机选择的几个箱子装入容器中；局部调整是根据目标函数值对随机放置容器的箱子序列作局部调整优化；通过递推的随机放置和局部调整优化，目标函数值逐步逼近最优值，从而获得一个较为理想的三维装箱方案.算法通过对BR1~BR10共1000组三维装箱问题测试实例的测试仿真，得到理想的装箱效果，说明用多元优化算法实现三维装箱问题的有效性和可行性.

文章导读

装箱问题按照目标函数的不同类型分为容器装载问题、箱柜装载问题和背包装载问题[1].容器装载问题是将所有待装箱子装入一个不限尺寸的容器中, 在诸多方案中找到一个使容器体积最小的装载方案, 该类型问题一般规定容器的长和宽为常数, 高为变量; 箱柜装载问题是给定一些规格统一的方型容器和一些不同类型的方型箱子, 找到一个能把所有箱子装入最少容器中的装载方案; 背包装载问题是给定一个固定规格的容器和一些有一定价值的箱子, 然后将部分箱子装入容器中, 找到一个使得装入容器中箱子总价值最大的装载方案, 若将箱子的体积作为价值, 则背包装载问题就转换为找到一个如何使容器的填充率最大的装载方案.其中容器装载问题和箱柜装载问题具有一定的局限性, 限制了其工业领域的应用范围.因此本文从背包装载问题入手对三维装箱问题作初步研究.

装箱问题是传统的NP问题, 具有广泛的应用领域.随着当今世界信息技术、大数据、数据流、数据关系的分析处理的不断发展, 为装箱问题的应用拓展了新的领域, 例如信息网络、交通网和云存储等有限资源的最大利用率问题, 有限资金投资的收益率最大化问题, 以及大数据相对关系匹配度最大化问题等.如何提高容器的空间利用率, 是当代科学研究和实践中一个非常重要的课题.找到高利用率的装箱方案, 对节约天然资源, 降低企业成本, 提高企业利润, 有着十分积极的现实意义.

近年来, 国内外的学者们陆续提出了一些解决三维装箱问题的算法. Ngoi等[2]采用独特的空间表征技术求解装箱问题. Bischoff等提出了一种启发式算法, 同时给出了三维装箱问题的一些测试实例[3-4], 其中文献[3]根据层和条的选择策略, 提出了按层布局的贪婪算法. Sixt提出了基于元启发式的禁忌搜索和模拟退火算法[5]. Gehring等提出并行化的遗传算法, 该方法先对箱子进行一定的预处理, 再用遗传算法对箱子进行优化组合来获得装载方案[6]. Bortfeldt等提出了一种禁忌搜索算法, 但该种方法只适用于箱子种类较少的情况[7].接着, Bortfeldt等针对层的策略, 又提出一种混合遗传算法[8].同时期, 国内学者何大勇等提出了求解复杂集装箱装载问题的遗传算法[9].随后, Eley提出了基于"块"的算法[10], 在此基础上, Bortfeldt等也基于"块"的概念, 给出了并行禁忌搜索算法[11]. Moura等基于"剩余空间的概念", 提出了一个贪心随机自适应搜索算法(Greedy randomized adaptive search procedures, GRASP)[12].张德富等针对圆形的装箱问题提出了拟人退火算法[13], 随后, 又提出了三维装箱问题的组合启发式算法[14]. Parrenóo等在文献[12]的基础上往前发展了一步, 将GRASP做了改进, 取得了明显的装箱效果[15]. Huang等针对单一类型的装箱问题提出了一个有效的拟人型穴度算法[16].张德富等提出了混合模拟退火算法, 该方法首先将箱子生成复合块, 接着给出一个基于块装载的构造型启发式算法, 然后将该启发式算法和模拟退火算法相结合, 提出了一个有效求解三维装箱问题的混合模拟退火算法[17]. Fanslau等也基于复合块的概念, 设计了一个有效的启发式树状搜索算法[18].张德富等又在文献[17-18]的基础上设计了一个多层启发式搜索算法[19], 该算法是采用深度和宽度同时搜索的思想, 提出的多层搜索算法, 该算法用多层搜索思想来选择一个近似最优块进行装载, 然后逐步构造直到获得一个装载序列, 较之前的算法取得了很好的装载效果, 但随着箱子规模的增大, 该算法需要较长的计算时间.刘胜等提出的求解三维装箱问题的启发式正交二叉树搜索算法[20], 该装箱算法装箱效率较已有算法装箱效率有显著提高, 但是当箱子种类较少时, 该算法的优势不明显.当然, 还有一些学者也取得了很好的研究成果[21-28].

在很多实际工业应用中, 待装箱子具有规格多样性和数量不确定性等特点.因此本文结合最优化原理, 用多元优化算法(Multi-variant optimization algorithm, MOA)实现三维装箱问题的求解, 该算法的基本思想是随机放置、局部调整和逐步逼近.通过对BR1 ∼ BR10共1 000组实例的仿真测试, 取得明显的装箱效果, 证明了本文算法的有效性和可行性.

图 1  空间的分割

图 2  箱子的摆放方式

图 3  空间合并方式

三维装箱问题属于典型的NP难题, 本文采用多元优化算法求解, 具有随机放置、局部调整和逐步逼近三大特性.经过多次实验测试, 取得理想的装箱效果, 证明了多元优化算法实现三维装箱问题的有效性和可行性.由于本文采用的是分批次随机放置, 因此针对实际装箱问题中的复杂性和不确定性具有很好的优势.但是算法若要得到更高的装箱效果, 就要增大试验次数, 随之计算时间也会增大.同时, 分多少批次装载和每批次装多少个等这些参数的设置与对象紧紧相关, 不具有一般性.

作者简介

施心陵

云南大学信息学院教授.主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学.E-mail:xlshi@ynu.edu.cn

张松海  

云南大学信息学院硕士研究生.主要研究方向为智能优化算法, 电网可靠性分析.E-mail:hai_zs@sina.com

董易  

云南大学信息学博士研究生.主要研究方向为智能优化算法及其应用.E-mail:yeo003@163.com

高莲  

博士, 云南大学信息学院讲师.主要研究方向为生物医学信号处理.E-mail:yanglianbao@yunneidongli.com

李孙寸  

云南大学信息学院硕士研究生.主要研究方向为智能算法及其应用.本文通信作者.E-mail:lisuncun@outlook.com