二维矩形件排样与组批优化：从数学建模到算法实现

1. 问题背景与核心挑战从“一张大板”到“高效切割”在制造业特别是板材加工、服装裁剪、印刷制版等行业一个看似简单却极其耗费成本的环节就是“下料”。想象一下你面前有一张巨大的原材料板材比如钢板、玻璃板、布料卷而你需要从上面切割出成百上千个指定尺寸的小矩形零件。如何安排这些零件的摆放位置才能最大限度地利用原材料减少边角废料从而降低成本这就是经典的“二维矩形件排样问题”。而“组批优化”则是这个问题的前置和延伸。在实际生产中订单往往是分批到达的每批订单包含多种不同尺寸、不同数量的零件。如果来一个订单就排一次版、切一次料效率极低因为每次切割都会产生独立的“起刀”成本和固定的板材余料。更经济的做法是将多个订单的零件“攒”在一起合并到少数几张甚至一张大板上进行统一排版和切割这就是“组批”。组批优化的目标就是在满足所有订单交货期等约束的前提下找到一种最优的零件合并方案使得排版切割后的总成本如使用的板材张数、切割路径总长度等最低。2022年“华为杯”中国研究生数学建模竞赛的B题“方形件组批优化问题”正是将这两个核心问题——组批与排样——进行了耦合。题目给出了多组订单数据每组订单包含若干种不同尺寸的方形件及其需求量。参赛者需要设计算法决定如何将这些订单的零件分组组批并为每一批零件在一块固定尺寸的大板上进行排版最终目标是使使用的板材总面积或张数最小。这听起来像是一个“拼图游戏”但其背后的数学复杂度和计算挑战是巨大的。它本质上是一个组合优化和混合整数规划问题。搜索空间随着零件种类和数量的增加呈指数级爆炸属于NP-Hard难题无法在多项式时间内求得精确最优解。因此这道题考察的核心不仅仅是数学建模能力更是启发式算法设计、问题分解策略以及编程实现的综合能力。接下来我将结合常见的解题思路和代码实现框架为你拆解这个问题的解决之道。2. 模型构建如何用数学语言描述“组批”与“排样”要解决这个问题首先需要将其转化为数学模型。一个清晰的模型是算法设计的蓝图。我们可以将问题分解为两个层次上层是组批决策下层是单板排样。2.1 问题定义与参数假设我们有N个订单每个订单i包含M_i种方形件。每种方形件j有其宽度w_j、高度h_j和需求量d_j属于某个订单。原材料大板尺寸固定为W宽和H高。目标最小化使用的板材总数K。2.2 混合整数规划模型框架一个经典的MIP模型会包含以下核心要素决策变量板材使用变量y_k 1表示第k块板被使用否则为0。零件分配变量x_{ijk} 1表示订单i中的零件j被安排到第k块板上否则为0。这里隐含了组批因为不同订单的零件可能x_{ijk}1且x_{ijk}1i≠i。零件位置变量(posx_{ijk}, posy_{ijk})表示零件j在板k上的左下角坐标。相对位置变量用于防止重叠例如引入0-1变量a_{ij, ij, k}表示在板k上零件j在零件j的左侧。约束条件需求满足约束对于每个零件j其被分配到所有板上的总数等于其需求量d_j。∑_k x_{ijk} d_j对于所有i, j板材边界约束零件必须完全放在板材内部。posx_{ijk} w_j W且posy_{ijk} h_j H当x_{ijk}1时非重叠约束任意两个在同一块板上的零件不能重叠。这是建模中最棘手的部分通常采用“四方位分离”约束基于MIP的经典方法零件A在零件B的左侧posx_A w_A posx_B M*(1 - a_{AB})零件A在零件B的右侧posx_B w_B posx_A M*(1 - b_{AB})零件A在零件B的下方posy_A h_A posy_B M*(1 - c_{AB})零件A在零件B的上方posy_B h_B posy_A M*(1 - d_{AB})并且a_{AB} b_{AB} c_{AB} d_{AB} 1。其中M是一个足够大的常数。板材激活约束如果至少有一个零件被分配到板k则y_k必须为1。x_{ijk} y_k对于所有i, j, k目标函数最小化总板材数Minimize ∑_k y_k注意这是一个概念模型直接求解对于大规模问题如竞赛数据是不可行的。变量数量巨大尤其是位置和相对位置变量导致模型规模爆炸即使使用Gurobi、CPLEX等商业求解器也可能在有限时间内无法得到可行解。因此竞赛中更实用的方法是设计启发式算法或元启发式算法。2.3 问题分解策略两阶段法鉴于直接求解的困难一个行之有效的策略是将组批和排样解耦采用两阶段法第一阶段组批。在不考虑具体排版位置的情况下决定哪些订单的哪些零件应该被合并到同一批即同一块板。这个阶段的目标可以近似为“最小化批次数”同时每批零件的总“面积”不超过板材面积。这可以看作一个“装箱问题”的变种。第二阶段排样。对第一阶段生成的每一个“批”即一篮子零件在一块固定尺寸的板上寻找一个可行的、高利用率的排版方案。这是一个标准的“二维矩形件排样问题”。两阶段法的优点是大大降低了问题的复杂度便于分别设计高效算法。缺点是可能存在“阶段间冲突”一个组批方案在排样阶段可能发现无法排下或者利用率很低这就需要反馈调整。因此更高级的算法会在两阶段间进行迭代或使用集成策略。3. 算法核心组批与排样的实用解法下面我们分别探讨两个阶段常用的算法思路和Python代码框架。3.1 第一阶段组批算法近似装箱组批的本质是将许多不同尺寸的“物品”零件以其面积或体积计装入尽可能少的“箱子”板材中且每个箱子的容量板材面积有限。常用算法首次适应递减法这是解决装箱问题最经典、最简单的启发式算法。步骤 a. 将所有零件按面积从大到小排序。 b. 遍历排序后的零件列表。 c. 对于当前零件依次检查已创建的每一个“批次”箱子。如果放入该批次后该批次的预估总面积不超过板材面积W*H则放入第一个满足条件的批次。 d. 如果所有现有批次都无法容纳则创建一个新的批次将零件放入。优点实现简单速度快。缺点是贪心算法无法保证最优。对于方形件面积相近但长宽比差异大的零件组合可能不如考虑形状的算法。最佳适应递减法与FFD类似但在选择批次时不是选择第一个能放下的而是选择放入后剩余空间最小的批次。这通常能产生更紧凑的装箱结果。考虑形状的启发式由于排样时不仅要看面积还要看能否在二维空间内摆放更高级的组批策略会考虑零件的尺寸。例如可以按零件的最长边或周长排序或者使用“占角”策略的模拟来粗略估计一批零件能否排下。Python代码示例首次适应递减法组批def first_fit_decreasing_grouping(orders, plate_width, plate_height): 使用首次适应递减法进行组批 :param orders: list of dict, 每个dict为{order_id: int, items: list} items中每个元素为{width: w, height: h, demand: d} :param plate_width: 板材宽度 :param plate_height: 板材高度 :return: batches: list of list, 每个内list包含该批次的所有零件(item对象)副本 # 1. 展开所有零件考虑需求量 all_items [] for order in orders: for item in order[items]: for _ in range(item[demand]): # 根据需求量复制零件 all_items.append(item.copy()) # 使用副本避免后续修改原数据 # 2. 按面积递减排序 all_items.sort(keylambda x: x[width] * x[height], reverseTrue) plate_area plate_width * plate_height batches [] # 存储所有批次每个批次是一个零件列表 for item in all_items: item_area item[width] * item[height] placed False # 3. 尝试放入现有批次 for batch in batches: # 计算当前批次已占用面积简单面积和是宽松估计 used_area sum(it[width] * it[height] for it in batch) if used_area item_area plate_area: batch.append(item) placed True break # 4. 如果放不下创建新批次 if not placed: batches.append([item]) return batches # 示例数据 orders_data [ {order_id: 1, items: [{width: 100, height: 150, demand: 2}, {width: 80, height: 80, demand: 3}]}, {order_id: 2, items: [{width: 120, height: 90, demand: 1}, {width: 60, height: 200, demand: 2}]}, ] plate_w, plate_h 1000, 1000 batches first_fit_decreasing_grouping(orders_data, plate_w, plate_h) print(f组批数量{len(batches)}) for i, batch in enumerate(batches): total_area sum(it[width] * it[height] for it in batch) print(f 批次 {i1}: 零件数 {len(batch)}, 预估总面积 {total_area})实操心得在实际竞赛中简单的面积FFD往往只是一个起点。你需要设计更精细的“价值”函数来评估一个零件放入某个批次的好坏。例如可以定义一个批次的“轮廓”或“拥挤度”或者用快速排样算法如最低水平线算法对候选批次进行快速可行性校验从而做出更智能的组批决策。这往往是拉开算法差距的关键。3.2 第二阶段排样算法二维矩形件摆放给定一批零件和一块板目标是在板上放置所有零件或尽可能多且不重叠、不出界。这里介绍几种竞赛中常用的启发式算法。1. 最低水平线算法这是最经典、最易实现的排样算法之一尤其适合“一刀切”的切割方式Guillotine Cutting。核心思想维护一个“轮廓线”它由一系列不断升高的水平线段组成。每次放置新零件时都将其放在当前轮廓线最低且最左的可行位置。步骤 a. 初始化轮廓线为板材底部的一条从x0到xW的线段高度为0。 b. 将零件按某种规则排序如宽度递减、高度递减、面积递减等。 c. 遍历零件在当前轮廓线上寻找最低点。从该点向右扫描确保有足够的连续宽度放置零件宽度并且放置后零件顶部不超出板高。 d. 放置零件更新轮廓线。新轮廓线在零件顶部产生一条新的水平线段。 e. 重复直到所有零件放置完毕或无法放置。优点实现简单速度快能产生近似矩形的切割排样适合实际生产。缺点是贪心算法可能留下“塔状”空隙利用率非最优。Python代码示例最低水平线算法核心class Plate: def __init__(self, width, height): self.width width self.height height self.items [] # 存放已放置的零件信息 (x, y, w, h) # 轮廓线用一组(x_start, x_end, y)表示水平线段 self.contour [(0, width, 0)] def find_best_position(self, item_width, item_height): 寻找最低最左的可放置位置 best_x, best_y None, float(inf) # 遍历轮廓线的每一段 for i in range(len(self.contour)): x_start, x_end, y self.contour[i] # 候选x从当前线段左端开始 x_candidate x_start while x_candidate item_width x_end: # 检查从x_candidate向右的item_width宽度内轮廓线高度是否一致且足够低 max_y_in_range y # 需要检查候选矩形区域底边所覆盖的所有轮廓线段 for seg in self.contour: seg_start, seg_end, seg_y seg # 如果该轮廓线段与候选矩形的底边有重叠 if not (seg_end x_candidate or seg_start x_candidate item_width): max_y_in_range max(max_y_in_range, seg_y) # 检查放置后顶部是否超出板高 if max_y_in_range item_height self.height: if max_y_in_range best_y or (max_y_in_range best_y and x_candidate best_x): best_x, best_y x_candidate, max_y_in_range x_candidate 1 # 可以优化步长 # 简化只在线段起点尝试更高效的实现需要扫描线算法 if best_x is not None: return best_x, best_y return None, None # 无处可放 def place_item(self, item, x, y): 放置零件并更新轮廓线 self.items.append({x: x, y: y, width: item[width], height: item[height]}) # 更新轮廓线是一个复杂操作需要合并和分割线段 # 此处为简化示意实际需要实现完整的轮廓线更新逻辑 new_contour [] item_top y item[height] item_left x item_right x item[width] # ... (省略复杂的轮廓线更新代码通常需要遍历现有轮廓处理相交、覆盖等情况) # 简化假设在最低点放置后该段轮廓线被提升到零件顶部 # 实际应用建议参考成熟的实现库或论文。 return True def lowest_horizontal_line_packing(items, plate_width, plate_height): 使用最低水平线算法进行排样 plate Plate(plate_width, plate_height) # 对零件排序通常按宽度或高度递减 sorted_items sorted(items, keylambda it: it[width], reverseTrue) for item in sorted_items: x, y plate.find_best_position(item[width], item[height]) if x is not None: plate.place_item(item, x, y) else: # 无法放置该零件处理方式取决于问题要求如允许跳过 print(f警告零件({item[width]}x{item[height]})无法放置) # 可以break或者记录未放置零件 return plate.items, plate.contour2. 最大剩余矩形算法这是BLBottom-Left算法的变种维护一个“剩余矩形”列表而不是轮廓线。核心思想将板材的未占用空间表示为一系列不重叠的矩形。每次放置零件时选择能容纳该零件且其放置后能使“浪费”最小的剩余矩形例如选择宽度匹配度最高的矩形。优点比最低水平线更灵活能更好地利用空间。缺点实现更复杂剩余矩形的合并与更新逻辑繁琐。3. 基于搜索的元启发式算法当追求更高利用率时需要超越贪心策略。遗传算法将一种排版方案编码为“染色体”如零件放置顺序和旋转角度的序列通过选择、交叉、变异等操作迭代进化种群寻找更优解。模拟退火从一个随机解开始以一定概率接受“更差”的邻域解从而跳出局部最优。邻域操作可以是交换两个零件的位置、旋转一个零件等。禁忌搜索通过记录近期操作禁忌表来避免循环搜索系统地探索解空间。避坑指南在竞赛中实现一个完整的元启发式算法时间成本很高。一个折中策略是用简单启发式如最低水平线作为构造解的方法用元启发式来优化零件放入的顺序和旋转策略。例如遗传算法的染色体可以就是零件的排列顺序适应度函数是使用最低水平线算法按此顺序排版后的板材利用率。这样既利用了元启发式的全局搜索能力又避免了直接对二维位置进行编码和操作的复杂性。4. 代码框架与实战技巧结合以上分析一个完整的解题代码框架可能如下import numpy as np from typing import List, Dict, Tuple import random # 数据加载与预处理 def load_data(file_path): # 读取订单、零件尺寸、需求量等 # 返回结构化的orders列表 pass # 第一阶段组批 def grouping_phase(orders, plate_area, strategyffd): 组批阶段 :param strategy: ffd, bfd, custom batches [] if strategy ffd: batches first_fit_decreasing_grouping(orders, plate_area) elif strategy bfd: # 实现最佳适应递减法 pass else: # 自定义组批策略可能结合快速排样校验 batches advanced_grouping_with_packing_check(orders, plate_area) return batches def advanced_grouping_with_packing_check(orders, plate_width, plate_height): 结合快速排样预估的组批算法 # 1. 展开所有零件 all_items [] item_to_order [] # 记录零件所属订单用于后续约束如交货期 for order in orders: for item in order[items]: for _ in range(item[demand]): all_items.append(item.copy()) item_to_order.append(order[id]) # 2. 排序策略可以更复杂例如按最长边排序 all_items_sorted sorted(all_items, keylambda x: max(x[width], x[height]), reverseTrue) batches [] batch_items [] batch_order_set set() for idx, item in enumerate(all_items_sorted): # 3. 尝试将零件加入现有批次 best_batch_idx -1 best_evaluation float(inf) # 评估值越小越好 for b_idx, batch in enumerate(batches): # 检查业务约束例如同一订单零件尽量集中这里简化处理 # 快速评估将当前批次零件新零件用最低水平线快速排样计算预估利用率 temp_batch batch [item] # 使用一个非常简化的排样评估器例如只计算面积和或运行一次快速但粗糙的排样 estimated_utilization evaluate_packing_quick(temp_batch, plate_width, plate_height) # 如果利用率可接受例如85%且评估值好则选择 if estimated_utilization 0.85: # 阈值可调 # 评估值可以是 (1 - estimated_utilization)选择利用率最高的批次 eval_score 1 - estimated_utilization if eval_score best_evaluation: best_evaluation eval_score best_batch_idx b_idx if best_batch_idx ! -1: batches[best_batch_idx].append(item) else: # 创建新批次 batches.append([item]) return batches def evaluate_packing_quick(items, plate_width, plate_height): 快速评估一批零件在给定板上的排版利用率近似 # 方法1简单面积和除以板面积非常宽松可能高估 total_item_area sum(it[width] * it[height] for it in items) plate_area plate_width * plate_height if total_item_area plate_area: return 0.0 # 面积和都超了肯定不行 # 方法2运行一次简化的、有高度限制的最低水平线算法获取实际利用率 # 这里调用一个设置最大运行步骤或简化逻辑的packing函数 placed_items, final_height simplified_lowest_line_packing(items, plate_width, plate_height, max_time0.01) if not placed_items: return 0.0 used_area sum(it[width] * it[height] for it in placed_items) return used_area / plate_area # 第二阶段排样 def packing_phase(batch, plate_width, plate_height, algorithmlowest-line): 对单个批次进行排样 :return: placement_result: 每个零件的坐标列表以及板材利用率 if algorithm lowest-line: placements, contour lowest_horizontal_line_packing(batch, plate_width, plate_height) elif algorithm max-rect: placements max_rectangle_packing(batch, plate_width, plate_height) else: # 元启发式优化排样顺序 placements metaheuristic_packing(batch, plate_width, plate_height) # 计算利用率 used_area sum(it[width] * it[height] for it in placements) plate_area plate_width * plate_height utilization used_area / plate_area if plate_area 0 else 0 return placements, utilization def metaheuristic_packing(items, plate_width, plate_height): 使用遗传算法优化排样顺序底层用最低水平线解码 # 编码零件的排列顺序列表索引 # 解码函数给定顺序运行 lowest_horizontal_line_packing返回利用率 # 适应度函数板材利用率越高越好 # 遗传操作顺序交叉、交换变异等 # 返回最优顺序对应的排版结果 best_order genetic_algorithm_for_order(items, plate_width, plate_height) # 用最优顺序进行最终排版 sorted_items [items[i] for i in best_order] final_placements, _ lowest_horizontal_line_packing(sorted_items, plate_width, plate_height) return final_placements # 主流程与迭代优化 def solve(orders_data, plate_width, plate_height): 主求解函数 # 1. 初始组批 print(阶段1: 初始组批...) batches grouping_phase(orders_data, plate_width*plate_height, strategyadvanced) total_plates_used len(batches) total_utilization 0.0 print(阶段2: 逐批排样与优化...) all_placements [] for i, batch in enumerate(batches): print(f 处理批次 {i1}/{len(batches)}, 包含零件数: {len(batch)}) # 2. 对每批进行排样 placements, util packing_phase(batch, plate_width, plate_height, algorithmmetaheuristic) all_placements.append(placements) total_utilization util print(f 该板材利用率: {util:.2%}) avg_utilization total_utilization / len(batches) if batches else 0 print(f\n总结: 共使用板材 {total_plates_used} 张平均利用率 {avg_utilization:.2%}) # 3. (可选) 迭代优化根据排样结果反馈调整组批 # 例如如果某批次利用率极低可以尝试将其拆散合并到其他批次 improved True iteration 0 while improved and iteration 5: # 限制迭代次数 improved False # 找出利用率最低的批次 # 尝试将其中的零件移动到其他批次重新评估 # 如果整体利用率提升则接受调整 # ... (具体优化逻辑) iteration 1 return all_placements, total_plates_used, avg_utilization # 结果输出与可视化 def output_results(all_placements, output_filesolution.json): 将排版结果输出为指定格式如JSON便于验证和可视化 result { plate_width: plate_width, plate_height: plate_height, plates: [] } for idx, placements in enumerate(all_placements): plate_info { plate_id: idx1, items: [] } for item in placements: plate_info[items].append({ x: item[x], y: item[y], width: item[width], height: item[height] # 还可以添加零件ID等信息 }) result[plates].append(plate_info) import json with open(output_file, w) as f: json.dump(result, f, indent2) print(f结果已保存至 {output_file}) def visualize_packing(placements, plate_width, plate_height, plate_id1): 使用matplotlib可视化单张板材的排版结果 try: import matplotlib.pyplot as plt import matplotlib.patches as patches fig, ax plt.subplots(1, figsize(10, 10)) ax.set_xlim(0, plate_width) ax.set_ylim(0, plate_height) ax.set_aspect(equal) ax.set_title(fPlate {plate_id} Packing Layout) # 绘制板材边框 border patches.Rectangle((0,0), plate_width, plate_height, linewidth2, edgecolorblack, facecolornone) ax.add_patch(border) # 绘制每个零件 colors plt.cm.tab20(np.linspace(0, 1, len(placements))) for idx, item in enumerate(placements): rect patches.Rectangle( (item[x], item[y]), item[width], item[height], linewidth1, edgecolorblack, facecolorcolors[idx], alpha0.7 ) ax.add_patch(rect) # 可选在零件中心添加编号 ax.text(item[x]item[width]/2, item[y]item[height]/2, str(idx1), hacenter, vacenter, fontsize8) plt.grid(True, linestyle--, alpha0.5) plt.xlabel(Width) plt.ylabel(Height) plt.show() except ImportError: print(可视化需要matplotlib库请安装 pip install matplotlib) # 主程序入口 if __name__ __main__: # 1. 加载数据假设数据已处理成orders_data格式 orders_data load_data(orders.json) plate_w, plate_h 1000, 1000 # 根据题目设定 # 2. 求解 final_placements, plates_used, avg_util solve(orders_data, plate_w, plate_h) # 3. 输出和可视化 output_results(final_placements) # 可视化第一张板 if final_placements: visualize_packing(final_placements[0], plate_w, plate_h)关键技巧与注意事项数据预处理至关重要仔细阅读题目数据格式。注意零件是否允许旋转90度。如果允许那么在排样时对于一个零件你可以尝试两种方向宽x高 和 高x宽选择更合适的一种。这能显著提升利用率。算法选择与权衡时间有限不要追求理论上最完美的算法。“快速构造可行解 元启发式优化”是竞赛中的黄金策略。先用FFD最低水平线跑出一个基准解确保有答案。再用遗传算法优化零件顺序甚至尝试多种组批策略。评估函数的设计在组批和排样的迭代优化中如何评估一个方案“好”或“坏”最简单的指标是板材利用率已使用面积/总面积。但也可以考虑其他因素如切割路径长度如果题目有要求、板材使用的张数等。明确你的优化目标。编程实现效率排样算法的核心操作如查找最低点、更新轮廓线会被调用成千上万次。使用高效的数据结构如优先队列heapq来维护轮廓线的最低点可以大幅提升速度。避免在循环中进行复杂的列表拷贝。随机性与随机种子使用遗传算法、模拟退火等随机算法时固定随机种子如random.seed(42)有助于结果复现和调试。可视化调试一定要实现排版结果的可视化如上文的visualize_packing函数。肉眼观察能快速发现算法缺陷比如是否产生了许多细长的空隙零件排列是否紧凑等。并行计算如果问题规模很大可以考虑对不同的批次进行并行排样计算以节省时间。5. 从解题到竞赛策略与时间管理面对72小时的数模竞赛除了技术策略同样重要。第一天理解与建模。彻底吃透题目将实际问题转化为清晰的数学问题。确定是两阶段解耦还是集成建模。完成数据的读取和基本预处理。产出问题重述、模型假设、符号说明、模型框架。第二天算法实现与调试。根据模型框架实现核心算法模块组批、排样。先实现基础版本如FFD最低水平线确保能跑通并输出结果。然后逐步添加高级功能如零件旋转、遗传算法优化。产出可运行的代码、初步结果、模型求解部分论文草稿。第三天优化、分析与论文撰写。对初步结果进行分析看哪些批次利用率低尝试手动或通过算法调整优化。进行灵敏度分析如改变板材尺寸、订单数量。同时必须留足时间撰写论文。产出最终结果、优化过程记录、完整的竞赛论文。论文写作要点模型部分清晰阐述你的两阶段模型包括组批的数学模型如装箱模型和排样的算法描述如最低水平线算法的步骤、遗传算法的编码解码方式。算法部分用流程图或伪代码说明整体求解流程。解释清楚关键步骤如“如何选择放置位置”、“如何更新轮廓线”、“遗传算法的交叉变异操作”。结果分析展示最终排版方案用可视化图表给出板材使用数、平均利用率等关键指标。与简单策略如不分批直接排进行对比突出你算法的优越性。分析算法的复杂度、优缺点。灵敏度分析讨论如果订单数据波动如零件尺寸变化、数量增加你的算法表现会如何。这能体现模型的鲁棒性。最后记住这类优化问题通常没有唯一的标准答案。评委看重的是你建模的合理性、算法的创新性、实现的完整性以及论文表述的清晰度。一个虽然简单但运行稳定、结果合理、论述清晰的方案远比一个复杂但漏洞百出、无法稳定运行的“高级”方案得分更高。祝你建模顺利