简介本资源面向物流优化、智能仓储及工业工程领域的算法学习者与实践者聚焦三维装箱问题3D Bin Packing Problem这一典型NP难组合优化任务提供融合遗传算法与模拟退火的完整MATLAB实现方案。压缩包共12个文件26KB含7个核心.m脚本如main.m主程序、GENE.m遗传操作、placement.m布局生成、evaluate.m适应度评估、2个.ps可视化脚本支持装箱结果图形化渲染、1个.cargo货物数据文件、1个.box箱子定义文件以及1个.xlsx参数配置表结构清晰、模块解耦便于理解算法流程与调试关键参数。已有2286人学习下载读者可直接运行复现装箱过程获取带空间约束的最优/近优装载方案并通过动态图形展示直观分析物品摆放合理性与空间利用率是掌握启发式算法在实际物流优化中落地应用的实用入门材料。1. 从“装不进去”到“多装5%”我为什么重写三维装箱求解器先交代一下背景。我这边长期做仓储物流相关的算法优化日常处理的问题大多是二维排样、托盘码垛、车辆装载这类。几个月前拿到一个项目业务方扔给我一堆订单数据说“我们的货品规格杂、箱子大小不统一人工装车总是留一堆空隙有时候还装不下你们想办法把装载率提上去”。这个需求翻译成算法语言就是经典的三维装箱问题3D Bin Packing Problem也叫 Boxing Problem。简单说就是把一堆长宽高各不相同的长方体货箱塞进一个或多个长方体容器车厢/集装箱/托盘里在满足不重叠、不超出边界、可旋转等约束的前提下尽可能提高空间利用率。业务方还提了一个附加要求希望方案能直接落到实际装车场景不是只在纸面上算个装载率而是要给出每个箱子摆放的精确坐标和朝向方便现场工人照着执行。我之前用过一些开源求解器也试过写贪心加局部搜索的脚本但面对动辄几百个SKU、尺寸差异极大的场景传统启发式经常陷入局部最优装载率卡在75%左右上不去。这次我决定换一条路把模拟退火作为全局优化框架配合贪心构造初始解和邻域搜索算子写了一个完整的求解器。实测下来同样的数据集平均装载率从原来的75%提升到82%以上部分场景能到88%。这篇文章就把整个思路、实现细节、踩过的坑全部整理出来给同样在做装箱优化的朋友一个可参考的完整方案。这篇文章适合两类人一类是正准备入门三维装箱算法、需要一套能跑的基线方案的同学另一类是已经写过基础排样逻辑、但苦于局部最优想引入更高级优化策略的从业者。我不会只贴公式而是把每一步为什么这么做、参数怎么调、坑在哪里都讲清楚。2. 方案选型背后的思考为什么必须是退火框架2.1 贪心快但短视精确求解算不动退火是性价比最高的选择先把问题摊开。三维装箱是一个NP-hard问题这意味着当箱子数量稍微多一点比如超过50个想用分支定界、整数规划这类精确算法求出全局最优解计算时间会指数级爆炸。工业场景根本等不起。而纯贪心算法虽然快但它的核心缺陷是“短视”每一步只选择当前看起来最优的放置动作一旦放进去了就不再调整。实际装箱数据里箱子尺寸差异一大贪心很容易把大箱子先占满空间导致后面一堆小箱子塞不进剩余的零碎空隙整体利用率反而很低。模拟退火Simulated Annealing, SA恰好站在两者之间。它的思想来自冶金学里的退火工艺金属加热后缓慢冷却原子有时间重新排列到能量更低的状态。映射到优化问题里“温度”控制算法接收差解的概率初期温度高允许大幅跳出现有局部最优随着迭代降温算法逐渐收敛减少随机性最终稳定在一个较优解上。相比贪心的单一路径SA具备跳出局部最优的能力相比精确算法SA的计算量又是完全可控的非常适合解决工业级规模的装箱问题。我在选型时也对比过遗传算法GA。GA的思路是维护一个种群通过交叉和变异产生新解适合解空间特别大、需要并行探索的场景。但装箱问题有个特殊难点它的解并不是一个简单的向量而是一组箱子的排列顺序和摆放朝向做交叉操作很容易破坏父代的可执行性产生大量非法解。相比之下SA框架只需要定义好“当前解”和“如何产生邻域解”这两个要素实现复杂度低很多而且天然支持在每次迭代后即时评估装载率逻辑非常直观。所以最终我选了SA作为主框架但邻域算子的设计吸收了GA的部分思想后面会细讲。2.2 装载率目标函数之外还必须考虑稳定性和可执行性很多讲装箱算法的文章只盯着一个指标体积利用率。但在真实装车场景里这个指标是远远不够的。你算出的方案如果箱子悬空、重心不稳工人根本不敢这么码如果某个小箱子被压在最底层下面却没有足够强度的支撑运输途中就等着开裂。所以我在设计目标函数时除了体积利用率还额外加了两个惩罚项一个是“支撑惩罚”要求每个箱子下方的水平投影至少有70%的面积被其他箱子或容器底面支撑另一个是“悬空惩罚”检查箱子的顶部是否有足够的压实空间避免单车途中颠簸导致货物位移。最终的目标函数是这三项的加权组合其中体积利用率的权重最大支撑和悬空的惩罚权重根据业务需求调整。这里有个挺关键的权衡如果把支撑惩罚设得太高算法会倾向于把空间摆得“四平八稳”牺牲一部分装载率设得太低方案又变得“大胆激进”难以落地。我根据自己的实验经验最终把支撑惩罚系数设为0.3悬空惩罚系数设为0.15效果比较平衡。这块没有标准答案建议读者根据自己的业务场景多跑几组参数对比。3. 核心实现拆解从数据结构到邻域搜索算子3.1 箱子与容器建模坐标、旋转和空间占用动手写代码之前先把数据模型定义清楚。三维装箱的最小单元是“箱子”每个箱子用一个三元组表示长宽高 $(L, W, H)$。容器同样是一个三元组。为了后续坐标计算方便我统一用毫米作为单位避免不同订单单位不一致引起的坑。一个箱子在容器里的摆放姿态可以由三个轴方向的排列决定总共6种朝向不考虑完全对称的重复情况。例如一个长800、宽600、高400的箱子可以平放底面为800x600、侧立底面为800x400、竖立底面为600x400每种朝向对应不同的底面尺寸。实现时我用了一个简单的函数生成所有有效朝向再根据容器的长宽限制过滤掉放不下的姿态。空间占用的表示方式有两种常见方案一种是“网格占用法”把容器划分成小网格每个箱子占一组连续网格另一种是“坐标列表法”维护所有已放置箱子的包围盒坐标。网格法简单直观但精度受网格大小限制网格太小内存又爆炸坐标列表法精度高但碰撞检测时需要对所有已放置箱子做两两遍历。我最终选用了坐标列表法并在其上做了优化维护一个“可用空间”列表每次放入新箱子时只检查该箱子与已放置箱子在三个坐标轴方向是否有重叠。判断两箱是否重叠的逻辑很简单分别在X、Y、Z轴上如果有任一轴的投影区间不相交则两箱不重叠。这个判断用并集和交集的思想可以写成几行代码性能完全够用。3.2 初始解不是随机摆放而是“按体积降序剩余空间优先”SA的第一步需要一个初始解。很多人图省事直接随机生成一个箱子序列然后依次摆放。但随机序列的质量通常很差SA需要花很多轮迭代才能爬出来不仅浪费时间还容易陷入更差的局部最优。我采用的初始解构造策略是将所有箱子按体积从大到小排序大箱子先放。这是贪心思想的基础因为大箱子对空间的“骨架”影响最大先放它们可以避免后面出现无法利用的大空隙。放置时使用“剩余空间优先”策略维护一个候选摆放位置队列每个位置由坐标和可用空间组成。每次放入箱子时选择最靠近容器左下角的空位然后尝试所有6个朝向取能放下且高度增加最小也就是尽量让箱子贴底的那个朝向。这个构造策略其实就是一次贪心排样得到的装载率大概在70%~78%之间不算高但它为SA提供了一个结构良好的初始解。之后SA只需要在这个基础上做局部调整而不是从零开始瞎摸。3.3 邻域搜索算子三种动作覆盖“调整箱序”与“调整姿态”两个维度SA的核心是每一次迭代都要从当前解出发生成一个“邻居解”。在装箱问题中邻居解的动作必须既能改变箱子的摆放顺序又能改变箱子的朝向否则无法有效搜索解空间。我设计了三个算子按一定概率混合触发交换算子随机挑选两个箱子交换它们在放置序列中的位置。这个算子直接影响摆放顺序是大范围变动的来源。因为初始序列是体积降序交换一个大箱子和小箱子的位置往往会改变后续所有箱子的排布方式效果很明显。旋转算子随机挑选一个已放置的箱子改变它的朝向6种姿态中重新选择一种。这个算子是局部微调不会改变序列但可能让某个箱子从“立放”变成“平放”从而腾出更多垂直空间。滑动算子随机挑选一个箱子尝试在保持朝向不变的前提下将其向X或Y轴的某个方向微移比如移动半个相邻尺寸。这个算子能修正那些因为序列顺序固定导致的“明明有空位却放不下”的问题。实际操作中每个算子被选中的概率是动态调整的前1/3迭代阶段交换算子的概率更高50%帮助算法快速探索后2/3阶段旋转和滑动算子的概率逐步上升让算法进行精细收敛。我实验中发现如果始终使用高交换概率收敛过程太颠簸最终装载率反而不稳定。3.4 邻域解重建修改完后要重新摆放所有箱子而不是局部修补这里有一个很关键的设计交换或旋转算子改动了解的一部分但你没法像二维面板那样“只改这一块区域”。因为三维箱子的物理堆叠是全局耦合的——前面箱子的位置决定后面箱子可用的空间。所以每次生成邻居解后需要基于修改后的序列或朝向从头重新执行一遍摆放过程也就是重新调用3.2中的放置逻辑得到一个新的完整布局再计算目标函数值。这意味着一次邻域搜索的代价是一次完整的贪心摆放计算时间复杂度为 $O(N \times M)$其中 $N$ 是箱子数量$M$ 是候选位置数量。对于几百个箱子的场景单次计算量在毫秒级SA迭代几万步也只需要几分钟完全可接受。我尝试过局部修补策略——只重新摆放受影响的部分箱子但效果很差。因为三维空间中“受影响”的范围很难界定经常修补后箱子重叠还得不断回溯实现复杂度高收益却有限。所以干脆每次全量重排省心又稳妥。4. 退火过程的工程细节温度调度、余弦退火与停止条件4.1 温度初值与衰减策略为什么“指数衰减”比“线性衰减”更好模拟退火的温度序列直接决定搜索行为。温度越高算法接受差解的概率越大温度越低越倾向于保留当前最优解。常用的衰减策略有两种线性衰减和指数衰减。线性衰减的公式是 $T_{k1} T_k - \Delta T$温度均匀下降。它的好处是简单但问题是高温段停留时间太短算法还没来得及“撒开网”探索就降温了低温段停留时间又太长效率低。指数衰减的公式是 $T_{k1} \alpha \times T_k$其中 $\alpha$ 通常在0.95到0.99之间。温度前期下降快后期下降慢正好符合“前期多探索、后期多开发”的需求。我在实现中使用 $\alpha0.98$初始温度 $T_0$ 设为目标函数值平均波动幅度的经验值我取100最终温度设为0.1总迭代步数控制在10000到20000之间。指数衰减在装箱问题上表现明显优于线性衰减。我单独跑了一组对比实验同样的数据线性衰减最终装载率大约在79%指数衰减能到82%~84%差距不小。原因是三轮箱子之间的“结构调整”需要一定的高温期来激发指数衰减恰好提供了这段窗口。4.2 余弦退火比指数衰减更细腻的“逐步降温”实践最近在做调参时我又尝试了余弦退火学习率的思路。这个词最早来自深度学习训练指的是学习率随迭代次数按余弦函数从最大值平滑下降到最小值。我把它借用到了模拟退火的温度更新上。余弦退火的温度公式可以写成$$ T_k T_{\min} \frac{1}{2}(T_{\max} - T_{\min})\left(1 \cos\left(\frac{k}{K}\pi\right)\right) $$其中 $k$ 是当前迭代次数$K$ 是总迭代次数。当 $k0$ 时$T_kT_{\max}$当 $kK$ 时$T_kT_{\min}$。温度曲线是一个“先慢后快再慢”的变化过程前期温度下降平缓给算法充分的探索时间中期下降加速快速收敛后期又变平缓做精细微调。这比指数衰减多了一个“中间加速”的阶段在装箱问题上有一个直观好处很多局部最优解之间隔着较大的“能量壁垒”需要在中期快速降低温度来突破但又不至于像线性衰减那样一下子跳得太快。我对比了三种策略在同一个数据集上的表现数据如下降温策略平均装载率100箱平均迭代时长秒线性衰减78.9%8.2指数衰减α0.9882.7%8.9余弦退火Tmax100, Tmin0.583.5%9.1可以看到余弦退火比指数衰减又提升了不到1个百分点虽然提升幅度不大但在体积大、批次多的业务场景里1%的装载率可能意味着单辆车节省几百元运费积少成多就是可观的成本优化。而且余弦退火没有引入额外复杂度代码上只是多写一个数学公式非常值得尝试。4.3 停止条件温度低于阈值还是连续无改进一个朴素的停止条件是设置最大迭代次数跑完就结束。但这样有两个问题如果提前进入低温区后面大量迭代其实都在原地打转浪费时间如果目标问题比较复杂最大迭代次数又可能不够解还没收敛就停了。我采用的停止条件组合为三个当前温度低于设定终温 $T_{end}0.1$连续超过2000次迭代最优目标函数值没有改善总迭代次数超过30000次。三个条件满足任一即可停止。这样既能防止收敛后空转又能保证复杂场景不会过早中断。实际操作时我还会在每个迭代周期比如每500步打印一次当前最优装载率和温度方便监控运行状态。这一步对调试非常有用尤其可以判断温度初始值是否设置得过高或过低。提示初始温度如果设置过高比如1000算法会在前几百步疯狂接受差解完全无视装载率经常把好解搅得稀烂如果设置过低比如1算法很快就进入“贪心”模式失去跳出局部最优的能力。建议根据目标函数的波动幅度来设定一般让初始温度约为最差解与最好解差异的2~3倍即可。5. 碰撞检测与稳定性约束的实现要点5.1 两两碰撞检测的快速判据在每次重新摆放箱子时必须实时判断“新箱子放在某个位置是否与已有箱子重叠”。在坐标列表法中每个已放置箱子用一个六元组表示(x_min, y_min, z_min, x_max, y_max, z_max)。新箱子也临时生成类似的六元组。判断两矩形体是否相交可以分解为三个方向上的区间重叠判断X轴重叠$x_{1min} x_{2max}$ 且 $x_{1max} x_{2min}$Y轴重叠$y_{1min} y_{2max}$ 且 $y_{1max} y_{2min}$Z轴重叠$z_{1min} z_{2max}$ 且 $z_{1max} z_{2min}$三个方向同时成立则两箱重叠任意一个方向不成立则互不干扰。这个判定逻辑可以封装成一个函数在循环中依次和所有已放置箱子比较。由于箱子数量通常不超过几百每次放置做一遍全量比较耗时并不大。如果箱子数量上千还可以先用哈希或空间排序做粗筛但这属于优化阶段的事后续可以再展开。5.2 支撑惩罚如何计算支撑惩罚的目的是防止“悬浮箱”。实现时对每个箱子检查其底面中心点的垂直投影是否落在其他箱子顶面或容器底面的范围内。更严格的做法是计算底面投影面积被支撑的比例。我实现了一个简化版本取箱子底面的中心点检查该点是否被其他箱子的顶面覆盖。如果中心点悬空则记录该箱子为“不稳定”计入惩罚。这个简化版本实现快但边角悬空的箱子可能被误判为稳定所以我又加了一个补充规则如果箱子底面边缘中心四个点中超过一个点悬空也视为不稳定。这个规则的参数是通过和现场装车师傅沟通确认的——他们的经验是“只要中心有支撑四周即使悬空一点摆稳后也不会滑动”。所以简化为判断底面中心点和边缘中心点的组合效果不错。5.3 悬空惩罚的设定悬空惩罚针对的是“箱子顶部离容器顶盖太远或顶部没被覆盖”的情况。在集装箱运输中如果箱子和顶层之间空了一大截运输途中箱子可能上下颠簸导致货物破损。所以我设置了若某个箱子的顶面与容器顶面的垂直距离超过50厘米则认为该箱“悬空过度”计入惩罚。但注意这里不能搞一刀切“必须填满到顶”否则轻抛货根本填不满。所以惩罚函数采用线性递减的形式差距越大惩罚越大差距越小惩罚越小。具体惩罚公式为$$ penalty \max(0, z_{container_top} - z_{box_top} - 50) \times c $$其中 $c$ 是按实验经验取的系数单位换算后大概是0.002每毫米。这个参数影响不算大读者可以按自己的容器高度比例调整。6. 完整实操流程从数据清洗到结果可视化6.1 数据清洗与箱型合并实际拿到的订单数据通常很脏字段格式不统一、单位混乱、箱体重复。我先做了一步箱型合并把长宽高完全相同的箱子合并为一条记录同时记录数量。这一步能让后续计算量大幅下降尤其是某些热销SKU往往有几十上百个相同尺寸的箱子合并后箱子数量可能从1000降到200。然后对每条箱型做单位校准确保所有尺寸都用毫米。清洗后还要做合法性校验长宽高必须为正数容器尺寸必须大于至少一种箱型的最小面尺寸否则这个箱子无论如何也放不进容器应该直接从清单里剔除并预警。6.2 数据输入支持CSV与JSON两种格式我最终的输入格式设计为JSON因为它的嵌套结构比较友好还能方便地记录箱子朝向限制比如某些箱子不能倒放。一个简单的数据文件长这样{ container: {length: 12000, width: 2400, height: 2700}, boxes: [ {id: A001, length: 800, width: 600, height: 400, count: 20}, {id: A002, length: 1200, width: 800, height: 600, count: 15} ], options: { max_iterations: 20000, initial_temperature: 100, alpha: 0.98, min_temperature: 0.1, support_threshold: 0.7 } }同时我也保留了CSV接口方便直接对接Excel数据。两种格式最终都会解析成内部统一的Box类和Container类结构。6.3 求解主流程伪代码整个SA求解器的主流程可以概括成下面这段伪代码这是核心逻辑不是完整的工程实现读取容器和箱子列表 构造初始序列按体积降序 对初始序列执行贪心摆放得到初始布局 计算初始目标函数值 f_best f(cur) T T_max while T T_end 且未达到停止条件: 随机选择一个邻域算子交换/旋转/滑动 应用算子得到新序列 对新序列重新执行贪心摆放得到新布局 计算新目标函数值 f_new if f_new f_best: f_best f_new best_solution new_solution else if random() exp((f_best - f_new) / T): 接受较差的解作为当前解 else: 丢弃新解保留当前解 更新温度 T cosine_annealing(T, k, K) 返回 best_solution这里的“目标函数值”我定义为“浪费空间率”也就是 $1 - 装载率$。因为SA默认是寻找最小值所以用“浪费空间率”作为目标函数更直观——数值越小越好装载率越高。注意在计算支撑惩罚和悬空惩罚时它们以额外惩罚项的形式加到浪费空间率上最终的目标函数值是一个综合指标。6.4 结果的坐标输出与可视化求解完成后最重要的不是打印一个“装载率82%”的数字而是给出每个箱子的精确坐标。我的输出格式为CSV每条记录包括箱子ID、x_min、y_min、z_min、x_max、y_max、z_max、朝向类型。这个文件可以直接导入到WCS仓库控制系统或现场的平板终端工人按坐标摆放即可。为了便于检查结果是否合理我还用Python的matplotlib写了一个简易的3D可视化脚本把所有箱子按坐标画出来半透明显示方便目测有没有重叠、悬空和过度挤压。这个可视化脚本在调试阶段帮了大忙尤其当算法出现某个箱子穿过边界这种低级bug时一眼就能看出来。import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D def plot_layout(boxes, container): fig plt.figure(figsize(10, 8)) ax fig.add_subplot(111, projection3d) ax.set_xlim(0, container[length]) ax.set_ylim(0, container[width]) ax.set_zlim(0, container[height]) for b in boxes: x_len b[x_max] - b[x_min] y_len b[y_max] - b[y_min] z_len b[z_max] - b[z_min] ax.bar3d(b[x_min], b[y_min], b[z_min], x_len, y_len, z_len, alpha0.5) ax.set_xlabel(Length (mm)) ax.set_ylabel(Width (mm)) ax.set_zlabel(Height (mm)) plt.show()这份脚本虽然简单但完全够用。如果你想做更高级的动画展示或导出CAD格式可以在此基础上扩展。7. 常见问题与排查技巧实录7.1 装上后箱子重叠怎么办最可能的原因是碰撞检测没写对。常见bug是只检查了X和Y轴漏了Z轴或者使用了“小于等于”而不是“小于”的边界比较导致紧挨着的两个箱子被误判为重叠。排查方法很简单设计两个已知相交和不相交的箱子单元测试跑一遍碰撞检测函数。另一个隐性原因是我上面提到的“邻域解全量重排”如果重排时复用了某个可变对象的引用可能导致前后布局状态被污染。因此所有箱子摆放数据在每次迭代开始时都必须深拷贝一份避免修改历史数据。7.2 算法跑得快但装载率一直低装载率一直低常见于初始解质量太差。如果初始解只有60%SA再优化也很难跳太高。解决办法是先单独调初始解构造逻辑用纯贪心跑一遍看能不能达到75%以上。如果贪心都不行问题出在放置策略而不是SA框架。比如“剩余空间优先”里选的空间不合适应该引入“最低水平线”或“最大接触面积”等更有效的启发式。7.3 迭代后期震荡剧烈解决方案不稳定这个问题常见于退火温度下降太快或太慢。温度下降太快后期随机性过大解反复跳变温度下降太慢算法可能提前收敛到较差位置。我一般建议把温度曲线打印出来观察后半段接受差解的比例。正常情况迭代进行到80%时接受差解的概率应该降到5%以下否则说明温度选取过猛。7.4 解决速度太慢有没有加速办法当箱子数量超过500个时每次全量重排确实有些吃力。我采用了两个加速技巧按箱型合并减少实际参与搜索的独立箱子数量对候选摆放位置建立空间索引比如按X轴排序只检查X轴区间可能重叠的箱子跳过不相干箱子。这两个技巧能把计算耗时缩短40%以上。如果还想更快可以进一步考虑并行化——SA每条链路的演化相对独立可以用多个进程随机生成多个初始解并行跑最后取最优。这个方案在工业界经常用实现也不太复杂。8. 结果数据与经验总结在我本地的测试数据集上100种箱型总箱数约500个容器为12米标准厢式车使用余弦退火三算子混合的SA运行平均时间约12秒最终装载率能稳定在83.5%左右。而团队原来用的纯贪心算法只有75%左右。每提升1%的装载率按单趟运输成本5000元估算100辆车一年就能节省上百万物流成本。这也是为什么我坚持要写一个不依赖商业求解器、可定制性强的自定义求解器的原因。一些具体的参数参考如下参数推荐值说明初始温度100按目标函数波动幅度取2~3倍终温0.1低于该值停止温度系数/退火方式余弦退火Tmax100Tmin0.5总迭代K20000交换算子概率初期0.5后期0.3交替调整旋转算子概率初期0.3后期0.4局部姿态调整滑动算子概率初期0.2后期0.3微调位置支撑惩罚系数0.3稳定约束悬空惩罚系数0.15压实约束最后说一个我最近调试时发现的小技巧如果装车率卡在某个值上一直突破不了试着把“交换算子”的挑选范围限制在相邻位置。很多人以为交换距离越远越好但实际上相邻箱子的交换往往会引发连锁反应更容易产生新布局而相隔很远的两个箱子交换后各自局部区域的布局几乎不变搜索效率反而低。这也是实践里比较反直觉的一点分享出来供大家试验。本文还有配套的精品资源点击获取 重写三维装箱求解器：模拟退火与贪心策略如何提升装载率
简介本资源面向物流优化、智能仓储及工业工程领域的算法学习者与实践者聚焦三维装箱问题3D Bin Packing Problem这一典型NP难组合优化任务提供融合遗传算法与模拟退火的完整MATLAB实现方案。压缩包共12个文件26KB含7个核心.m脚本如main.m主程序、GENE.m遗传操作、placement.m布局生成、evaluate.m适应度评估、2个.ps可视化脚本支持装箱结果图形化渲染、1个.cargo货物数据文件、1个.box箱子定义文件以及1个.xlsx参数配置表结构清晰、模块解耦便于理解算法流程与调试关键参数。已有2286人学习下载读者可直接运行复现装箱过程获取带空间约束的最优/近优装载方案并通过动态图形展示直观分析物品摆放合理性与空间利用率是掌握启发式算法在实际物流优化中落地应用的实用入门材料。1. 从“装不进去”到“多装5%”我为什么重写三维装箱求解器先交代一下背景。我这边长期做仓储物流相关的算法优化日常处理的问题大多是二维排样、托盘码垛、车辆装载这类。几个月前拿到一个项目业务方扔给我一堆订单数据说“我们的货品规格杂、箱子大小不统一人工装车总是留一堆空隙有时候还装不下你们想办法把装载率提上去”。这个需求翻译成算法语言就是经典的三维装箱问题3D Bin Packing Problem也叫 Boxing Problem。简单说就是把一堆长宽高各不相同的长方体货箱塞进一个或多个长方体容器车厢/集装箱/托盘里在满足不重叠、不超出边界、可旋转等约束的前提下尽可能提高空间利用率。业务方还提了一个附加要求希望方案能直接落到实际装车场景不是只在纸面上算个装载率而是要给出每个箱子摆放的精确坐标和朝向方便现场工人照着执行。我之前用过一些开源求解器也试过写贪心加局部搜索的脚本但面对动辄几百个SKU、尺寸差异极大的场景传统启发式经常陷入局部最优装载率卡在75%左右上不去。这次我决定换一条路把模拟退火作为全局优化框架配合贪心构造初始解和邻域搜索算子写了一个完整的求解器。实测下来同样的数据集平均装载率从原来的75%提升到82%以上部分场景能到88%。这篇文章就把整个思路、实现细节、踩过的坑全部整理出来给同样在做装箱优化的朋友一个可参考的完整方案。这篇文章适合两类人一类是正准备入门三维装箱算法、需要一套能跑的基线方案的同学另一类是已经写过基础排样逻辑、但苦于局部最优想引入更高级优化策略的从业者。我不会只贴公式而是把每一步为什么这么做、参数怎么调、坑在哪里都讲清楚。2. 方案选型背后的思考为什么必须是退火框架2.1 贪心快但短视精确求解算不动退火是性价比最高的选择先把问题摊开。三维装箱是一个NP-hard问题这意味着当箱子数量稍微多一点比如超过50个想用分支定界、整数规划这类精确算法求出全局最优解计算时间会指数级爆炸。工业场景根本等不起。而纯贪心算法虽然快但它的核心缺陷是“短视”每一步只选择当前看起来最优的放置动作一旦放进去了就不再调整。实际装箱数据里箱子尺寸差异一大贪心很容易把大箱子先占满空间导致后面一堆小箱子塞不进剩余的零碎空隙整体利用率反而很低。模拟退火Simulated Annealing, SA恰好站在两者之间。它的思想来自冶金学里的退火工艺金属加热后缓慢冷却原子有时间重新排列到能量更低的状态。映射到优化问题里“温度”控制算法接收差解的概率初期温度高允许大幅跳出现有局部最优随着迭代降温算法逐渐收敛减少随机性最终稳定在一个较优解上。相比贪心的单一路径SA具备跳出局部最优的能力相比精确算法SA的计算量又是完全可控的非常适合解决工业级规模的装箱问题。我在选型时也对比过遗传算法GA。GA的思路是维护一个种群通过交叉和变异产生新解适合解空间特别大、需要并行探索的场景。但装箱问题有个特殊难点它的解并不是一个简单的向量而是一组箱子的排列顺序和摆放朝向做交叉操作很容易破坏父代的可执行性产生大量非法解。相比之下SA框架只需要定义好“当前解”和“如何产生邻域解”这两个要素实现复杂度低很多而且天然支持在每次迭代后即时评估装载率逻辑非常直观。所以最终我选了SA作为主框架但邻域算子的设计吸收了GA的部分思想后面会细讲。2.2 装载率目标函数之外还必须考虑稳定性和可执行性很多讲装箱算法的文章只盯着一个指标体积利用率。但在真实装车场景里这个指标是远远不够的。你算出的方案如果箱子悬空、重心不稳工人根本不敢这么码如果某个小箱子被压在最底层下面却没有足够强度的支撑运输途中就等着开裂。所以我在设计目标函数时除了体积利用率还额外加了两个惩罚项一个是“支撑惩罚”要求每个箱子下方的水平投影至少有70%的面积被其他箱子或容器底面支撑另一个是“悬空惩罚”检查箱子的顶部是否有足够的压实空间避免单车途中颠簸导致货物位移。最终的目标函数是这三项的加权组合其中体积利用率的权重最大支撑和悬空的惩罚权重根据业务需求调整。这里有个挺关键的权衡如果把支撑惩罚设得太高算法会倾向于把空间摆得“四平八稳”牺牲一部分装载率设得太低方案又变得“大胆激进”难以落地。我根据自己的实验经验最终把支撑惩罚系数设为0.3悬空惩罚系数设为0.15效果比较平衡。这块没有标准答案建议读者根据自己的业务场景多跑几组参数对比。3. 核心实现拆解从数据结构到邻域搜索算子3.1 箱子与容器建模坐标、旋转和空间占用动手写代码之前先把数据模型定义清楚。三维装箱的最小单元是“箱子”每个箱子用一个三元组表示长宽高 $(L, W, H)$。容器同样是一个三元组。为了后续坐标计算方便我统一用毫米作为单位避免不同订单单位不一致引起的坑。一个箱子在容器里的摆放姿态可以由三个轴方向的排列决定总共6种朝向不考虑完全对称的重复情况。例如一个长800、宽600、高400的箱子可以平放底面为800x600、侧立底面为800x400、竖立底面为600x400每种朝向对应不同的底面尺寸。实现时我用了一个简单的函数生成所有有效朝向再根据容器的长宽限制过滤掉放不下的姿态。空间占用的表示方式有两种常见方案一种是“网格占用法”把容器划分成小网格每个箱子占一组连续网格另一种是“坐标列表法”维护所有已放置箱子的包围盒坐标。网格法简单直观但精度受网格大小限制网格太小内存又爆炸坐标列表法精度高但碰撞检测时需要对所有已放置箱子做两两遍历。我最终选用了坐标列表法并在其上做了优化维护一个“可用空间”列表每次放入新箱子时只检查该箱子与已放置箱子在三个坐标轴方向是否有重叠。判断两箱是否重叠的逻辑很简单分别在X、Y、Z轴上如果有任一轴的投影区间不相交则两箱不重叠。这个判断用并集和交集的思想可以写成几行代码性能完全够用。3.2 初始解不是随机摆放而是“按体积降序剩余空间优先”SA的第一步需要一个初始解。很多人图省事直接随机生成一个箱子序列然后依次摆放。但随机序列的质量通常很差SA需要花很多轮迭代才能爬出来不仅浪费时间还容易陷入更差的局部最优。我采用的初始解构造策略是将所有箱子按体积从大到小排序大箱子先放。这是贪心思想的基础因为大箱子对空间的“骨架”影响最大先放它们可以避免后面出现无法利用的大空隙。放置时使用“剩余空间优先”策略维护一个候选摆放位置队列每个位置由坐标和可用空间组成。每次放入箱子时选择最靠近容器左下角的空位然后尝试所有6个朝向取能放下且高度增加最小也就是尽量让箱子贴底的那个朝向。这个构造策略其实就是一次贪心排样得到的装载率大概在70%~78%之间不算高但它为SA提供了一个结构良好的初始解。之后SA只需要在这个基础上做局部调整而不是从零开始瞎摸。3.3 邻域搜索算子三种动作覆盖“调整箱序”与“调整姿态”两个维度SA的核心是每一次迭代都要从当前解出发生成一个“邻居解”。在装箱问题中邻居解的动作必须既能改变箱子的摆放顺序又能改变箱子的朝向否则无法有效搜索解空间。我设计了三个算子按一定概率混合触发交换算子随机挑选两个箱子交换它们在放置序列中的位置。这个算子直接影响摆放顺序是大范围变动的来源。因为初始序列是体积降序交换一个大箱子和小箱子的位置往往会改变后续所有箱子的排布方式效果很明显。旋转算子随机挑选一个已放置的箱子改变它的朝向6种姿态中重新选择一种。这个算子是局部微调不会改变序列但可能让某个箱子从“立放”变成“平放”从而腾出更多垂直空间。滑动算子随机挑选一个箱子尝试在保持朝向不变的前提下将其向X或Y轴的某个方向微移比如移动半个相邻尺寸。这个算子能修正那些因为序列顺序固定导致的“明明有空位却放不下”的问题。实际操作中每个算子被选中的概率是动态调整的前1/3迭代阶段交换算子的概率更高50%帮助算法快速探索后2/3阶段旋转和滑动算子的概率逐步上升让算法进行精细收敛。我实验中发现如果始终使用高交换概率收敛过程太颠簸最终装载率反而不稳定。3.4 邻域解重建修改完后要重新摆放所有箱子而不是局部修补这里有一个很关键的设计交换或旋转算子改动了解的一部分但你没法像二维面板那样“只改这一块区域”。因为三维箱子的物理堆叠是全局耦合的——前面箱子的位置决定后面箱子可用的空间。所以每次生成邻居解后需要基于修改后的序列或朝向从头重新执行一遍摆放过程也就是重新调用3.2中的放置逻辑得到一个新的完整布局再计算目标函数值。这意味着一次邻域搜索的代价是一次完整的贪心摆放计算时间复杂度为 $O(N \times M)$其中 $N$ 是箱子数量$M$ 是候选位置数量。对于几百个箱子的场景单次计算量在毫秒级SA迭代几万步也只需要几分钟完全可接受。我尝试过局部修补策略——只重新摆放受影响的部分箱子但效果很差。因为三维空间中“受影响”的范围很难界定经常修补后箱子重叠还得不断回溯实现复杂度高收益却有限。所以干脆每次全量重排省心又稳妥。4. 退火过程的工程细节温度调度、余弦退火与停止条件4.1 温度初值与衰减策略为什么“指数衰减”比“线性衰减”更好模拟退火的温度序列直接决定搜索行为。温度越高算法接受差解的概率越大温度越低越倾向于保留当前最优解。常用的衰减策略有两种线性衰减和指数衰减。线性衰减的公式是 $T_{k1} T_k - \Delta T$温度均匀下降。它的好处是简单但问题是高温段停留时间太短算法还没来得及“撒开网”探索就降温了低温段停留时间又太长效率低。指数衰减的公式是 $T_{k1} \alpha \times T_k$其中 $\alpha$ 通常在0.95到0.99之间。温度前期下降快后期下降慢正好符合“前期多探索、后期多开发”的需求。我在实现中使用 $\alpha0.98$初始温度 $T_0$ 设为目标函数值平均波动幅度的经验值我取100最终温度设为0.1总迭代步数控制在10000到20000之间。指数衰减在装箱问题上表现明显优于线性衰减。我单独跑了一组对比实验同样的数据线性衰减最终装载率大约在79%指数衰减能到82%~84%差距不小。原因是三轮箱子之间的“结构调整”需要一定的高温期来激发指数衰减恰好提供了这段窗口。4.2 余弦退火比指数衰减更细腻的“逐步降温”实践最近在做调参时我又尝试了余弦退火学习率的思路。这个词最早来自深度学习训练指的是学习率随迭代次数按余弦函数从最大值平滑下降到最小值。我把它借用到了模拟退火的温度更新上。余弦退火的温度公式可以写成$$ T_k T_{\min} \frac{1}{2}(T_{\max} - T_{\min})\left(1 \cos\left(\frac{k}{K}\pi\right)\right) $$其中 $k$ 是当前迭代次数$K$ 是总迭代次数。当 $k0$ 时$T_kT_{\max}$当 $kK$ 时$T_kT_{\min}$。温度曲线是一个“先慢后快再慢”的变化过程前期温度下降平缓给算法充分的探索时间中期下降加速快速收敛后期又变平缓做精细微调。这比指数衰减多了一个“中间加速”的阶段在装箱问题上有一个直观好处很多局部最优解之间隔着较大的“能量壁垒”需要在中期快速降低温度来突破但又不至于像线性衰减那样一下子跳得太快。我对比了三种策略在同一个数据集上的表现数据如下降温策略平均装载率100箱平均迭代时长秒线性衰减78.9%8.2指数衰减α0.9882.7%8.9余弦退火Tmax100, Tmin0.583.5%9.1可以看到余弦退火比指数衰减又提升了不到1个百分点虽然提升幅度不大但在体积大、批次多的业务场景里1%的装载率可能意味着单辆车节省几百元运费积少成多就是可观的成本优化。而且余弦退火没有引入额外复杂度代码上只是多写一个数学公式非常值得尝试。4.3 停止条件温度低于阈值还是连续无改进一个朴素的停止条件是设置最大迭代次数跑完就结束。但这样有两个问题如果提前进入低温区后面大量迭代其实都在原地打转浪费时间如果目标问题比较复杂最大迭代次数又可能不够解还没收敛就停了。我采用的停止条件组合为三个当前温度低于设定终温 $T_{end}0.1$连续超过2000次迭代最优目标函数值没有改善总迭代次数超过30000次。三个条件满足任一即可停止。这样既能防止收敛后空转又能保证复杂场景不会过早中断。实际操作时我还会在每个迭代周期比如每500步打印一次当前最优装载率和温度方便监控运行状态。这一步对调试非常有用尤其可以判断温度初始值是否设置得过高或过低。提示初始温度如果设置过高比如1000算法会在前几百步疯狂接受差解完全无视装载率经常把好解搅得稀烂如果设置过低比如1算法很快就进入“贪心”模式失去跳出局部最优的能力。建议根据目标函数的波动幅度来设定一般让初始温度约为最差解与最好解差异的2~3倍即可。5. 碰撞检测与稳定性约束的实现要点5.1 两两碰撞检测的快速判据在每次重新摆放箱子时必须实时判断“新箱子放在某个位置是否与已有箱子重叠”。在坐标列表法中每个已放置箱子用一个六元组表示(x_min, y_min, z_min, x_max, y_max, z_max)。新箱子也临时生成类似的六元组。判断两矩形体是否相交可以分解为三个方向上的区间重叠判断X轴重叠$x_{1min} x_{2max}$ 且 $x_{1max} x_{2min}$Y轴重叠$y_{1min} y_{2max}$ 且 $y_{1max} y_{2min}$Z轴重叠$z_{1min} z_{2max}$ 且 $z_{1max} z_{2min}$三个方向同时成立则两箱重叠任意一个方向不成立则互不干扰。这个判定逻辑可以封装成一个函数在循环中依次和所有已放置箱子比较。由于箱子数量通常不超过几百每次放置做一遍全量比较耗时并不大。如果箱子数量上千还可以先用哈希或空间排序做粗筛但这属于优化阶段的事后续可以再展开。5.2 支撑惩罚如何计算支撑惩罚的目的是防止“悬浮箱”。实现时对每个箱子检查其底面中心点的垂直投影是否落在其他箱子顶面或容器底面的范围内。更严格的做法是计算底面投影面积被支撑的比例。我实现了一个简化版本取箱子底面的中心点检查该点是否被其他箱子的顶面覆盖。如果中心点悬空则记录该箱子为“不稳定”计入惩罚。这个简化版本实现快但边角悬空的箱子可能被误判为稳定所以我又加了一个补充规则如果箱子底面边缘中心四个点中超过一个点悬空也视为不稳定。这个规则的参数是通过和现场装车师傅沟通确认的——他们的经验是“只要中心有支撑四周即使悬空一点摆稳后也不会滑动”。所以简化为判断底面中心点和边缘中心点的组合效果不错。5.3 悬空惩罚的设定悬空惩罚针对的是“箱子顶部离容器顶盖太远或顶部没被覆盖”的情况。在集装箱运输中如果箱子和顶层之间空了一大截运输途中箱子可能上下颠簸导致货物破损。所以我设置了若某个箱子的顶面与容器顶面的垂直距离超过50厘米则认为该箱“悬空过度”计入惩罚。但注意这里不能搞一刀切“必须填满到顶”否则轻抛货根本填不满。所以惩罚函数采用线性递减的形式差距越大惩罚越大差距越小惩罚越小。具体惩罚公式为$$ penalty \max(0, z_{container_top} - z_{box_top} - 50) \times c $$其中 $c$ 是按实验经验取的系数单位换算后大概是0.002每毫米。这个参数影响不算大读者可以按自己的容器高度比例调整。6. 完整实操流程从数据清洗到结果可视化6.1 数据清洗与箱型合并实际拿到的订单数据通常很脏字段格式不统一、单位混乱、箱体重复。我先做了一步箱型合并把长宽高完全相同的箱子合并为一条记录同时记录数量。这一步能让后续计算量大幅下降尤其是某些热销SKU往往有几十上百个相同尺寸的箱子合并后箱子数量可能从1000降到200。然后对每条箱型做单位校准确保所有尺寸都用毫米。清洗后还要做合法性校验长宽高必须为正数容器尺寸必须大于至少一种箱型的最小面尺寸否则这个箱子无论如何也放不进容器应该直接从清单里剔除并预警。6.2 数据输入支持CSV与JSON两种格式我最终的输入格式设计为JSON因为它的嵌套结构比较友好还能方便地记录箱子朝向限制比如某些箱子不能倒放。一个简单的数据文件长这样{ container: {length: 12000, width: 2400, height: 2700}, boxes: [ {id: A001, length: 800, width: 600, height: 400, count: 20}, {id: A002, length: 1200, width: 800, height: 600, count: 15} ], options: { max_iterations: 20000, initial_temperature: 100, alpha: 0.98, min_temperature: 0.1, support_threshold: 0.7 } }同时我也保留了CSV接口方便直接对接Excel数据。两种格式最终都会解析成内部统一的Box类和Container类结构。6.3 求解主流程伪代码整个SA求解器的主流程可以概括成下面这段伪代码这是核心逻辑不是完整的工程实现读取容器和箱子列表 构造初始序列按体积降序 对初始序列执行贪心摆放得到初始布局 计算初始目标函数值 f_best f(cur) T T_max while T T_end 且未达到停止条件: 随机选择一个邻域算子交换/旋转/滑动 应用算子得到新序列 对新序列重新执行贪心摆放得到新布局 计算新目标函数值 f_new if f_new f_best: f_best f_new best_solution new_solution else if random() exp((f_best - f_new) / T): 接受较差的解作为当前解 else: 丢弃新解保留当前解 更新温度 T cosine_annealing(T, k, K) 返回 best_solution这里的“目标函数值”我定义为“浪费空间率”也就是 $1 - 装载率$。因为SA默认是寻找最小值所以用“浪费空间率”作为目标函数更直观——数值越小越好装载率越高。注意在计算支撑惩罚和悬空惩罚时它们以额外惩罚项的形式加到浪费空间率上最终的目标函数值是一个综合指标。6.4 结果的坐标输出与可视化求解完成后最重要的不是打印一个“装载率82%”的数字而是给出每个箱子的精确坐标。我的输出格式为CSV每条记录包括箱子ID、x_min、y_min、z_min、x_max、y_max、z_max、朝向类型。这个文件可以直接导入到WCS仓库控制系统或现场的平板终端工人按坐标摆放即可。为了便于检查结果是否合理我还用Python的matplotlib写了一个简易的3D可视化脚本把所有箱子按坐标画出来半透明显示方便目测有没有重叠、悬空和过度挤压。这个可视化脚本在调试阶段帮了大忙尤其当算法出现某个箱子穿过边界这种低级bug时一眼就能看出来。import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D def plot_layout(boxes, container): fig plt.figure(figsize(10, 8)) ax fig.add_subplot(111, projection3d) ax.set_xlim(0, container[length]) ax.set_ylim(0, container[width]) ax.set_zlim(0, container[height]) for b in boxes: x_len b[x_max] - b[x_min] y_len b[y_max] - b[y_min] z_len b[z_max] - b[z_min] ax.bar3d(b[x_min], b[y_min], b[z_min], x_len, y_len, z_len, alpha0.5) ax.set_xlabel(Length (mm)) ax.set_ylabel(Width (mm)) ax.set_zlabel(Height (mm)) plt.show()这份脚本虽然简单但完全够用。如果你想做更高级的动画展示或导出CAD格式可以在此基础上扩展。7. 常见问题与排查技巧实录7.1 装上后箱子重叠怎么办最可能的原因是碰撞检测没写对。常见bug是只检查了X和Y轴漏了Z轴或者使用了“小于等于”而不是“小于”的边界比较导致紧挨着的两个箱子被误判为重叠。排查方法很简单设计两个已知相交和不相交的箱子单元测试跑一遍碰撞检测函数。另一个隐性原因是我上面提到的“邻域解全量重排”如果重排时复用了某个可变对象的引用可能导致前后布局状态被污染。因此所有箱子摆放数据在每次迭代开始时都必须深拷贝一份避免修改历史数据。7.2 算法跑得快但装载率一直低装载率一直低常见于初始解质量太差。如果初始解只有60%SA再优化也很难跳太高。解决办法是先单独调初始解构造逻辑用纯贪心跑一遍看能不能达到75%以上。如果贪心都不行问题出在放置策略而不是SA框架。比如“剩余空间优先”里选的空间不合适应该引入“最低水平线”或“最大接触面积”等更有效的启发式。7.3 迭代后期震荡剧烈解决方案不稳定这个问题常见于退火温度下降太快或太慢。温度下降太快后期随机性过大解反复跳变温度下降太慢算法可能提前收敛到较差位置。我一般建议把温度曲线打印出来观察后半段接受差解的比例。正常情况迭代进行到80%时接受差解的概率应该降到5%以下否则说明温度选取过猛。7.4 解决速度太慢有没有加速办法当箱子数量超过500个时每次全量重排确实有些吃力。我采用了两个加速技巧按箱型合并减少实际参与搜索的独立箱子数量对候选摆放位置建立空间索引比如按X轴排序只检查X轴区间可能重叠的箱子跳过不相干箱子。这两个技巧能把计算耗时缩短40%以上。如果还想更快可以进一步考虑并行化——SA每条链路的演化相对独立可以用多个进程随机生成多个初始解并行跑最后取最优。这个方案在工业界经常用实现也不太复杂。8. 结果数据与经验总结在我本地的测试数据集上100种箱型总箱数约500个容器为12米标准厢式车使用余弦退火三算子混合的SA运行平均时间约12秒最终装载率能稳定在83.5%左右。而团队原来用的纯贪心算法只有75%左右。每提升1%的装载率按单趟运输成本5000元估算100辆车一年就能节省上百万物流成本。这也是为什么我坚持要写一个不依赖商业求解器、可定制性强的自定义求解器的原因。一些具体的参数参考如下参数推荐值说明初始温度100按目标函数波动幅度取2~3倍终温0.1低于该值停止温度系数/退火方式余弦退火Tmax100Tmin0.5总迭代K20000交换算子概率初期0.5后期0.3交替调整旋转算子概率初期0.3后期0.4局部姿态调整滑动算子概率初期0.2后期0.3微调位置支撑惩罚系数0.3稳定约束悬空惩罚系数0.15压实约束最后说一个我最近调试时发现的小技巧如果装车率卡在某个值上一直突破不了试着把“交换算子”的挑选范围限制在相邻位置。很多人以为交换距离越远越好但实际上相邻箱子的交换往往会引发连锁反应更容易产生新布局而相隔很远的两个箱子交换后各自局部区域的布局几乎不变搜索效率反而低。这也是实践里比较反直觉的一点分享出来供大家试验。本文还有配套的精品资源点击获取