多约束三维装箱问题探究综述

《多约束三维装箱问题探究综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、多约束三维装箱问题探究综述摘要：至今三维装箱已经诞生出了很多优秀的研究结果，这其中包含有启发式算法，遗传算法，蚁群算法，以及模拟退火算法等解决方法。近几年来随着物流行业的飞速发展，成本控制在物流行业中显得尤为重要，因此，针对三维装箱这一类典型NP-complete问题有了更高的要求。在此，对三位装箱近几年来几种典型的研究算法进行了相应的详细介绍，并通过对各种算法进行比对分析，总结了多约束三维装箱过程现阶段所存在的一些问题，最后展望了该问题的发展方向。关键词：三维装箱；装箱策略；自由落体算法；遗传算法；条

2、形装箱；NP完全问题；启发式规则；多目标优化；模拟退火算法；禁忌搜索算法；组合优化；交互式算法；预分配策略；现实约束中图分类号：TP301.6文献标识码：A文章编号：1007-9599(2012)17-0000-031引言近些年来随着物流行业的快速发展，在激烈的竞争下，物流企业在控制成本的方面提出了越来越高的要求。在物流公司的运营成本中，集装箱装载成本已成为最重要的一项内容。因此，在最大程度上的提高集装箱装载水平，降低集装箱装载成本，已成为当务之急。在问题求解的早期阶段，大多采用单独设计一组启发式规则来

3、满足某一种通用的装箱问题求解方案。George在AHeuristicforPackingBoxesintoaVontainer—文中提出将箱体分层的策略之后，很多研究人员均采用了这一原则。启发式策略在解决装箱问题时的确具有其独到之处，但在规模化程度上升时，重复的使用启发式算法不能在有限的时间内得出比较理想的结果。之后，更多的人逐渐意识到具有全局搜索能力的遗传算法（GA）去解决装箱问题具有独特的优势，随后关于GA解决装箱问题的算法逐渐涌现。与单一的启发式算法比较，通过引入遗传算法，无论在设计的可扩展性，规

4、范性还是在求解问题效率方面都得到了很大的改善。最后，一种新的协同进化计算方法也被应用到装箱问题的过程中，相信随着各类算法的进一步的深入研究，可以得到更好的装箱的解决方法。2三种代表性算法在三维装箱问题中的研究2.1启发式算法解决方案首先介绍一下国外的具有代表性的启发式算法，George和Robinson算法的主要思想是通过建立容器宽度层，结合空间平整规划，使得剩余空间外表面平整，来提高容器的利用率。Bischoff和Dowsland方法同George和Robinson方法相类似，也是基于通过建立容器宽度

5、层进行填充的。Bischoff和Dowsland方法和George和Robinson方法相比较还有着明显的不同：第一，箱体内各个层的物品种类单一;第二，单体层内的布局采用二维布局过程，将单个容器的宽*高面积的利用率最大化。这两种方法共同点是：在物品的种类单一，数量很大的情况下，可以得到较好的解。DavidPisinger提出了基于墙壁支撑理论的容器启发式装载方法，该方法是把空间先分层然后划条的方式来分割。采用分枝定界法来规划层和条的划分，该方法针对Hetrogeneous类和Homogeneous类的具

6、体问题进行了测试，结果表明较大规模的问题所获得的较优解的质量更好。MichaelEley提出了建立同一个方向上的同质块算法，首先，将物品在相同的方向上进行排放，然后将堆放好的物品继续放入集装箱。这种装箱方式使装入容器中的物品装卸方便，摆放稳定。国内具有代表性的是陈治亚提出的启发式算法：在模拟实际装箱的过程中，总是尽量使得每一层装箱效果比较"平直”，从而设计了一种智能启发式算法，用来克服一般启发式算法对于经验的依赖，该算法的主要思想是对人工智能思路的模拟，在装箱的过程中人们总是在经验的指导下挑选与已经装入

7、的箱体尺寸相差较小的一只箱子装入，在这种方式的指导下可以确保每一层装的相对平直，例如，我们可以在一个坐标方向进行选择，然后通过目测所选尺寸与已装入尺寸相差不大的物品来装入，假如某个方向上有缺口，那么通常的做法采用寻找一件物品来把缺口填平，直到没有合适的物品为止，然后在该方向上继续装入新物品。另一种比较有代表性的启发式算法是由国内张德富教授提出的组合启发式算法：在日常的生活中，采用拟人的思想来解决实际问题通常是很有效的。在砌墙的过程中，人们一般会先放置一块参考砖，并且将参考砖的高度作为基准，设定每块物体的

8、高度均不能超过参考高度，当物体不再能放入箱体时则提高参考高度，受此类思想的启发，我们在解决三维装箱问题的过程中，在垂直和水平方向上均引入参考高度来指导装填的过程，采用了记录可放置特殊点的方式来查找装填位置，此方法的不同之处在于不需要装填结构作为特定的条件，从而使装填过程比较灵活，并且通过垂直水平参考线和水平参考线来指导装填的全过程，最终与模拟退火算法相结合来改变箱子的装填方向与装填顺序。结果表明，此方法可以获得较高的填装效率。但是在箱子种类