集装箱轻重货物混合平衡装载模型与算法

2020-04-24雷定猷洪舒华张英贵

计算机工程与应用 2020年8期

雷定猷，洪舒华，张英贵

1.中南大学交通运输工程学院，长沙410075

2.中南大学交通运输工程学院智慧交通湖南省重点实验室，长沙410075

1 引言

集装箱平衡装载必须满足负载平衡约束，即货物总重心位置在规定范围内，装运车辆受均匀载荷[1]。该约束是公路和铁路等货物装运实践中的基本约束，对于保障装卸运输中的货物及设备安全、提升作业效率、减少运输成本和能源消耗等各方面都有积极意义，同时也是实现货物机械装运自动化、一体化的关键所在。货物轻重差别较小时，无需专门操作往往也可实现负载平衡。但随着集装箱应用领域不断拓展，运输范围不断延伸，以及装运货物不断增多，在实际装货过程中，常把重量较大的货物与重量较小的货物混合装载，这种情况下若无特殊处理，负载平衡约束难以满足[2]。本文将这类把轻重差异较大的货物混合装入同一集装箱的问题称为集装箱轻重货物混合平衡装载问题，它是集装箱装载布局问题的一个子类，是NP-hard问题。

近年来，在集装箱布局空间表示方面，Moura 和Oliveira[3]证明最大覆盖法在求解时间和解的质量上比分割法更有优势；姜义东等人[4]则利用三叉树结构表示空间的分解状态。在待装货物处理方面，Fanslau 和Bortfeldt[5]提出将多种不同货物组合成货物单元，并验证用货物单元装载比用单个货物更高效；朱向等人[6]针对集重货物提出构建塔型货物单元；Araya等人[7]提出一个有效的货物单元评估函数；Zhu 等人[8]将集装箱装载布局问题归纳为6个要素，并提出了简洁高效的二步前瞻检索策略；雷定猷等人[9]结合装运实际，提出中心骨架思想。在负载平衡约束研究方面，Costa 和Captivo[10]，Trivella 和Pisinger[11]都将其划分为纵向、横向和竖直方向三个子约束；Teresa等人[12]在处理负载平衡约束时，要求货物总重心尽可能靠近集装箱几何中心；Moon 和Nguyen[1]将负载平衡约束表示为一个可行区域；Ramos等人[2]通过负载分析，将负载平衡约束转换为负载分布图。目前针对轻重货物混合平衡装载的研究较少，且多将负载平衡约束简化处理或仅作为解的评价指标，没有结合实际装运车辆进行分析[2]，难以在保持较高集装箱利用率的同时实现符合实际情况的负载平衡。

本文结合集装箱装运车辆，将负载平衡约束量化为负载平衡函数，建立轻重货物混合平衡装载模型；通过对布局空间和待装货物进行分析，把货物组合成轻重货物单元，用启发式算法进行分类处理，提出轻重货物混合平衡装载算法；最后利用标准算例和轻重货物算例进行测试并与其他算法比较，验证算法可行性和实用性。

2 模型建立

集装箱几何中心被一致认为是货物总重心的理想位置[2]，可用货物总重心偏离集装箱几何中心的距离表示负载平衡约束。在包含了负载平衡约束的传统模型中，一般是在纵向、横向和竖直方向三个维度上分别给定货物总重心位置的容许偏移量，偏移过量则视为负载失衡。这种方法对于有明确统一标准的铁路运输来说是可行的，但对于公路运输有较大局限性，因为不同的地区、路面、车辆和货物等都有着不同标准，缺乏统一的量化方法。为解决这一问题，尝试通过力学分析构造负载平衡函数。

2.1 负载平衡函数

负载平衡函数将负载平衡约束精确地描述为货物总重心位置与货物最大容许重量之间的关系，利用它可以得知当货物总重心位于某一点时，车辆能够安全承载的货物总重上限。由于轻重货物混合装载时，优先装载重货，在车辆载重限定内极少出现重心在竖直方向上偏移过量的情况，因此主要考虑纵向和横向负载平衡函数。具体构造过程如下。

图1 所示是一辆板架式三轴集装箱卡车纵向和横向示意图，假设车辆左右两边对称，整车重量集中于点CG ，每个车轮代表一个轴，车轮上力的作用点位于其轴心。由于车轴超过两个，系统是超静定结构，为便于计算，将轴划分为前轴和后轴，使用前后轴的理论中心线位置进行计算[2]。

图1 集装箱卡车纵横示意及负载平衡函数曲线

构造纵向负载平衡函数需知空车重量(U=19 t,g取10 N/kg)、空车重心位置(CG)、前轴最大容许载重量(FAmax=12 t)、前轴最小转向载重比(%FAmin=0.30)、后轴最大容许载重量(RAmax=19 t)、后轴最小驱动载重比(%RAmin=0.44)、车辆最大容许载重量(Pmax=9 t)、前后轴中心线位置(FC,RC) 、前后轴中心线距离(D3=5.425 m)、前轴与空车重心位置距离(D2=2.426 m)以及前轴与集装箱靠近车头端内壁的距离(D1=1.698 m)。

构造横向负载平衡函数需知车辆行驶轨迹宽度(D4=1.750 m)、集装箱内尺寸宽度(D5=2.330 m)以及货物的横向偏移量（一般为车辆行驶轨迹宽度的给定百分比），但该值会随胎压、悬挂弹簧挠度等机械特性而改变，因此使用负载转移比进行计算。负载转移比LMR量化了从车辆一侧到另一侧的负载转移[12]，如式（1）所示可用单侧支撑载荷Tl和Tr求得，当负载均匀分布时等于0。为防止侧翻，车辆在出厂时就设定了该值的极值，对于本文所述车辆，LMR=±0.055。

站立于车辆尾部，面对车尾，规定左手端为集装箱左端，靠近车头端为集装箱内端。用x 和y 分别表示货物总重心距集装箱内端内壁和左端内壁的距离，即货物总重心在纵向和横向上的位置；Px表示货物总重心纵向位置为x 时的货物最大容许重量，Py表示货物总重心横向位置为y 时的货物最大容许重量。

在纵向列静态平衡方程如下：

根据车辆最大容许载重量有：

将数据带入式（2）～（6）可得纵向函数：

利用纵向函数可绘制图1（a）所示曲线，可行域为Ωx。

在横向列静态平衡方程如下：

根据车辆最大容许载重量有：

将数据带入式（8）和（9）可得横向函数：

利用横向函数可绘制图1（b）所示曲线，可行域为Ωy。

2.2 平衡装载模型

假设货物均为长方体或能包装为长方体，能够承重且不是危险品等特殊货物。在集装箱内部，以其左内下角为坐标原点（图1点O）建立三维坐标系。L,W,H,V分别表示集装箱内部长、宽、高和体积，集装箱载重量Q等于车辆最大容许载重量Pmax；集合C={C1,C2,…,Ci,…,Cn}表示n 类待装货物，它们的总重量和总体积分别为QT和VT，其中Ci={ci1,ci2,…,cij,…,cim}表示第i 类货物中有m 个货物，类重量和类体积分别为Qi和Vi；li,wi,hi,qi,vi分别表示第i 类货物的长、宽、高、重量和体积；分别表示第i 类货物放入集装箱后，投影在X,Y,Z 轴方向上的尺寸长度；装载状态变量uij=0或1 分别表示货物cij未放入或已放入集装箱；(xij,yij,zij)和()分别表示货物cij放入集装箱后，cij的左内下角（与集装箱方位规定一致）顶点坐标和重心坐标；(CGx,CGy,CGz)表示集装箱中所有货物的总重心坐标，其中：

CGx对应于纵向函数中的x，CGy对应于横向函数中的y。

根据上述分析，采用公路集装箱车负载平衡函数，以集装箱容积利用率最大为目标建立模型：

式（14）和（15）为负载平衡约束，规定货物总重心纵向和横向坐标与货物总重量关系满足相应可行域；式（16）规定任一货物cij不能超出集装箱边界；式（17）要求任意两货物cij和cef不能互相重叠，即如果两者同时放入集装箱，它们在X,Y,Z 轴上的三对坐标必须有一对满足坐标值较小者与货物相应尺寸之和不能大于坐标值较大者，式中假设cij的三个坐标值均小于cef；式（18）为重量约束；式（19）为旋转约束，表示货物可经旋转实现的所有可行放置方式，μ1和μ2为0-1 变量，取1 时分别表示货物的长和宽能够垂直于水平面（X-Y 平面），此时货物共有6种放置方式。若某类货物C0顶面必须朝上，即只允许高垂直于水平面，则μ1=μ2=0，其旋转约束可简化为：

3 算法设计

围绕集装箱布局空间和待装货物进行讨论，通过空间划分选择与更新、轻重货物分组与单元构造，以及货物单元分类处理等操作，设计轻重货物混合平衡装载算法。

3.1 空间划分选择与更新过程

为使集装箱布局空间每次可接收更多不同的货物单元，采用最大覆盖法，货物放入空间后，用3个互相重叠的最大长方体表示剩余空间，如图2中r1,r2,r3所示。

图2 最大覆盖法示意

确定划分方式后开始选择空间。如图3所示，空间r 为集装箱中某一空间，设其顶点ve1 坐标为(x1,y1,z1),与之对应的集装箱顶点VE1 坐标为(x2,y2,z2),两点间曼哈顿距离为 ||x1-x2+ ||y1-y2+ ||z1-z2。类似可得其余7 段曼哈顿距离，将其中最短者称为锚距，与之对应的空间r 的顶点称为锚角[8]。选择空间时，选取拥有最短锚距者，并将货物放在它的锚角处，这样布局可使货物紧靠集装箱内壁，剩余空间会逐步聚集于集装箱中部而非分散在各处，有利于剩余空间的合并利用。

图3 集装箱与空间位置关系示意

空间被选中放入货物后，用最大覆盖法将其划分成3个新空间。若其余空间与放入货物产生重叠，还需将重叠部分删去，即用最大覆盖法重新表示这些空间，至多可划分为6 个新空间。此外需检查现有空间是否已为最大，将被最大空间包含的小空间删去。

3.2 轻重货物单元装载规则

考虑轻重货物对总重心位置的影响程度不同，将其分为重货和轻货，分别构造货物单元，用不同的启发式方法进行处理。

3.2.1 货物分类

货物重量和密度越大，对总重心位置的影响越大，因此货物分类需按货物重量和密度进行两次排序。

算法1 货物分类算法

输入：货物集合C，重货占比系数λ；

输出：重货集合K 。

步骤1 确定候选货物重量和体积。先将待装货物按类密度降序排列，设候选货物总重量和总体积分别为QK和VK，若VT≤V ，则令VK=VT,QK=QT；否则找到a0使得V1+V2+…+Vi+…+Va0≤V 且V1+V2+…+Vi+…+＞V,令VK=V1+V2+…+Vi+…+Va0,QK=Q1+Q2+…+Qi+…+Qa0。而后与集装箱载重量比较，令QK=min{Q,QK}。

步骤2 降序排列。把候选货物按类重量降序排列，若重量相同，类货物个数较少的排前，取前a1=0.5n+1类；再按类密度降序排列，若密度相同，类货物个数较少的排前。设该排列为C1,C2,…,Ca1。

步骤3 确定重货。对于上述排列，找到a2使得Q1+Q2+…+Qi+…+Qa2≤λQK且Q1+Q2+…+Qi+…+（λ 常取0.4）。

步骤4 返回重货集合K={C1,C2,…,Ca2}。

3.2.2 货物单元构造

构造货物单元可实现货物的高效装载。需注意，同一个货物可存在于不同的货物单元，一旦某货物单元b被选择放入集装箱后，其余包含b 中货物的所有货物单元都需删去，即确保剩余货物单元能够由未装载的货物组成。货物单元的旋转约束为其包含的所有货物旋转约束的交集。

算法2 货物单元构造算法（以输入重货进行叙述）

输入：重货集合K ，生成重货单元数NK；

输出：重货单元集合B。

步骤1 初始化。将集合K 中重货放入集合B（即单个货物也看作一个货物单元）；把集合B 中的重货单元复制到集合B′ ，用于遍历组合；集合SA 赋空集，存放满足构造条件的货物单元。

步骤2 进入循环。遍历集合B′ 和B，每次分别取出一个重货单元b1和b2，将b2以其旋转约束允许的所有放置方式依次靠在b1的三个坐标轴方向，组成重货单元b3。若b3中所有货物的体积与其最小外接长方体体积之比大于0.98，则满足构造条件，将b3放入集合SA。

步骤3 数量判断。循环完毕后，若集合SA 不为空，将集合SA 与集合B 的并集交给集合B，将集合SA交给集合B′ 用于下一次遍历组合，集合SA 重新赋空集，同时判断集合B 中重货单元数是否大于NK（常取10 000），是则转步骤4，否则转步骤2；若集合SA 为空，转步骤4。

步骤4 返回规定数量的重货单元集合B。

3.2.3 重货单元处理

由于重货对总重心位置影响较大，可优先选取若干重货单元固定总重心位置，即采用中心骨架思想[9]，并提出新的中心骨架构建规则。

算法3 重货单元组合算法

输入：货物集合C，重货单元集合B；

输出：中心骨架候选集合SK ，候选集合中各组合对应轻货单元集合的集合

步骤1 搜索重货单元。设一个重货单元重量为qb，所有重货单元总重量为QB，搜索集合B，每次取出一个重货单元，若其满足式（21），可单独构建1 中心骨架；若其满足式（22），则继续搜索一个同类单元（不包含同一货物，下同），二者可构建2 中心骨架，或搜索两个满足式（24）的单元，三者可构建3 中心骨架；若其满足式（23），则继续搜索两个同类单元，三者可构建3 中心骨架；若其满足式（24），则继续搜索三个同类单元，四者可构建4 中心骨架。搜索到满足上述中心骨架构建条件的重货单元，则转步骤2；否则转步骤4。

步骤2 构成组合。将能够一同构建中心骨架的一个或若干重货单元作为组合cp，放入中心骨架候选集合SK 。

步骤3 生成轻货集合。复制集合C 到集合C′ ，删去集合C′ 中包含在cp 内的重货，剩余货物为轻货，调用算法2，输入集合C′和轻货单元数得到轻货单元集合（每个组合都存在不同的、与之对应的轻货集合），把集合放入集合，随后转步骤1。

步骤4 返回中心骨架候选集合SK 和各组合对应轻货单元集合的集合。

中心骨架数理论上还可继续增加，但骨架的不稳定性和对空间的分割会随骨架数量的增加而增大，因此文本仅构建4 及以下中心骨架。确定中心骨架候选集合后，从中取出重货单元组合放入集装箱中构建中心骨架。若重货单元有超过1种放置方式，选择重心高度最低者。以图4（b）为例，黑色线框表示集装箱底面，灰色方块表示两个重货单元，其重心投影分别位于A1和A2，放置时需要重货单元组合的重心投影A′与集装箱底面几何中心A0重合。

图4 中心骨架构建示意

当所得装载方案不满足负载平衡约束时，需对重货单元进行移动。将所得方案的货物总重心位置视为重货单元组合的重心位置，移动重货单元，使其组合重心在集装箱底面的投影重回集装箱底面几何中心。图5所示为图4（b）、（c）和（d）各两种可能的移动方式。

图5 中心骨架移动示意

3.2.4 轻货单元处理

下面是轻货单元评估函数：

式（25）中，Vol(b)表示轻货单元b 的体积；Cov(b,pl)反映b 放入集装箱后，集装箱内壁及其他货物单元，对b的表面覆盖率，可以是直接接触覆盖，或是距离小于pl与pl 所在坐标轴方向上集装箱尺寸乘积的投影覆盖，覆盖率越高，说明b 对已选空间的契合度越高；Loss(b,r)为b 放入空间以后造成的空间损失率，具体值为b 放入空间r 后，用剩余的轻货单元对b 的三个坐标轴方向分别求一维背包问题，得到的剩余无法利用的空间体积与空间r 原本体积之比；Num(b)表示构成b 的货物个数，在体积和重量相同的情况下，其值越小，说明构成b 的单个货物的体积和重量越大；在前人研究基础上新增Wei(b)表示b 的重量，它将引导轻货单元中较重者被优先选取。经控制变量测试可知，当pl=0.04,α=0.2,β=0.5,γ=0.2,δ=0.1,ε=0.2 时，解质量较好。

算法4 轻货单元选择算法

输入：搜索系数ω，当前布局空间r ，空间集合R，货物集合C，轻货集合

输出：轻货单元b0。

步骤1 生成一步解。对于当前布局空间r ，根据评估函数从集合中选出评估值排名前ω 的轻货单元（不同放置方式有不同的评估值，若同一货物单元有两种放置方式的评估值皆排名前ω，则该货物单元将被选取两次），分别放在r 锚角处，得到ω 个一步解（见图6），更新集合。

步骤2 生成二步解。从集合R 中选出每个一步解下一步骤的布局空间r′ ，再次从集合Bˉ中选出评估值排名前ω 的轻货单元，分别放在r′锚角处，得到ω2个二步解（见图6），更新集合。

步骤3 生成完整解。从集合R 中选出每个二步解下一步骤的布局空间r′ ，仅从集合Bˉ中选出一个轻货单元b，若不能找到符合条件的b，则标记r′，使之在下次集合更新前不再被选取；若能找到，则将其放在r′ 锚角处，更新集合并删去所有空间标记。随后检查空间集合中是否仍有未标记的空间，若有则继续判断货物集合中是否有货物剩余，是则重复步骤3，否则均转步骤4。

步骤4 输出ω2个完整解，找到其中最优者对应的一步解，返回实现该一步解的轻货单元b0（见图6），将其作为当前阶段放入的轻货单元。

图6 轻货单元选择示意(ω=2)

3.3 轻重货物混合平衡装载算法

算法5 轻重货物混合平衡装载算法

输入：空间集合R，货物集合C，计算时间Sec；输出：装载方案sbest。

步骤1 货物分类。调用算法1，输入集合C 和重货占比系数λ，得到重货集合K 。

步骤2 初始化。调用算法2，输入集合K 和重货单元数，得到重货单元集合B；调用算法3，输入集合C 和B，得到中心骨架候选集合SK 和各组合对应轻货单元集合的集合----TB；设定搜索系数ω，集合R 中初始布局空间为集装箱本身。

步骤3 构建骨架。判断集合SK 中是否还有重货单元组合，是则从中取出一个组合cp，同时分别复制集合R 和C 到集合R′和C′，用组合cp 在集合R′中构建中心骨架；否则转步骤6。

步骤4 选择轻货单元。中心骨架构建完毕后，从集合R′中选出布局空间r，调用算法4，输入系数ω，空间r ，集合R′和C′ ，以及集合中cp 对应的轻货单元集合，搜索当前阶段放入的轻货单元b0。若不能找到符合条件的b0，则标记r ，使之在下次集合更新前不再被选取；若能找到，则将b0放到r 锚角处，更新集合R′,C′和，删去所有空间标记。随后检查集合R′中是否仍有未标记的空间，是则转步骤5，否则转步骤3。

步骤5 生成装载方案。判断集合C′中是否有轻货剩余，是则转步骤4，否则输出一个装载方案s。检查s是否满足负载平衡约束，是则与至今找到的最好方案进行比较，将较好者记为sbest；否则将组合cp 放入负载失衡方案集合Sˉ中。随后判断是否遍历完所有组合，是则转步骤6，否则转步骤3。

步骤6 时间判断。判断时间是否剩余，是则令ω=，转步骤3，移动重货单元，重新构建集合Sˉ中方案的中心骨架；否则转步骤7。

步骤7 返回规定时间内最优方案sbest。

4 算例分析

测试电脑处理器为Intel®Core i5-7600 CPU，3.5GHz，内存8 GB，系统Windows10，代码以Java实现，并用Eclipse Neon 3编译。

4.1 标准算例

Bischoff和Ratcliff[13]提出一套集装箱装载算法的测试算例，包含货物种类由1 到100 共16 组（BR0～15），每组100 个算例，被公认为集装箱装载算法的标准算例。由于这套算例中没有考虑货物重量，Ramos 等人[2]在标准算例基础上，设定货物密度区间为(ρmin,ρmax)，其中ρmin=0.5ρc,ρmax=(ρc-ρmin)/E[x]+ρmin(ρc=QT/(g ⋅VT)，即待装货物平均密度，E[x]为贝塔分布期望），并按贝塔分布f(x,2,5) 得到货物密度。本文利用同样的数据进行测试，并与三个代表性算法进行比较，分别是等人[14]提出的最大空间算法（MS），Gonçalves和Resende[15]提出的偏随机密钥遗传算法（BRK）以及Ramos等人[2]提出的带静态稳定的多种群偏随机密钥遗传算法（MPBRK）。测试集装箱选用20 英尺通用集装箱(L=5.870 m,W=2.330 m,H=2.200 m)，为契合混合装载，去掉货物种类为1的算例，其余1 500个算例各计算100 s，同组100个算例平均结果见表1。

“Vol.”表示集装箱容积利用率，该方面本文算法略低于其他算法，较最优者低1.57%。这是因为本文算法为了保证每一次都能选到最合适的货物单元，以树形检索为解空间搜索内核，在有限的时间内，与以遗传算法为搜索内核的算法相比搜索能力较弱。“Unb.”表示负载失衡的算例数，该方面本文算法能够100%实现测试算例负载平衡，但其余最优者也达99.33%，差距较小。计算可知按f(x,2,5)得到的货物密度期望近似等于ρc，且方差仅为0.026，这样的货物产生的负载相对均匀，稍加处理即可实现负载平衡。标准算例结果可以说明本文算法具有一定的普适性，但不能证明实现轻重货物混合平衡装载的可行性，因此还需使用轻重货物算例进行测试。

4.2 轻重货物算例

以标准算例为基础，增大货物密度区间，令ρmin=0.05ρc，将密度下限固定在一个较小值；ρmax=Q/g((n-i0)⋅m0)（n 即货物类数，i0表示已被赋予重量的货物类数，m0表示当前被赋予重量的货物个数），密度上限保持当前载重允许最大值。同时改贝塔分布为f(x,0.075,0.075)，生成较轻较重货物期望增大，且方差比标准算例大8.5 倍，图7 可见两贝塔分布差异。以此生成15组共1 500个轻重货物算例，每个算例计算100 s，同组100个算例平均结果见表2。