1. 从“三维装箱”到“五一赛E题”一个老建模人的实战拆解又到了一年一度的五一数学建模联赛今年E题毫无意外地又落在了“三维装箱”这个经典又磨人的问题上。看到这个题目我估计不少参赛队伍是既兴奋又头疼。兴奋的是这题目标明确有大量现成文献和算法可以参考头疼的是正因为参考资料太多如何从海量信息中提炼出适合自己队伍的、能在有限时间内跑出结果的方案反而成了最大的挑战。作为一个从本科到研究生再到后来带学生参赛跟各种装箱、排样、路径规划问题打了十几年交道的“老油条”我想结合这次E题的背景聊聊三维装箱问题到底该怎么“啃”以及如何把那些经典的算法和模型真正变成你论文里能拿分的“硬通货”。三维装箱问题3D Bin Packing Problem, 3D-BPP本质上是一个组合优化问题属于NP-hard难题。简单说就是给你一堆大小、形状、重量可能各不相同的货物我们称之为“物品”或“项目”以及若干个标准尺寸的箱子“容器”你的目标是用最少的箱子把所有货物都装进去同时满足一系列约束条件比如货物不能超出箱子边界、不能相互重叠、朝向可能有限制、承重要求等等。这个问题在物流、仓储、运输、芯片设计、甚至游戏开发比如背包系统等领域都有极其广泛的应用。所以数学建模比赛出这个题既考察了学生的优化建模能力也紧密贴合了实际工程需求。但比赛题目永远不会是教科书式的“标准三维装箱”。以“2024年五一数学建模联赛E题”为引我们虽然不知道具体题干但可以预见它一定会在经典问题上增加新的“花样”或约束比如多目标优化可能不仅仅是箱子数量最少成本最低还要考虑重心稳定防止运输倾覆、装载效率空间利用率、装卸顺序后进先出LIFO或先进先出FIFO等多个目标。复杂约束物品可能有特殊的放置要求如“必须竖直放置”、“不能倒置”、“易碎品上方不能压货”箱子可能有多个隔板或承重分区甚至要考虑装载工具的机械臂活动空间。动态或在线装箱物品不是一次性全部给出而是随时间陆续到达需要实时做出装箱决策。异构容器可用的箱子不止一种尺寸你需要同时决策选用哪种箱子以及如何装载。面对这样一个“包装”过的赛题很多新手容易陷入两个极端要么被吓住觉得无从下手要么一头扎进某个复杂算法如遗传算法、模拟退火的代码实现里却忽略了最根本的模型建立和简化。我的经验是搞定这类问题关键在于建立清晰的解决框架先吃透题意并抽象出严谨的数学模型再根据模型特点和自身能力选择合适的求解策略最后通过巧妙的算法实现和结果分析来提升论文档次。2. 第一步问题解析与模型建立——把现实“翻译”成数学语言看到题目后别急着找代码。第一要务是和小组成员一起像法官审案一样逐字逐句地分析题目把所有明示和暗示的条件、目标、假设都列出来。这是整个建模工作的基石一旦理解偏差后面所有工作都可能白费。2.1 核心要素定义与假设合理化我们需要用数学语言定义问题中的所有实体和关系。决策变量这是模型的核心。最直接的思路是为每个物品在每个箱子的每个可能位置和朝向上定义一个0-1变量。例如定义二进制变量 ( x_{ijk} 1 ) 表示将物品 ( i ) 以朝向 ( k ) 放入箱子 ( j ) 的某个特定坐标位置。但这样变量维度会爆炸直接求解不可能。因此实际建模中需要更巧妙的定义比如只定义物品是否放入某个箱子以及它在箱子内的相对位置坐标 ((x_i, y_i, z_i))朝向用旋转角度或枚举表示。目标函数题目要求最小化什么最小化使用箱子总数最经典的目标。(\min \sum_{j1}^{M} y_j)其中 (y_j 1) 表示箱子 (j) 被使用。最小化总成本如果箱子有多种型号成本不同则目标为 (\min \sum_{j1}^{M} c_j \cdot y_j)。最大化空间利用率在固定箱子数量下最大化所有物品总体积与所用箱子总容积的比值。多目标组合例如首要目标是最少箱子数次要目标是重心最低(\min \sum \text{物品质量} \times \text{其重心高度})。这时需要引入多目标优化方法如加权和法、分层序列法或帕累托前沿求解。约束条件这是体现建模功底的地方必须无遗漏地列出并数学化。每个物品必须且只能放入一个箱子(\sum_{j} \sum_{k} x_{ijk} 1, \forall i)。物品必须在箱子内部对于物品 (i) 在箱子 (j) 中的放置坐标 ((x_i, y_i, z_i)) 及其在朝向 (k) 下的长 ((l_{ik}))、宽 ((w_{ik}))、高 ((h_{ik}))需满足 (0 \le x_i \le L_j - l_{ik}) (0 \le y_i \le W_j - w_{ik}) (0 \le z_i \le H_j - h_{ik}) 这里假设箱子一个角在原点物品放置位置以其某个角为基准。物品之间不能重叠这是最核心也是最难表达的约束。通常需要引入辅助变量。一种常见方法是“相对位置约束”对于任意两个放入同一箱子的物品 (i) 和 (p)它们在x, y, z三个维度上至少有一个方向是分离的。这可以通过引入0-1变量来线性化。例如定义 (a_{ip}1) 表示物品 (i) 在 (x) 方向上位于物品 (p) 的左侧那么不重叠约束可以转化为一组“析取约束”并通过大M法线性化。朝向限制如果物品只能以某些特定边作为高那么决策变量 (k) 的取值集合就需要被限制。支撑约束物品必须被底部箱底或其他物品完全支撑或者至少支撑面积超过某个阈值。这需要判断物品底面与下方支撑面的接触区域。重心稳定性约束整个箱子的整体重心投影需落在底面支撑多边形内。对于单个箱子可以计算所有装入物品的合重心位置并施加约束。承重约束每个物品上方的累计重量不能超过其承压强度。这需要建立物品之间的空间上下关系图并计算传递的载荷。合理假设比赛时间有限不可能模拟真实世界所有细节。必须做出合理简化假设并在论文中明确说明。例如假设所有物品和箱子都是刚体不会变形。假设物品的放置方向是正交的即只能0°或90°旋转不能任意角度倾斜。忽略包装材料的厚度。假设物品质量均匀分布重心在几何中心。对于支撑约束可以简化为“物品必须直接放置在箱底或另一个物品的顶部平面上且底面完全被支撑”。注意建立数学模型时优先追求“清晰”和“可求解”。一个包含了所有复杂约束但完全无法求解的模型不如一个做了合理简化但能给出优良可行解的模型。在论文中你需要展示从“理想模型”到“可计算模型”的简化过程这本身就是建模能力的体现。2.2 模型复杂度分析与求解策略选择完成上述抽象后你会得到一个混合整数规划MIP模型变量和约束数量巨大。直接调用商业求解器如Gurobi, CPLEX求解小规模问题尚可对于比赛规模的数据几十上百个物品在几小时内求精确解几乎不可能。因此我们必须转向启发式或元启发式算法。这里就面临选择用经典的构造启发式还是用搜索能力更强的元启发式构造启发式如首次适应递减FFD、最佳适应递减BFD及其三维变种。思路直接运行速度快能快速得到一个可行解但解的质量可能一般容易陷入局部最优。适用于对结果要求不高或作为元启发式初始解的场景。元启发式算法如遗传算法GA、模拟退火SA、禁忌搜索TS、粒子群优化PSO。这类算法通过模拟自然或社会现象进行全局搜索有更大潜力找到更优解但算法设计复杂、参数调优耗时、运行时间较长。我的建议是对于初次参赛或编程能力中等的队伍优先考虑“构造启发式局部搜索”的策略。先用一个简单的启发式规则如按体积从大到小排序依次尝试放入当前箱子生成一个初始装载方案然后设计一些局部优化操作如“交换两个物品的位置”、“将一个物品移到另一个箱子”、“在箱子内重新排列物品”来改进这个方案。这种方法实现难度相对可控且容易解释在论文中也能清晰地展示优化过程。如果队伍算法能力强可以挑战元启发式。以遗传算法为例你需要设计编码如何用一个染色体数组表示一个装箱方案常见的有基于序列的编码表示物品放入的顺序、基于箱子的编码等。解码如何将染色体解码成一个可行的装箱方案这通常需要一个“解码器”它按照染色体提供的顺序和规则调用一个放置策略如墙角法、最大空隙法来实际放置物品。适应度函数通常就是目标函数如箱子数量的倒数箱子数越少适应度越高但也要考虑对不可行解的惩罚如加入重叠惩罚项。遗传操作选择、交叉、变异。针对装箱问题的特性设计有效的交叉如交换两个子序列的箱子分配和变异如随机改变一个物品的箱子算子至关重要。3. 第二步算法核心——放置策略与空间表示无论你选择哪种上层优化框架启发式或元启发式底层都需要一个核心子程序给定一个箱子或一个正在装载中的箱子和一个待放入的物品如何决定把这个物品放在这个箱子里的具体哪个位置这个子程序就是“放置策略”它的效率和贪婪程度直接决定了整体算法的性能。3.1 几种经典的放置策略墙角法Corner Placement思路物品总是紧贴着箱子的一个角称为“墙角点”放置。墙角点定义为位于箱内其相邻的三个面左、后、下要么是箱壁要么是其他已放置物品的表面。优点生成的放置方案紧凑空间利用率高。概念清晰易于实现。缺点需要动态维护墙角点列表。每次放入新物品后可能生成新的墙角点也可能使一些旧的墙角点失效被遮挡。实现关键用一个列表存储所有当前可用的墙角点。对于待放置物品遍历所有墙角点和所有允许的朝向检查放置后是否满足约束是否在箱内、是否与其他物品重叠。选择第一个可行的位置首次适应或评估所有可行位置后选择“最优”的如选择放置后剩余空间最“方正”的位置。最大空隙法Maximal Space思路与墙角法类似但它维护的不是点而是“最大空隙”即箱内当前可用的、未被物品占据的最大矩形空间。物品被放入某个最大空隙中。优点更符合直观能更有效地利用大块空间。缺点最大空隙的识别、合并、更新算法比墙角点更复杂。实现关键初始时箱子本身就是一个最大空隙。放入物品后该空隙被分割。通常一个物品放入一个空隙后会将该空隙在三个维度上分割产生最多3个新的候选空隙右方空间、前方空间、上方空间。然后需要检查这些新空隙与现有空隙的包含关系进行合并以保持“最大”性。分层放置法Layering思路将箱子在高度Z轴方向上分成若干层优先将物品填充到当前层当前层填满后再开始新的一层。这模拟了人工装箱时“先铺底再往上码”的过程。优点算法简单特别适合需要考虑支撑稳定性的场景物品只能放在底部或下一层物品的顶部。缺点可能不如墙角法或最大空隙法灵活空间利用率可能略低。实现关键如何定义“层”可以是固定高度也可以是根据当前待放置物品动态调整。在层内可以再用二维矩形排样算法如左下角法来放置物品。选择建议墙角法和最大空隙法是三维装箱中最主流、最有效的两种底层放置策略。对于比赛而言实现墙角法是一个性价比很高的选择。它的逻辑相对直接在论文中也容易用图示说明。3.2 空间冲突检测算法的“交警”放置策略中每尝试一个位置都必须进行冲突检测Collision Detection即判断物品放入后是否与箱壁或其他物品重叠。这是算法中最耗时的部分之一需要高效实现。最朴素的方法是“边界框检测”对于两个物品分别计算它们在x, y, z轴上的投影区间如果在这三个轴上的投影区间都重叠则判定为碰撞。这种方法计算量小但前提是物品都是规则的立方体。如果物品是正交放置的立方体这方法是精确的。对于更复杂的形状题目很少涉及可能需要更复杂的几何计算。但在数学建模竞赛中绝大多数情况都假设物品为长方体且正交放置因此边界框检测完全足够。为了提高效率可以使用空间数据结构来加速查询例如网格法将箱子空间划分为均匀的立方体网格。每个物品占据一系列网格。放置新物品时只需检查它将要占据的网格是否已被占用。这种方法查询速度极快O(1)但精度受网格大小影响且内存消耗与网格数量成正比。空间索引如四叉树在二维排样中、八叉树或BVH包围体层次结构。这些方法在图形学和游戏物理引擎中常用能高效处理大量物体的碰撞检测但实现复杂度较高。对于比赛规模的题目物品数通常在100以内朴素的边界框检测遍历所有已放置物品通常是可以接受的。如果物品数量很大可以考虑简单的网格法进行优化。4. 第三步编程实现与技巧——从理论到跑出结果思路清晰了接下来就是硬碰硬的编程实现。这里我分享一些用Python实现的关键技巧和避坑点。4.1 数据结构设计良好的数据结构是高效算法的基础。class Item: def __init__(self, id, length, width, height, weight1.0, orientation_list[(0,1,2)]): self.id id # 原始尺寸 self.L length self.W width self.H height self.weight weight # 允许的朝向列表每个朝向是一个三元组 (l_idx, w_idx, h_idx) # 表示将原始尺寸的哪一维作为放置后的长、宽、高 # 例如 (0,1,2) 表示 [L, W, H] - [长, 宽, 高]原始朝向 # (1,0,2) 表示 [W, L, H] - [长, 宽, 高]旋转了90度 self.orientation_list orientation_list def get_dimensions(self, orientation): 根据朝向编号返回实际放置时的长、宽、高 dims [self.L, self.W, self.H] l_idx, w_idx, h_idx orientation return dims[l_idx], dims[w_idx], dims[h_idx] class Bin: def __init__(self, id, length, width, height, max_weightfloat(inf)): self.id id self.L length self.W width self.H height self.max_weight max_weight self.items [] # 存放已放置的物品信息 self.corners [(0, 0, 0)] # 当前可用的墙角点列表初始为原点 def get_used_volume(self): vol 0 for item_info in self.items: # item_info 可能是一个字典或元组包含物品引用、放置位置、朝向 item item_info[item] orientation item_info[orientation] l, w, h item.get_dimensions(orientation) vol l * w * h return vol def get_total_weight(self): weight 0 for item_info in self.items: weight item_info[item].weight return weight4.2 墙角法放置策略的实现示例以下是墙角法核心放置函数的一个简化框架def place_item_using_corners(bin, item, strategyfirst_fit): 尝试将物品放入箱子的某个墙角点。 strategy: first_fit - 找到第一个可行位置就放置。 best_fit - 评估所有可行位置选择最优如重心最低、剩余空间最规整。 best_position None best_orientation None best_evaluation float(inf) if strategy best_fit else None # 遍历所有当前墙角点 for corner in bin.corners: cx, cy, cz corner # 遍历物品所有允许的朝向 for orient in item.orientation_list: l, w, h item.get_dimensions(orient) # 检查放置后是否超出箱子边界 if cx l bin.L or cy w bin.W or cz h bin.H: continue # 假设物品放置后其占据的空间为 [cx, cxl] x [cy, cyw] x [cz, czh] # 检查是否与箱内已有物品重叠 if not check_collision(bin, cx, cy, cz, l, w, h): # 无冲突是一个可行位置 if strategy first_fit: # 直接放置并更新墙角点 perform_placement(bin, item, cx, cy, cz, orient) return True elif strategy best_fit: # 评估这个位置例如计算放置后新的重心高度 # 这里用放置高度cz作为简单评估倾向于先填底部 current_eval cz if current_eval best_evaluation: best_evaluation current_eval best_position (cx, cy, cz) best_orientation orient if strategy best_fit and best_position is not None: cx, cy, cz best_position perform_placement(bin, item, cx, cy, cz, best_orientation) return True return False # 无法放入该箱子 def check_collision(bin, x, y, z, l, w, h): 检查一个候选放置位置是否与箱内已有物品重叠 for placed_item_info in bin.items: px, py, pz placed_item_info[position] pl, pw, ph placed_item_info[item].get_dimensions(placed_item_info[orientation]) # 边界框检测在三个轴上投影都不重叠则无碰撞 if not (x l px or px pl x or y w py or py pw y or z h pz or pz ph z): return True # 发生碰撞 return False # 无碰撞 def perform_placement(bin, item, x, y, z, orientation): 执行放置操作更新箱子状态和墙角点列表 # 记录物品放置信息 bin.items.append({ item: item, position: (x, y, z), orientation: orientation }) # 更新墙角点列表移除被占用的墙角点添加新生成的墙角点 # 新墙角点可能产生在 (xl, y, z), (x, yw, z), (x, y, zh) # 需要检查这些点是否有效未被占据且在箱内 l, w, h item.get_dimensions(orientation) new_corners [(x l, y, z), (x, y w, z), (x, y, z h)] # 此处应有逻辑将新点加入bin.corners并移除无效点被物品遮挡的点 # 这是一个简化示例实际实现更复杂。 update_corner_list(bin, new_corners)4.3 整体算法流程与局部搜索结合放置策略一个完整的构造启发式算法流程如下数据预处理读取物品数据按某种规则排序如体积降序、最长边降序、重量降序。初始化创建空箱子列表。主循环遍历排序后的物品列表。 a. 对于当前物品遍历所有已打开的箱子按某种顺序如创建顺序、剩余空间大小。 b. 在每个箱子中调用place_item_using_corners尝试放置。 c. 如果所有已打开箱子都无法放入则打开一个新箱子并将物品放入新箱子的原点。输出结果记录每个箱子的装载方案。为了提升解的质量可以在上述构造解的基础上进行局部搜索物品交换随机选择两个在同一箱子或不同箱子中的物品尝试交换它们的位置如果交换后满足约束且目标更优如箱子数减少、空间利用率提高则接受交换。物品重定位随机选择一个物品将其从当前箱子中移除然后尝试放入其他箱子包括新箱子寻找更好的位置。箱子内重排清空一个箱子然后用不同的物品顺序或放置策略重新装载看是否能腾出空间装入更多物品。这些局部搜索操作可以迭代进行直到达到时间限制或连续多次迭代没有改进。5. 第四步论文写作与结果分析——把工作“卖”出去数学建模比赛模型和算法是基础但论文才是最终呈现给评委的答卷。一个清晰的、有逻辑的、美观的论文能极大提升获奖几率。5.1 论文结构要点问题重述与分析不要照抄题目要用自己的话精炼概括问题背景、条件和目标并分析问题的难点和关键点如NP-Hard、多约束等。模型假设与符号说明将之前讨论的合理假设清晰列出。符号说明用三线表格呈现显得专业。模型建立这是核心章节。逐步推导你的数学模型从决策变量、目标函数到每一个约束条件。对于复杂的约束如不重叠约束务必给出清晰的数学表达式并附上必要的文字解释。可以画示意图辅助说明。算法设计详细描述你的求解算法。建议用“流程图伪代码文字解释”的方式。流程图展示算法的主干逻辑。伪代码用接近编程语言但更数学化的方式描述关键步骤。文字解释说明你为何选择该算法算法的创新点或改进在哪里例如你改进了墙角点的生成规则或者设计了一种新的适应度函数。求解结果与数据分析测试数据如果题目给了多组数据要分别求解。也可以自己生成一些标准测试数据如BR实例来验证算法通用性。结果展示用表格清晰列出结果包括使用的箱子数、空间利用率、计算时间等。对于最优解或满意解提供每个箱子的装载明细物品ID、位置坐标、朝向。可视化这是极大的加分项使用Matplotlib、Plotly或专业的3D渲染库绘制出装箱结果的3D示意图。用不同颜色区分物品可以旋转查看。一张精美的3D装箱图能直观证明你的算法是有效的并给评委留下深刻印象。分析分析结果例如“随着物品数量增加空间利用率的变化趋势”、“我们的算法相比简单FFD算法箱子数减少了X%”。如果有多个目标可以讨论它们之间的权衡关系Pareto前沿。模型评价与推广客观评价自己模型的优点如求解效率高、解的质量好和缺点如忽略了某些实际约束、对大规模问题求解慢。提出可能的改进方向并简要说明模型可以推广到哪些类似场景。5.2 可视化让你的结果“活”起来在Python中可以使用matplotlib的mpl_toolkits.mplot3d模块进行简单的3D绘图。import matplotlib.pyplot as plt from mpl_toolkits.mplot3d.art3d import Poly3DCollection import numpy as np def plot_bin_packing(bin, items_info): fig plt.figure(figsize(10, 8)) ax fig.add_subplot(111, projection3d) # 绘制箱子轮廓 # 略... # 为每个物品绘制长方体 colors plt.cm.tab20(np.linspace(0, 1, len(items_info))) for idx, info in enumerate(items_info): item info[item] x, y, z info[position] l, w, h item.get_dimensions(info[orientation]) # 定义长方体的8个顶点 vertices np.array([ [x, y, z], [xl, y, z], [xl, yw, z], [x, yw, z], [x, y, zh], [xl, y, zh], [xl, yw, zh], [x, yw, zh] ]) # 定义组成长方体的6个面 faces [ [vertices[0], vertices[1], vertices[2], vertices[3]], # 底面 [vertices[4], vertices[5], vertices[6], vertices[7]], # 顶面 [vertices[0], vertices[1], vertices[5], vertices[4]], # 前面 [vertices[2], vertices[3], vertices[7], vertices[6]], # 后面 [vertices[1], vertices[2], vertices[6], vertices[5]], # 右面 [vertices[0], vertices[3], vertices[7], vertices[4]] # 左面 ] # 绘制 ax.add_collection3d(Poly3DCollection(faces, facecolorscolors[idx], linewidths1, edgecolorsk, alpha0.8)) ax.set_xlabel(Length) ax.set_ylabel(Width) ax.set_zlabel(Height) ax.set_xlim(0, bin.L) ax.set_ylim(0, bin.W) ax.set_zlim(0, bin.H) plt.title(f3D Bin Packing Visualization - Bin {bin.id}) plt.show()5.3 灵敏度分析与稳定性讨论这是体现建模思维深度的部分。你可以探讨参数敏感性如果你的算法中有可调参数如遗传算法的种群大小、变异率可以分析这些参数对最终结果箱子数、运行时间的影响。画出一张参数-结果关系图。数据扰动将物品尺寸或重量随机微调例如±5%重新运行算法观察结果的变化。这可以检验算法的鲁棒性。算法对比实现一个简单的基准算法如FFD与你的算法在相同数据上对比。用表格和柱状图展示在箱子数、空间利用率、运行时间上的差异。最后在论文的结尾不要写“通过本文我们...”、“综上所述...”这类套话。可以直接以你对这个问题的体会收尾例如“三维装箱问题是一个充满挑战的优化问题本次实践中我们深刻体会到一个高效的底层放置策略如墙角法配合一个合理的上层搜索框架如启发式构造局部搜索往往能在有限时间内得到令人满意的工程解。未来若考虑物品的承重、稳定性等更多实际约束问题将更加复杂也需要我们设计更精细的模型和算法。” 这样的结尾更自然更像一篇经验分享。