集装箱装载问题的动态融合策略优化算法

高 鹏，张德珍，张秀国

1.大连大学 经济管理学院（旅游学院），辽宁 大连 116622

2.大连海事大学 信息科学技术学院，辽宁 大连 116026

“一带一路”建设极大促进了沿线各国间的贸易往来，跨境货物运输量大为提高。由于集装箱在多式联运中可以有效减少货物转运时间，节省成本，提高运输效率，因此，使用集装箱装载货物成为海运和铁路运输的首选方式。然而近年来国际经济形势复杂多变，加之受新冠疫情影响，集装箱运费不断攀升。单个集装箱使用效率成为企业降低物流成本的关键。然而，实际应用中，货物生产企业在将客户所订购的多种规格、不同数量货物装入集装箱，往往因为货物摆放位置和次序不恰当，而装不下或浪费空间，导致多次“倒箱”操作，从而浪费大量人力、物力，甚至延误离岸时间，造成经济损失。该问题实际上是复杂现实约束条件下的集装箱布局优化问题。根据待装载货物种类多少以及每种货物数量多少，可以分为弱异类和强异类问题[1]、单集装箱和多集装箱问题[2]。本文研究的是单一集装箱强异类问题。该问题主要目标是提高填充率，在采用相同测试数据的前提下，Gongalves 等[3]在2012 年提出的解决方案的填充率比Bischoff 等[4]在1995 年提出的解决方案平均高出11%；但2017年，Araya等[5]提出BSG_VCS算法，填充率已达到94.6%，仅提高了约0.68%。在保证填充率的前提下，如何用更短时间来求解是值得深入考虑的另一个问题。

集装箱装载问题（CLP）理论上属于NP-Hard 问题，随着问题的规模的增加，采用数学规划的方法会消耗大量的内存和运行时间[6]，目前常用启发式算法进行求解[7]。对CLP问题，可以分为单一启发式算法和融合启发式算法。其中，单一启发式算法又可分为单一传统启发式算法与单一现代启发式算法。单一传统启发式算法较为实用，借助于人的主观经验进行设计，计算效率较高，而且能够对计算过程进行详细描述。如Bischoff等[4]提出了一种将货物均匀分布与多点负载相结合的元启发式算法，并为三维装箱问题提供了公共测试数据集。但传统启发式算法设计过于依赖人的主观经验，缺乏严格的数学理论证明，导致算法设计具有一定的随意性。现代启发式算法以仿自然体算法为主，主要有蚁群算法[8]、遗传算法[9]等，能够有效求解组合优化等问题，但若仅采用单一现代启发式算法，在运算初期其收敛速度较慢，货物选择具有较大随机性，所以求解效率往往较差。

考虑到融合启发式算法在处理超大规模问题时表现出更好的时间性能和优化性能，能在很大程度上弥补单一启发式算法的不足。部分学者提出可采用两阶段的分步求解策略，将求解过程进行严格划分，两个阶段求解过程相对独立。如Toffolo 等[10]将装箱过程划分为建立货物堆垛和将堆垛装箱两个阶段，将三维装箱问题转化为二维装箱问题；Paquay等[11]第一阶段采用自定义打包算法，为给定货物及ULD类型提供装载模式，第二阶段考虑可用容器的多样性，并设计算法进行打包；Saraiva等[12]第一阶段生成构造块，第二阶段构造元启发式算法。以上这些严格意义上的两阶段求解策略，在初期采用一种算法A以快速求解，在后期完全采用另一种算法B 进行求解。这类算法在初期有可能局限于某种算法而降低了整体随机性，并且在后期，由于完全采用B 算法而又丢弃了第一阶段采用A 算法的优越性。相对上述明确的两阶段划分求解策略，也存在未对求解过程进行明确划分的情况。如张煜等[13]提出了一种粒子群算法和邻域搜索算法融合的基于PSO 的模因算法；Goncalves 等[14]基于随机密钥提出了一种偏向随机密钥遗传算法（BRKGA）；Jamrus 等[15]基于扩展优先级策略，提出了一种混合遗传算法（EP-HGA）；张长勇等[16]基于一种由在线极值点算法与模拟退火算法相融合的算法；Moura等[17]基于墙体构造策略，提出一种贪婪随机自适应搜索算法（GRASP）；于明正等[18]将启发式算法和遗传算法的同时增加了一层提高搜索广度的遗传迭代层，从而构成了二层规划算法。这类算法主要以嵌套混合为主增加了算法的复杂性和计算负担。

蚁群算法的优势是在时间和空间上的寻优性能，但是蚁群算法前期信息素积累慢，导致算法收敛较慢，而贪心算法具有收敛快、计算量小的优势[19]。本文提出了一种基于概率的融合策略，来控制三空间贪心层叠法（GSM）与三空间蚁群层叠法（ASM）在选货方式上的参与程度，从而在保证解的多样性前提下，更好地发挥贪心算法的收敛优势和蚁群算法的寻优优势。在该策略下，初始阶段以GSM为主获得局部最优解，避免在算法执行初期因蚂蚁的信息素浓度偏低导致容易陷入局部最优解及运算时间过长的问题；逐步地以ASM为主，对各种不同局部最优装载链进行优化求解，获得全局解；通过调整分布函数，可以实现前后两个阶段中两种选货方式的参与程度可控，也有一定的概率产生随机解以保证解的多样性，最终实现算法的动态融合以提升求解效率。同时，在蚁群算法求解过程中，通过构造状态值和剪枝矩阵，对装载过程中的每个状态值，择优存储并更新剪枝矩阵。在剪枝矩阵中，每一个状态值只对应一条装载链，缩减了问题的可行解空间，从而有效缩短了程序运算时间。最后，基于本文提出的算法，采用Bischoff和Ratcliff[4]提出的BR1-BR10公共测试数据进行测试和对比分析。实验结果表明，本文所提出的算法对快速求解单箱强异类集装箱布局优化问题具有有效性和可行性。

1 问题分析与建模

1.1 问题描述

单一集装箱强异类装载问题，可描述为在满足一定约束条件下，将若干种类（通常大于10 种）且规格尺寸不同的长方体货物（每一种待装货物数量较多）装入一个尺寸固定的集装箱中，要求装载完成后剩余空间最小，即空间利用率最大化。

实际装箱问题因为条件复杂程度各异，制约了建模和求解过程，但现实条件如果过于简化，则无法满足实际装箱需要。本文根据所面向的实际工程问题，做如下假设：

（1）将集装箱和货物均看作是长方体，且货物的尺寸均小于集装箱尺寸；

（2）货物质量均匀分布，货物重心即为几何中心；

（3）不考虑货物承载能力，货物上可放置任意货物；

（4）货物没有挤压和变形；

（5）货物均到达同一个目的地。

1.2 符号说明

由于待装载货物种类多样且每类货物数量各不相同，故本文对关于集装箱装载问题变量及符号进行如下定义。

N：待装载货物的总数量；

nk：第k类货物的装载数量，范围为[nkmin,nkmax]；

uk：第k类货物的堆码层数，ukmax为第k类货物作为最底层货物的最大承载堆放层数；

vi：货物i的体积；

K：货物的种类数；

CT：最大迭代次数；

Ui：货物i装入集装箱则Ui=1，否则Ui=0；

L,W,H：集装箱的长、宽、高；

li,wi,hi：货物i的长、宽、高；

PiT(xTi ,yiT ,zTi)：货物i在集装箱中的右-前-上角点及其坐标；

PiB(xiB ,yiB ,ziB)：货物i在集装箱中的左-后-下角点及其坐标；

s：状态值，即由已装载货物种类和各类货物的数量生成的二进制数；

SΠ(i,p)：货物i在货物p上沿Z轴方向在XOY面上的投影面积。

1.3 装载模型约束条件描述

（1）每类货物的实际装载数量不能超出该类货物给定的数量范围；

（2）货物放置方向与集装箱两侧面平行或正交；

（3）货物不能悬空放置，即上方货物必须完全放置在下方货物的上面；

（4）实际装载货物的总容积不能大于集装箱的最大装载容积；

（5）货物其上可承载的层数为给定层数。

由于本文所研究的待装载货物在总重量和质心方面均在允许范围内，故不再对此类约束讨论。

根据实际装箱考虑的约束条件，建立约束条件表达式如下所示。

（1）数量约束：每类货物的实际装载数量不能超出该类货物给定的数量范围，即：

（2）方向约束：货物放置方向与集装箱两侧箱面平行或正交，其放置姿态共有6种。以图1放置为例，货物i在集装箱中的右-前-上角坐标、左-后-下角坐标及其与集装箱坐标轴间的位置关系，其形式化描述为：

图1 货物放置方向及标识点示意图Fig.1 Schematic diagram of cargo placement direction and marking points

其余5种可类比写出。

（3）放置约束：货物不能悬空放置，即上方货物的下表面必须与下方货物的上表面接触，有：

（4）容积约束：实际装载货物的总容积不能大于集装箱的最大装载容积，即：

（5）层数约束：实际装载货物纵向层数不能超过最底层货物的最大承载堆放层数，即：

1.4 装载模型目标函数

单集装箱装载问题的优化目标是满足一定约束条件下，使集装箱的闲置空间最小，即最大化集装箱的利用率，目标函数表示如下：

定义1（闲置空间VI(m,s)）蚂蚁m在状态值为s时对应的闲置空间集，如果剩余的未装载货物当中没有任何一个货物可以装入该剩余空间，则此空间被称为闲置空间。

1.5 空间模型建立

选货方式是基于货物体积与当前待装箱空间的相对大小以及摆放次序的操作，每一个所选货物放置于待装载空间后，都将对布局空间产生结构性影响。三空间分割法[20]是布局空间分解的一种典型方法，本文以该方法为基础，进行空间的分解和综合利用。货物在充填剩余空间时，采用从下到上（Z轴方向），从左到右（Y轴方向），从后到前（X轴方向）的顺序依次摆放，在YOZ平面摆放完一层空间后，再开始第二层，直到装满该集装箱。

针对装箱后所产生的空间定义如下，并在后续过程中加以引用。

定义2（剩余空间（VA））对已分层来说，可以利用的空间以及可以进行空间合并的空间。

定义3（残余空间（VR））所有不能放置货物以及无法进行空间合并的空间。

定义4（待装载空间（VU））对当前层来说，待放置货物的空间。

图2 对闲置空间（VⅠ）、剩余空间（VA）、残余空间（VR）、待装载空间（VU）给出图示。

图2 空间定义示意图Fig.2 Schematic diagram of space definition

2 货物装载方法

2.1 数据预处理算法

装箱问题理论上属于NP-Hard 的问题，货物的种类、尺寸大小、数量等因素都会对装载结果产生较大影响。随着货物种类的增加（即异构性的增强），结果组合种类呈指数爆炸式增长。通过聚类算法能够将一组强异类问题拆分为若干组弱异类问题，提前对解空间进行收敛，加快求解速度[21]。

本文采用经典的K-means聚类方法，以选定货物体积大小以及货物最长边长度的归一化数据作为聚类的两个指标进行聚类，最终根据聚类簇质心的体积及最长边的数据按照加权公式（8）从大到小排列，并将聚类簇中的货物按最长边降序排列，以获得每个类别下货物装箱顺序列表。综合考虑货物体积及最长边长度，将货物划分为体积较大最长边较长、体积较大最长边较短、体积较小最长边较长以及体积较小最长边较短四种情况，故令聚类中心k=4，其聚类类别示意图如图3所示。

图3 聚类类别示意图Fig.3 Schematic diagram of clustering categories

其中，p为第i簇质心体积vi所占的权重，(1-p)为第i簇质心最长边li所占的权重，经过实验中对比计算，p为0.7时，聚类分析结果相对较好。

为了对数据处理算法的可用性进行验证，本文以国际公测数据集BR8中的第一例实验数据为例，进行聚类分析。因篇幅限制，只对部分数据进行展示，全部数据可从文献[4]中下载。数据的长、宽、高等详细信息如表1所示；聚类后数据的簇类型、质心坐标等详细结果如表2所示。

表1 待装载货物信息Table 1 Ⅰnformation of goods to be loaded

表2 聚类结果Table 2 Clustering results

数据预处理算法并非简单对货物进行分类，而是综合考虑待装载货物的体积及最长边长，依据数据特征减少装箱货物类型，尽可能保证同类货物摆放规整，减少空间的浪费提高集装箱空间利用率。

2.2 剩余空间合并算法

在三维空间分解装箱过程中，随着箱体的不断装入，在不同位置将产生越来越多不规则“散碎”空间。空间合并就是把剩余的小空间进行合并、分解，将其处理成一个个可利用的矩形体，便于后续装箱过程中盛放适当箱体，以提高空间利用率。

空间合并按照先左右合并，再前后合并的顺序将待合并空间整理到闲置空间列表中。合并前剩余空间如图4所示。其中，i代表位于剩余空间A所在的区域，t代表位于剩余空间B所在的区域。

图4 剩余空间示意图Fig.4 Schematic diagram of remaining space

（1）左右合并：假设存在两个剩余空间（剩余空间A和B），位于右侧的剩余空间(B)为待合并空间，将待合并空间的左下角尽可能向左移动。需要保证左侧剩余空间的右侧面包含右侧剩余空间的左侧面，即：

根据选出的Ymin，将空间向左侧扩大，并更新剩余空间表中的信息。左右合并后如图5所示。

图5 左右合并后剩余空间示意图Fig.5 Diagram of remaining space of merging left and right

（2）前后合并：将当前待合并空间分解为LEFT、RⅠGHT两个空间，如图6所示。

图6 前后合并后剩余空间示意图Fig.6 Diagram of remaining space of merging front and rear

其中，i代表位于闲置空间C所在的区域，t代表位于LEFT 空间所在的区域。假设存在两个剩余空间（RⅠGHT 和C），位于前方的剩余空间C为待合并空间，将待合并空间的左后下角尽可能向后移动。保证后方的剩余空间的前侧面包含前方剩余空间的后侧面，即：

根据选出的Xmin将空间向后方扩大，并更新剩余空间表中的信息。前后合并后，最终效果如图7所示。

图7 空间合并最终效果图Fig.7 Final effect diagram of space merging

上述两种合并策略的综合利用，将有效整合“散碎”剩余空间，进而提高空间利用率。

2.3 确定货物放置方向的启发式策略

对每一个待装载货物而言，其放置方向如果不当，将造成剩余空间浪费，从而影响空间利用率。放置过程中，每一只蚂蚁将综合考虑待装载货物六种放置方向所产生的上方、右方和前方剩余空间的形态和大小，使货物放入后所产生的剩余空间尽可能规整。该过程中，蚂蚁将综合考虑闲置的三个空间，使剩下的空间再一次放进其他货物，或尽可能使残余空间为零。放置方向的确定是一个回溯过程，可以减少顶部和侧部的废弃空间数量。

如图8 所示为对货物及待装载空间在YOZ面投影。若高度方向和宽度方向的剩余尺度面积之和最小（如阴影面积所示），则局部空间利用率最高，即：

图8 货物及待装载空间投影图Fig.8 Projection diagram of cargo and space to be loaded

其中，PTΩ(0,yTΩ,zTΩ)、PBΩ(0,yBΩ,zBΩ)分别为当前待装载空间的右上、左下角坐标；PT i(0,yT i ,zTi)、PB i(0,yB i ,zB i)分别为货物i的右上、左下角坐标。

据此，本文提出了如下货物放置方向策略：

（1）按公式（11）确定货物摆放方向的优先级；

（2）按最高优先级确定层的宽度，将相同尺寸物体布局在该层，转化为二维装箱问题。

2.4 局部空间姿态调整策略

对每一个待装箱体，存在6 种摆放姿态，姿态选择恰当与否，对于箱体装载规整性以及尽可能减少空间浪费，具有重要作用。在局部空间的计算中，由于装载顺序的原因，即上、右、前方向递归操作，前方向（即集装箱箱体深度方向）远大于其他两个方向，因而只要控制好集装箱顶部和侧方部位（分别对应着装载箱体的高度和宽度方向）的狭小缝隙，长度方向就不存在问题，使局部空间利用率最大化。

待装箱体i初始姿态下的左-后-下角点PiB(xiB ,yiB ,ziB)和右-前-上角点，姿态调整在空间操作上意味着箱体分别绕X、Y、Z轴旋转α、β、γ角，且遵守右手螺旋法则，变换后对应的角点分别为和。因箱体轴线与集装箱各轴线保持平行关系，这里α,β,γ∈{0°,90°}。以PiT和Pi′T为例，姿态调整前后二者之间的关系如式（12）所示：

并且有α∈{0°,90°},β=0°,γ=0°,α∈{0°,90°},β=90°,γ=90°,α∈{0°,90°},β=0°,γ=90°，在当前摆放层，对货物i经过姿态调整后，将其代入公式（11），使局部空间利用率最高。

3 选货策略

3.1 三空间贪心层叠法选货策略

一方面，装箱问题的NP-Hard 本质，决定了精确求解算法难以实现，启发式求解方法是求解该类问题的首选。另一方面，实际应用中，由于约束条件多，且待装箱体货物类多、数量大，导致计算规模大，算法复杂度高，传统的单一启发式算法难以解决。因此，融合策略启发式算法是解决该问题的有效思路之一。本文结合蚁群算法，提出了一种新的动态融合策略优化算法，用于求解三维装箱问题。

针对蚁群算法有较强的寻优性能、分布式并行计算、易于与其他方法相结合的优点，以及算法运行初期收敛速度慢、容易陷入局部最优解等不足，本文构建了按货物体积大小和摆放次序为决定因素的三空间贪心层叠法（GSM）选货策略，用于前期选货，弥补蚁群算法的收敛慢的不足，其步骤为：

步骤1初始化每个节点的信息素浓度。

步骤2判断当前空间是否是新开启的一层，若是，选择一个所能选择的体积最大的待装载货物按照2.3节进行摆放；若不是，直接转到步骤3。

步骤3按照前一次摆放货物的上-右-前的顺序，并按照2.2节确定待装载空间。

步骤4在步骤3 中确定的待装载空间内选择一个能够装载的体积最大货物，并按照2.3节进行摆放，更新当前节点的信息素浓度。

步骤5循环步骤2 至步骤4，直至本层都是残余空间。

其中，考虑当前待装货物i的前置货物i-1，若vi+Δ≤vi-1，Δ∈[ ]0,C为常数，则放置规则为：

上述规则使货物按（1）、（2）、（3）次序所确定放置方向，并调整放置姿态，否则终止装箱。本策略确保当前待装载空间尽可能装满，并且使所装载货物尽可能规整。

3.2 三空间蚁群层叠法选货策略

通过GSM 算法的前期计算，使得信息素浓度有较大提升，此时采用蚁群算法能发挥其快速收敛的优势。因此本文基于三空间分解法构建了三空间蚁群层叠法（ASM）选货策略用于后期选货，其规则为：

步骤1判断当前节点信息素浓度是否达到有效范围，若是，则利用当前节点信息素；若不是，则初始化当前节点信息素浓度。

步骤2判断当前空间是否是新开启的一层，若是，选择一个能够装载的体积最大货物，按照2.3 节进行摆放，并进行下一步；若不是，转到步骤3。

步骤3按照前一次摆放货物的上-右-前的顺序，并按照2.2节确定待装载空间。

步骤4根据节点信息素浓度及算子序列等确定待装载货物，并按照2.3节进行摆放。

步骤5更新信息素浓度，重复步骤2到步骤5，直至当前层都为残余空间。

步骤6开启新的一层，判断当前层能否装载货物，若能，则转到步骤2；若不能，将蚂蚁数加1，更新信息素浓度。

步骤7判断蚂蚁数是否达到最大蚂蚁数，若是，结束装载，输出最优装载链；否则执行步骤1。放置规则如3.1节中（1）、（2）、（3）所示。

3.3 动态融合策略

若能控制两个阶段中GSM 算法与ASM 的参与程度，则能更好地将两种算法动态融合，发挥各自算法优势的同时，解决好解的随机多样性问题。本文通过构造具有均匀随机分布函数与正态分布函数相比较的方法确定选货方式。

对均匀随机分布函数，采用C++中伪随机数生成函数rand()，其当前时刻t产生0-RAND_MAX之间的随机数，RAND_MAX 为所有随机数中的最大值，为便于比较对其进行归一化处理，即：

这里R(t)∈[0,1]。

对正态分布函数P(t)，为便于比较，取对称轴右侧大于零的部分，且进行归一化处理，即：

其中，ct是当前迭代次数，则P(ct)∈[0,1]。在求解过程中，二者动态融合的选货概率规则如下：当R(t)-P(t)≤0 时，采用三空间贪心层叠法进行选货；当R(t)-P(t)>0时，采用三空间蚁群层叠法进行选货。如图9所示为与迭代次数t相关的差值图。

图9 两种选货策略动态融合示意图Fig.9 Schematic diagram of dynamic hybrid of two selection methods

从图9 可以看出，在算法初期采用GSM 概率较大（横轴以下的范围），但也存在一定概率选用ASM（横轴以上的范围）；随着迭代次数的增加，采用ASM 的概率逐渐增大，但仍存在采用GSM的概率。

因此，可以实现求解初期以GSM 为主，ASM 算法为辅，后期以ASM算法为主，GSM算法为辅，并且两种算法在前后两个阶段参与程度可控。

4 快速求解策略

4.1 信息素存取数据结构设计

上述算法的快速求解有赖于大量信息素的存取设计，本文分别提出并设计了如下策略以实现快速求解。

蚂蚁的每一次迭代查找以及对信息素进行更新的过程中，都需要对信息素进行查询，识别出装载货物的种类、每种货物的装载数量以及装载序列等信息，随着问题求解规模变大，信息素的存取结构对算法的运算效率至关重要。由于问题规模无法在算法设计时确定，难以确定表规模大小；采用一般的哈希表结构不易于对其进行遍历，而红黑树是一种自平衡二叉查找树，能够保障在最坏的情况下，查询、插入或删除的时间复杂度都为O(logn)，故本文采用红黑树对装载信息进行存取。其中，节点键码表示当前情况下装载货物的种类及各种货物的装载数量，节点的键值表示当前情况下信息素值的大小。

对于键码本文设计了一种新的状态值表示方法。设货物的种类数为K，则状态字的结构如图10所示。

图10 状态字表示形式Fig.10 State word representation

一般地，状态值的形式化表示为：

其中，K为待装货物种类数，a为蚂蚁编号。tk={0,1}表示第k种货物是否装载，1 表示已装载，0 表示未装载。[0 …0]由0或1二进制码组成的Q位数，表示第k种货物装载数量，最大可装载2Q-1 个货物。以K×(1+Q)位二进制码作为状态值，为树结构的key值，信息素量为value 值。信息素的value 值函数形式化表示如下：

其中，中括号内分别对应货物种类i、货物i摆放方式、货物i左下角坐标、货物i长宽高、货物i摆放后集装箱残余空间大小。由于组合爆炸的原因导致可行解空间巨大，本文基于信息素存储方法，设计了剪枝策略，去掉其中明显不符合装载目标的装载链，提高算法的运行效率。

4.2 剪枝矩阵

本文所针对的问题规模大，且无法在算法运行初期确定，若采用穷尽搜索，当解空间较大时，算法时间复杂度也会相应增大。考虑到有的解在运行初期就产生大量残余空间，明显无法达到算法所要求的近似最优解，没有计算必要，因此算法并没有对每一个解都进行完全计算。

采用剪枝策略，即通过设立特定的过滤条件，提前减少不必要的搜索路径，可大大降低算法的时间复杂度。本文将VR（残余空间）的大小作为过滤条件，残余空间大小反映本条路径的好坏，既提高了算法运行准确性，又大大降低算法的时间复杂度。

根据上一层已经得到的当前最优结果，决定当前的搜索是否还需要继续。通过查询状态值和闲置空间大小建立的红黑树进行剪枝操作。

设K为货物类型数，T*i为对第i个箱体摆放后对应的最优类型域，Q*i为对应的最优数量域，VR*为对应的残余空间。

若存在蚂蚁a对第i个箱体进行空间摆放后，所对应的类型域为，对应的数量域为，其残余空间为且

当前蚂蚁b，在某时刻完成摆放后对应类型域为，对应的箱体数域为，其残余空间为

当Tai=Tbi且Qai=Qbi时：

当状态值相同时，择优存储装载链并更新剪枝矩阵，在剪枝矩阵中，每一个状态值对应一条当前最优装载链。而状态值只与装载货物的种类、数量有关，每一个状态值只保存一条最优装载链信息，从而有效缩减了问题的解空间。

5 算法流程

本文提出了一种新的基于空间划分与合并融合策略的启发式算法，以此求解上述集装箱装载问题。首先，利用启发式算法的局部最优收敛性，得到一组粗略的解，并用该粗略解充实蚁群算法的信息素信息。其次，利用蚁群算法的潜在并行性、正反馈性及全局收敛性获得最优解。本算法相关参数设定如表3所示，其中ρ、α、β的取值来自于文献[22]，m和CT的取值根据实践经验兼顾优化效果与运行时间后确定。

表3 算法参数取值Table 3 Algorithm parameter values

算法的具体的算法步骤如下所示。

步骤1初始化数据：货物总数量N、货物的种类数n、最大蚂蚁数量AntNum、当前蚂蚁数m、货物与集装箱的尺寸和数量、初始时刻各路径上的信息素均为τ0=C（v为常数）、剪枝矩阵信息、货物装载链信息（装载顺序、货物的摆放方向以及货物的坐标等）、最大迭代次数CT。

步骤2判断当前迭代次数k是否大于最大迭代次数CT，若是则执行步骤11；否则执行步骤3。

步骤3判断当前蚂蚁数m是否大于最大蚂蚁数量AntNum，若是则将当前迭代次数自增1后执行步骤2；否则更新信息素信息。

步骤4若蚂蚁i已经装载全部货物或集装箱已经达到饱和，则将当前蚂蚁数m自增1 后执行步骤3；否则，执行步骤5。

步骤5查询闲置空间集并重新对闲置空间进行划分和合并。

步骤6根据选货概率公式确定贪心层叠法或蚁群层叠法作为本次选择货物方式，最终确定待装载的货物g。

步骤7确定货物g的放置方向和姿态。

步骤8更新装载链信息并生成状态值。

步骤9依据状态值查询剪枝矩阵，若当前对应的残余空间体积大于查询获取的值，则放弃当前蚂蚁m，直接选择下一只蚂蚁m+1；否则更新剪枝矩阵，将当前蚂蚁数m自增1并转向步骤3，直至装载完毕。

步骤10当所有蚂蚁完成一次循环后，各个路径上的信息素浓度进行实时更新。

步骤11更新迭代次数，若达到最大迭代次数CT后，从所有的装载链中选择最优解输出；否则，执行步骤2。

6 实验验证

本文算法采用Visual Studio C++2017 开发，实验程序运行在Ⅰntel®CoreTMi5-6500 CPU @ 3.20 GHz的处理器上，运行内存为8 GB。

本文采用了代表性测试数据集[4]进行实验计算，该数据集为Bischoff和Ratcliff提出[4]的10组共1 000个算例，并与国内外代表性求解算法的计算结果进行了比较，比较结果如表4所示。

表4 多种算法对装箱问题填充率及运行时间比较Table 4 Comparison of filling rate and time of various algorithms for loading problem

通过对表4 所示的数据进行分析可以发现：（1）随着待装载货物种类的增加，箱体填充率呈下降趋势。随着货物种类增加，相同种类的货物装载数量减少，必然造成剩余空间数量的增多，即需要不断对剩余空间进行合并，导致算法运行效率降低，同时也造成箱体空间利用率下降。（2）在同时满足方向约束与稳定性约束的前提下求解三维布局优化问题，从表4 中数据可以看出，获得平均填充率由高到低的算法依次排序，第1 为BSG_VCS算法（填充率：94.60%）；第2为MOA算法（填充率：93.64%）；第3为是本文所提出的HSHA算法（填充率：93.59%）。同时也可以发现，在同时考虑两种约束条件，且填充率相差不超过2%的前提下，运行速度最快的是本文提出的HSHA 算法（运行时间：69.96 s），本文算法运行时间较之前文献所述算法有较大的缩减。总体来说HSHA算法能够以较快的速度对数据集进行处理，具有较强的有效性与可行性。

表5 给出了融合策略启发式算法实现强异类CLP时的一些测试细节，本文只考虑解决强异类装箱问题，表中分别给出了10 组测例的运行时间和填充率的Minimum（最小值）、Maxmum（最大值）及Average（平均值）。根据表5 可得图11 的拟合关系，可以看出平均运行时间与货物种类是呈对数关系，也说明算法具有O(logn)的复杂度。

表5 HSHA在强异类集装箱装载时的测试细节Table 5 Test details of HSHA for strongly heterogeneous container loading

图11 平均时间与货物种类拟合关系Fig.11 Fitting relationship between average time and cargo type

7 结束语

本文提出了一种动态融合策略启发式算法，对单箱强异类问题进行了综合求解。通过聚类方法将强异类问题转化为弱异类问题，使问题解空间提前收敛。设计了货物局部空间姿态调整策略以及剩余空间合并策略以提高集装箱空间利用率；设计了三空间贪心层叠法与三空间蚁群层叠法，并提出一种基于概率选择的动态融合算法，实现两者优势互补且参与程度可控。此外，为了实现快速求解，构建了状态值与剪枝矩阵，在装载过程中对每个状态值择优存储并更新剪枝矩阵，通过缩减问题的可行解空间，以加快求解速度。通过与公共数据集具体算例的运行结果对比，在保证装箱率的前提下，本文算法具有较好的竞争力。本文算法在填充率方面还有待进一步提高，今后的研究将考虑在聚类方法和概率融合策略方面进一步地改进与优化。