A Novel Approach to Solve Complex Packing Problems

Abstract

A novel approach which can solve complex packing problems is proposed. It solves the complex packing problems in two steps： Firstly, the volume-maximizing loading is carried out according to some heuristic rules, and the loading space is divided into many layers according to the cargo in depth direction, and each layer will then be decomposed. Secondly, the position of the center of gravity is adjusted optimally by genetic algorithm, so as to make the packing result more fit for practice. The practical result shows that it is better than other packing approaches in terms of the usage rate of space, the center of gravity and the calculating efficiency.

Content

《1 引言》

1 引言

装箱问题是指将各种尺寸的物品摆放入一定容量的容器, 以获得某种最佳的效益。装箱问题是一个具有复杂约束条件的组合优化问题, 在理论上属于NP-hard问题, 其求解是极为困难的。为了快速求解与优化, 以及实用性, 人们开始寻找更有效的求解方法。

有关装箱问题的综述性工作详见文献[1,2], 其中大部分是研究二维或三维矩形物体在矩形容器中的布局。目前常用的布局优化方法有数学规划、图论法、启发式、人工智能^[3], 多为不带约束的简化布局问题。杨传民等通过全面枚举搜索方法研究相同大小立方体的装箱优化问题^[4]。Mannchen 设计的数搜索算法^[5], 在理论上对三维箱体布局有效, 但由于三维箱体布局属于NP-hard问题, 随着布局箱体的增多, 解空间剧增, 因而计算效率较低。Gehring 提出按阶段填充、在深度方向按层布局的启发式算法^[6], 不仅考虑了空间利用率, 而且考虑了重心平衡。姜义东等提出利用遍历三叉树结构的方法对空间进行分解^[7], 虽然有效避免了空间干涉现象, 但无法处理更复杂的约束, 如后到先放、尽量平铺、重心约束等, 这些约束往往是至关重要的。何大勇等在文献[7]的基础上运用遗传算法做了改进^[8], 其优点是能处理多目标、多约束的问题;缺点是在货物很多时, 应用遗传算法对每件货物进行整数编码构成的染色体, 基因数量多, 规模巨大;加上众多约束条件, 导致算法收敛非常慢, 甚至大多数情况下得不到可行解。

在三维空间布局问题研究中, 应用最广泛、效果最好的是启发式方法^{[3,4,5,6,7,9,10,11,12,13]}和人工智能方法^[8,14]。启发式方法的优点是速度快, 缺点是无法处理多目标、多约束的问题;人工智能方法如遗传算法, 虽然解决了这类问题, 但收敛慢, 算法效率不高。笔者提出了一种按照深度分层的基于空间分解的启发式算法, 在保证体积装载最大化的同时, 考虑了许多约束条件, 得到了成功的应用。

《2 问题描述》

2 问题描述

现有一批长方体货物, 要求装入一个长方体的集装箱, 装箱要求为:在满足一定约束条件下的最大化体积装载率或重量装载率, 以提高集装箱的利用率, 获得最佳的效益。装箱的目标可描述为最大化函数

$\begin{array}{l} \max {\frac{\sum_{i = 1}^{n} l_{i} \times w_{i} \times h_{i}}{L \times W \times Η}} \\ 或 \max {\frac{\sum_{i = 1}^{n} l_{i} \times w_{i} \times h_{i} \times g_{i}}{Μ}}, \end{array}$ $\begin{array}{l} \max {\frac{\sum_{i = 1}^{n} l_{i} \times w_{i} \times h_{i}}{L \times W \times Η}} \\ 或 \max {\frac{\sum_{i = 1}^{n} l_{i} \times w_{i} \times h_{i} \times g_{i}}{Μ}}, \end{array}$

式中n为货物数量;l, w, h分别为长方体货物的长、宽、高;L, W, H分别为集装箱内壁的长、宽、高;g为货物密度;M为集装箱的最大承载质量。

在实际装载过程中需要考虑的约束条件有:

1) 方向约束。货物摆放的方向受约束, 例如有些货物的包装标有向上的箭头等。一般货物装载时的方向约束可归纳为三种:任意旋转、水平旋转和不能旋转。

2) 承载能力约束。货物所能承受的最大压力受限制, 下面的货物不允许被上面的货物压坏, 所以装载层数、装载次序要受到限制。

3) 稳定性约束。装载完后, 集装箱的重心应该在一个安全的范围之内, 要尽量做到左右平衡, 以确保运输安全。这对于大型车辆尤为重要。

4) 货物装载位置约束。货物的种类千差万别, 包装材料也各式各样, 有些货物不能任意摆放, 例如纸箱不应放到木箱边上, 以防运输过程中损坏。

5) 货物装载顺序约束。不同货物应按不同的顺序装载, 例如根据货物到站的顺序, 按照“后到先放”的原则装载。

6) 集装箱最大载量约束。集装箱内装载的货物总体积 (质量) 不能超过集装箱允许的最大容积 (载重量) 。

《3 按照深度分层的基于空间分解的启发式算法》

3 按照深度分层的基于空间分解的启发式算法

笔者提出的这种算法分两个步骤:首先应用基于空间分解的启发式算法, 将货物按照适当的启发式规则进行体积最大化装载;再以货物的深度方向对集装箱进行分层, 运用遗传算法在深度方向进行优化, 使整个集装箱的重心处于安全范围之内。

《3.1 基于空间分解的启发式算法》

3.1 基于空间分解的启发式算法

《3.1.1 定序规则》

3.1.1 定序规则

定序规则用来确定物体放入布局空间的先后顺序, 它将影响最终布局结果的优劣。物体对布局者而言, 其重要程度是不同的;重要的先放入, 次重要的后放入。定序规则按优先级由高到低有:a. 后到先放;b. 按照物体底面积递减定序;c. 按物体体积递减定序。

《3.1.2 定位规则》

3.1.2 定位规则

长方体货物布局的定位规则主要有:a. 占角策略, 即物体首先摆放在布局空间的某一角;b.顺放策略, 从一个角开始, 沿布局空间的某一边顺序摆放;c.先沿布局空间的四边摆放, 然后填中心;d. 平铺优先, 为了降低装载后的集装箱重心高度及集装箱各个部分受载均匀, 利于行车安全, 将货物优先平铺, 然后再起层。

应用领域不同, 布局的定位规则也不同, 这里采用占角优先策略为定位规则。货物在空间内的摆放位置以及空间分解策略如图1所示:

《图1》

图1 空间分解策略示意图

Fig.1 The figure of space decomposition strategy

《3.1.3 空间分解》

3.1.3 空间分解

空间分解过程采用三叉树数据结构表示, 先对原始空间求解, 此时原始空间为当前空间, 对应于三叉树的根节点。按照定序规则, 从可选的未装载物体中用枚举法选择一个相对于当前空间为最优先的物体, 然后按照定位规则将其定位于当前空间后部的左下角或右下角, 这样原空间的剩余空间可分为三个子空间, 即如图所示的L, M, R三个空间, 分别对应于三叉树根节点的左、中、右三个子节点, 剩余空间就变成三个独立的空间。依次将L, M, R当作当前空间, 对这三个空间重复上述分解过程, 直至没有待布局物体满足要求或集装箱无可利用空间为止。

《3.1.4 约束条件的处理》

3.1.4 约束条件的处理

在基于空间分解的启发式算法中, 笔者对其中一些约束做了特殊处理:

1) 对摆放方向约束的处理。根据货物的具体属性, 如能否侧放、能否倒置等, 可以将一件货物复制为多个货物。例如某货物既可以侧放也可以倒置, 就分别以它的3个不同面作为底面, 得到6种不同的摆放姿势, 在这里把它们当作6个不同的货物进行处理。

2) 对重心高度约束的处理。为了降低重心高度并使货物质量尽量均匀分布, 采取优先平铺策略。开始时, 优先对L, R空间进行分解, 处理方法为平面二叉树分解, 对产生的M空间只记录不分解。当摆放完一层后, 依次将记录下来的M空间作为当前解空间, 进行L, R空间分解, 如此循环直至货物装载完毕或者没有足够的空间为止。

3) 对左右平衡约束的处理。对于大型集装箱或者大型车辆, 运输过程中的左右平衡无疑是等级最高的约束条件。为了使集装箱左右尽量平衡, 并且使未填充空间尽量出现在中间以利于稳定性, 笔者将未布局空间按照其中轴线的位置分为两类, 相对于集装箱的中轴线来说, 偏左的待布局空间, 每次将物体定位于它的后部左下角;偏右的待布局空间, 每次将物体定位于它的后部右下角。与此相对应, 两种方法的空间分解策略也略有不同。应用这种策略, 货物会优先摆两边, 然后填充中间, 符合算法的定位规则。

《3.2 按照深度分层的重心位置调整算法》

3.2 按照深度分层的重心位置调整算法

在基于空间分解的启发式算法中, 对重心在高度和宽度方向也做了一些处理, 包括对左右平衡约束的处理。但是由于车辆的各个部位承重能力不一样, 例如VOLVO FL6E42T型厢式货车, 满载时最大允许均布20 000 kg, 前部牵引轴附近最大允许均布7 000 kg, 后轴附近最大允许均布12 000 kg, 中间位置最大允许均布11 000 kg。为了调整车厢各个部分的载重, 在按照深度分层的重心位置调整算法中, 应用了遗传算法对货物进行调整, 这样既可以使货物在深度方向合理分布, 又不致破坏前一步骤的货物在高度和宽度方向的合理分布。

《3.2.1 深度方向分层策略》

3.2.1 深度方向分层策略

采用深度方向分层结构处理整个集装箱空间, 每一层由装入该层的第一件货物确定, 该货物可以称为层定义货物LDB (layer determining box) 。每一层的宽、高与集装箱的宽、高尺寸相同, 层的长度取决于该层的LBD的长度。这样, 整个装载后的集装箱便根据LBD划分为l层, 把每一层的所有货物当作一个整体, 将一层内货物的质量之和定义为该层的质量LM_i, 其中0 <i≤l。

《3.2.2 重心约束函数》

3.2.2 重心约束函数

在这里只考虑深度方向重心约束, 货物装载结束后, 集装箱的重心应该在限定的范围内, 并且每一个区域的载重量不大于该区域的最大允许承重量。集装箱深度方向的重心计算公式为

$d_{g} = \sum L Μ_{i} (d_{i} + l_{i} / 2) / \sum L Μ_{i},$ $d_{g} = \sum L Μ_{i} (d_{i} + l_{i} / 2) / \sum L Μ_{i},$

其中0 < i ≤ l。

《3.2.3 遗传算法应用》

3.2.3 遗传算法应用

采用整数编码方式, 每个层作为一个基因, 一个染色体即为全部层的一种排列方式, 遗传算法的目的是寻找一种排列方式, 使深度方向的重心分布接近最优。关于遗传算法的具体步骤参见文献[15]。

假设根据运输工具载重分布的要求, 期望集装箱重心分布在[d_a, d_b]区间, 则算法的目标函数为 $\min | d_{g} - \frac{d_{b} + d_{a}}{2} |$ $\min | d_{g} - \frac{d_{b} + d_{a}}{2} |$ , 且要满足各个区域载重量的约束条件。此法也可以推广到期望质量分布在多个区域的情况。

《3.3 算法流程》

3.3 算法流程

算法流程图如图2。

《图2》

图2 算法流程图

Fig.2 The flow chart of algorithm

《4 应用实例》

4 应用实例

从文献上看, 具有多目标、多约束的复杂集装箱空间规划问题只有用遗传算法求解的, 但由于自身的局限性, 使其在装载货物多的大规模 (集装箱或车厢通常要摆放300件以上的货物) 问题中无能为力, 没有一个样题可以与笔者提出的算法相比较。因此, 笔者根据算法在实际中的应用, 提出一个实例, 以证明算法的有效性。在实例中, 布局空间为3.2节提到的VOLVO FL6E42T型厢式货车, 其尺寸为12 842×2 410×2 512 (mm) 。待布局货物为500件真实尺寸的货物, 原始信息除了货物的长、宽、高外, 还包括质量、材料, 是否易碎、怕压, 可否倾斜倒置以及目的地顺序。计算结果如图2所示, 装载货物数量为301件, 计算平均所用时间小于6 s, 体积利用率达到85 %, 高于手工装载的体积利用率 (视货物类型以及货物尺寸而定, 一般为70 %～80 %) , 满足了各种约束, 避免了手工装载时因约束条件而频繁调整货物位置造成的时间浪费。实际配载效果如图3、图4所示。

《图3》

图3 实际装载图 (第一层)

Fig.3 The actual loading figure (the first floor only)

《图4》

图4 实际装载图 (全部)

Fig.4 The actual loading figure (all)

《5 结语》

5 结语

空间规划问题大量出现在工程领域, 寻找一个效率高的方法解决实际问题是非常有意义的, 笔者通过算法在实际工程中的应用, 验证了按照深度分层的基于空间分解的启发式算法的有效性, 并提出了解决考虑重心的此类问题的一个新方法——按深度分层, 将重心优化放在体积优化后单独进行。

Show More