基于混合遗传算法的多箱型集装箱装载问题研究

周勇

寰宇东方国际集装箱（青岛）有限公司 山东青岛 266500

1 问题描述

多箱型集装箱装载问题可以描述为：在一定的约束条件下，将大量质量不等、大小不同的货物以适当的装载方法装入到多个集装箱中，其中待装载集装箱为常用的四种航空集装箱（AMA、AKE、AMF、AAU集装箱），使得满足实际约束的情况下各集装箱的体积利用率最大，以提高航空集装箱运输中对集装箱的合理利用，从而降低运输成本提高经济效益。

考虑到货物实际装箱问题的复杂性，作出如下假设：①货物密度均匀，形状均为长方体，尺寸各异且不大于集装箱尺寸；②货物由挤压产生的微小形变可忽略；③货物的码放不受限制，可放置在箱内任意位置。④货物具有不同到站。

2 模型搭建

符号说明：

以各集装箱底面为XY平面、垂直底面向上为Z轴，以其左后下角为原点建立空间直角坐标系。符号说明如下：n为待装货物总数量，N为航空集装箱总数量；αij为0/1变量，货物i装入集装箱j则值为1，否则值为0；λj为0/1变量，若集装箱j被使用则为1，若未使用则为0；，jjMV为集装箱j的最大载重量及容积：wi，hi，di，vi，mi，[gxi，gyi，gzi]是货物i的长、宽、高、体积、质量及其重心坐标；Beari，BLi分别是货物i所承受的重量及最大承受力；Bi，Ci分别是货物编号、装载顺序编号。[conx1，conx2]，[cony1，cony2]，[0，conz]分别是x、y、z轴重心安全区间；（xi，yi，zi）是货物i在集装箱中的放置位置坐标即左后下，右前上角坐标。

3 混合遗传算法设计

3.1 遗传操作过程

选择操作：

选择过程采用轮盘赌与最佳个体保护策略。

最佳个体保护策略：为保留最优的算子，应尽可能地保证高评价值个体的存在，充分利用遗传算法“适者生存”的特点，当生成新种群后，通过评价函数计算出本代中最差的个体，并用上代最优的个体去替代，使得最优个体得到保存。

3.2 混合遗传算法装载多箱型集装箱的步骤

基于以上思想，加入模拟退火算子，用其突跳性使遗传避免陷入局部最优的情况。混合遗传算法求解多箱型集装箱具体步骤如下：第1步将集装箱的型号、尺寸与货物的基本信息输入程序，并设置算法相关参数。第2步计算初始所需集装箱数量N，对货物编号进行预处理并确定问题采用的编码方式。第3步采用随机产生初始种群S的方式以方便进行全局搜索，保证算法的全局搜索优越性，避免早熟现象的出现。第4步基于空间划分的拟人式放置原则装载初始数量的集装箱。第5步判断货物是否剩余，若剩余，随机打开新的集装箱N：=N+1，转步骤3；若货物无剩余，转第6步。第6步对现有种群进行以下操作，直到生成下一代新种群：计算种群中个体的评价函数值，利用轮盘赌实现个体选择。

4 实例验证

由表1可以看出，虽然货物具有强异构性，且集装箱形状不规则，但四种不同集装箱的平均体积利用率高于82%，在满足实际装载条件的前提下保证了较高的体积利用率，避免了不必要的空间浪费。

表1 航空集装箱参数

5 结语

（1）模拟工人的操作经验与方法，设计了货物的放置规则，采用罚函数处理重心约束、不重叠约束和承重约束，并加入最佳个体保护策略、模拟退火算子等进一步提高了遗传算法的优化效果。

（2）实验部分通过性能测试，表明所提算法能够较好的解决大规模货物的装载问题，并通过实际航空货物装载实验，四种不同箱型的集装箱体积利用率均高于82%，表明该算法能够有效解决多箱型航空集装箱的装载问题。