基于混合模拟退火算法的多约束装箱问题研究

胡智莹，周翔，李建伶，刘峻良

摘 要：文章针对现实中在实际多种约束条件下存在的三维装箱问题，考虑在多种现实约束条件下，建立一个装箱模型。该模型通过启发式算法得到一个初始解，再根据模拟退火法得到最优解，利用标准抽样对最优解进行多次测试，得到符合实际情况的最优解，提高空间利用率，从而实现利润最大化。最后，以一个具体的例子进行测试，计算结果表明在约束条件下装箱问题的解决方案可行性较强。

关键词：多约束装箱问题;启发式算法;模拟退火算法

1 新型的混合模拟退火法

在多种约束条件下，为了解决最优化装箱问题，本文运用了改进后的模拟退火法[1]与启发式算法[2]相结合的方式产生了一种新型的混合模拟退火法。该方法利用启发式算法对最优解进行搜索，同时在搜索最优解的过程中引入记忆功能，保证了利用本方案搜索解的不重复性和全面性，确保搜索到的解为最合适的解。

2 现实约束

实际情况的不一样，导致受到的约束也不一样，本文考虑了如下几种约束条件[3]：

（1）方向约束。规则的箱体有6个面，所以装箱时，每一种货物都有6种摆放方式。本文考虑的方向约束条件中包含了6种摆放方式，即认为6个面的摆放方式会产生6种不同的结果。

（2）各货物堆放时，没有出现形变、重叠的情况。

（3）各货物严格与装载的箱体平行，没有斜放的情况出现。

（4）容积约束。各箱体装载时只在有效容积以内，即装载的货物都包含在将要装载的箱体以内。

（5）重量约束。货物有一定的堆放层数的约束，并且装载的货物不能超过箱体的最大承重量。

（6）装载顺序约束。由于实际生活的需要，货物在装载和卸货中，遵循“先上后下”的原则。

3 理想模型的假设

本文研究多约束的装箱问题，同时结合现实生活中方向、容积、重量、装载顺序等多方面的条件约束做出如下模型假设：集装箱为标准的长方体;集装箱外部尺寸与内部尺寸相同;货物重量分布均匀且为标准的长方体;货物不会产生形变。

4 模型的建立

设在每一温度下抽样次数的最大值为Max，在不改变当前温度状态的抽样次数的最大值表示为z，接受该状态的次数表示为a，则利用混合模拟退火法解决多种约束条件下三维装箱问题的具体方法如下。

4.1 运用启发式算法得初始解

（1）在给定的n种货物中，根据其实际的下载顺序，逆序生成上载顺序，从而生成不同的批次，在每一批次，根据各货物体积的大小生成一个集合B[4]。

（2）初始化条件：设现阶段已经完成装箱任务的货物种类数量为i，且i的初始值为0。

（3）将i加1得到预比值，并将预比值与n进行比较，如果预比值小于或者等于n，则继续进行下一步，如果大于则跳转到第（5）步。

（4）对于将要装箱的第i种货物按照体积进行分块，得到集合Si，对每一个块即Si的元素按照前述方法进行装载，Si每个元素装载完毕即认为第i种货物装载完毕，转第（3）步。

（5）结束。

4.2 改进模拟退火算法

（1）设在每一温度下抽样次数的最大值为Max，在不改变当前温度所在状态的抽样次数的最大值表示为z，接受该状态的次数表示为a。

（2）对启始温度ts和结束温度tf等参数进行初始化处理。

（3）运行启发式算法程序，得到初始解s，令i=0且令得到的初始解s为目前得到的最优解，即best=s，当前状态，s（k+1）=s（k） ，s（i）=s。

（4）令T=t（i），以T，best以及s（i）为参数代入改进的抽样过程程序，运行程序，将得到的值，更新为当前的最优解best，并将此结果返回到抽样过程中，并令s（i+1）=best。

（5）if f（best）≤f（best），则best=best。

（6）退温：

;T=e-paT; i=i+1

（7）假設T

（8）输出最优解的结果best，当前算法结束。

4.3 改进标准抽样过程

（1）令k=0，初始状态s（k）=s（i），初始最优解best=best，q=0， accept=0; k为抽样的次数，q为连续抽样而没有改进状态的次数。

（2）通过执行邻域操作，由当前的状态s（k）产生一个新的状态s*， 然后运用评估函数计算?f=f（s（k））-f（s*）。

（3）如果条件?f<0成立，则令s（k+1）=s*，best=s*，accept=accept+1，以及q=0。

（4）当?f≥0的条件满足时，则程序将以exp（﹣?f/T）的概率接受新得到的解s*， 假设概率方式即新解被接受后，则令s（k+1）=s*， q=0， accept=accept+1。

（5）如果条件没有被满足，那么对抽样的状态以及抽样进行的次数进行更新，即令s（k+1）=s（k） ， q= q+1。

（6）令k=k+1，若k≥L或者q≥stay，则转向步骤（5），否则，转向步骤（2）。

（7）将得到的accept，best值输出，并退出退火过程，此次抽样的过程到此结束。

5 实例验证

模型建立后，考虑到容积、方向、稳定性、装载顺序、重量等多方面的约束在实际装载过程中的运用，本文采用标准的RAR集装箱进行装箱的计算，其具体的长、宽、高数据和载重量属性如表1所示。

本例采用的货物数据源于赵雨霏的《我国快递企业航空货运飞机装载优化研究》一文，详情如表2所示。将以上货物数据代入程序进行装箱的模拟，程序运行结束后可以得到结果：利用两个标准集装箱就可以将表2的货物全部转载完，且其中装载量最大的集装箱体积利用率为96.25%，箱号为1的集装箱长度公差、宽度公差、高度公差分别为1 cm，2 cm，1 cm，体积利用率为96.25%。本次算例最大三维装箱如图1所示。

6 結语

在解决多约束条件下的三维装箱问题，本文采用启发式算法以及模拟退火算法与标准抽样算法相结合的方式，提出了一种新的解决方案。结合约束条件，对现实生活中的货物装载算例进行了测试，得到了一种理想条件下的装箱解决方案，证明了本文算法的高效性和可行性。在利用启发式算法过程中，模拟了人工进行装箱的过程，通过标准抽样与模拟退火法的集成，大大提高了集装箱体积利用率，为多约束装箱问题的求解提供了一种解决方案。

作者简介：胡智莹（1999— ），女，湖北武汉人，本科生;研究方向：电气工程及其自动化。

[参考文献]

[1]张钧，贺可太.求解三维装箱问题的混合遗传模拟退火算法[J].计算机工程与应用，2019（14）：32-39，47.

[2]张德富，彭煜，张丽丽.求解三维装箱问题的多层启发式搜索算法[J].计算机学报，2012（12）：2553-2361.

[3]曹玲芝.求解三维装箱问题的混合模拟退火算法研究[D].广州：华南理工大学，2013.

[4]陈丽.基于三维装箱问题的混合遗传模拟退火算法的改进[D].郑州：郑州大学，2013.

Research on multi-constraint packing problem based on hybrid simulated annealing algorithm

Hu Zhiying， Zhou Xiang， Li Jianling， Liu Junliang

（College Of Electrical Engineering&New Energy， Three Gorges University， Yichang 443002， China）

Abstract：In view of the three-dimensional packing problem existing in real variety of constraints in the reality， this paper takes into consideration the establishment of a packing model under various practical constraints. In this model， an initial solution is obtained by a heuristic algorithm， and the optimal solution is obtained according to the simulated annealing method， and the optimal solution is tested for many times by the standard sampling， the optimal solution of the actual situation is obtained， and the space utilization ratio is improved， and the profit maximization is realized. Finally， the test is carried out in a specific example， and the calculation result shows that the solution of the packing problem is strong under the constraint condition.

Key words：multi-constraint packing problem; heuristic algorithm; simulated annealing algorithm