1. 问题引入从一张订单到一车板材去年备赛的时候我遇到了一个特别“实在”的优化问题——2022年“华为杯”研究生数学建模竞赛B题方形件组批优化。这题目听起来有点学术但说白了就是咱们制造业里天天要面对的“套裁”问题。想象一下你是一个板材加工厂的计划员。每天你会收到来自不同客户的一大堆订单每个订单要求生产若干种特定尺寸的矩形零件方形件。你的原材料是大张的矩形板材尺寸固定。你的任务很明确如何把这些零散的订单组合成一批批的生产任务即“组批”使得切割这些板材时浪费的边角料最少从而用最少的板材、花最少的钱完成所有订单这可不是简单的“拼图游戏”。首先订单不能拆散一个订单里的所有零件必须安排在同一批中生产这保证了生产管理的连贯性和可追溯性。其次一批任务所能使用的板材总面积是有限的这受限于你的设备产能或原材料库存。最后你的目标函数是双重的既要最小化使用的板材总张数直接对应原材料成本又要最小化生产的批次数这关系到设备切换、调度等间接成本。这两个目标往往相互冲突减少批次可能意味着单批需要更多板材反之亦然。题目给了我们几组不同规模的数据从几十个订单到上千个订单零件种类也从几种到几十种。这要求我们的求解方法不能只在小数据上“绣花”还得能扛住大规模实际数据的考验。当时我和队友们看到这个问题第一反应是这得用运筹学里的混合整数规划MIP来建模。但真动起手来才发现从“想到”到“解出”中间隔了无数个需要权衡和优化的细节。2. 模型核心构建一个精确的混合整数规划框架面对这样一个带有分组和排样双重特性的组合优化问题建立一个精确的数学模型是第一步也是厘清思路的关键。我们最终构建的模型其核心思想是将“组批”和“排样”两个阶段的问题进行合理的解耦与关联。2.1 决策变量设计如何描述“选择”与“安排”模型的“骨骼”在于决策变量。我们主要定义了三类变量批处理变量 (x_ik)这是一个0-1变量。如果订单i被安排在第k批进行生产则x_ik 1否则为0。这个变量直接描述了“哪个订单去哪一批”这个核心的组批决策。板材使用变量 (y_k)同样是一个0-1变量。如果第k批被启用即至少包含一个订单则y_k 1否则为0。它决定了我们最终使用的批次数。板材数量变量 (n_k)这是一个非负整数变量。表示生产第k批所有订单所需的原材料板材总张数。它由该批次内所有零件的总面积、板材尺寸以及排样利用率共同决定。这里有一个关键的建模技巧我们并没有在MIP模型中直接求解复杂的二维排样即具体每张板上零件怎么摆。那样会导致模型变量爆炸无法求解。取而代之的是我们引入了一个排样利用率参数 η。它的含义是在最优或近优的排样方案下单张板材的面积利用率所能达到的一个理论下界例如根据历史经验或简单启发式算法估算为85%。那么对于第k批其所需板材数n_k必须满足n_k * (板材面积 * η) 该批次所有零件的总面积。这样我们就把复杂的二维几何约束转化为了一个线性的面积约束使模型得以简化并可求解。注意这个 η 的设定至关重要。如果设得过于乐观如95%模型计算出的n_k可能偏少导致实际无法排下如果设得过于保守如70%则模型会高估板材需求浪费成本。通常需要通过前期实验或文献参考确定一个合理的、略低于实际可达平均利用率的数值。2.2 约束条件为问题戴上“紧箍咒”变量定义好了就要用约束条件来规范它们的行为使其符合实际问题规则订单完整性约束每个订单必须且只能被分配到一个批次中。用数学表达就是对于每个订单i∑_k x_ik 1。这是最基本的要求。批次启用逻辑约束如果一个批次没有被分配任何订单那么它不能被启用且所需板材数为0。这需要建立y_k和x_ik之间的逻辑关系∑_i x_ik M * y_k其中M是一个足够大的常数比如订单总数。这意味着只要有任一x_ik为1y_k就必须为1。同时n_k M * y_k确保未启用的批次其板材数强制为0。板材面积约束这是连接组批决策与排样结果的核心。对于每个启用的批次k其所有零件的总面积必须小于等于该批次所分配板材的总有效面积∑_i (订单i零件总面积 * x_ik) n_k * (板材面积 * η)。这个约束确保了我们的组批方案在理论上以利用率η衡量是“可排样”的。批次生产能力约束可选题目中隐含了每批任务有最大板材消耗上限。我们可以将其转化为对n_k的约束n_k N_max其中N_max是单批允许使用的最大板材数。如果题目未明确此约束可省略或根据实际情况设定。2.3 目标函数寻找成本平衡点我们的目标有两个按重要性通常分为主次首要目标最小化板材总消耗张数即Minimize ∑_k n_k。这直接最小化最主要的原材料成本。次要目标在板材数相同或相近的方案中最小化使用的批次数即Minimize ∑_k y_k。这可以减少生产切换、调度和管理成本。在优化中处理多目标问题常用“分层序列法”或“加权求和法”。对于本题由于板材成本通常远高于批次切换成本我们采用分层优化首先求解最小化板材总张数得到一个最优值Z1*然后在约束中增加∑_k n_k Z1*在此前提下再求解最小化批次数∑_k y_k。这样就得到了一个兼顾两者的Pareto最优解。至此一个完整的、可被标准求解器处理的混合整数线性规划MILP模型就建立起来了。但模型建好只是万里长征第一步。3. 求解策略精确与启发式的双轨制攻坚直接将上述MILP模型扔给CPLEX或Gurobi求解器去解中等以上规模的数据很可能遭遇“维度灾难”几个小时甚至几天都得不到可行解。我们必须设计高效的求解策略。3.1 精确求解针对小规模数据的“手术刀”对于零件种类少、订单数量小例如题目中的小规模测试数据的情况完整的MILP模型可以直接求解。我们使用Python的pulp或ortools库调用Gurobi求解器。关键技巧在于模型预处理减少变量预先计算每个订单的零件总面积。对于明显不可能同批的订单如总面积之和远超单批产能上限可以预先固定其x_ik为0减少搜索空间。设定初始解可以采用简单的启发式规则如按订单总面积降序排列依次贪心地放入当前批次放不下则开新批生成一个初始的组批方案。将这个方案转化为决策变量的赋值作为“热启动”输入给求解器能极大加速求解进程。调整求解器参数设置合适的MIP Gap如1%在可接受的时间内获取高质量可行解而非执着于理论最优。# 示例使用PuLP库定义模型骨架关键部分 import pulp # 定义问题 prob pulp.LpProblem(Square_Part_Batching, pulp.LpMinimize) # 定义变量 x pulp.LpVariable.dicts(assign, ((i, k) for i in orders for k in batches), catBinary) y pulp.LpVariable.dicts(batch_used, (k for k in batches), catBinary) n pulp.LpVariable.dicts(plates_needed, (k for k in batches), lowBound0, catInteger) # 设置目标函数分层目标需分两步实现此处示意首要目标 prob pulp.lpSum([n[k] for k in batches]), Minimize_Total_Plates # 添加约束 for i in orders: prob pulp.lpSum([x[i, k] for k in batches]) 1, fOrder_{i}_Assigned for k in batches: # 批次启用逻辑 prob pulp.lpSum([x[i, k] for i in orders]) bigM * y[k], fBatch_{k}_Activation_Logic prob n[k] bigM * y[k], fPlate_Logic_for_Batch_{k} # 板材面积约束 prob pulp.lpSum([order_area[i] * x[i, k] for i in orders]) n[k] * (plate_area * eta), fArea_Constraint_Batch_{k} # 批次产能约束 prob n[k] max_plates_per_batch, fCapacity_Constraint_Batch_{k} # 求解 solver pulp.GUROBI_CMD(timeLimit300, gapRel0.01) # 设置5分钟时限和1%的Gap prob.solve(solver)3.2 启发式算法应对大规模数据的“组合拳”当订单数成百上千时精确模型无能为力。我们必须借助启发式算法。我们设计了一种两阶段启发式算法第一阶段快速获得一个较好的组批方案第二阶段对这个方案进行局部优化。第一阶段基于聚类思想的贪心组批我们不再将每个订单视为独立点而是将其零件总面积作为特征。问题转化为如何将这些“订单点”聚类成若干组批使得每组的特征和总面积不超过某个上限板材面积 * η * N_max同时组数尽可能少。 我们采用了按面积降序排列的首次适应贪心算法FFD将所有订单按零件总面积从大到小排序。初始化第一个空批次。遍历排序后的订单对于当前订单尝试放入第一个能容纳它的批次即放入后该批次预估总面积不超过容量上限。如果所有现有批次都无法容纳则开启一个新的批次放入该订单。这个算法简单快速能很快得到一个可行解但通常不是最优的。第二阶段基于邻域搜索的批优化在获得初始批方案后我们通过定义和搜索“邻域”来改进它。主要设计了两种邻域操作订单移动将一个订单从当前批次移动到另一个批次。订单交换交换两个分属不同批次的订单。搜索策略采用模拟退火SA或禁忌搜索TS框架以避免陷入局部最优。以模拟退火为例初始温度设置一个较高的初始温度T。邻域操作在当前解的基础上随机执行一次“移动”或“交换”操作得到一个新解。接受准则如果新解的目标值板材总数次要考虑批次数更优则接受如果更差则以一定概率exp(-ΔE / T)接受其中ΔE是目标值增量。这给了算法跳出局部最优的可能。降温按照一定的冷却速率如0.95逐步降低温度T。终止当温度降至阈值以下或连续若干步没有改进时停止搜索。# 示例模拟退火算法的核心结构伪代码 import random import math def simulated_annealing(initial_solution): current_solution initial_solution current_cost calculate_cost(current_solution) # 计算板材总数和批次数 best_solution current_solution.copy() best_cost current_cost T initial_temperature while T final_temperature: for _ in range(iterations_per_T): # 生成邻域新解 new_solution generate_neighbor(current_solution) # 随机移动或交换一个订单 new_cost calculate_cost(new_solution) delta_cost new_cost - current_cost # 接受新解 if delta_cost 0 or random.random() math.exp(-delta_cost / T): current_solution new_solution current_cost new_cost if current_cost best_cost: best_solution current_solution.copy() best_cost current_cost # 降温 T * cooling_rate return best_solution, best_cost3.3 排样验证从“理论可行”到“实际可行”通过MILP或启发式算法我们得到了一个组批方案以及每批预估的板材数n_k。但这只是基于平均利用率η的估算。我们必须验证每一批的零件是否真的能用n_k张板材排下。这就需要调用一个二维矩形排样算法。我们采用了经典的左下角填充算法Bottom-Left Fill, BLF的一种改进版本作为验证器。对于每一批输入该批次所有零件的长宽列表以及板材的长宽和可用张数n_k。过程算法尝试将零件依次放入当前板材。放置策略是优先选择能放下该零件且剩余空间最“紧凑”的位置通常是最低最左的可放置点。如果当前板材放不下剩余任何零件则启用下一张板材。输出如果成功将所有零件放入n_k张板内则验证通过如果需要更多板材则说明原组批方案不可行需要调整例如微调η值或返回上一步重新优化组批。这个排样验证步骤是保证方案实际可操作性的关键它充当了组批模型与真实生产之间的“桥梁”。4. 编程实现与结果分析在代码中打磨细节我们将整个求解流程在Python中实现主要依赖pulp(用于MILP模型)、numpy、pandas(数据处理)以及自实现的启发式算法和排样验证模块。4.1 数据预处理与参数校准读入订单数据后首要任务是计算每个订单的零件总面积、零件种类分布等特征。对于参数η排样利用率我们采用了一个动态校准的策略先用一个保守值如0.8运行启发式算法得到初始批方案然后用排样算法对每一批进行实际排样计算实际的排样利用率。如果实际利用率均值远高于0.8说明我们的估计过于保守可以适当调高η如至0.85重新优化以期减少板材数反之则调低。通过几次迭代找到一个与后续排样算法能力相匹配的η值。4.2 算法流程集成我们的主程序逻辑如下def main_solver(order_data, plate_width, plate_height, max_plates_per_batch, initial_eta0.82): # 1. 数据预处理 orders preprocess_orders(order_data) # 2. 参数动态校准简化示意 eta initial_eta for _ in range(3): # 迭代3次 # 3. 启发式组批或小规模用MILP if len(orders) 50: batch_plan, plate_estimates solve_by_milp(orders, plate_width, plate_height, eta, max_plates_per_batch) else: batch_plan, plate_estimates greedy_batching(orders, plate_width, plate_height, eta, max_plates_per_batch) batch_plan, plate_estimates simulated_annealing_improvement(batch_plan, plate_estimates, ...) # 4. 排样验证 all_valid True actual_plates_needed [] for batch_id, component_list in batch_plan.items(): needed, success packing_verifier(component_list, plate_width, plate_height, plate_estimates[batch_id]) actual_plates_needed.append(needed) if not success: all_valid False print(fBatch {batch_id} packing failed, estimated {plate_estimates[batch_id]} plates, actually needs more.) # 如果失败根据实际情况调整eta或采取其他策略 # 例如记录该批的实际利用率用于整体调整eta break if all_valid: print(All batches packed successfully!) # 计算实际总板材数和平均利用率 total_plates sum(actual_plates_needed) avg_utilization calculate_avg_utilization(batch_plan, actual_plates_needed, plate_width, plate_height) print(fTotal plates: {total_plates}, Average utilization: {avg_utilization:.2%}) # 可以用当前平均利用率微调eta进行下一轮优化可选 # eta avg_utilization * 0.95 # 稍微保守一点 break else: # 验证失败调低eta使组批更“宽松” eta * 0.98 print(fPacking validation failed. Adjusting eta down to {eta:.3f} for retry.) return batch_plan, actual_plates_needed, total_plates4.3 结果对比与方案解读我们对竞赛提供的多组数据进行了测试。以其中一组中等规模数据为例直接贪心FFD得到方案需要153张板材分为28批。贪心模拟退火优化后方案优化为需要142张板材分为25批。板材数减少了7.2%批次数减少了10.7%。小规模数据MILP精确解作为基准验证了启发式算法在可求解范围内的解质量与最优解的差距在3%以内证明了启发式策略的有效性。输出方案不仅包括每批包含哪些订单还包括每批所需的板材张数以及基于排样验证器的、每张板材上零件的近似布局示意图输出为坐标列表或图形。这为生产部门提供了可直接执行的作业指导。5. 经验总结与延伸思考回顾整个求解过程有几个点对于解决此类实际优化问题至关重要1. 模型简化与精确度的权衡引入排样利用率η是对现实问题的极大简化它让模型可解。关键在于η的取值必须基于对后续排样算法能力的准确评估。一个实用的方法是用历史数据或代表性数据单独测试你的排样算法统计其平均利用率然后取一个略低于该值的η用于组批模型。这相当于为“理论”和“实际”之间设置了一个安全缓冲。2. 算法组合的艺术没有一种算法能通吃所有规模和所有特点的问题。我们的“精确模型小规模 启发式算法大规模 排样验证保障可行性”的管道式策略是有效的。在启发式算法中简单的贪心构造一个“还不错”的初始解再用元启发式算法模拟退火、禁忌搜索进行精细化改进这种“构造-改进”两阶段法是求解组合优化问题的经典范式。3. 计算效率与解质量的平衡对于大规模数据模拟退火中的参数初始温度、冷却速率、迭代次数需要仔细调优。温度下降太快容易陷入局部最优太慢则耗时过长。我们采用了自适应调整策略在搜索初期接受较差解的概率较高以广泛探索在搜索后期则更倾向于接受改进解进行局部深耕。4. 从竞赛到实际应用的鸿沟竞赛模型假设零件是简单的矩形且方向固定。现实中零件可能有复杂的形状、需要留出工艺边、需要考虑切割刀路损耗、板材可能存在缺陷区域等。此外目标函数可能还包括最小化切割总路径时间、平衡各批次的加工时间等。因此真正的工业级套料软件如AutoNEST、SigmaNEST其算法核心要复杂得多往往融合了更高级的几何算法、动态规划和强大的启发式规则。5. 编程实践中的坑数据结构的效率在模拟退火中频繁评估解的成本计算板材数如果每次都从头计算批次总面积会非常慢。我们维护了每个批次的总面积、零件列表等状态信息在移动或交换订单时只需增量更新受影响批次的状态极大提升了性能。随机性的控制启发式算法带有随机性为了结果可复现需要固定随机数种子。但在多轮测试中也需要通过改变种子来验证算法的鲁棒性。可视化调试将排样结果用matplotlib画出来是检查算法错误如零件重叠、超出边界最直观的方式。这在开发排样验证器时必不可少。解决这个方形件组批问题就像完成了一次从数学建模到算法设计再到工程实现的完整闭环。它教会我的不仅是混合整数规划或启发式算法更是一种解决复杂工业优化问题的系统思维如何分解问题、如何在精确与启发之间取舍、如何用计算实验来验证和校准模型。这份经历对于后来处理其他资源调度、路径规划等问题都提供了非常宝贵的范式参考。
混合整数规划与启发式算法在方形件组批优化中的应用
1. 问题引入从一张订单到一车板材去年备赛的时候我遇到了一个特别“实在”的优化问题——2022年“华为杯”研究生数学建模竞赛B题方形件组批优化。这题目听起来有点学术但说白了就是咱们制造业里天天要面对的“套裁”问题。想象一下你是一个板材加工厂的计划员。每天你会收到来自不同客户的一大堆订单每个订单要求生产若干种特定尺寸的矩形零件方形件。你的原材料是大张的矩形板材尺寸固定。你的任务很明确如何把这些零散的订单组合成一批批的生产任务即“组批”使得切割这些板材时浪费的边角料最少从而用最少的板材、花最少的钱完成所有订单这可不是简单的“拼图游戏”。首先订单不能拆散一个订单里的所有零件必须安排在同一批中生产这保证了生产管理的连贯性和可追溯性。其次一批任务所能使用的板材总面积是有限的这受限于你的设备产能或原材料库存。最后你的目标函数是双重的既要最小化使用的板材总张数直接对应原材料成本又要最小化生产的批次数这关系到设备切换、调度等间接成本。这两个目标往往相互冲突减少批次可能意味着单批需要更多板材反之亦然。题目给了我们几组不同规模的数据从几十个订单到上千个订单零件种类也从几种到几十种。这要求我们的求解方法不能只在小数据上“绣花”还得能扛住大规模实际数据的考验。当时我和队友们看到这个问题第一反应是这得用运筹学里的混合整数规划MIP来建模。但真动起手来才发现从“想到”到“解出”中间隔了无数个需要权衡和优化的细节。2. 模型核心构建一个精确的混合整数规划框架面对这样一个带有分组和排样双重特性的组合优化问题建立一个精确的数学模型是第一步也是厘清思路的关键。我们最终构建的模型其核心思想是将“组批”和“排样”两个阶段的问题进行合理的解耦与关联。2.1 决策变量设计如何描述“选择”与“安排”模型的“骨骼”在于决策变量。我们主要定义了三类变量批处理变量 (x_ik)这是一个0-1变量。如果订单i被安排在第k批进行生产则x_ik 1否则为0。这个变量直接描述了“哪个订单去哪一批”这个核心的组批决策。板材使用变量 (y_k)同样是一个0-1变量。如果第k批被启用即至少包含一个订单则y_k 1否则为0。它决定了我们最终使用的批次数。板材数量变量 (n_k)这是一个非负整数变量。表示生产第k批所有订单所需的原材料板材总张数。它由该批次内所有零件的总面积、板材尺寸以及排样利用率共同决定。这里有一个关键的建模技巧我们并没有在MIP模型中直接求解复杂的二维排样即具体每张板上零件怎么摆。那样会导致模型变量爆炸无法求解。取而代之的是我们引入了一个排样利用率参数 η。它的含义是在最优或近优的排样方案下单张板材的面积利用率所能达到的一个理论下界例如根据历史经验或简单启发式算法估算为85%。那么对于第k批其所需板材数n_k必须满足n_k * (板材面积 * η) 该批次所有零件的总面积。这样我们就把复杂的二维几何约束转化为了一个线性的面积约束使模型得以简化并可求解。注意这个 η 的设定至关重要。如果设得过于乐观如95%模型计算出的n_k可能偏少导致实际无法排下如果设得过于保守如70%则模型会高估板材需求浪费成本。通常需要通过前期实验或文献参考确定一个合理的、略低于实际可达平均利用率的数值。2.2 约束条件为问题戴上“紧箍咒”变量定义好了就要用约束条件来规范它们的行为使其符合实际问题规则订单完整性约束每个订单必须且只能被分配到一个批次中。用数学表达就是对于每个订单i∑_k x_ik 1。这是最基本的要求。批次启用逻辑约束如果一个批次没有被分配任何订单那么它不能被启用且所需板材数为0。这需要建立y_k和x_ik之间的逻辑关系∑_i x_ik M * y_k其中M是一个足够大的常数比如订单总数。这意味着只要有任一x_ik为1y_k就必须为1。同时n_k M * y_k确保未启用的批次其板材数强制为0。板材面积约束这是连接组批决策与排样结果的核心。对于每个启用的批次k其所有零件的总面积必须小于等于该批次所分配板材的总有效面积∑_i (订单i零件总面积 * x_ik) n_k * (板材面积 * η)。这个约束确保了我们的组批方案在理论上以利用率η衡量是“可排样”的。批次生产能力约束可选题目中隐含了每批任务有最大板材消耗上限。我们可以将其转化为对n_k的约束n_k N_max其中N_max是单批允许使用的最大板材数。如果题目未明确此约束可省略或根据实际情况设定。2.3 目标函数寻找成本平衡点我们的目标有两个按重要性通常分为主次首要目标最小化板材总消耗张数即Minimize ∑_k n_k。这直接最小化最主要的原材料成本。次要目标在板材数相同或相近的方案中最小化使用的批次数即Minimize ∑_k y_k。这可以减少生产切换、调度和管理成本。在优化中处理多目标问题常用“分层序列法”或“加权求和法”。对于本题由于板材成本通常远高于批次切换成本我们采用分层优化首先求解最小化板材总张数得到一个最优值Z1*然后在约束中增加∑_k n_k Z1*在此前提下再求解最小化批次数∑_k y_k。这样就得到了一个兼顾两者的Pareto最优解。至此一个完整的、可被标准求解器处理的混合整数线性规划MILP模型就建立起来了。但模型建好只是万里长征第一步。3. 求解策略精确与启发式的双轨制攻坚直接将上述MILP模型扔给CPLEX或Gurobi求解器去解中等以上规模的数据很可能遭遇“维度灾难”几个小时甚至几天都得不到可行解。我们必须设计高效的求解策略。3.1 精确求解针对小规模数据的“手术刀”对于零件种类少、订单数量小例如题目中的小规模测试数据的情况完整的MILP模型可以直接求解。我们使用Python的pulp或ortools库调用Gurobi求解器。关键技巧在于模型预处理减少变量预先计算每个订单的零件总面积。对于明显不可能同批的订单如总面积之和远超单批产能上限可以预先固定其x_ik为0减少搜索空间。设定初始解可以采用简单的启发式规则如按订单总面积降序排列依次贪心地放入当前批次放不下则开新批生成一个初始的组批方案。将这个方案转化为决策变量的赋值作为“热启动”输入给求解器能极大加速求解进程。调整求解器参数设置合适的MIP Gap如1%在可接受的时间内获取高质量可行解而非执着于理论最优。# 示例使用PuLP库定义模型骨架关键部分 import pulp # 定义问题 prob pulp.LpProblem(Square_Part_Batching, pulp.LpMinimize) # 定义变量 x pulp.LpVariable.dicts(assign, ((i, k) for i in orders for k in batches), catBinary) y pulp.LpVariable.dicts(batch_used, (k for k in batches), catBinary) n pulp.LpVariable.dicts(plates_needed, (k for k in batches), lowBound0, catInteger) # 设置目标函数分层目标需分两步实现此处示意首要目标 prob pulp.lpSum([n[k] for k in batches]), Minimize_Total_Plates # 添加约束 for i in orders: prob pulp.lpSum([x[i, k] for k in batches]) 1, fOrder_{i}_Assigned for k in batches: # 批次启用逻辑 prob pulp.lpSum([x[i, k] for i in orders]) bigM * y[k], fBatch_{k}_Activation_Logic prob n[k] bigM * y[k], fPlate_Logic_for_Batch_{k} # 板材面积约束 prob pulp.lpSum([order_area[i] * x[i, k] for i in orders]) n[k] * (plate_area * eta), fArea_Constraint_Batch_{k} # 批次产能约束 prob n[k] max_plates_per_batch, fCapacity_Constraint_Batch_{k} # 求解 solver pulp.GUROBI_CMD(timeLimit300, gapRel0.01) # 设置5分钟时限和1%的Gap prob.solve(solver)3.2 启发式算法应对大规模数据的“组合拳”当订单数成百上千时精确模型无能为力。我们必须借助启发式算法。我们设计了一种两阶段启发式算法第一阶段快速获得一个较好的组批方案第二阶段对这个方案进行局部优化。第一阶段基于聚类思想的贪心组批我们不再将每个订单视为独立点而是将其零件总面积作为特征。问题转化为如何将这些“订单点”聚类成若干组批使得每组的特征和总面积不超过某个上限板材面积 * η * N_max同时组数尽可能少。 我们采用了按面积降序排列的首次适应贪心算法FFD将所有订单按零件总面积从大到小排序。初始化第一个空批次。遍历排序后的订单对于当前订单尝试放入第一个能容纳它的批次即放入后该批次预估总面积不超过容量上限。如果所有现有批次都无法容纳则开启一个新的批次放入该订单。这个算法简单快速能很快得到一个可行解但通常不是最优的。第二阶段基于邻域搜索的批优化在获得初始批方案后我们通过定义和搜索“邻域”来改进它。主要设计了两种邻域操作订单移动将一个订单从当前批次移动到另一个批次。订单交换交换两个分属不同批次的订单。搜索策略采用模拟退火SA或禁忌搜索TS框架以避免陷入局部最优。以模拟退火为例初始温度设置一个较高的初始温度T。邻域操作在当前解的基础上随机执行一次“移动”或“交换”操作得到一个新解。接受准则如果新解的目标值板材总数次要考虑批次数更优则接受如果更差则以一定概率exp(-ΔE / T)接受其中ΔE是目标值增量。这给了算法跳出局部最优的可能。降温按照一定的冷却速率如0.95逐步降低温度T。终止当温度降至阈值以下或连续若干步没有改进时停止搜索。# 示例模拟退火算法的核心结构伪代码 import random import math def simulated_annealing(initial_solution): current_solution initial_solution current_cost calculate_cost(current_solution) # 计算板材总数和批次数 best_solution current_solution.copy() best_cost current_cost T initial_temperature while T final_temperature: for _ in range(iterations_per_T): # 生成邻域新解 new_solution generate_neighbor(current_solution) # 随机移动或交换一个订单 new_cost calculate_cost(new_solution) delta_cost new_cost - current_cost # 接受新解 if delta_cost 0 or random.random() math.exp(-delta_cost / T): current_solution new_solution current_cost new_cost if current_cost best_cost: best_solution current_solution.copy() best_cost current_cost # 降温 T * cooling_rate return best_solution, best_cost3.3 排样验证从“理论可行”到“实际可行”通过MILP或启发式算法我们得到了一个组批方案以及每批预估的板材数n_k。但这只是基于平均利用率η的估算。我们必须验证每一批的零件是否真的能用n_k张板材排下。这就需要调用一个二维矩形排样算法。我们采用了经典的左下角填充算法Bottom-Left Fill, BLF的一种改进版本作为验证器。对于每一批输入该批次所有零件的长宽列表以及板材的长宽和可用张数n_k。过程算法尝试将零件依次放入当前板材。放置策略是优先选择能放下该零件且剩余空间最“紧凑”的位置通常是最低最左的可放置点。如果当前板材放不下剩余任何零件则启用下一张板材。输出如果成功将所有零件放入n_k张板内则验证通过如果需要更多板材则说明原组批方案不可行需要调整例如微调η值或返回上一步重新优化组批。这个排样验证步骤是保证方案实际可操作性的关键它充当了组批模型与真实生产之间的“桥梁”。4. 编程实现与结果分析在代码中打磨细节我们将整个求解流程在Python中实现主要依赖pulp(用于MILP模型)、numpy、pandas(数据处理)以及自实现的启发式算法和排样验证模块。4.1 数据预处理与参数校准读入订单数据后首要任务是计算每个订单的零件总面积、零件种类分布等特征。对于参数η排样利用率我们采用了一个动态校准的策略先用一个保守值如0.8运行启发式算法得到初始批方案然后用排样算法对每一批进行实际排样计算实际的排样利用率。如果实际利用率均值远高于0.8说明我们的估计过于保守可以适当调高η如至0.85重新优化以期减少板材数反之则调低。通过几次迭代找到一个与后续排样算法能力相匹配的η值。4.2 算法流程集成我们的主程序逻辑如下def main_solver(order_data, plate_width, plate_height, max_plates_per_batch, initial_eta0.82): # 1. 数据预处理 orders preprocess_orders(order_data) # 2. 参数动态校准简化示意 eta initial_eta for _ in range(3): # 迭代3次 # 3. 启发式组批或小规模用MILP if len(orders) 50: batch_plan, plate_estimates solve_by_milp(orders, plate_width, plate_height, eta, max_plates_per_batch) else: batch_plan, plate_estimates greedy_batching(orders, plate_width, plate_height, eta, max_plates_per_batch) batch_plan, plate_estimates simulated_annealing_improvement(batch_plan, plate_estimates, ...) # 4. 排样验证 all_valid True actual_plates_needed [] for batch_id, component_list in batch_plan.items(): needed, success packing_verifier(component_list, plate_width, plate_height, plate_estimates[batch_id]) actual_plates_needed.append(needed) if not success: all_valid False print(fBatch {batch_id} packing failed, estimated {plate_estimates[batch_id]} plates, actually needs more.) # 如果失败根据实际情况调整eta或采取其他策略 # 例如记录该批的实际利用率用于整体调整eta break if all_valid: print(All batches packed successfully!) # 计算实际总板材数和平均利用率 total_plates sum(actual_plates_needed) avg_utilization calculate_avg_utilization(batch_plan, actual_plates_needed, plate_width, plate_height) print(fTotal plates: {total_plates}, Average utilization: {avg_utilization:.2%}) # 可以用当前平均利用率微调eta进行下一轮优化可选 # eta avg_utilization * 0.95 # 稍微保守一点 break else: # 验证失败调低eta使组批更“宽松” eta * 0.98 print(fPacking validation failed. Adjusting eta down to {eta:.3f} for retry.) return batch_plan, actual_plates_needed, total_plates4.3 结果对比与方案解读我们对竞赛提供的多组数据进行了测试。以其中一组中等规模数据为例直接贪心FFD得到方案需要153张板材分为28批。贪心模拟退火优化后方案优化为需要142张板材分为25批。板材数减少了7.2%批次数减少了10.7%。小规模数据MILP精确解作为基准验证了启发式算法在可求解范围内的解质量与最优解的差距在3%以内证明了启发式策略的有效性。输出方案不仅包括每批包含哪些订单还包括每批所需的板材张数以及基于排样验证器的、每张板材上零件的近似布局示意图输出为坐标列表或图形。这为生产部门提供了可直接执行的作业指导。5. 经验总结与延伸思考回顾整个求解过程有几个点对于解决此类实际优化问题至关重要1. 模型简化与精确度的权衡引入排样利用率η是对现实问题的极大简化它让模型可解。关键在于η的取值必须基于对后续排样算法能力的准确评估。一个实用的方法是用历史数据或代表性数据单独测试你的排样算法统计其平均利用率然后取一个略低于该值的η用于组批模型。这相当于为“理论”和“实际”之间设置了一个安全缓冲。2. 算法组合的艺术没有一种算法能通吃所有规模和所有特点的问题。我们的“精确模型小规模 启发式算法大规模 排样验证保障可行性”的管道式策略是有效的。在启发式算法中简单的贪心构造一个“还不错”的初始解再用元启发式算法模拟退火、禁忌搜索进行精细化改进这种“构造-改进”两阶段法是求解组合优化问题的经典范式。3. 计算效率与解质量的平衡对于大规模数据模拟退火中的参数初始温度、冷却速率、迭代次数需要仔细调优。温度下降太快容易陷入局部最优太慢则耗时过长。我们采用了自适应调整策略在搜索初期接受较差解的概率较高以广泛探索在搜索后期则更倾向于接受改进解进行局部深耕。4. 从竞赛到实际应用的鸿沟竞赛模型假设零件是简单的矩形且方向固定。现实中零件可能有复杂的形状、需要留出工艺边、需要考虑切割刀路损耗、板材可能存在缺陷区域等。此外目标函数可能还包括最小化切割总路径时间、平衡各批次的加工时间等。因此真正的工业级套料软件如AutoNEST、SigmaNEST其算法核心要复杂得多往往融合了更高级的几何算法、动态规划和强大的启发式规则。5. 编程实践中的坑数据结构的效率在模拟退火中频繁评估解的成本计算板材数如果每次都从头计算批次总面积会非常慢。我们维护了每个批次的总面积、零件列表等状态信息在移动或交换订单时只需增量更新受影响批次的状态极大提升了性能。随机性的控制启发式算法带有随机性为了结果可复现需要固定随机数种子。但在多轮测试中也需要通过改变种子来验证算法的鲁棒性。可视化调试将排样结果用matplotlib画出来是检查算法错误如零件重叠、超出边界最直观的方式。这在开发排样验证器时必不可少。解决这个方形件组批问题就像完成了一次从数学建模到算法设计再到工程实现的完整闭环。它教会我的不仅是混合整数规划或启发式算法更是一种解决复杂工业优化问题的系统思维如何分解问题、如何在精确与启发之间取舍、如何用计算实验来验证和校准模型。这份经历对于后来处理其他资源调度、路径规划等问题都提供了非常宝贵的范式参考。