• 基于最低水平面的三维装箱问题的启发式算法


    ⭐️ 前言

    小编之前写过一篇博文:求解三维装箱问题的启发式深度优先搜索算法(python),详述了基于空间选择的三维装箱算法。本文考虑了一个事实:在某些情况下,我们在摆放物品时,总是优先选择较低的平面,基于这个常识,本文提出一种基于平面选择的三维装箱算法。废话不多说,开始算法之旅吧。

    ⭐️ 块

    块的定义及生成可以参考博文:求解三维装箱问题的启发式深度优先搜索算法(python),这里就不在赘述。

    ⭐️ 平面

    “平面”指可用于摆放货物的面。初始平面就是箱的整个底面,放入第一批货物后,“平面”包括了同批货物顶面形成的面和箱底面空余的部分。
    本文算法采用由底向上的方式完成物品的装载,既优先铺满底面,然后再向上堆放物品。大体过程是:首先由完全相同的货物组成“块”,然后用块自底向上依次填充所选择的目标平面,并重新生成若干新的平面,然后不断重复上述过程来完成最终的摆放方案。下图演示了一个用4个“块”进行填充的简单过程,每个块顶部都生成了一个的平面。在这个例子中,填充完毕后,从原先的1个平面,分成了8个新的平面。
    在这里插入图片描述

    ⭐️ 选择平面

    当所用容器仅有一个时,初始情况下只有一个备选平面,即箱底面。
    选择装载目标平面时,按照以下几条准则依次进行判断:

    1) 为避免堆积过高,影响货物堆放的稳定性,优先选择空间位置较低(即参考点z坐标较小)的平面;
    2) 若几个平面参考点z坐标相同,则优先选择面积较小的平面,因为面积小的平面在后面可能更难使用;
    3) 若这些平面的参考点z坐标与面积均相同,则优先选择相对较狭长的平面,同样因为狭长的平面在后面可能更加难以利用;
    4) 若以上3点均相同,先比较它们参考点的x坐标,选择x坐标最小的一个。若x坐标相同,则选择y坐标最小的一个。
    
    • 1
    • 2
    • 3
    • 4

    ⭐️ 填充平面

    为能够充分利用空间,物品块与目标平面组合的保留规则依次为:

    1) 货物组成的“块”能最大限度地利用目标平面,即放入块后目标平面剩余面积最小;
    2) 若剩余面积相同,比较块的体积,保留最大体积的块。
    
    • 1
    • 2

    下文将该准则简称为准则。

    ⭐️ 合并平面

    当所选择的平面不能容纳任何一个货物时,更有效地利用空间,需进行平面合并。一个平面只能和其相邻的平面合并,相邻平面指高度相同,即具有相同参考点z坐标,至少有一边平齐,如下图所示类似情况的平面(图中蓝色部分表示目标平面(gs),白色部分表示其相邻平面(ns)):
    在这里插入图片描述
    首先目标平面(gs)先后在平面列表和备用平面列表中依次顺序查找是否有相邻平面(ns)。平面列表指还未使用的新平面列表,备用平面列表指已经过计算不可能放入任何物品的平面的列表。当一个目标平面找到与其相邻的平面时,通过试合并决定是否保留这一合并,并进行正式合并。保留某次试合并的基本准则包括:

    (1) 可以装入至少一个仍有剩余的物品(种类、方向不限);
    (2) 合并后新平面的面积是否比原先两个平面都大。
    
    • 1
    • 2

    设试合并后新生产的两块平面分别为ms1和 ms2,判断是否保留该次试合并及正式合并的步骤为:

    1. 判断 ns 是否满足准则(1)。若不满足则执行第 2)步,若满足执行第 3)步;
    2. 判断 ms1 和 ms2 是否满足准则(1)。将满足的一个平面插入平面列表,不满足的放入备用平面列表。若均不满足准则(1),则判断 ms1 和 ms2 中是否有能够足准则(2)的,若有,则将ms1和ms2均放入备用平面列表;否则不保留此次试合并,重新开始寻找相邻平面;
    3. 计算在放入物品后gs和ns将浪费的总面积(ws1)。根据ms1和ms2满足准则(1)的情况,计算合并后可能浪费的面积之和(ws2)。设平面 xs 的面积为Sqr(xs),在该平面上放入物品后将浪费的面积为WsSqr(xs),则根据ms1和ms2的满足准则(1)的情况,ws2有以下几种情况:
      在这里插入图片描述
      若ws1>ws2,则执行平面合并程序,并更新平面和备用平面列表;若ws1<=ws2,则不保留此次试合并,继续寻找其他相邻平面;
    4. 若对平面列表和备用平面列表搜索完毕侯,最终仍没有找到可合并的平面,则将目标平面gs从平面列表移入备用平面列表。

    ⭐️ 产生新平面

    在放入一“块”后,原目标平面被分成3个子平面,一个位于块的顶部(下图中深色部分),另外两个可有下面两种方式(下图中Rsa1和Rsa2)。我们选择产生的子平面面积较大的一个方式,即比较两种方式中面积较大的两个子平面,选择有最大面积子平面的生成方式。以下图为例,若(a)Rsa1>Rsa2,(b)Rsb2>Rsb1,则比较 Rsa1与Rsb2,若Rsa1>Rsb2,选择(a)方式。产生的子平面放入平面列表中。
    在这里插入图片描述

    ⭐️ 程序及运行结果(笔者python运行环境为python3.7)

    import copy
    import sys
    from itertools import product
    import math
    from matplotlib import pyplot as plt
    from mpl_toolkits.mplot3d.art3d import Poly3DCollection
    import numpy as np
    
    MAX_GAP = 0
    
    # 绘图相关函数
    def plot_linear_cube(ax, x, y, z, dx, dy, dz, color='red', linestyle=None):
        xx = [x, x, x+dx, x+dx, x]
        yy = [y, y+dy, y+dy, y, y]
        kwargs = {"alpha": 1, "color": color, "linewidth":2.5, "zorder":2}
        if linestyle:
            kwargs["linestyle"] = linestyle
        ax.plot3D(xx, yy, [z]*5, **kwargs)
        ax.plot3D(xx, yy, [z+dz]*5, **kwargs)
        ax.plot3D([x, x], [y, y], [z, z+dz], **kwargs)
        ax.plot3D([x, x], [y+dy, y+dy], [z, z+dz], **kwargs)
        ax.plot3D([x+dx, x+dx], [y+dy, y+dy], [z, z+dz], **kwargs)
        ax.plot3D([x+dx, x+dx], [y, y], [z, z+dz], **kwargs)
    
    
    def cuboid_data(o, size=(1, 1, 1)):
        X = [[[0, 1, 0], [0, 0, 0], [1, 0, 0], [1, 1, 0]],
             [[0, 0, 0], [0, 0, 1], [1, 0, 1], [1, 0, 0]],
             [[1, 0, 1], [1, 0, 0], [1, 1, 0], [1, 1, 1]],
             [[0, 0, 1], [0, 0, 0], [0, 1, 0], [0, 1, 1]],
             [[0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 1, 0]],
             [[0, 1, 1], [0, 0, 1], [1, 0, 1], [1, 1, 1]]]
        X = np.array(X).astype(float)
        for i in range(3):
            X[:, :, i] *= size[i]
        X += np.array(o)
        return X
    
    
    def plotCubeAt(positions, sizes=None, colors=None, **kwargs):
        if not isinstance(colors, (list, np.ndarray)):
            colors = ["C0"] * len(positions)
        if not isinstance(sizes, (list, np.ndarray)):
            sizes = [(1, 1, 1)] * len(positions)
        g = []
        for p, s, c in zip(positions, sizes, colors):
            g.append(cuboid_data(p, size=s))
        return Poly3DCollection(np.concatenate(g), facecolors=np.repeat(colors, 6), **kwargs)
    
    
    # 箱子类
    class Box:
        def __init__(self, lx, ly, lz, weight=0.0, type=0):
            # 长
            self.lx = lx
            # 宽
            self.ly = ly
            # 高
            self.lz = lz
            # 重
            self.weight = weight
            # 类型
            self.type = type
    
        def __str__(self):
            return "lx: {}, ly: {}, lz: {}, weight: {}, type: {}".format(self.lx, self.ly, self.lz, self.weight, self.type)
    
    
    # 块类
    class Block:
        def __init__(self, lx, ly, lz, require_list=[], weight=0.0, box_rotate=False):
            # 长
            self.lx = lx
            # 宽
            self.ly = ly
            # 高
            self.lz = lz
            # 需要的物品数量
            self.require_list = require_list
            # 需要的物品重量
            self.weight = weight
            # 体积
            self.volume = 0
            # 是否旋转
            self.box_rotate = box_rotate
    
        def __str__(self):
            return "lx: %s, ly: %s, lz: %s, volume: %s, require: %s, weight: %s, box_rotate: %a" % (self.lx, self.ly, self.lz, self.volume, self.require_list, self.weight, self.box_rotate)
    
        def __eq__(self, other):
            return self.lx == other.lx and self.ly == other.ly and self.lz == other.lz and self.box_rotate == other.box_rotate and (np.array(self.require_list) == np.array(other.require_list)).all()
    
    
    # 平面类
    class Plane:
        def __init__(self, x, y, z, lx, ly, height_limit=0):
            # 坐标
            self.x = x
            self.y = y
            self.z = z
            # 长
            self.lx = lx
            # 宽
            self.ly = ly
            # 限高
            self.height_limit = height_limit
            self.origin = None
    
        def __str__(self):
            return "x:{}, y:{}, z:{}, lx:{}, ly:{}, height_limit:{}".format(self.x, self.y, self.z, self.lx, self.ly, self.height_limit)
    
        def __eq__(self, other):
            return self.x == other.x and self.y == other.y and self.z == other.z and self.lx == other.lx and self.ly == other.ly
    
        # 判断是否与另一个平面相邻(z坐标相同,至少有一个边平齐),并返回合并后的两个平面
        def adjacent_with(self, other):
            if self.z != other.z:
                return False, None, None
            # 矩形中心
            my_center = (self.x + self.lx / 2, self.y + self.ly / 2)
            other_center = (other.x + other.lx / 2, other.y + other.ly / 2)
            # 矩形相邻时的中心距离
            x_adjacent_measure = self.lx / 2 + other.lx / 2
            y_adjacent_measure = self.ly / 2 + other.ly / 2
            # 宽边相邻,长边对齐
            if x_adjacent_measure + MAX_GAP >= math.fabs(my_center[0] - other_center[0]) >= x_adjacent_measure:
                if self.y == other.y and self.ly == other.ly:
                    ms1 = Plane(min(self.x, other.x), self.y, self.z, self.lx + other.lx, self.ly)
                    return True, ms1, None
                if self.y == other.y:
                    ms1 = Plane(min(self.x, other.x), self.y, self.z, self.lx + other.lx, min(self.ly, other.ly))
                    if self.ly > other.ly:
                        ms2 = Plane(self.x, self.y + other.ly, self.z, self.lx, self.ly - other.ly)
                    else:
                        ms2 = Plane(other.x, self.y + self.ly, self.z, other.lx, other.ly - self.ly)
                    return True, ms1, ms2
                if self.y + self.ly == other.y + other.ly:
                    ms1 = Plane(min(self.x, other.x), max(self.y, other.y), self.z, self.lx + other.lx, min(self.ly, other.ly))
                    if self.ly > other.ly:
                        ms2 = Plane(self.x, self.y, self.z, self.lx, self.ly - other.ly)
                    else:
                        ms2 = Plane(other.x, other.y, self.z, other.lx, other.ly - self.ly)
                    return True, ms1, ms2
            # 长边相邻,宽边对齐
            if y_adjacent_measure + MAX_GAP >= math.fabs(my_center[1] - other_center[1]) >= y_adjacent_measure:
                if self.x == other.x and self.lx == other.lx:
                    ms1 = Plane(self.x, min(self.y, other.y), self.z, self.lx, self.ly + other.ly)
                    return True, ms1, None
                if self.x == other.x:
                    ms1 = Plane(self.x, min(self.y, other.y), self.z, min(self.lx, other.lx), self.ly + other.ly)
                    if self.lx > other.lx:
                        ms2 = Plane(self.x + other.lx, self.y, self.z, self.lx - other.lx, self.ly)
                    else:
                        ms2 = Plane(self.x + self.lx, other.y, self.z, other.lx - self.lx, other.ly)
                    return True, ms1, ms2
                if self.x + self.lx == other.x + other.lx:
                    ms1 = Plane(max(self.x, other.x), min(self.y, other.y), self.z, min(self.lx, other.lx), self.ly + other.ly)
                    if self.lx > other.lx:
                        ms2 = Plane(self.x, self.y, self.z, self.lx - other.lx, self.ly)
                    else:
                        ms2 = Plane(other.x, other.y, self.z, other.lx - self.lx, other.ly)
                    return True, ms1, ms2
            return False, None, None
    
    
    # 问题类
    class Problem:
        def __init__(self, container: Plane, height_limit=sys.maxsize, weight_limit=sys.maxsize, box_list=[], num_list=[], rotate=False):
            # 初始最低水平面
            self.container = container
            # 限高
            self.height_limit = height_limit
            # 限重
            self.weight_limit = weight_limit
            # 箱体列表
            self.box_list = box_list
            # 箱体数量
            self.num_list = num_list
            # 是否考虑板材旋转
            self.rotate = rotate
    
    
    # 放置类
    class Place:
        def __init__(self, plane: Plane, block: Block):
            self.plane = plane
            self.block = block
    
        def __eq__(self, other):
            return self.plane == other.plane and self.block == other.block
    
    
    # 装箱状态类
    class PackingState:
        def __init__(self, plane_list=[], avail_list=[], weight=0.0):
            # 装箱计划
            self.plan_list = []
            # 可用箱体数量
            self.avail_list = avail_list
            # 可用平面列表
            self.plane_list = plane_list
            # 备用平面列表
            self.spare_plane_list = []
            # 当前排样重量
            self.weight = weight
            # 当前排样体积
            self.volume = 0
    
    
    # 选择平面
    def select_plane(ps: PackingState):
        # 选最低的平面
        min_z = min([p.z for p in ps.plane_list])
        temp_planes = [p for p in ps.plane_list if p.z == min_z]
        if len(temp_planes) == 1:
            return temp_planes[0]
        # 相同高度的平面有多个的话,选择面积最小的平面
        min_area = min([p.lx * p.ly for p in temp_planes])
        temp_planes = [p for p in temp_planes if p.lx * p.ly == min_area]
        if len(temp_planes) == 1:
            return temp_planes[0]
        # 较狭窄的
        min_narrow = min([p.lx/p.ly if p.lx <= p.ly else p.ly/p.lx for p in temp_planes])
        new_temp_planes = []
        for p in temp_planes:
            narrow = p.lx/p.ly if p.lx <= p.ly else p.ly/p.lx
            if narrow == min_narrow:
                new_temp_planes.append(p)
        if len(new_temp_planes) == 1:
            return new_temp_planes[0]
        # x坐标较小
        min_x = min([p.x for p in new_temp_planes])
        new_temp_planes = [p for p in new_temp_planes if p.x == min_x]
        if len(new_temp_planes) == 1:
            return new_temp_planes[0]
        # y坐标较小
        min_y = min([p.y for p in new_temp_planes])
        new_temp_planes = [p for p in new_temp_planes if p.y == min_y]
        return new_temp_planes[0]
    
    
    # 将某平面从可用平面列表转移到备用平面列表
    def disable_plane(ps: PackingState, plane: Plane):
        ps.plane_list.remove(plane)
        ps.spare_plane_list.append(plane)
    
    
    # 生成简单块
    def gen_simple_block(init_plane: Plane, box_list, num_list, max_height, can_rotate=False):
        block_table = []
        for box in box_list:
            for nx in np.arange(num_list[box.type]) + 1:
                for ny in np.arange(num_list[box.type] / nx) + 1:
                    for nz in np.arange(num_list[box.type] / nx / ny) + 1:
                        if box.lx * nx <= init_plane.lx and box.ly * ny <= init_plane.ly and box.lz * nz <= max_height - init_plane.z:
                            # 该简单块需要的立体箱子数量
                            requires = np.full_like(num_list, 0)
                            requires[box.type] = int(nx) * int(ny) * int(nz)
                            # 简单块
                            block = Block(lx=box.lx * nx, ly=box.ly * ny, lz=box.lz * nz, require_list=requires)
                            # 简单块填充体积
                            block.volume = box.lx * nx * box.ly * ny * box.lz * nz
                            # 简单块重量
                            block.weight = int(nx) * int(ny) * int(nz) * box.weight
                            block_table.append(block)
                        if can_rotate:
                            # 物品朝向选择90度进行堆叠
                            if box.ly * nx <= init_plane.lx and box.lx * ny <= init_plane.ly and box.lz * nz <= max_height - init_plane.z:
                                requires = np.full_like(num_list, 0)
                                requires[box.type] = int(nx) * int(ny) * int(nz)
                                # 简单块
                                block = Block(lx=box.ly * nx, ly=box.lx * ny, lz=box.lz * nz, require_list=requires, box_rotate=True)
                                # 简单块填充体积
                                block.volume = box.ly * nx * box.lx * ny * box.lz * nz
                                # 简单块重量
                                block.weight = int(nx) * int(ny) * int(nz) * box.weight
                                block_table.append(block)
        return block_table
    
    
    # 生成可行块列表
    def gen_block_list(plane: Plane, avail, block_table, max_height, avail_weight=sys.maxsize):
        block_list = []
        for block in block_table:
            # 块中需要的箱子数量必须小于最初的待装箱的箱子数量
            # 块的尺寸必须小于放置空间尺寸
            # 块的重量必须小于可放置重量
            if (np.array(block.require_list) <= np.array(avail)).all() and block.lx <= plane.lx and block.ly <= plane.ly \
                    and block.lz <= max_height - plane.z and block.weight <= avail_weight:
                block_list.append(block)
        return block_list
    
    
    # 查找下一个可行块
    def find_block(plane: Plane, block_list, ps: PackingState):
        # 平面的面积
        plane_area = plane.lx * plane.ly
        # 放入块后,剩余的最小面积
        min_residual_area = min([plane_area - b.lx * b.ly for b in block_list])
        # 剩余面积相同,保留最大体积的块
        candidate = [b for b in block_list if plane_area - b.lx * b.ly == min_residual_area]
        # 可用平面最大高度
        max_plane_height = min([p.z for p in ps.plane_list])
        _candidate = sorted(candidate, key=lambda x: x.volume, reverse=True)
        # if max_plane_height == 0:
        #     # 第一次放置体积最大的块
        #     _candidate = sorted(candidate, key=lambda x: x.volume, reverse=True)
        # else:
        #     # 选择平面时尽量使放置物品后与已经放置的物品平齐
        #     _candidate = sorted(candidate, key=lambda x: x.lz + plane.z - max_plane_height)
        #     _candidate = sorted(candidate, key=lambda x: x.volume + ps.volume - 2440*1220*1000)
        return _candidate[0]
    
    
    # 裁切出新的剩余空间(有稳定性约束)
    def gen_new_plane(plane: Plane, block: Block):
        # 块顶部的新平面
        rs_top = Plane(plane.x, plane.y, plane.z + block.lz, block.lx, block.ly)
        # 底部平面裁切
        if block.lx == plane.lx and block.ly == plane.ly:
            return rs_top, None, None
        if block.lx == plane.lx:
            return rs_top, Plane(plane.x, plane.y + block.ly, plane.z, plane.lx, plane.ly - block.ly), None
        if block.ly == plane.ly:
            return rs_top, Plane(plane.x + block.lx, plane.y, plane.z, plane.lx - block.lx, block.ly), None
        # 比较两种方式中面积较大的两个子平面,选择有最大面积子平面的生成方式
        rsa1 = Plane(plane.x, plane.y + block.ly, plane.z, plane.lx, plane.ly - block.ly)
        rsa2 = Plane(plane.x + block.lx, plane.y, plane.z, plane.lx - block.lx, block.ly)
        rsa_bigger = rsa1 if rsa1.lx * rsa1.ly >= rsa2.lx * rsa2.ly else rsa2
        rsb1 = Plane(plane.x, plane.y + block.ly, plane.z, block.lx, plane.ly - block.ly)
        rsb2 = Plane(plane.x + block.lx, plane.y, plane.z, plane.lx - block.lx, plane.ly)
        rsb_bigger = rsb1 if rsb1.lx * rsb1.ly >= rsb2.lx * rsb2.ly else rsb2
        if rsa_bigger.lx * rsa_bigger.ly >= rsb_bigger.lx * rsb_bigger.ly:
            return rs_top, rsa1, rsa2
        else:
            return rs_top, rsb1, rsb2
    
    
    # 计算平面浪费面积
    def plane_waste(ps: PackingState, plane: Plane, block_table, max_height, max_weight=sys.maxsize):
        # 浪费面积
        waste = 0
        if plane:
            block_list = gen_block_list(plane, ps.avail_list, block_table, max_height, max_weight - ps.weight)
            if len(block_list) > 0:
                block = find_block(plane, block_list, ps)
                waste = plane.lx * plane.ly - block.lx * block.ly
            else:
                waste = plane.lx * plane.ly
        return waste
    
    
    # 判断平面是否可以放置物品
    def can_place(ps: PackingState, plane: Plane, block_table, max_height, max_weight=sys.maxsize):
        if plane is None:
            return False
        block_list = gen_block_list(plane, ps.avail_list, block_table, max_height, max_weight - ps.weight)
        return True if len(block_list) > 0 else False
    
    
    # 用块填充平面
    def fill_block(ps: PackingState, plane: Plane, block: Block):
        # 更新可用箱体数目
        ps.avail_list = (np.array(ps.avail_list) - np.array(block.require_list)).tolist()
        # 更新放置计划
        place = Place(plane, block)
        ps.plan_list.append(place)
        # 更新体积利用率
        ps.volume = ps.volume + block.volume
        # 产生三个新的平面
        rs_top, rs1, rs2 = gen_new_plane(plane, block)
        # 移除裁切前的平面
        ps.plane_list.remove(plane)
        # 装入新的可用平面
        if rs_top:
            ps.plane_list.append(rs_top)
        if rs1:
            ps.plane_list.append(rs1)
        if rs2:
            ps.plane_list.append(rs2)
    
    
    # 合并平面
    def merge_plane(ps: PackingState, plane: Plane, block_table, max_height, max_weight=sys.maxsize):
        # print("合并平面开始了")
        for ns in ps.plane_list + ps.spare_plane_list:
            # 不和自己合并
            if plane == ns:
                continue
            # 找相邻平面
            is_adjacent, ms1, ms2 = plane.adjacent_with(ns)
            if is_adjacent:
                # print("有相邻平面呦")
                block_list = gen_block_list(ns, ps.avail_list, block_table, max_height, max_weight - ps.weight)
                # 相邻平面本身能放入至少一个剩余物品
                if len(block_list) > 0:
                    block = find_block(ns, block_list, ps)
                    # 计算相邻平面和原平面浪费面积的总和
                    ws1 = ns.lx * ns.ly - block.lx * block.ly + plane.lx * plane.ly
                    # 计算合并后平面的总浪费面积
                    ws2 = plane_waste(ps, ms1, block_table, max_height, max_weight) + plane_waste(ps, ms2, block_table, max_height, max_weight)
                    # 合并后,浪费更小,则保留合并
                    if ws1 > ws2:
                        # 保留平面合并
                        ps.plane_list.remove(plane)
                        if ns in ps.plane_list:
                            ps.plane_list.remove(ns)
                        else:
                            ps.spare_plane_list.remove(ns)
                        if ms1:
                            ps.plane_list.append(ms1)
                        if ms2:
                            ps.plane_list.append(ms2)
                        return
                    else:
                        # 放弃平面合并,寻找其他相邻平面
                        continue
                # 相邻平面本身无法放入剩余物品
                else:
                    # 合共后产生一个平面
                    if ms2 is None:
                        # 能放物品,则保留平面合并
                        if can_place(ps, ms1, block_table, max_height, max_weight):
                            ps.plane_list.remove(plane)
                            if ns in ps.plane_list:
                                ps.plane_list.remove(ns)
                            else:
                                ps.spare_plane_list.remove(ns)
                            ps.plane_list.append(ms1)
                            return
                        elif ms1.lx * ms1.ly > plane.lx * plane.ly and ms1.lx * ms1.ly > ns.lx * ns.ly:
                            ps.plane_list.remove(plane)
                            if ns in ps.plane_list:
                                ps.plane_list.remove(ns)
                            else:
                                ps.spare_plane_list.remove(ns)
                            # ps.spare_plane_list.append(ms1)
                            ps.plane_list.append(ms1)
                            return
                        else:
                            continue
                    # 合并后产生两个平面
                    else:
                        if (not can_place(ps, ms1, block_table, max_height, max_weight)) and (not can_place(ps, ms2, block_table, max_height, max_weight)):
                            if (ms1.lx * ms1.ly > plane.lx * plane.ly and ms1.lx * ms1.ly > ns.lx * ns.ly) or (ms2.lx * ms2.ly > plane.lx * plane.ly and ms2.lx * ms2.ly > ns.lx * ns.ly):
                                ps.plane_list.remove(plane)
                                if ns in ps.plane_list:
                                    ps.plane_list.remove(ns)
                                else:
                                    ps.spare_plane_list.remove(ns)
                                ps.spare_plane_list.append(ms1)
                                ps.spare_plane_list.append(ms2)
                                return
                            else:
                                continue
                        else:
                            ps.plane_list.remove(plane)
                            if ns in ps.plane_list:
                                ps.plane_list.remove(ns)
                            else:
                                ps.spare_plane_list.remove(ns)
                            if can_place(ps, ms1, block_table, max_height, max_weight):
                                ps.plane_list.append(ms1)
                            else:
                                ps.spare_plane_list.append(ms1)
    
                            if can_place(ps, ms2, block_table, max_height, max_weight):
                                ps.plane_list.append(ms2)
                            else:
                                ps.spare_plane_list.append(ms2)
                            return
    
        # 若对平面列表和备用平面列表搜索完毕后,最终仍没有找到可合并的平面,则将目标平面从平面列表移入备用平面列表
        disable_plane(ps, plane)
    
    
    # 构建箱体坐标,用于绘图
    def build_box_position(block, init_pos, box_list):
        # 箱体类型索引
        box_idx = (np.array(block.require_list) > 0).tolist().index(True)
        if box_idx > -1:
            # 所需箱体
            box = box_list[box_idx]
            # 箱体的相对坐标
            if block.box_rotate:
                nx = block.lx / box.ly
                ny = block.ly / box.lx
                x_list = (np.arange(0, nx) * box.ly).tolist()
                y_list = (np.arange(0, ny) * box.lx).tolist()
            else:
                nx = block.lx / box.lx
                ny = block.ly / box.ly
                x_list = (np.arange(0, nx) * box.lx).tolist()
                y_list = (np.arange(0, ny) * box.ly).tolist()
            nz = block.lz / box.lz
            z_list = (np.arange(0, nz) * box.lz).tolist()
            # 箱体的绝对坐标
            dimensions = (np.array([x for x in product(x_list, y_list, z_list)]) + np.array([init_pos[0], init_pos[1], init_pos[2]])).tolist()
            # 箱体的坐标及尺寸
            if block.box_rotate:
                return sorted([d + [box.ly, box.lx, box.lz] for d in dimensions], key=lambda x: (x[0], x[1], x[2])), box_idx
            else:
                return sorted([d + [box.lx, box.ly, box.lz] for d in dimensions], key=lambda x: (x[0], x[1], x[2])), box_idx
        return None, None
    
    
    # 绘制排样结果
    def draw_packing_result(problem: Problem, ps: PackingState):
        # 绘制结果
        fig = plt.figure()
        ax1 = fig.gca(projection='3d')
        # 绘制容器
        plot_linear_cube(ax1, 0, 0, 0, problem.container.lx, problem.container.ly, problem.height_limit)
        for p in ps.plan_list:
            # 绘制箱子
            box_pos, _ = build_box_position(p.block, (p.plane.x, p.plane.y, p.plane.z), problem.box_list)
            positions = []
            sizes = []
            colors = ["yellow"] * len(box_pos)
            for bp in sorted(box_pos, key=lambda x: (x[0], x[1], x[2])):
                positions.append((bp[0], bp[1], bp[2]))
                sizes.append((bp[3], bp[4], bp[5]))
    
            pc = plotCubeAt(positions, sizes, colors=colors, edgecolor="k")
            ax1.add_collection3d(pc)
        plt.title('Cube{}'.format(0))
        plt.show()
        # plt.savefig('3d_lowest_plane_packing.png', dpi=800)
    
    
    # 基本启发式算法
    def basic_heuristic(problem: Problem):
        # 生成简单块
        block_table = gen_simple_block(problem.container, problem.box_list, problem.num_list, problem.height_limit, problem.rotate)
        # 初始化排样状态
        ps = PackingState(avail_list=problem.num_list)
        # 开始时,剩余空间堆栈中只有容器本身
        ps.plane_list.append(Plane(problem.container.x, problem.container.y, problem.container.z, problem.container.lx,problem.container.ly))
        max_used_high = 0
        # 循环直到所有平面使用完毕
        while ps.plane_list:
            # 选择平面
            plane = select_plane(ps)
            # 查找可用块
            block_list = gen_block_list(plane, ps.avail_list, block_table, problem.height_limit, problem.weight_limit - ps.weight)
            if block_list:
                # 查找下一个近似最优块
                block = find_block(plane, block_list, ps)
                # 填充平面
                fill_block(ps, plane, block)
                # 更新排样重量
                ps.weight += block.weight
                # 更新最大使用高度
                if plane.z + block.lz > max_used_high:
                    max_used_high = plane.z + block.lz
            else:
                # 合并相邻平面
                merge_plane(ps, plane, block_table, problem.height_limit, problem.weight_limit)
    
        # 板材的位置信息
        box_pos_info = [[] for _ in problem.num_list]
        for p in ps.plan_list:
            box_pos, box_idx = build_box_position(p.block, (p.plane.x, p.plane.y, p.plane.z), problem.box_list)
            for bp in box_pos:
                box_pos_info[box_idx].append((bp[0], bp[1], bp[2]))
        # 计算容器利用率
        used_volume = problem.container.lx * problem.container.ly * max_used_high
        used_ratio = round(float(ps.volume) * 100 / float(used_volume), 3) if used_volume > 0 else 0
    
        # # 绘制排样结果图
        draw_packing_result(problem, ps)
    
        return ps.avail_list, used_ratio, max_used_high, box_pos_info, ps
    
    
    # 主算法
    def simple_test():
        # 容器底面
        container = Plane(0, 0, 0, 2440, 1220)
        # 箱体列表
        box_list = [Box(lx=2390, ly=70, lz=10, weight=3001, type=0),
                    Box(lx=2390, ly=50, lz=10, weight=10, type=1),
                    Box(lx=625, ly=210, lz=10, weight=5, type=2),
                    Box(lx=625, ly=110, lz=10, weight=5, type=3),
                    Box(lx=2160, ly=860, lz=10, weight=5, type=4),
                    Box(lx=860, ly=140, lz=10, weight=5, type=5),
                    Box(lx=860, ly=120, lz=10, weight=5, type=6)]
        num_list = [200, 3, 200, 180, 20, 5, 10]
        # 问题
        problem = Problem(container=container, height_limit=300, weight_limit=4000, box_list=box_list, num_list=copy.copy(num_list))
        # 具体计算
        new_avail_list, used_ratio, used_high, box_pos_, _ = basic_heuristic(problem)
        # 箱体原始数量
        print(num_list)
        # 剩余箱体
        print(new_avail_list)
        # 利用率
        print(used_ratio)
    
    
    if __name__ == "__main__":
        simple_test()
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
    • 475
    • 476
    • 477
    • 478
    • 479
    • 480
    • 481
    • 482
    • 483
    • 484
    • 485
    • 486
    • 487
    • 488
    • 489
    • 490
    • 491
    • 492
    • 493
    • 494
    • 495
    • 496
    • 497
    • 498
    • 499
    • 500
    • 501
    • 502
    • 503
    • 504
    • 505
    • 506
    • 507
    • 508
    • 509
    • 510
    • 511
    • 512
    • 513
    • 514
    • 515
    • 516
    • 517
    • 518
    • 519
    • 520
    • 521
    • 522
    • 523
    • 524
    • 525
    • 526
    • 527
    • 528
    • 529
    • 530
    • 531
    • 532
    • 533
    • 534
    • 535
    • 536
    • 537
    • 538
    • 539
    • 540
    • 541
    • 542
    • 543
    • 544
    • 545
    • 546
    • 547
    • 548
    • 549
    • 550
    • 551
    • 552
    • 553
    • 554
    • 555
    • 556
    • 557
    • 558
    • 559
    • 560
    • 561
    • 562
    • 563
    • 564
    • 565
    • 566
    • 567
    • 568
    • 569
    • 570
    • 571
    • 572
    • 573
    • 574
    • 575
    • 576
    • 577
    • 578
    • 579
    • 580
    • 581
    • 582
    • 583
    • 584
    • 585
    • 586
    • 587
    • 588
    • 589
    • 590
    • 591
    • 592
    • 593
    • 594
    • 595
    • 596
    • 597
    • 598
    • 599
    • 600
    • 601
    • 602
    • 603

    算法运行结果如下:
    在这里插入图片描述

    ⭐️ 写在最后

    本文理论部分参考上海交通大学硕士论文《三维装箱问题的混合遗传算法研究》,论文作者和导师都很牛,读者可以自行百度获取论文原文😏。

    笔者水平有限,若有不对的地方欢迎评论指正!

  • 相关阅读:
    【华为OD机试真题 python】 水仙花数【2022 Q4 | 100分】
    Nautlius Chain主网正式上线,模块Layer3时代正式开启
    新华三路由器+华为交换机,实现华为交换机指定端口访问外网
    1. 变量和基本类型
    Spring-webflux 响应式编程
    『现学现忘』Git基础 — 3、Git介绍
    cola 架构简单记录
    标准C++中string类函数总结
    C++算法之旅、06 基础篇 | 第四章 动态规划 详解
    被CTO推荐的SQL总结
  • 原文地址:https://blog.csdn.net/weixin_37522117/article/details/127983485