1. 项目概述从“方形件组批优化”到工业排样的实战拆解最近在整理过往的竞赛资料翻到了2022年研究生数学建模竞赛B题“方形件组批优化问题”的解题笔记。这个题目当时在圈内讨论度很高因为它完美地戳中了制造业尤其是板材加工、服装裁剪、玻璃切割等离散制造行业的一个核心痛点——如何把一堆大小不一的矩形订单方形件高效、经济地组合到固定尺寸的原材料板如大张的钢板、布料、玻璃板上进行切割以最小化原材料的浪费。这听起来是个简单的“拼图”问题但在工业规模下它瞬间变成一个极其复杂的组合优化难题。题目要求我们不仅要考虑单张板材上如何摆放排样还要考虑如何将众多订单分成若干批次组批每个批次用一张原材料板来生产最终目标是使使用的板材总面积最小或者说材料利用率最高。这本质上是一个二维排样问题与一维装箱问题的混合体再叠加了生产排序的考量对建模能力和算法设计都是不小的挑战。今天我就结合当年的解题思路和后续的工程实践把这个问题的内核、常见的建模方法、实用的求解策略以及代码实现中的那些“坑”系统地梳理一遍。无论你是正在备战数模竞赛的学生还是对运筹优化、工业智能排产感兴趣的工程师相信这篇近万字的“脱水干货”都能给你带来实实在在的启发。2. 问题本质与数学模型构建2.1 核心问题拆解为什么它这么难方形件组批优化问题之所以经典且困难在于它同时包含了三个层次的决策且相互耦合组批决策决定哪些方形件被分配到同一张原材料板上进行生产。这类似于一维装箱问题但“箱”的容量是二维的板材的长和宽且“物品”方形件放入“箱”后还需要具体的二维位置。排样决策对于每一批即每一张板材需要确定其中每个方形件的具体放置位置左下角坐标x, y和旋转角度0度或90度。必须保证所有方形件互不重叠且完全位于板材边界内。优化目标最小化所有使用的板材总面积。由于板材规格固定这等价于最小化使用的板材张数并尽可能提高每张板材的利用率。这三个决策环环相扣。组批的好坏直接影响排样的难度和最终利用率而如果不考虑排样可行性单纯按面积组批很可能导致一批件根本无法排入一张板内。这种耦合性使得问题无法被简单地分解。从计算复杂性上看即使不考虑组批只考虑单张板上给定一组方形件的排样问题二维矩形排样问题也属于NP-hard问题。加上组批搜索空间呈指数级增长。对于竞赛规模的数据通常几十到几百个方形件想求出严格的数学最优解几乎不可能我们必须依赖启发式或元启发式算法来寻找高质量的可行解。2.2 数学建模的两种主流范式针对这类问题学术界和工业界主要有两种建模思路直接建模法和两阶段法。2.2.1 直接建模法混合整数线性规划这是最“正统”的运筹学方法试图用一个完整的MILP模型来描述所有约束。其核心思想是预先定义可能的位置通过离散化坐标或使用位置点并为每个方形件在每个板材的每个可能位置定义一个0-1决策变量。假设有N个方形件M张板材M可以是一个足够大的上界如N。定义决策变量 ( x_{i,k,p,q,r} )如果方形件i被放置在板材k上位置为(p,q)旋转状态为r0或1则取1否则取0。约束包括每个方形件必须被分配且只被分配一次。每张板材上任意两个方形件不能重叠这会产生大量的非线性约束通常需要线性化技巧如引入相对位置辅助变量。方形件必须在板材边界内。目标最小化使用的板材数量即至少放置了一个方形件的板材k的求和。注意这种模型的变量和约束数量会随着问题规模爆炸式增长。即使对于中等规模问题如50个件也可能产生数百万个变量和约束求解器如Gurobi, CPLEX在有限时间内通常只能得到下界或很差的可行解。因此在竞赛中除非问题规模非常小否则直接求解完整MILP通常不是首选但它可以为其他算法提供理论下界。2.2.2 两阶段法启发式策略的胜利这是实践中更常用、也更灵活的方法将复杂的原问题分解为两个相对独立的子问题并循环迭代改进。第一阶段组批Batching。目标是将所有方形件分组使得每组方形件的总面积不超过单张板材面积且尽可能接近提高利用率。同时要隐含地考虑后续排样的可行性例如组内不应同时存在一个非常长而窄的件和一个非常宽而短的件这会给排样带来困难。常用的组批策略有基于规则的启发式如首次适应递减法FFD、最佳适应递减法BFD。先将方形件按面积或最长边排序然后依次尝试放入当前已打开的“批次”虚拟板材中若放入后总面积不超限则放入否则开新批次。这种方法快但质量一般。聚类算法将方形件视为二维物体用长、宽作为特征使用K-means等算法进行聚类使得同一簇内的方形件形状较为相似便于排样。数学模型求解可以建立一个简化的、只考虑面积约束的装箱问题模型来求组批方案忽略具体的二维位置约束。第二阶段排样Packing/Nesting。对第一阶段产生的每一个批次独立求解一个二维矩形排样问题目标是在固定尺寸的板材上放置该批次所有方形件允许旋转。如果某个批次无法排下则需要反馈给第一阶段调整组批方案。排样算法这是核心中的核心。常见算法包括左下角放置算法Bottom-Left, BL将方形件依次放置到当前板材中尽可能低、然后尽可能左的位置。简单快速但效果不稳定。最低水平线算法Guillotine Cutting模拟一刀切适合可 Guillotine 切割的场景。通过维护一组不断上升的“水平线”来寻找放置位置。最大矩形算法Maximal Rectangles维护板材上所有可用的最大空白矩形。放置方形件时选择能容纳它的一个合适矩形如最短边匹配、面积匹配等策略。这是目前效果较好的启发式算法之一。基于序列的启发式如模拟退火、遗传算法、禁忌搜索等。这些算法不直接操作排样布局而是操作一个方形件的放置顺序和旋转状态的编码然后用一个快速的位置解码器如BLF算法将序列转化为具体布局并评估其利用率。通过迭代改进序列来优化布局。两阶段法的优势在于模块化可以分别对组批和排样算法进行研究和优化。其挑战在于如何让两个阶段有效协同避免“短视”的组批导致排样失败或利用率低下。通常需要引入迭代机制先用快速方法得到一个初始组批和排样然后通过交换批次间的方形件、拆分过满批次、合并过空批次等局部搜索操作来改进整体方案。3. 核心算法实现与代码解析这里我将重点介绍一个在竞赛和工程中平衡了效果与复杂度的经典两阶段框架并使用Python进行示意性实现。我们假设板材尺寸为W * H有N个方形件每个件有宽度w_i和高度h_i允许90度旋转即件i可以以(w_i, h_i)或(h_i, w_i)的尺寸放入。3.1 第一阶段改进的基于面积与形状的组批算法单纯的按面积FFD算法效果有限。我们引入一个“形状兼容性”的概念。定义一个件的长宽比ratio max(w, h) / min(w, h)。长宽比大的件如101的条状和长宽比小的件如33的方形放在一起很难排样。因此我们在组批时除了面积约束还应尽量将形状相似的件分在一起。def batch_items_by_shape_and_area(items, plate_width, plate_height, batch_area_threshold0.95): 基于形状聚类和面积约束的组批算法。 items: list of tuples [(w1, h1), (w2, h2), ...] plate_area: 板材面积 batch_area_threshold: 批次目标面积利用率阈值用于控制批次不要过满给排样留余地。 plate_area plate_width * plate_height target_batch_area plate_area * batch_area_threshold # 1. 计算每个件的特征面积和长宽比 item_features [] for w, h in items: area w * h ratio max(w, h) / min(w, h) if min(w, h) 0 else 1 item_features.append((area, ratio, (w, h))) # 2. 简单聚类按长宽比分组 sorted_by_ratio sorted(item_features, keylambda x: x[1]) batches [] current_batch [] current_batch_area 0 for area, ratio, size in sorted_by_ratio: # 尝试放入当前批次 if current_batch_area area target_batch_area: current_batch.append(size) current_batch_area area else: # 当前批次已满保存并开新批次 if current_batch: batches.append(current_batch) current_batch [size] current_batch_area area # 别忘了最后一个批次 if current_batch: batches.append(current_batch) # 3. 后处理尝试合并过小的批次 merged_batches [] for batch in batches: batch_area sum(w*h for w, h in batch) if merged_batches and (merged_batches[-1][area] batch_area) plate_area: # 合并到上一个批次 merged_batches[-1][items].extend(batch) merged_batches[-1][area] batch_area else: merged_batches.append({items: batch, area: batch_area}) # 返回批次列表每个批次是一个字典包含物品列表和总面积 return [b[items] for b in merged_batches]实操心得batch_area_threshold这个参数至关重要。不要设为1即板材面积因为排样算法几乎不可能达到100%的理论面积利用率。根据经验对于矩形排样设定在0.85到0.95之间比较合理为排样留出调整空间。如果排样阶段频繁失败应降低此阈值。3.2 第二阶段基于最大矩形算法MaxRectangles的排样这里实现一个相对完整的MaxRectangles算法。其核心是维护一个“最大空白矩形列表”。class MaxRectanglesPacker: def __init__(self, plate_width, plate_height): self.width plate_width self.height plate_height # 初始时整个板材就是一个最大矩形 self.free_rectangles [(0, 0, plate_width, plate_height)] # (x, y, w, h) self.placed_items [] # (x, y, w, h, item_id) def find_placement(self, item_width, item_height, heuristicbest_area_fit): 为给定尺寸的物品寻找最佳放置位置和旋转。 返回 (x, y, rotated, rect_index) best_score float(inf) best_placement None # (x, y, rotated, rect_index) best_rect_index -1 # 尝试两种旋转方向 for rotated, (w, h) in enumerate([(item_width, item_height), (item_height, item_width)]): if w self.width or h self.height: continue # 单件尺寸超过板材这种旋转不可行 for idx, rect in enumerate(self.free_rectangles): rx, ry, rw, rh rect if w rw and h rh: # 可以放入此矩形 # 选择放置策略通常放在矩形的左下角 placement_x, placement_y rx, ry # 根据启发式规则计算得分 if heuristic best_area_fit: # 最小化剩余面积 score (rw * rh) - (w * h) elif heuristic best_short_side_fit: # 最小化放置后短边的剩余长度 leftover_horiz rw - w leftover_vert rh - h score min(leftover_horiz, leftover_vert) else: # bottom_left # 优先选择y小的y相同选x小的 score ry * self.width rx if score best_score: best_score score best_placement (placement_x, placement_y, rotated, idx) return best_placement def place_item(self, item_width, item_height, item_idNone, heuristicbest_area_fit): placement self.find_placement(item_width, item_height, heuristic) if placement is None: return False # 无法放置 x, y, rotated, rect_index placement w_placed item_height if rotated else item_width h_placed item_width if rotated else item_height # 放置物品 self.placed_items.append((x, y, w_placed, h_placed, item_id)) # 从空闲矩形列表中移除被使用的矩形 used_rect self.free_rectangles.pop(rect_index) # 计算切割剩余区域产生的新最大矩形关键步骤 self._split_free_rectangles(used_rect, (x, y, w_placed, h_placed)) # 合并重叠或可合并的矩形可选用于优化 self._merge_free_rectangles() return True def _split_free_rectangles(self, used_rect, placed_rect): 根据已放置的矩形切割原空闲矩形生成新的最大矩形。 这是MaxRectangles算法的核心常用“分割法” 将原矩形按放置矩形的右边界和上边界分割成可能的新矩形。 rx, ry, rw, rh used_rect px, py, pw, ph placed_rect # 生成右侧矩形 if pw rw: self.free_rectangles.append((rx pw, ry, rw - pw, rh)) # 生成上方矩形 if ph rh: self.free_rectangles.append((rx, ry ph, rw, rh - ph)) # 生成左上角矩形当放置不在左下角时 # 更严谨的实现需要考虑所有分割可能性但上述是常见简化。 def _merge_free_rectangles(self): 合并相邻或包含的矩形避免列表膨胀。 # 实现略涉及矩形包含和相邻判断逻辑较繁琐但能提升性能。 pass def pack_batch(self, batch_items, heuristicbest_area_fit): 对一个批次的所有物品进行排样。 batch_items: list of (w, h) 返回排样结果和利用率。 # 物品排序策略对结果影响巨大常见策略按面积降序、按最长边降序。 sorted_items sorted(batch_items, keylambda it: it[0]*it[1], reverseTrue) for idx, (w, h) in enumerate(sorted_items): success self.place_item(w, h, idx, heuristic) if not success: # 排样失败这个批次需要调整或拆分 return False, self.placed_items # 计算利用率 used_area sum(w*h for _, _, w, h, _ in self.placed_items) utilization used_area / (self.width * self.height) return True, self.placed_items, utilization注意事项物品排序在调用pack_batch前对物品排序至关重要。“先大后小”原则几乎总是有效的因为大件决定了布局的骨架小件可以填补缝隙。按面积或最长边降序排列是标准操作。启发式规则选择best_area_fit最佳面积适应通常能获得更高的板材利用率因为它倾向于将物品放入大小最匹配的空白矩形中。best_short_side_fit最佳短边适应有时能产生更规整的剩余空间。可以多种启发式都尝试选择最好的结果。旋转策略上述代码允许每个物品自由旋转90度。在某些实际场景如有纹理的布料、有轧制方向的钢材可能不允许旋转需要在find_placement中关闭旋转尝试。排样失败处理如果pack_batch返回False意味着当前批次无法排入一张板。此时需要反馈到组批阶段可以将这个“问题批次”拆分成两个更小的批次或者从中移出一个或几个物品到其他批次。3.3 迭代优化框架让两个阶段“对话”单纯的顺序两阶段法可能陷入局部最优。我们需要一个外层循环来迭代改进。def iterative_packing_optimization(all_items, plate_w, plate_h, max_iterations100): 迭代优化框架。 1. 初始组批 2. 对每个批次排样 3. 如果所有批次成功计算总板材数或总面积 4. 尝试一些扰动操作如交换批次间的物品、拆分批次、合并批次 5. 如果新方案更好则接受 6. 重复直到迭代次数用尽或收敛 # 初始组批 batches batch_items_by_shape_and_area(all_items, plate_w, plate_h) best_solution None best_plate_count float(inf) for iteration in range(max_iterations): total_plates_used 0 all_placements [] failed False # 对每个批次尝试排样 for batch in batches: packer MaxRectanglesPacker(plate_w, plate_h) success, placements, util packer.pack_batch(batch) if not success: failed True break # 当前方案不可行 total_plates_used 1 all_placements.append(placements) if not failed: # 计算目标函数这里就是板材数量 if total_plates_used best_plate_count: best_plate_count total_plates_used best_solution (batches.copy(), all_placements.copy()) print(fIteration {iteration}: Found better solution with {total_plates_used} plates.) # 基于当前最佳方案进行扰动生成新批次 if best_solution: current_batches, _ best_solution # 扰动操作示例随机交换两个批次中的两个物品 new_batches perturb_batches(current_batches, plate_w*plate_h) batches new_batches else: # 如果还没有可行解则放松组批阈值重新组批 batches batch_items_by_shape_and_area(all_items, plate_w, plate_h, threshold0.8) return best_solution def perturb_batches(batches, plate_area): 简单的扰动随机选择两个批次交换一个物品如果面积允许。 import random new_batches [b.copy() for b in batches] if len(new_batches) 2: return new_batches i, j random.sample(range(len(new_batches)), 2) if not new_batches[i] or not new_batches[j]: return new_batches item_i random.choice(new_batches[i]) item_j random.choice(new_batches[j]) # 检查交换后面积是否大致合理简单检查 area_i sum(w*h for w,h in new_batches[i]) area_j sum(w*h for w,h in new_batches[j]) new_area_i area_i - item_i[0]*item_i[1] item_j[0]*item_j[1] new_area_j area_j - item_j[0]*item_j[1] item_i[0]*item_i[1] if new_area_i plate_area * 1.05 and new_area_j plate_area * 1.05: # 允许小幅超限 new_batches[i].remove(item_i) new_batches[j].remove(item_j) new_batches[i].append(item_j) new_batches[j].append(item_i) return new_batches这个框架是一个简单的模拟退火或局部搜索的雏形。更高级的实现会引入模拟退火的接受准则以一定概率接受更差的解以避免陷入局部最优。4. 关键难点、调试技巧与性能优化4.1 你一定会遇到的坑与解决方案排样算法“死锁”即使批次总面积远小于板材面积排样算法也可能失败。这通常是因为物品顺序和放置启发式导致产生了大量无法利用的“碎片空间”。解决方案尝试不同的物品排序策略面积降序、周长降序、随机排序。对于MaxRectangles除了best_area_fit也试试best_short_side_fit或bottom_left。一种强力方法是多次随机排序并取最佳结果。组批与排样的矛盾组批追求高面积填充率排样需要留有余地。组批时形状差异大的件放在一起排样困难。解决方案在组批的评估函数中不仅考虑总面积还加入一个形状差异惩罚项。例如计算批次内所有件长宽比的方差方差越大惩罚越高。或者在迭代优化中将排样失败作为强有力的反馈直接拆分失败批次或调整组批。算法运行时间过长迭代优化、多次随机尝试可能导致计算时间爆炸。解决方案设定时间/迭代上限竞赛或实际应用都有时间限制。使用更快的排样解码器BLF算法通常比完整的MaxRectangles快。在迭代优化的内循环中可以用BLF快速评估最后再用MaxRectangles精细排样。并行计算不同批次间的排样是独立的可以并行处理。迭代中的多次随机尝试也可以并行。结果的可视化与验证你怎么知道算法排出来的方案是对的重叠了吗出界了吗解决方案必须实现可视化。用Matplotlib把每张板材的排样结果画出来用不同颜色和边框区分物品。这是调试最直观的工具。同时编写校验函数检查所有物品是否无重叠、是否在边界内。import matplotlib.pyplot as plt import matplotlib.patches as patches def visualize_packing(plate_width, plate_height, placed_items, title): fig, ax plt.subplots(1, figsize(10, 8)) ax.set_xlim(0, plate_width) ax.set_ylim(0, plate_height) ax.set_aspect(equal) ax.invert_yaxis() # 通常左下角为原点 ax.set_title(title) for idx, (x, y, w, h, item_id) in enumerate(placed_items): rect patches.Rectangle((x, y), w, h, linewidth1, edgecolorblack, facecolorplt.cm.tab20(idx%20), alpha0.6) ax.add_patch(rect) # 可选在矩形中心添加编号 ax.text(x w/2, y h/2, str(item_id), hacenter, vacenter, fontsize8) plt.grid(True, linestyle--, alpha0.5) plt.show()4.2 高级策略与竞赛提分点如果想在数模竞赛中拿高分或在实际系统中追求极致效果可以考虑以下方向混合整数规划求解器作为“辅助”虽然不能直接求解原问题但可以用MILP求解简化版问题。例如用求解器求一个线性规划松弛的下界这个下界所需板材数量的理论最小值可以用来评估你启发式解的质量Gap。在论文中给出这个Gap是理论深度的体现。元启发式算法的深度应用遗传算法GA将组批方案编码为染色体每个基因代表一个件所属的批次号。适应度函数板材总数 排样失败惩罚。交叉、变异操作在批次间交换物品。模拟退火SA当前状态是一个组批方案。邻域操作可以是随机移动一个件到另一个批次交换两个批次中的两个件拆分一个批次合并两个批次。以概率接受恶化解。禁忌搜索TS记录近期移动如“将件A从批次X移到批次Y”禁止短期内反向移动以避免循环。考虑实际工艺约束竞赛题往往做了简化。实际工业中还需考虑切割工艺是否必须是“一刀切”Guillotine Cut这会影响排样算法的设计。刀缝损耗切割刀具有厚度排样时物品间需留出缝隙。原材料缺陷板材上可能有固定区域不能使用。生产顺序先切割的件不能影响后切割的件的支撑。论文写作中的“亮点”包装将你的算法框架描述清楚突出“两阶段迭代优化”、“融合多种启发式规则”、“采用模拟退火跳出局部最优”等设计思想。用图表展示算法收敛过程、不同参数对比结果、以及与简单基准算法如单纯FFDBL的对比突出你方案的优越性。详细记录测试数据、利用率结果并做统计分析。5. 从竞赛到实践工程化思考竞赛环境是理想的而实际项目要复杂得多。如果你要将这套东西用于生产环境以下几点需要重点考虑数据接口与预处理实际订单数据可能来自ERP系统格式杂乱。需要健壮的数据清洗、尺寸校验长宽是否为正数、是否超过板材尺寸、订单合并相同尺寸件合并数量模块。算法稳定性与速度的权衡工厂排产可能要求几分钟甚至秒级出结果。你需要为算法设置严格的时间限制。可能需要在迭代初期使用快速低精度算法后期对重点批次进行精细优化。缓存机制也很重要对于重复出现的订单组合直接返回历史排样结果。人机交互与可解释性排样结果最终要交给车间工人执行。可视化界面必须清晰能标注切割路径、顺序。算法应允许人工干预比如老师傅凭经验知道某个件必须靠边放系统应能接受这种固定约束并重新计算。与下游系统的集成排样结果需要生成数控切割机CNC可识别的G代码或DXF文件。这涉及到将抽象的矩形布局转化为具体的切割路径并优化切割头移动顺序旅行商问题以最小化空程时间。回过头看2022年这道赛题它就像一个微缩的工业智能排产系统原型。解决它不仅需要数学建模和编程能力更需要一种系统性的工程思维——如何分解问题、如何设计算法框架、如何平衡效果与效率、如何验证和调试。我个人的体会是这类优化问题的魅力就在于你永远可以找到改进点一个新的启发式规则、一个更巧妙的邻域操作、一次更智能的并行化都可能将利用率提升零点几个百分点。而这零点几个百分点在动辄数千平米板材用量的工厂里就意味着每月节省数万甚至数十万元的成本。这才是数学建模和算法优化真正的价值所在。