浅论装箱多约束三维装箱理由综述一般

论文导读：
摘要：至今三维装箱已经诞生出了很多优秀的研究结果，这其中包含有启发式算法，遗传算法，蚁群算法，以及模拟退火算法等解决方法。近几年来随着物流行业的飞速发展，成本控制在物流行业中显得尤为重要，因此，针对三维装箱这一类典型NP-complete问题有了更高的要求。在此，对三位装箱近几年来几种典型的研究算法进行了相应的详细介绍，并通过对各种算法进行比对分析，总结了多约束三维装箱过程现阶段所存在的一些问题，最后展望了该问题的发展方向。
关键词：三维装箱；装箱策略；自由落体算法；遗传算法；条形装箱；NP完全问题；启发式规则；多目标优化；模拟退火算法；禁忌搜索算法；组合优化；交互式算法；预分配策略；现实约束
1007-9599 （2012） 17-0000-03
1引言
近些年来随着物流行业的快速发展，在激烈的竞争下，物流企业在控制成本的方面提出了越来越高的要求。在物流公司的运营成本中，集装箱装载成本已成为最重要的一项内源于：毕业论文致谢范文www.7ctime.com
容。因此，在最大程度上的提高集装箱装载水平，降低集装箱装载成本，已成为当务之急。
在问题求解的早期阶段，大多采用单独设计一组启发式规则来满足某一种通用的装箱问题求解方案。George在A Heuristic for Packing Boxes into a Vontainer一文中提出将箱体分层的策略之后，很多研究人员均采用了这一原则。启发式策略在解决装箱问题时的确具有其独到之处，但在规模化程度上升时，重复的使用启发式算法不能在有限的时间内得出比较理想的结果。之后，更多的人逐渐意识到具有全局搜索能力的遗传算法（GA）去解决装箱问题具有独特的优势，随后关于GA解决装箱问题的算法逐渐涌现。与单一的启发式算法比较，通过引入遗传算法，无论在设计的可扩展性，规范性还是在求解问题效率方面都得到了很大的改善。最后，一种新的协同进化计算方法也被应用到装箱问题的过程中，相信随着各类算法的进一步的深入研究，可以得到更好的装箱的解决方法。
2三种代表性算法在三维装箱问题中的研究

2.1启发式算法解决方案

首先介绍一下国外的具有代表性的启发式算法，George和Robinson算法的主要思想是通过建立容器宽度层，结合空间平整规划，使得剩余空间外表面平整，来提高容器的利用率。Bischoff和Dowsland方法同George和Robinson方法相类似，也是基于通过建立容器宽度层进行填充的。Bischoff和Dowsland方法和George和Robinson方法相比较还有着明显的不同：第一，箱体内各个层的物品种类单一；第二，单体层内的布局采用二维布局过程，将单个容器的宽*高面积的利用率最大化。这两种方法共同点是：在物品的种类单一，数量很大的情况下，可以得到较好的解。
Did Pisinger提出了基于墙壁支撑理论的容器启发式装载方法，该方法是把空间先分层然后划条的方式来分割。采用分枝定界法来规划层和条的划分，该方法针对Hetrogeneous类和Homogeneous类的具体问题进行了测试，结果表明较大规模的问题所获得的较优解的质量更好。
Michael Eley提出了建立同一个方向上的同质块算法，首先，将物品在相同的方向上进行排放，然后将堆放好的物品继续放入集装箱。这种装箱方式使装入容器中的物品装卸方便，摆放稳定。
国内具有代表性的是陈治亚提出的启发式算法：在模拟实际装箱的过程中，总是尽量使得每一层装箱效果比较“平直”，从而设计了一种智能启发式算法，用来克服一般启发式算法对于经验的依赖，该算法的主要思想是对人工智能思路的模拟，在装箱的过程中人们总是在经验的指导下挑选与已经装入的箱体尺寸相差较小的一只箱子装入，在这种方式的指导下可以确保每一层装的相对平直，例如，我们可以在一个坐标方向进行选择，然后通过目测所选尺寸与已装入尺寸相差不大的物品来装入，假如某个方向上有缺口，那么通常的做法采用寻找一件物品来把缺口填平，直到没有合适的物品为止，然后在该方向上继续装入新物品。
另一种比较有代表性的启发式算法是由国内张德富教授提出的组合启发式算法：在日常的生活中，采用拟人的思想来解决实际问题通常是很有效的。在砌墙的过论文导读：的总长度尽量小于F的总长度L，且具体的高与宽应当尽量接近。Step2：将R’的宽按照具体的宽度来进行排列。Step3：将排好的元素逐个放入装箱页面中，其中R’宽度较大的对应当前较窄的一段，依据当前装箱的凹凸度来具体判断箱体是否下移。Step4：在R=R-R’时，假如R已经为空，算法结束，否则进行下一步。Step5：假如已装
程中，人们一般会先放置一块参考砖，并且将参考砖的高度作为基准，设定每块物体的高度均不能超过参考高度，当物体不再能放入箱体时则提高参考高度，受此类思想的启发，我们在解决三维装箱问题的过程中，在垂直和水平方向上均引入参考高度来指导装填的过程，采用了记录可放置特殊点的方式来查找装填位置，此方法的不同之处在于不需要装填结构作为特定的条件，从而使装填过程比较灵活，并且通过垂直水平参考线和水平参考线来指导装填的全过程，最终与模拟退火算法相结合来改变箱子的装填方向与装填顺序。结果表明，此方法可以获得较高的填装效率。但是在箱子种类较少的情况下，解空间比较有限，改进效果不明显；而在箱子种类较多的情况下，算法的运行时间较长。

2.2遗传式算法解决方案

遗传算法（GA）本身作为一种随机搜索的算法，具有非常强的全局搜索能力，特别针对求解问题的近似最优过程，用遗传算法来解决装箱问题具有可行性。但遗传算法本身存在着许多的不足，尤其在针对解群分布不均匀的时候容易出现未成熟的收敛，陷入局部最优。目前针对基本遗传算法仍有很多需要改进的工作，为避免未成熟的收敛，以及提高群体多样性是改进的主要方面之一。
国外首先提出遗传算法应用于三维装箱领域的是Gehring H。在解决三维装箱的问题上采用建立多维模型的遗传算法，并且在当时具有很大程度的创新性。之后，相关的国内文献中，大多数均会涉及到该算法的核心思想。
国内在求解基于遗传算法的三维装箱问题方案中，具有代表性的是曹先彬，他提出了采用免疫遗传算法对装箱问题来进行求解，下面具体介绍一下他提出的相关算法：已有待装箱的一个组合R={R1，R2，R3……，RN}，Ri代表第i个箱体，其中ai，bi，ci表示箱体的长，宽，高。F=L*W代表将要填充的箱子。对R求出相应的子集，将其中的各个元素互不重叠的对方在F中，最终可达到较高的空间利用率。
具体的装箱步骤如下：
Step1：针对当前装箱的墙面，对R求出相应的子集R’，并且R’中的元素的总长度尽量小于F的总长度L，且具体的高与宽应当尽量接近。
Step2：将R’的宽按照具体的宽度来进行排列。
Step3：将排好的元素逐个放入装箱页面中，其中R’宽度较大的对应当前较窄的一段，依据当前装箱的凹凸度来具体判断箱体是否下移。
Step4：在R=R- R’时，假如R已经为空，算法结束，否则进行下一步。
Step5：假如已装入元素的顶点坐标已经在方向上大于W，则超出宽度剩余的元素一同放回至R中，若当前装箱完全处理结束时，进行下一步，否则转到第二步继续执行。
Step6：若R不为空，同时F还有剩余空间时，转到第二步对上一层进行装箱，否则结束算法。
此外，江那提出的关于遗传模拟退火算法的港口装箱研究，同样代表了一种新的解决方案。将模拟退火算法与遗传算法相结合，生成一种创新的优化算法。虽然遗传算法具有很多优点，比如：应用范围广，鲁棒性强，使用简单等。但其本身也有许多的不足，尤其在过早的收敛上，容易陷入到局部最优解中，所以将模拟退火算法引入至遗传算法中，过程如下：
（1）针对控制参数进行初始化：α为温度冷却参数；T。为退火初始温度；Pm为变异概率；N为群体规模；
（2）初始化随即种群；
（3）具体产生种群的操作如下所示：
·在种群中对每个个体的适应度进行评价，将空间利用率作为适应度的函数。
·通过选择算法来选择个体。
选择的具体思想是：生成随即数γ∈[0，1]，同时计算相对适应值pi=fi/∑fi，假如，p0+p1+…+pi-1<γ≤p0+p1+…+pi，则相应个体被选择至下一代。由此可见，个体的适应度值大的个体被选至下一代中的几率相应较高。
·对复制的个体进行交叉操作，分别选择两个个体xi和xj进行交叉操作，相应计算个体的适应函数值f（x'i）和f（x'j）；生成具体在[0，1]之间的随机数，记为random，以min{1，exp（-Δf/Tk）}>random[0，1]概率得出的新解，作为新个体。
·对交叉后的个体进行变异操作，按第三步中的方法决定是否接收变异后的解；
（4）若在收敛条件得到满足时，结束进化过程；否则Tk+1=α，转（3）。
首先模拟退火算法利用选择法淘汰了较低适应度的个体，而遗传算法的核心是交叉操作，从而实现了进一步的寻优过程。在这一思想的指导下，模拟退火算法在选择后代的过程中均采论文导读：
用交叉操作，将编译与交叉后的父代与子代充分竞争，不但对保留优良个体有利，同时预防了过早收敛等问题。随着进化过程，逐渐温度下降，接受劣质解的概率同时也逐渐下降，充分利用了模拟退火算法的特性，提高了收敛的速度。

2.3一种新的协同进化计算方法

由国内张新征提出了一种创新型协同进化算法Coop&compEA与某种启发式规则相结合来解决典型的NP-complete问题。在用该策略求解的过程中，通过利用Coop&compEA算法将个体层的合作进化过程添加到种群竞争的行列中。在该过程中，即对合作进化的求解质量进行了优化，又为竞争的收敛效果增加了融合度；此外，装箱过程的启发式规则得到了完善，实验结果表明，这种求解方式，无论在进化速度还是在求解效果上都优于传统CCGA方法和GA方法。
下面对Coop&compEA协同进化算法做进一步具体介绍：
Step1：该问题由n个小问题组成。算法随即的初始化个体，子群和种群。其中种群中子群的向量Si=（Si1， Si2， Si3…， Sin），种群向量S=（S1，S2），种群i的第j个子群个数即为子群大小为|Sij|。
Step2：种群内的子群采用合作方式，在种群S1，S2的子群向量采用目标函数合作计算的方式得出个体适应度。依据适应度值来组成全局最优解。若在当前的过程中得出满意结果或者超出进化代数的限制而结束。
Step3：将种群的向量S中的每个个体组成全局解，进行采样并放入向量集T=（T1，T2）中。
Step4：对测试集向量T=（ T1，T2）采用种群竞争的方式进行计算。
Step5：将反馈因子以竞争结果的方式来奖励给个体，并对适应值进行修改。
Step6：将最佳个体逐个保存，并对种群中的子群向量Si=（Si1， Si2， Si3…， Sin）依据适应度数值来采用GA操作，并转至Step2。
3对比分析
在比较中，本文中包含了Bischoff在文献中所提及的启发式算法H_BR，Gehring[9]提出的GA_GB算法以及Bortfeldt所采用的禁忌搜索算法TS_BG，Bortfeldt等提出摘自：毕业论文提纲www.7ctime.com
的混合遗传算法HGA_BG以及并行遗传算法，Bortfeldt等提出的并行禁忌搜索算法PTSA，Kim提出的MFB算法，Biles等提出的GRASP算法，Bischoff提出的新启发算法H_B以及Bortfeldt等提出的启发式算法SPPBBL-C，张德富等提出的组合启发式算法CH，模拟退火算法HSA以及黄文琪等提出的A2算法。
表1和表2都是在满足C1的条件下进行装箱的，此外HAS，TS_BG，GA_GB，H_BR算法的装箱结果均满足C2的约束，并属于完全支撑的类型。在问题需要满足越来越多约束的条件下，求解的过程也相对较为困难。
此外，表2的最后两行中都是在不采用其他算法的辅助下，表示混合模拟退火算法基础启发中的填充率和组合启发式算法你人启发中的填充率，他们均在默认输入下计算。拟人启发式序列以体积从大到小排序，而基础启发式则更多考虑约束条件C1和C2得到满足。在这种情况下，由表2可知，基础启发式的计算结果实际过程中均超出拟人启发式策略，填充率的平均值高出约1.5%。在组合启发式策略下的平均填充率高出约2.0%。结果充分证明了初始启发式算法，具有很大的优势。由上可见，启发式算法的优劣对提升领域搜索算法在复杂三维装箱问题上有着举足轻重的作用。
4结论
本文主要介绍了关于启发式算法，遗传算法以及其他混合算法来解决复杂三维装箱中装箱效率的问题，随后对这些算法的优劣程度进一步进行了归纳，并通过1000个测试的计算结果来分析实际装箱过程中装箱算法的效率问题。由以上分析得出，在领域搜索技术紧密结合的启发式算法是求解复杂三维装箱问题的一种有效解决方案。
参考文献
陈德良，陈治亚.三维装箱问题的智能启发式算法[J].中南林业科技大学学报 Vol.29 No.3.
阎威武，邵惠鹤，田雅杰.集装箱装载的一种启发式算法[J].信息与控制，2002，31（4）：353-356.
[3]张德富，魏丽军，陈青山，陈火旺.三维装箱问题的组合启发式算法[J].软件学报，2007，9.
[4]周明，孙树栋.遗传算法原理及应用.北京：国防工业出版社，2论文导读：000.江娜，丁香乾，刘同义等.集装箱装载问题的模拟退火遗传算法.电子技术应用，2005，10.张新征.用Coop&compEA解决三维装箱问题.计算机工程与应用，2005，（15）：82-85.黄文琪.基于A2算法的装箱问题求解.小型微型计算机系统，2000，21（4）：273-279.上一页1234
000.
[5]江娜，丁香乾，刘同义等.集装箱装载问题的模拟退火遗传算法[J].电子技术应用，2005，10.
[6]张新征.用Coop&compEA解决三维装箱问题[J].计算机工程与应用，2005，（15）：82-85.
[7]黄文琪.基于A2算法的装箱问题求解[J].小型微型计算机系统，2000，21（4）：273-279.