首页 > 编程语言 >基于最低水平面的三维装箱问题的启发式算法

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

时间:2023-04-24 15:56:19浏览次数:57  
标签:ps list self 水平面 plane 启发式 装箱 lx ly

本文考虑了一个事实:

在某些情况下,我们在摆放物品时,总是优先选择较低的平面,基于这个常识,本文提出一种基于平面选择的三维装箱算法。

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

⭐️ 选择平面

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

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

⭐️ 填充平面

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

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

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

⭐️ 合并平面

当所选择的平面不能容纳任何一个货物时,更有效地利用空间,需进行平面合并。一个平面只能和其相邻的平面合并,相邻平面指高度相同,即具有相同参考点z坐标,至少有一边平齐,如下图所示类似情况的平面(图中蓝色部分表示目标平面(gs),白色部分表示其相邻平面(ns)):

首先目标平面(gs)先后在平面列表和备用平面列表中依次顺序查找是否有相邻平面(ns)。平面列表指还未使用的新平面列表,备用平面列表指已经过计算不可能放入任何物品的平面的列表。当一个目标平面找到与其相邻的平面时,通过试合并决定是否保留这一合并,并进行正式合并。保留某次试合并的基本准则包括:
(1) 可以装入至少一个仍有剩余的物品(种类、方向不限);
(2) 合并后新平面的面积是否比原先两个平面都大。

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

判断 ns 是否满足准则(1)。若不满足则执行第 2)步,若满足执行第 3)步;
判断 ms1 和 ms2 是否满足准则(1)。将满足的一个平面插入平面列表,不满足的放入备用平面列表。若均不满足准则(1),则判断 ms1 和 ms2 中是否有能够足准则(2)的,若有,则将ms1和ms2均放入备用平面列表;否则不保留此次试合并,重新开始寻找相邻平面;
计算在放入物品后gs和ns将浪费的总面积(ws1)。根据ms1和ms2满足准则(1)的情况,计算合并后可能浪费的面积之和(ws2)。设平面 xs 的面积为Sqr(xs),在该平面上放入物品后将浪费的面积为WsSqr(xs),则根据ms1和ms2的满足准则(1)的情况,ws2有以下几种情况:

若ws1>ws2,则执行平面合并程序,并更新平面和备用平面列表;若ws1<=ws2,则不保留此次试合并,继续寻找其他相邻平面;
若对平面列表和备用平面列表搜索完毕侯,最终仍没有找到可合并的平面,则将目标平面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()

算法运行结果如下:

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

标签:ps,list,self,水平面,plane,启发式,装箱,lx,ly
From: https://www.cnblogs.com/guangzhiruijie/p/17349742.html

相关文章

  • 求解三维装箱问题的启发式深度优先搜索算法(python)
    ⭐️问题描述给定一个容器(其体积为VVV)和一系列待装载的箱子,容器和箱子的形状都是长方体。问题的目标是要确定一个可行的箱子放置方案使得在满足给定装载约束的情况下,容器中包含的箱子总体积SSS尽可能的大,即填充率尽可能的大,这里填充率指的是S/V∗100%S/V*100\%S/V∗......
  • Java中的自动装箱与自动拆箱
    前言在Java中,基本数据类型与其对应的封装类之间可以进行自动转换,这种特性称为自动装箱(autoboxing)和自动拆箱(unboxing)。自动装箱和自动拆箱使得我们在使用基本数据类型时更加方便,同时也提高了代码的可读性和健壮性。本文将详细介绍Java中的自动装箱和自动拆箱机制。基本数据类型......
  • PAT Basic 1090. 危险品装箱
    PATBasic1090.危险品装箱1.题目描述:集装箱运输货物时,我们必须特别小心,不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱,否则很容易造成爆炸。本题给定一张不相容物品的清单,需要你检查每一张集装箱货品清单,判断它们是否能装在同一只箱子里。2.输入格......
  • 什么是装箱和拆箱
    什么是装箱和拆箱?装箱:将值类型转换成引用类型inta=2;Objectb=a;拆箱:将引用类型转换成值类型Objectobj;inta=(int)obj; ......
  • 启发式合并(树上)
    一般用于:查询每一个子树的相关所有信息, 内容:dfs,后,合并儿子的时候,继承一个重儿子,然后把其他儿子暴力合进去就行了,最坏的时间复杂度:NlongN 如何继承的时候不是暴力捏?给每一个点赋值一个新的ID,就行了. 重点是在结构体tr[]节点里面的各种定义的东西, ......
  • IL阅读第二篇,拆箱装箱
    //装箱拆箱stringname="Zery";intage=22;Console.WriteLine(age.ToString()+name);//已ToString的操作Console.WriteLine(age+name);//未ToString操作老规矩,一段C#,一段IL //MethodbeginsatRVA......
  • AcWing 1024. 装箱问题
    有一个箱子容量为V,同时有n个物品,每个物品有一个体积(正整数)。要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。输入格式第一行是一个整数V,表示箱子容量。第二行是一个整数n,表示物品数。接下来n行,每行一个正整数(不超过10000),分别表示这n个物品的各自体积。......
  • 【二维装箱】基于BL算法求解矩形地块二维装箱放置优化问题附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 基于PaddleOCR的多视角集装箱箱号检测识别
    基于PaddleOCR的多视角集装箱箱号检测识别一、项目介绍集装箱号是指装运出口货物集装箱的箱号,填写托运单时必填此项。标准箱号构成基本概念:采用ISO6346(1995)标准标准集装......
  • 算法学习笔记(19): 树上启发式合并(DSU on tree)
    树上启发式合并DSUontree,我也不知道DSU是啥意思这是一种看似特别玄学的优化可以把树上部分问题由\(O(n^2)\)优化到\(O(n\logn)\)。例如CodeForces600E。又......