1. 项目概述从“方形件组批”到现实生产优化如果你在制造业特别是板材加工、服装裁剪、玻璃切割或者印刷包装行业待过听到“方形件组批优化”这个词大概率会会心一笑。这几乎是每个生产计划员或工艺工程师每天都要面对的“甜蜜的烦恼”。手头有一堆订单每个订单要求生产不同尺寸、不同数量的矩形零件方形件而你的原材料是大张的规则板材。如何把这些零散的订单科学地组合成一批批生产任务塞进固定尺寸的原材料里从而最大限度地减少边角料、节省板材、降低成本、提高效率这就是方形件组批优化问题的核心。2022年“华为杯”中国研究生数学建模竞赛的B题正是将这个经典的工业工程问题抽象成了一个极具挑战性的数学优化模型。它绝不是纸上谈兵其背后直指制造业的核心痛点——降本增效。题目通常会提供一系列不同长宽尺寸和需求数量的方形件订单以及原板材的固定尺寸。参赛者的任务就是设计算法找到一种最优的组批方案使得使用的板材总面积最少或者板材张数最少亦或是满足某种特殊约束如切割刀路最短、换刀次数最少等。为什么这个问题值得用数学建模来攻坚因为当订单数量达到几十、上百甚至上千时可能的组批组合是天文数字人脑和经验完全无法处理。靠老师傅“目测”排样材料利用率可能只有70%-80%而一个优秀的优化算法可以将利用率提升到95%甚至更高。这中间几个百分点的差距对于大规模生产来说意味着每年节省数十万乃至数百万元的原材料成本。因此这道题连接了运筹学、组合优化、智能算法和工业软件是数学赋能产业的典型范例。2. 问题核心与数学模型构建2.1 问题拆解一维与二维的耦合方形件组批优化问题通常可以分解为两个层次或者说两个耦合在一起的子问题组批问题Batching Problem决定哪些订单方形件应该被分到同一张板材上进行生产。这类似于装箱问题但比一维装箱复杂因为每个“物品”订单集合的“体积”不是固定的它取决于第二个问题——排样。排样问题Nesting Problem给定一批被分配到同一张板材上的方形件如何具体安排它们的位置使得所有件都能放入板材内并且占据的总面积最小即浪费的边角料最少。这是经典的二维矩形排样优化问题。这两个问题相互影响、相互制约。组批方案决定了排样问题的输入而排样结果即材料利用率又是评价组批方案好坏的标准。这种耦合性使得问题异常复杂无法简单地先组批后排样或者先排样后组批。2.2 数学模型抽象从业务描述到数学语言要将这个问题转化为可计算的模型我们需要定义清晰的数学符号和约束。参数定义I: 订单集合i 1, 2, ..., n。w_i,h_i: 第i个订单所需方形件的宽度和高度。d_i: 第i个订单的需求数量。W,H: 原板材的宽度和高度通常题目假设为固定值如WH3000mm。M: 一个足够大的正整数Big-M用于线性化逻辑约束。决策变量x_{ijk}: 0-1变量。表示第i个订单的第j个件j1,...,d_i是否被安排在第k张板材上。这是最直接的变量但数量庞大。y_k: 0-1变量。表示第k张板材是否被使用。(px_{ijk}, py_{ijk}): 连续变量。表示第i个订单的第j个件在第k张板材上的左下角坐标。o_{ijk}: 0-1变量。表示第i个订单的第j个件是否旋转90度放置o1表示旋转此时件尺寸变为(h_i, w_i)。约束条件需求满足约束每个订单的所有件都必须被分配到某张板材上。∑_k ∑_j x_{ijk} d_i, 对于所有i。板材边界约束每个件必须完全位于板材内部。px_{ijk} 0,py_{ijk} 0,px_{ijk} (1-o_{ijk})*w_i o_{ijk}*h_i W,py_{ijk} (1-o_{ijk})*h_i o_{ijk}*w_i H当x_{ijk}1时。件间无重叠约束同一张板材上的任意两个件不能重叠。这是建模中最关键也最复杂的部分。通常采用“分离约束” 对于任意两个不同的件(i,j)和(i,j)在同一板k上它们至少满足以下四个不等式之一件A在件B的左边px_A width_A px_B件A在件B的右边px_A px_B width_B件A在件B的下边py_A height_A py_B件A在件B的上边py_A py_B height_B这需要引入额外的0-1辅助变量来线性化“或”关系是模型规模膨胀的主要原因。板材使用约束如果一个件被分配到板k则板k必须被标记为使用。x_{ijk} y_k对于所有i, j, k。目标函数最直接也是最常见的目标是最小化使用的板材总数。Minimize ∑_k y_k或者在板材尺寸固定且足够大的情况下可以等价为最小化所有使用板材的总面积但通常板材总数目标更直观。注意这是一个经典的混合整数线性规划MILP模型框架。它的优点是精确、严谨能保证找到数学上的最优解如果求解器能在可接受时间内完成的话。但致命缺点是当订单数量稍多比如超过20个不同订单模型变量和约束的数量会呈指数级增长变得无法求解。因此这个精确模型更多是作为理论基准和理解问题本质的工具在实际竞赛和工程中我们需要寻求启发式或元启发式算法。3. 核心算法策略与选型思路面对大规模问题我们无法直接求解精确的MILP模型。竞赛中常用的策略是设计“分解-协调”的启发式算法框架将组批和排样两个子问题分开处理通过迭代或搜索来逼近最优解。3.1 主流算法框架剖析1. 基于顺序的构造式启发算法这是最直观的方法思路是“先排样后反推组批”。思路将所有订单的所有件视为一个大的零件集合。然后采用一种排样策略如最低水平线算法、最大适应度算法等像拼图一样依次将零件放入一张张板材中直到所有零件放完。流程定义零件放入顺序如按面积降序、按周长降序、按长边降序。定义板材中空闲区域的选取规则如始终选择最低的可放置点。定义零件在选定区域的放置规则如靠左靠下、选择适应度最高的位置。依次处理每个零件放入当前板材。若当前板材无法放入该零件则开启一张新板材。优点实现简单速度快能快速得到一个可行解。缺点解的质量严重依赖排序规则和放置规则通常不是最优解甚至可能远离最优。它本质上只解决了排样问题组批是排样过程的副产品缺乏全局优化视角。适用场景对求解速度要求极高对材料利用率要求不苛刻的在线实时排样或作为更高级算法的初始解生成器。2. 两阶段法先组批后排样这是更符合问题逻辑的经典框架也是竞赛中获奖论文最常用的思路之一。第一阶段组批优化。目标是将零件聚合为若干“批”使得每一批内零件的总“尺寸”尽可能匹配板材尺寸。这里的挑战在于零件的“尺寸”是二维的且排样后的实际占用面积不是简单的加法。常用的代理目标有面积利用率预估用批内零件总面积除以板材面积作为一个粗略的利用率下界。轮廓拟合尝试用一些简单规则如按高度或宽度分组预估这批零件能否紧凑排列。基于一维装箱的近似将问题简化为只考虑宽度或高度的一维装箱问题先进行分组但这会损失很多信息。第二阶段批内排样优化。对第一阶段生成的每一个批使用精确算法如MILP适用于小批或高效启发式算法如基于左下角放置的启发式、模拟退火局部搜索等进行排样计算该批实际所需的板材数量可能一张板放不下需要多张。关键与难点两个阶段之间存在“反馈”。第二阶段排样的实际结果真实利用率可能表明第一阶段的组批方案并不好。因此需要引入迭代机制根据排样结果调整组批策略例如将利用率低的批次拆散重组。3. 集成优化算法智能优化算法的应用这是当前研究的热点也是解决此类NP-hard问题的有力武器。其核心是将组批和排样作为一个整体进行搜索。遗传算法GA编码如何表示一个解是关键。一种常见编码是“顺序分割”编码。染色体由所有零件的一个排列序列组成再通过一个“分割点”列表或解码规则将这个序列切割成多个子序列即批次然后对每个子序列用构造式启发算法进行排样评估适应度如总板材数。操作交叉、变异操作在排列序列上进行。优点全局搜索能力强能有效探索解空间。缺点解码过程排样计算量大算法收敛速度慢参数调优复杂。模拟退火SA思路从一个初始组批方案开始通过“扰动”产生新方案如将某个零件从一个批移到另一个批或交换两个批中的部分零件然后对新方案进行排样评估。根据Metropolis准则决定是否接受新解。优点结构简单容易实现能逃离局部最优。缺点对初始解和降温 schedule 敏感可能需要大量迭代。禁忌搜索TS思路通过定义邻域动作如移动零件、交换零件进行局部搜索并使用禁忌表禁止近期访问过的解以避免循环。优点搜索效率高能在局部区域进行深度挖掘。缺点对邻域结构的设计要求高全局探索能力可能不如GA。在实际竞赛中混合策略往往效果最好。例如用构造式启发法生成初始解用遗传算法进行全局框架搜索在遗传算法的解码器或局部搜索中嵌入模拟退火或禁忌搜索来优化单个批次的排样。3.2 排样子问题的关键算法无论采用哪种框架批内排样都是一个必须高效解决的子问题。除了商业软件竞赛中常用以下方法最低水平线算法Bottom-Left, BL维护一个不断上升的“水平线”始终将零件放在当前最低可放置的位置并尽量向左靠。这是最基础的贪心算法速度快但效果一般。最佳适应度算法Best-Fit对于当前待放置的零件评估所有可能放置的空闲区域或角落点选择一个“适应度”最高的位置放置。适应度可以定义为放置后剩余空间的形状规整度、面积利用率等。基于搜索的排样对于一个小批次如少于10个零件可以将其建模为小规模的MILP模型调用Gurobi、CPLEX等求解器求精确解。对于稍大的批次可以采用启发式规则结合局部搜索如交换两个零件的位置、旋转某个零件来改进排样方案。4. 实战建模步骤与代码实现要点假设我们采用“两阶段法遗传算法优化”的混合策略。以下是详细的实战步骤和代码片段要点以Python为例。4.1 数据预处理与参数定义import numpy as np import random from typing import List, Tuple class Order: def __init__(self, id, width, height, demand): self.id id self.w width self.h height self.d demand # 计算面积和是否可以旋转通常方形件可以但需看题目 self.area width * height self.rotatable True class Plate: W 3000 # 板材宽度 H 3000 # 板材高度 AREA W * H # 读取数据假设数据格式为列表每个元素是 (width, height, demand) def load_orders(data): orders [] for idx, (w, h, d) in enumerate(data): orders.append(Order(idx, w, h, d)) return orders4.2 第一阶段设计遗传算法进行组批优化编码与解码设计我们采用“顺序分组”编码。染色体是一个列表包含所有“零件个体”的ID。每个订单有demand个重复的ID。解码时我们需要一个规则将长序列分割成批。def decode_chromosome(chromosome: List[int], orders: List[Order], batch_area_threshold0.95): 解码染色体生成批次。 策略顺序遍历染色体将零件加入当前批次直到预估面积超过阈值*板材面积则开启新批次。 这是一种简单的启发式解码。 batches [] # 每个batch是一个零件ID列表 current_batch [] current_batch_area 0 for part_id in chromosome: order_idx part_id # 这里简化part_id即order_id实际需映射 order orders[order_idx] part_area order.area # 如果当前批次加入此零件后预估面积过大则封存当前批次开新批次 # 注意这是面积预估非常粗略 if current_batch_area part_area batch_area_threshold * Plate.AREA and current_batch: batches.append(current_batch.copy()) current_batch [part_id] current_batch_area part_area else: current_batch.append(part_id) current_batch_area part_area if current_batch: batches.append(current_batch) return batches适应度评估这是最耗时的部分。需要对解码得到的每个批次调用排样算法计算该批次实际需要多少张板材。def evaluate_batch(batch: List[int], orders: List[Order]): 评估一个批次需要多少张板。 这里使用一个简化的最低水平线排样算法作为示例。 返回该批次消耗的板材数量。 # 将batch中的part_id转化为具体的零件尺寸列表考虑旋转 parts [] for pid in batch: order orders[pid] parts.append((order.w, order.h, order.rotatable)) plates_used 0 remaining_parts parts.copy() while remaining_parts: # 初始化一张新板 plate_width Plate.W plate_height Plate.H # 用最低水平线法排样此处为极度简化版仅示意 # 实际需要实现完整的BL算法或调用更优的排样函数 placed_parts, remaining_parts simple_bl_packing(remaining_parts, plate_width, plate_height) plates_used 1 if plates_used 100: # 防止死循环 break return plates_used def fitness_function(chromosome, orders): 计算染色体的适应度总板材数越少适应度越高 batches decode_chromosome(chromosome, orders) total_plates 0 for batch in batches: total_plates evaluate_batch(batch, orders) # 适应度可以设为 1 / (total_plates 1) 或 -total_plates return -total_plates # 我们求最小化所以用负值遗传操作def create_initial_population(orders, pop_size): 创建初始种群每个染色体是所有零件ID的随机排列 # 生成零件ID列表每个订单根据需求数量重复ID all_parts [] for order in orders: all_parts.extend([order.id] * order.d) population [] for _ in range(pop_size): ind all_parts.copy() random.shuffle(ind) population.append(ind) return population def selection(population, fitnesses, methodtournament, tournament_size3): 选择操作例如锦标赛选择 if method tournament: selected [] for _ in range(len(population)): contestants random.sample(list(zip(population, fitnesses)), tournament_size) winner max(contestants, keylambda x: x[1])[0] # 适应度越大越好 selected.append(winner) return selected def crossover(parent1, parent2, cx_rate0.8): 顺序交叉OX用于排列编码 if random.random() cx_rate: return parent1[:], parent2[:] size len(parent1) cp1, cp2 sorted(random.sample(range(size), 2)) child1 [-1] * size child2 [-1] * size # 保留父代片段 child1[cp1:cp2] parent1[cp1:cp2] child2[cp1:cp2] parent2[cp1:cp2] # 填充剩余位置 fill_child(child1, parent2, cp1, cp2) fill_child(child2, parent1, cp1, cp2) return child1, child2 def fill_child(child, parent, start, end): 辅助函数用于OX交叉的填充 size len(child) pointer end % size for gene in parent: if gene not in child[start:end]: child[pointer] gene pointer (pointer 1) % size def mutation(chromosome, mut_rate0.05): 变异操作交换两个随机位置 if random.random() mut_rate: i, j random.sample(range(len(chromosome)), 2) chromosome[i], chromosome[j] chromosome[j], chromosome[i] return chromosome4.3 第二阶段批内排样算法的实现以BL算法为例def simple_bl_packing(parts, plate_width, plate_height): 一个极度简化的最低水平线排样算法。 输入parts列表每个元素为 (w, h, rotatable) 输出(placed_parts, remaining_parts) 注意此函数仅为教学示意实际算法复杂得多需维护水平线轮廓。 placed [] remaining [] # 假设一个简单的贪心按面积从大到小排序后尝试放置 sorted_parts sorted(parts, keylambda x: x[0]*x[1], reverseTrue) current_x 0 current_y 0 max_height_in_row 0 for part in sorted_parts: w, h, rot part # 尝试旋转 if rot and h w: w, h h, w if current_x w plate_width and current_y h plate_height: # 可以放在当前位置 placed.append((current_x, current_y, w, h)) current_x w max_height_in_row max(max_height_in_row, h) else: # 换行 if current_x 0: # 当前行第一个就放不下说明板高不够 remaining.append(part) else: current_x 0 current_y max_height_in_row max_height_in_row 0 # 重试放置当前零件 if current_y h plate_height: placed.append((current_x, current_y, w, h)) current_x w max_height_in_row h else: remaining.append(part) return placed, remaining实操心得在实际编程中排样算法是性能瓶颈和效果关键。上述simple_bl_packing函数过于简陋材料利用率会很低。建议实现或引用更成熟的算法如rectpackPython库中的Packer类或者认真实现一个带“最佳适应度”选择的排样算法。在遗传算法中每次适应度评估都要调用排样因此其效率至关重要。一个技巧是可以对批次进行预处理如果批次内零件总面积远小于板材面积则直接估算为1张板避免调用复杂排样。4.4 主流程与迭代优化def main_ga(orders, pop_size50, generations100, cx_rate0.8, mut_rate0.05): 主遗传算法流程 population create_initial_population(orders, pop_size) best_individual None best_fitness float(inf) # 记录最小板材数 for gen in range(generations): # 评估适应度 fitnesses [fitness_function(ind, orders) for ind in population] # fitnesses是负的板材数 current_best_fitness max(fitnesses) # 最大适应度 current_best_plate_count -current_best_fitness # 对应的板材数 if current_best_plate_count best_fitness: best_fitness current_best_plate_count best_individual population[fitnesses.index(current_best_fitness)] print(fGeneration {gen}: Best plates {best_fitness}) # 选择 selected selection(population, fitnesses) # 交叉与变异生成新一代 new_population [] for i in range(0, pop_size, 2): parent1, parent2 selected[i], selected[i1] child1, child2 crossover(parent1, parent2, cx_rate) child1 mutation(child1, mut_rate) child2 mutation(child2, mut_rate) new_population.extend([child1, child2]) population new_population[:pop_size] # 解码最优解得到最终批次方案 final_batches decode_chromosome(best_individual, orders) return final_batches, best_fitness5. 常见问题、优化技巧与避坑指南在实际建模和编程中你会遇到一系列典型问题。以下是我从多次实战中总结的经验和避坑点。5.1 算法效率与精度平衡问题排样算法太慢导致遗传算法迭代一次需要几分钟无法在有限时间内竞赛通常72小时进行充分搜索。解决分层优化不要对所有零件都用最精细的排样算法。对于很小的零件面积小于板材的1%可以先用“填充”策略或者用简单的贪心算法处理。近似评估在遗传算法初期可以使用快速的、近似度量的排样算法如只做面积估算或使用非常简化的排样规则来筛选种群。在算法后期对少数精英个体再用精确排样算法进行精细评估。并行计算适应度评估是独立的可以并行化。使用Python的multiprocessing库或joblib将种群评估任务分配到多个CPU核心。记忆化Memoization对于完全相同的批次其排样结果是固定的。可以建立一个哈希表缓存批次用元组表示到板材数量的映射避免重复计算。5.2 解的质量陷入局部最优问题遗传算法很快收敛到一个解但感觉材料利用率还有提升空间。解决增加种群多样性提高变异率或者在选择操作中保留一部分随机个体随机选择。多种群进化运行多个子种群定期交换一些个体迁移防止早熟。混合局部搜索在得到一批较优的个体后对其施加局部搜索。例如随机交换两个批次中的几个零件或者将一个批次拆散合并到其他批次如果结果变好则接受。这相当于在遗传算法中嵌入了模拟退火或禁忌搜索的思想。改进解码规则前述解码器用的固定面积阈值可能不灵活。可以尝试动态阈值或者设计更复杂的解码器例如尝试多种分割方式并选择最好的一个。5.3 排样算法效果不佳问题自己的排样算法材料利用率始终比商业软件或已知优秀算法低很多。解决引入“空白矩形”算法不要只维护一条水平线。维护一个“空白矩形”列表记录板材上所有未被占用的最大矩形区域。放置零件时选择能容纳该零件且适应度如放置后剩余空间最小最高的空白矩形。这是效果较好的启发式算法。允许零件旋转这能显著提升利用率。在评估放置位置时同时考虑旋转和不旋转两种状态。后处理优化对排样结果进行局部调整。例如尝试交换两个零件的位置或者微调某个零件的位置看是否能腾出空间放入之前放不下的零件。使用开源库在竞赛中合理使用开源库是明智的。例如Python的rectpack库提供了多种启发式算法可以直接调用比自己从头实现更稳定高效。5.4 模型与代码的健壮性问题程序遇到特殊数据如超大零件、极多小零件时崩溃或结果荒谬。解决输入校验在读取数据后立即检查是否有零件的尺寸超过板材尺寸。如果有直接报错或给出明确提示如“零件XXX无法切割”这可能是题目中的边界条件。异常处理在排样函数中对可能出现的边界情况如零件面积和为0进行判断避免除零错误或无限循环。结果可视化务必编写一个可视化函数将最终的排样方案用Matplotlib等库画出来。一张图能立刻告诉你算法是否正常工作哪里存在明显浪费。这是调试和验证的终极武器。与简单基准对比实现一个极其简单的算法如所有零件不组批每个订单单独排样计算其板材用量。你的优化算法结果必须显著优于这个基准否则说明算法可能有问题。5.5 竞赛策略与论文写作问题算法实现了但不知道如何在论文中清晰展示并取得高分。解决分阶段论述在论文中清晰呈现“两阶段”或“混合算法”的框架图。用流程图说明算法各个模块如何协作。突出创新点不要只描述用了遗传算法。要说明你在编码如何表示组批、解码如何从染色体得到批次、适应度函数如何高效评估批次、局部搜索如何提升解质量等方面的具体设计和改进。哪怕是一个小的启发式规则只要有效果就是创新点。实验分析要充分设计对比实验。例如对比不同解码规则的效果。对比不同选择、交叉、变异算子的效果。对比纯遗传算法和嵌入局部搜索的混合算法的效果。将你的最终结果与题目提供的参考结果如果有或其他经典算法结果进行对比。使用表格清晰展示数据。灵敏度分析分析算法中关键参数如种群大小、变异率、批次面积阈值对结果的影响。这体现了你对模型的理解深度。可视化展示在论文中放入关键迭代过程的收敛曲线图以及最终排样结果的示意图。一图胜千言。最后记住数学建模竞赛的核心是“建模”而不是单纯的编程。你的模型思想、对问题的分析和转化过程往往比代码实现更重要。确保你的论文逻辑严密从问题分析、模型建立、算法设计到结果验证形成一个完整的闭环。方形件组批优化是一个深不见底的问题每一次尝试都可能带来新的启发这也是它作为经典赛题的魅力所在。
