引子
三维装箱问题在一些领域很普遍。
对于三维装箱问题，笔者之前写过一篇博文：
在这篇文章中，只考虑了尺寸的限制，没有加入重量限制。应广大粉丝的强烈要求😄，加入重量限制势在必行。🚚
加入重量限制后，主要思路有两个关键点：
👉 1、在简单块和复合块生成的时候，记录块的重量。
👉 2、在填充块的时候，记录装箱过程中的总重量，达到限重则不进行填充。
代码
import copy from itertools import product from matplotlib import pyplot as plt from mpl_toolkits import mplot3d from mpl_toolkits.mplot3d.art3d import Poly3DCollection import numpy as np import sys # 复合块的最小填充率 MIN_FILL_RATE = 0.9 # 可行放置矩形与相应复合块顶部面积比的最小值 MIN_AREA_RATE = 0.9 # 复合块最大复杂度 MAX_TIMES = 2 # 搜索树深度 MAX_DEPTH = 3 # 搜索树节点分支数 MAX_BRANCH = 2 # 临时的最优放置方案 tmp_best_ps = None # 栈数据结构，用于存储剩余空间 class Stack: def __init__(self): self.data = [] def empty(self): return len(self.data) == 0 def not_empty(self): return len(self.data) > 0 def pop(self): return self.data.pop() if len(self.data) > 0 else None def push(self, *items): for item in items: self.data.append(item) def top(self): return self.data[len(self.data) - 1] if len(self.data) > 0 else None def clear(self): self.data.clear() def size(self): return len(self.data) # 箱子类 class Box: def __init__(self, lx, ly, lz, type=0, weight=0.0): # 长 self.lx = lx # 宽 self.ly = ly # 高 self.lz = lz # 类型 self.type = type # 重 self.weight = weight def __str__(self): return "lx: {}, ly: {}, lz: {}, type: {}, weight: {}".format(self.lx, self.ly, self.lz, self.type, self.weight) # 剩余空间类 class Space: def __init__(self, x, y, z, lx, ly, lz, origin=None): # 坐标 self.x = x self.y = y self.z = z # 长 self.lx = lx # 宽 self.ly = ly # 高 self.lz = lz # 表示从哪个剩余空间切割而来 self.origin = origin def __str__(self): return "x:{},y:{},z:{},lx:{},ly:{},lz:{}".format(self.x, self.y, self.z, self.lx, self.ly, self.lz) 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 and self.lz == other.lz # 装箱问题类 class Problem: def __init__(self, container: Space, box_list=[], num_list=[], weight_limit=sys.maxsize): # 容器 self.container = container # 箱子列表 self.box_list = box_list # 箱子对应的数量 self.num_list = num_list # 限重 self.weight_limit = weight_limit # 块类 class Block: def __init__(self, lx, ly, lz, require_list=[], children=[], direction=None, weight=0.0): # 长 self.lx = lx # 宽 self.ly = ly # 高 self.lz = lz # 需要的物品数量 self.require_list = require_list # 体积 self.volume = 0 # 子块列表，简单块的子块列表为空 self.children = children # 复合块子块的合并方向 self.direction = direction # 需要的物品重量 self.weight = weight # 顶部可放置矩形尺寸 self.ax = 0 self.ay = 0 # 复杂度，复合次数 self.times = 0 # 适应度，块选择时使用 self.fitness = 0 def __str__(self): return "lx: %s, ly: %s, lz: %s, volume: %s, ax: %s, ay: %s, times:%s, fitness: %s, require: %s, children: " \ "%s, direction: %s" % (self.lx, self.ly, self.lz, self.volume, self.ax, self.ay, self.times, self.fitness, self.require_list, self.children, self.direction) def __eq__(self, other): return self.lx == other.lx and self.ly == other.ly and self.lz == other.lz and self.ax == other.ax and self.ay == self.ay and (np.array(self.require_list) == np.array(other.require_list)).all() def __hash__(self): return hash(",".join([str(self.lx), str(self.ly), str(self.lz), str(self.ax), str(self.ay), ",".join([str(r) for r in self.require_list])])) # 放置类 class Place: def __init__(self, space: Space, block: Block): # 空间 self.space = space # 块 self.block = block def __eq__(self, other): return self.space == other.space and self.block == other.block # 装箱状态类 class PackingState: def __init__(self, plan_list=[], space_stack: Stack = Stack(), avail_list=[], weight=0.0): # 已生成的装箱方案列表 self.plan_list = plan_list # 剩余空间堆栈 self.space_stack = space_stack # 剩余可用箱体数量 self.avail_list = avail_list # 当前排样重量 self.weight = weight # 已装载物品总体积 self.volume = 0 # 最终装载物品的总体积的评估值 self.volume_complete = 0 # 合并块时通用校验项目 def combine_common_check(combine: Block, container: Space, num_list, max_weight=sys.maxsize): # 合共块尺寸不得大于容器尺寸 if combine.lx > container.lx: return False if combine.ly > container.ly: return False if combine.lz > container.lz: return False # 合共块需要的箱子数量不得大于箱子总的数量 if (np.array(combine.require_list) > np.array(num_list)).any(): return False # 合并块的填充体积不得小于最小填充率 if combine.volume / (combine.lx * combine.ly * combine.lz) < MIN_FILL_RATE: return False # 合并块的顶部可放置矩形必须足够大 if (combine.ax * combine.ay) / (combine.lx * combine.ly) < MIN_AREA_RATE: return False # 合并块的复杂度不得超过最大复杂度 if combine.times > MAX_TIMES: return False # 合并块的重量不得超过最大重量 if combine.weight > max_weight: return False return True # 合并块时通用合并项目 def combine_common(a: Block, b: Block, combine: Block): # 合并块的需求箱子数量 combine.require_list = (np.array(a.require_list) + np.array(b.require_list)).tolist() # 合并填充体积 combine.volume = a.volume + b.volume # 构建父子关系 combine.children = [a, b] # 合并后的复杂度 combine.times = max(a.times, b.times) + 1 # 重量相加 combine.weight = a.weight + b.weight # 生成简单块 def gen_simple_block(container, box_list, num_list, max_weight=sys.maxsize): 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 <= container.lx and box.ly * ny <= container.ly and box.lz * nz <= container.lz and \ int(nx) * int(ny) * int(nz) * box.weight <= max_weight: # 该简单块需要的立体箱子数量 requires = np.full_like(num_list, 0) requires[box.type] = nx * ny * nz # 简单块 block = Block(box.lx * nx, box.ly * ny, box.lz * nz, requires) # 顶部可放置矩形 block.ax = box.lx * nx block.ay = box.ly * ny # 简单块填充体积 block.volume = box.lx * nx * box.ly * ny * box.lz * nz # 简单块重量 block.weight = int(nx) * int(ny) * int(nz) * box.weight # 简单块复杂度 block.times = 0 block_table.append(block) return sorted(block_table, key=lambda x: x.volume, reverse=True) # 生成复合块 def gen_complex_block(container, box_list, num_list, max_weight=sys.maxsize): # 先生成简单块 block_table = gen_simple_block(container, box_list, num_list, max_weight) for times in range(MAX_TIMES): new_block_table = [] # 循环所有简单块，两两配对 for i in np.arange(0, len(block_table)): # 第一个简单块 a = block_table[i] for j in np.arange(0, len(block_table)): # 简单块不跟自己复合 if j == i: continue # 第二个简单块 b = block_table[j] # 复杂度满足当前复杂度 if a.times == times or b.times == times: c = Block(0, 0, 0) # 按x轴方向复合 if a.ax == a.lx and b.ax == b.lx and a.lz == b.lz: c.direction = "x" c.ax = a.ax + b.ax c.ay = min(a.ay, b.ay) c.lx = a.lx + b.lx c.ly = max(a.ly, b.ly) c.lz = a.lz combine_common(a, b, c) if combine_common_check(c, container, num_list, max_weight): new_block_table.append(c) continue # 按y轴方向复合 if a.ay == a.ly and b.ay == b.ly and a.lz == b.lz: c.direction = "y" c.ax = min(a.ax, b.ax) c.ay = a.ay + b.ay c.lx = max(a.lx, b.lx) c.ly = a.ly + b.ly c.lz = a.lz combine_common(a, b, c) if combine_common_check(c, container, num_list, max_weight): new_block_table.append(c) continue # 按z轴方向复合 if a.ax >= b.lx and a.ay >= b.ly: c.direction = "z" c.ax = b.ax c.ay = b.ay c.lx = a.lx c.ly = a.ly c.lz = a.lz + b.lz combine_common(a, b, c) if combine_common_check(c, container, num_list, max_weight): new_block_table.append(c) continue # 加入新生成的复合块 block_table = block_table + new_block_table # 去重，拥有相同三边长度、物品需求和顶部可放置矩形的复合块被视为等价块，重复生成的等价块将被忽略 block_table = list(set(block_table)) # 按填充体积对复合块进行排序 return sorted(block_table, key=lambda x: x.volume, reverse=True) # 生成可行块列表 def gen_block_list(space: Space, avail, block_table, avail_weight=sys.maxsize): block_list = [] for block in block_table: # 块中需要的箱子需求数量必须小于当前待装箱的箱子数量 # 块的尺寸必须小于放置空间尺寸 # 块的重量必须小于可放置重量 if (np.array(block.require_list) <= np.array(avail)).all() and block.lx <= space.lx and block.ly <= space.ly \ and block.lz <= space.lz and block.weight <= avail_weight: block_list.append(block) return block_list # 裁切出新的剩余空间（有稳定性约束） def gen_residual_space(space: Space, block: Block, box_list=[]): # 三个维度的剩余尺寸 rmx = space.lx - block.lx rmy = space.ly - block.ly rmz = space.lz - block.lz # 三个新裁切出的剩余空间（按入栈顺序依次返回） if rmx >= rmy: # 可转移空间归属于x轴切割空间 drs_x = Space(space.x + block.lx, space.y, space.z, rmx, space.ly, space.lz, space) drs_y = Space(space.x, space.y + block.ly, space.z, block.lx, rmy, space.lz, space) drs_z = Space(space.x, space.y, space.z + block.lz, block.ax, block.ay, rmz, None) return drs_z, drs_y, drs_x else: # 可转移空间归属于y轴切割空间 drs_x = Space(space.x + block.lx, space.y, space.z, rmx, block.ly, space.lz, space) drs_y = Space(space.x, space.y + block.ly, space.z, space.lx, rmy, space.lz, space) drs_z = Space(space.x, space.y, space.z + block.lz, block.ax, block.ay, rmz, None) return drs_z, drs_x, drs_y # 空间转移 def transfer_space(space: Space, space_stack: Stack): # 仅剩一个空间的话，直接弹出 if space_stack.size() <= 1: space_stack.pop() return None # 待转移空间的原始空间 discard = space # 目标空间 space_stack.pop() target = space_stack.top() # 将可转移的空间转移给目标空间 if discard.origin is not None and target.origin is not None and discard.origin == target.origin: new_target = copy.deepcopy(target) # 可转移空间原先归属于y轴切割空间的情况 if discard.lx == discard.origin.lx: new_target.ly = discard.origin.ly # 可转移空间原来归属于x轴切割空间的情况 elif discard.ly == discard.origin.ly: new_target.lx = discard.origin.lx else: return None space_stack.pop() space_stack.push(new_target) # 返回未发生转移之前的目标空间 return target return None # 还原空间转移 def transfer_space_back(space: Space, space_stack: Stack, revert_space: Space): space_stack.pop() space_stack.push(revert_space) space_stack.push(space) # 块放置算法 def place_block(ps: PackingState, block: Block): # 栈顶剩余空间 space = ps.space_stack.pop() # 更新可用箱体数目 ps.avail_list = (np.array(ps.avail_list) - np.array(block.require_list)).tolist() # 更新放置计划 place = Place(space, block) ps.plan_list.append(place) # 更新体积利用率 ps.volume = ps.volume + block.volume # 更新排样重量 ps.weight += block.weight # 压入新的剩余空间 cuboid1, cuboid2, cuboid3 = gen_residual_space(space, block) ps.space_stack.push(cuboid1, cuboid2, cuboid3) # 返回临时生成的放置 return place # 块移除算法 def remove_block(ps: PackingState, block: Block, place: Place, space: Space): # 还原可用箱体数目 ps.avail_list = (np.array(ps.avail_list) + np.array(block.require_list)).tolist() # 还原排样计划 ps.plan_list.remove(place) # 还原体积利用率 ps.volume = ps.volume - block.volume # 还原排样重量 ps.weight -= block.weight # 移除在此之前裁切出的新空间 for _ in range(3): ps.space_stack.pop() # 还原之前的空间 ps.space_stack.push(space) # 补全放置方案 def complete(ps: PackingState, block_table, max_weight=sys.maxsize): # 不对当前的放置状态进行修改 tmp = copy.deepcopy(ps) while tmp.space_stack.not_empty(): # 栈顶空间 space = tmp.space_stack.top() # 可用块列表 block_list = gen_block_list(space, ps.avail_list, block_table, max_weight - ps.weight) if len(block_list) > 0: # 放置块 place_block(tmp, block_list[0]) else: # 空间转移 transfer_space(space, tmp.space_stack) # 补全后的使用体积 ps.volume_complete = tmp.volume # 带深度限制的深度优先搜索算法 def depth_first_search(ps: PackingState, depth, branch, block_table, max_weight=sys.maxsize): global tmp_best_ps if depth != 0: space = ps.space_stack.top() block_list = gen_block_list(space, ps.avail_list, block_table, max_weight - ps.weight) if len(block_list) > 0: # 遍历所有分支 for i in range(min(branch, len(block_list))): # 放置块 place = place_block(ps, block_list[i]) # 放置下一个块 depth_first_search(ps, depth - 1, branch, block_table, max_weight) # 移除刚才添加的块 remove_block(ps, block_list[i], place, space) else: # 转移空间 old_target = transfer_space(space, ps.space_stack) if old_target: # 放置下一个块 depth_first_search(ps, depth, branch, block_table, max_weight) # 还原转移空间 transfer_space_back(space, ps.space_stack, old_target) else: # 补全该方案 complete(ps, block_table, max_weight) # 更新最优解 if ps.volume_complete > tmp_best_ps.volume_complete: tmp_best_ps = copy.deepcopy(ps) # 评价某个块 def estimate(ps: PackingState, block_table, search_params, max_weight=sys.maxsize): # 空的放置方案 global tmp_best_ps # tmp_best_ps = PackingState() tmp_best_ps = PackingState([], Stack(), []) # 开始深度优先搜索 depth_first_search(ps, MAX_DEPTH, MAX_BRANCH, block_table, max_weight) return tmp_best_ps.volume_complete # 查找下一个可行块 def find_next_block(ps: PackingState, block_list, block_table, search_params, max_weight=sys.maxsize): # 最优适应度 best_fitness = 0 # 初始化最优块为第一个块（填充体积最大的块） best_block = block_list[0] # 遍历所有可行块 for block in block_list: # 栈顶空间 space = ps.space_stack.top() # 放置块 place = place_block(ps, block) # 评价值 fitness = estimate(ps, block_table, search_params, max_weight) # 移除刚才添加的块 remove_block(ps, block, place, space) # 更新最优解 if fitness > best_fitness: best_fitness = fitness best_block = block return best_block # # 也可以采用贪心算法，直接返回填充体积最大的块 # return block_list[0] # 递归构建箱体坐标，用于绘图 def build_box_position(block, init_pos, box_list): # 遇到简单块时进行坐标计算 if len(block.children) <= 0 and block.times == 0: # 箱体类型索引 box_idx = (np.array(block.require_list) > 0).tolist().index(True) if box_idx > -1: # 所需箱体 box = box_list[box_idx] # 箱体的相对坐标 nx = block.lx / box.lx ny = block.ly / box.ly nz = block.lz / box.lz x_list = (np.arange(0, nx) * box.lx).tolist() y_list = (np.arange(0, ny) * box.ly).tolist() 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() return sorted([d + [box.lx, box.ly, box.lz] for d in dimensions], key=lambda x: (x[0], x[1], x[2])) return [] pos = [] for child in block.children: pos += build_box_position(child, (init_pos[0], init_pos[1], init_pos[2]), box_list) # 根据子块的复合方向，确定下一个子块的左后下角坐标 if block.direction == "x": init_pos = (init_pos[0] + child.lx, init_pos[1], init_pos[2]) elif block.direction == "y": init_pos = (init_pos[0], init_pos[1] + child.ly, init_pos[2]) elif block.direction == "z": init_pos = (init_pos[0], init_pos[1], init_pos[2] + child.lz) return pos # 绘制立方体边框 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_data2(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 plotCubeAt2(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_data2(p, size=s)) return Poly3DCollection(np.concatenate(g), facecolors=np.repeat(colors, 6), **kwargs) # 绘制排样结果 def draw_packing_result(problem: Problem, ps: PackingState): # 绘制结果 fig = plt.figure() ax1 = mplot3d.Axes3D(fig, auto_add_to_figure=False) fig.add_axes(ax1) # 绘制容器 plot_linear_cube(ax1, 0, 0, 0, problem.container.lx, problem.container.ly, problem.container.lz) for p in ps.plan_list: # 箱子位置及尺寸 box_pos = build_box_position(p.block, (p.space.x, p.space.y, p.space.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 = plotCubeAt2(positions, sizes, colors=colors, edgecolor="k") ax1.add_collection3d(pc) plt.title('PackingResult') plt.show() # plt.savefig('3d_multilayer_search.png', dpi=800) # 基本启发式算法 def basic_heuristic(is_complex, search_params, problem: Problem): if is_complex: # 生成复合块 block_table = gen_complex_block(problem.container, problem.box_list, problem.num_list, problem.weight_limit) else: # 生成简单块 block_table = gen_simple_block(problem.container, problem.box_list, problem.num_list, problem.weight_limit) # 初始化排样状态 ps = PackingState(avail_list=problem.num_list) # 开始时，剩余空间堆栈中只有容器本身 ps.space_stack.push(problem.container) # 所有剩余空间均转满，则停止 while ps.space_stack.size() > 0: space = ps.space_stack.top() block_list = gen_block_list(space, ps.avail_list, block_table, problem.weight_limit - ps.weight) if block_list: # 查找下一个近似最优块 block = find_next_block(ps, block_list, block_table, search_params, problem.weight_limit) # 弹出顶部剩余空间 ps.space_stack.pop() # 更新可用物品数量 ps.avail_list = (np.array(ps.avail_list) - np.array(block.require_list)).tolist() # 更新排样计划 ps.plan_list.append(Place(space, block)) # 更新已利用体积 ps.volume = ps.volume + block.volume # 更新排样重量 ps.weight += block.weight # 压入新裁切的剩余空间 cuboid1, cuboid2, cuboid3 = gen_residual_space(space, block) ps.space_stack.push(cuboid1, cuboid2, cuboid3) else: # 转移剩余空间 transfer_space(space, ps.space_stack) # 打印剩余箱体和已使用容器的体积 print("ps.avail_list") print(ps.avail_list) print(ps.volume) print(ps.weight) # 绘制排样结果图 draw_packing_result(problem, ps) # 主算法 def main(): # 容器 container = Space(0, 0, 0, 10, 10, 10) # 箱体列表及数量 # 深度优先遍历算法效率较低，可以采用如下测试数据 box_list = [Box(1, 2, 3, 0, 13), Box(4, 5, 5, 1, 19), Box(1, 1, 1, 2, 33), Box(2, 2, 2, 3, 77), Box(4, 5, 2, 4, 46)] num_list = [3, 4, 3, 2, 1] # 贪心算法效率较高，可以采用如下测试数据 # box_list = [Box(1, 2, 3, 0, 13), Box(4, 5, 5, 1, 19), Box(1, 1, 1, 2, 33), Box(2, 2, 2, 3, 77), Box(4, 5, 2, 4, 46)] # num_list = [11, 4, 5, 8, 6] # 问题 # container: Space, box_list = [], num_list = [], weight_limit = sys.maxsize problem = Problem(container, box_list, num_list, 120) search_params = dict() # 具体计算 basic_heuristic(True, search_params, problem) if __name__ == "__main__": main()
排样效果如下：
作者这水平有限，有不足之处欢迎留言指正
