三维装箱算法实战：启发式、物理约束与装载率优化-北京尧图网络

简介面向物流仓储、制造业排产及算法学习者的三维装箱3D-Bin-PackingJava 实现资料聚焦在有限体积标准箱约束下最大化空间利用率的组合优化问题。资源以 BestFit 动态分配策略为主线先按物体占用空间排序再优先填入已有剩余空间的箱子找不到合适箱体时新开箱从而减少总用箱数。代码中涵盖 ArrayList 等数据结构选型、体积排序算法、箱体集合遍历与插入、放入条件判断与循环控制并涉及对象数量较大时的内存管理、NP 难问题下的复杂度分析以及单元测试验证目录结构便于按模块拆分阅读与复用。压缩包共 313 个文件以 206 个 txt 说明与数据文件、33 个 java 源码、46 个 class 编译文件为主另有 xml、fxml、css 等界面与配置资源整体约 923KB。已有 6741 人学习适合想通过完整项目理解装箱算法落地细节与工程规范的读者参考。1. 三维装箱不是“把箱子塞进去”那么简单托盘还剩 12 厘米高度系统却说装不下换个人手动摆一遍同样的货硬是多塞了 8 箱。这类问题的学名是三维装箱3D Bin Packing而这个压缩包里是一套能直接跑的代码货物与容器的数据结构、贪心/层叠/极值点几类启发式、物理约束钩子、结果校验器和 matplotlib 三维可视化。它不适合想求精确最优解的人适合做车厢配载、托盘排布、集装箱装载率估算的工程场景——先跑通再看装载率能不能从 78% 推到 90%。2. 拆包先看骨架四个模块与一次最小可运行压缩包解开之后不用急着看算法先用十分钟把调用链摸清楚。三维装箱的代码包最容易出的问题不是算法不够好而是坐标系、单位、朝向三套约定各写各的最后可视化画得挺漂亮导出的坐标拿去给现场用却全错位。2.1 目录里有什么模块职责与调用链这类包的目录组织基本是同一套骨架拆开后我一般按下面这张表对号入座缺哪块心里就有数了目录/文件职责是否常改packing/model.pyItem/Bin/Placement数据结构、几何工具少改改要全链路同步packing/heuristics/贪心、层叠shelf/layer、极值点extreme point常改算法选型都在这里packing/constraints.py支撑、重心、重量、朝向限制的钩子常改业务差异最大packing/validate.py越界、重叠、支撑三类校验不改但每次都要跑packing/viz.pymatplotlib 三维立方体绘制按需改配色与标注main.py/cli.py参数入口、实例加载、结果导出常改跑批参数都在这data/JSON/CSV 实例含容器尺寸与货物清单换成自己的数据调用链很线性load_instance → packer.pack → validate → plot / export。真正值得读的只有heuristics和constraints两块其余是胶水代码看一遍知道签名就够了。2.2 一次装箱的数据结构Item、Bin、Placement 与坐标约定先看数据结构因为后面所有坑都从这里冒出来。核心三个类from dataclasses import dataclass from typing import Tuple dataclass(frozenTrue) class Item: id: str size: Tuple[float, float, float] # (长, 宽, 高)单位必须和容器完全一致 weight: float 0.0 # 重心约束要用没有就填 0 allow_rotate: bool True # 易碎面朝上、有液体的货这里关掉 dataclass class Bin: size: Tuple[float, float, float] # 容器内空尺寸别把壁厚算进去 max_weight: float float(inf) # 车厢/托盘有承重上限填上更保险 dataclass class Placement: item_id: str pos: Tuple[float, float, float] # 箱子最小角坐标不是几何中心 axis: Tuple[int, int, int] # 三个边长分别对应原尺寸的哪一维 orientation: int # 0..5六种朝向编号三个约定必须一次讲清否则后面每步都要还债pos记的是箱子的最小角不是中心点。用最小角判重叠只需要比较区间写起来最省事用中心点每次都要减半边长浮点误差翻倍。坐标系是右手系原点在容器的最小角z 轴朝上。可视化、导出、校验三处必须共用同一个原点约定。orientation和axis是同一件事的两种表达。axis便于算尺寸orientation便于限制“只允许水平旋转”。改代码时只改一个另一个用函数推导出来别两处手写。提示单位混用是最高频的翻车点。货物清单常是毫米容器图纸常是厘米两边一混装载率会算出 800% 这种离谱数字而校验器还告诉你“没重叠”。2.3 十分钟跑出第一张三维装箱图环境很轻numpy matplotlib 就够不需要求解器。我一般先建虚拟环境再装避免和系统里的老版本打架# 建环境三维可视化和浮点计算都吃版本别用系统 Python 硬装 python -m venv .venv source .venv/bin/activate # Windows 换成 .venv\Scripts\activate pip install -r requirements.txt # 跑示例实例极值点启发式六向旋转 0.5 单位间隙 python main.py \ --instance data/sample_01.json \ --algo ep \ --rotations 6 \ --gap 0.5 \ --seed 42 \ --viz out/sample_01.png参数逐个说--algo ep选极值点启发式另有greedy最快装载率一般和shelf分层适合规整货物。第一次跑建议用ep能直接看到质量上限。--rotations取1/2/61 完全不转2 只允许绕 z 轴转 90°6 允许任意翻转。取 6 装载率最高但可能把“不可倒置”的货放倒。--gap是货物之间的安全间隙必须和容器同单位。现场装卸要留手的空间0.52 厘米是常见值取 0 会让结果好看但装不进去。--seed别省。贪心本身确定性较强但排序打平、候选点排序一旦掺了随机不固定种子就没法复现也没法对比两次改动谁更好。第一张图出来之后先别急着调算法盯着图看三件事有没有箱子悬空、有没有明显的大块空洞、顶层是不是被一两个大件把空间锁死了。这三眼比看装载率数字有用得多。3. 算法选型贪心、层叠、极值点三条路怎么选包里的算法不止一个选错路线比调错参数损失大得多。同一批货层叠式可能只装到 72%极值点能到 88%但极值点的候选点维护开销是前者的好几倍。选型要看货物尺寸分布和现场作业方式不是看谁的名字高级。3.1 精确解为什么不现实规模与复杂度的硬边界三维装箱是 NP-hard这点不用证明只要看解空间n 个货物有 n! 种装载顺序每个货物最多 6 种朝向再加上容器内的连续坐标变量数量随规模指数增长。用 CP-SAT 或 MIP 建模把坐标离散化成网格、给每个货物一个“落在哪个格点”的 0-1 变量几十个货物加一个容器还能在几分钟内跑出最优解上百个货物时光是模型构建就能把内存吃满。所以工程上的分层很清楚方案可解规模解质量典型耗时适用MIP / CP-SAT2040 件最优或近似最优分钟到小时高价值少量货、方案评审贪心 / 层叠上千件70%85%毫秒到秒在线报价、实时估算极值点启发式几百到上千件82%92%秒级车厢配载、托盘排布启发式局部搜索几百件再涨 25 个点十秒到分钟离线出方案我的习惯是先用极值点跑出基准解把这个装载率当成“这个实例大概能到多少”的心理锚点再去调参数或上局部搜索。上来就写遗传算法多半是在给一个本身只有 75% 上限的编码方式做无用功。3.2 层叠式与极值点两种空间划分思路的取舍层叠式shelf / layer把容器按高度切成若干层每层内部当成二维装箱来做。优点是每一层是平的现场可以整层码放、整层卸货作业效率高缺点是层高由该层最高货物决定矮货上方会浪费一截层数一多浪费就累加。极值点extreme point走的是另一条路每放一个箱子就用它的三个可见面在空间里投影出新的候选放置点维护一个点集每次从点集里挑最靠“左下后”的点放货。它的空间利用率明显更高代价是候选点数量会增长每放一个箱子都要对点集做一次排序和过滤规模大时要加剪枝。选型判断可以简化成两句话货物长宽高差异大、追求装载率选极值点货物规格统一、现场要求分层码放或整托出库选层叠。两者都跑一遍对比装载率花不了几分钟比拍脑袋强。3.3 代码落地一次完整的启发式装箱调用下面这段是典型的调用方式参数名各包略有差异逻辑一致from packing import load_instance, ExtremePointPacker, validate, plot inst load_instance(data/sample_01.json) packer ExtremePointPacker( bin_sizeinst.bin.size, sort_keyvolume_desc, # 也可 maxside_desc / height_desc见 3.4 rotations6, # 允许的朝向数1 / 2 / 6 gap0.5, # 货物之间的安全间隙与容器同单位 support_ratio0.7, # 底面至少 70% 有支撑才允许放 max_weightinst.bin.max_weight, ) res packer.pack(inst.items) # 多容器时内部会自动开新箱 print(f装载率 {res.fill_rate:.3f}使用容器 {len(res.bins)} 个) bad validate(res, inst) # 返回违规项列表空列表才算通过 if bad: for b in bad[:10]: print(违规:, b) plot(res, out/ep_result.png) # 出图先看悬空和大空洞几个点值得展开sort_keyvolume_desc决定放货顺序体积降序是最稳的默认值。大件先放小件才有缝隙可填反过来先放小件大件最后往往找不到连续空间。support_ratio是后面第 4 章要讲的物理约束入口这里先给 0.7。取 1.0 表示必须完全被支撑现场最安全装载率会掉 38 个点取 0 等于允许悬空。pack返回的是多容器解不是单个容器内的布局。判读装载率时要看清分母是所有容器体积之和还是单个容器体积。这个口径不同数字能差一倍。validate一定要跑。启发式为了速度会在候选点过滤上用近似判断浮点误差累积后可能出现 1e-9 级别的“假重叠”校验器用容差过滤掉不然导出时会看到两个箱子贴在一起。3.4 参数怎么调排序策略、旋转集合与间隙参数不多但敏感度差别很大。按我实际调过的经验排个序参数常用取值敏感度调大的后果sort_keyvolume_desc / maxside_desc高换策略比调数值有用值得全试一遍rotations2 或 6高6 提升 410 个点但可能违反朝向限制support_ratio0.71.0中越大越安全装载率下降gap02按单位中间隙翻倍装载率掉 25 个点max_weight按容器标定低但致命不填等于不限制超重方案直接不可用排序策略值得单独说一句volume_desc和maxside_desc在不同实例上互有胜负差 3 个点很常见。我的做法是同一批实例把三种排序都跑一遍记下装载率挑最稳的那个作为默认而不是每次都重新扫。旋转集合则要看货纸箱类大多可以六向翻家电、带压缩机的设备只能立着放这时rotations2不是妥协是硬约束。4. 把物理约束加进去重心、承压与不可翻转只判“不重叠”的装箱结果在纸面上永远漂亮在现场永远不能用。真正决定方案能不能落地的是三条箱子底面积够不够被支撑、整车重心偏不偏、有没有货被放倒。这三条不加装载率再高也只是数字游戏。4.1 三条约束的数学表达支撑约束。箱子 i 放在高度 z 上下方所有顶面与该高度重合的箱子提供的接触面积之和除以 i 的底面积要大于阈值 τsupport(i) Σ_j area_xy(i ∩ j) / area_xy(i) ≥ ττ 取 1.0 是最保守的“完全支撑”实际常用 0.70.85因为小件搁在大件边缘一点点是允许的只要不形成悬臂。重心约束。整体重心在 xy 平面的投影要落在安全区内G Σ w_i · c_i / Σ w_i 要求 G_xy ∈ 容器底面内缩 tol 后的矩形c_i是每个箱子的几何中心。tol取 0.10.15 表示重心不能超出中心区 10%15% 的范围。这条对整车配载尤其关键轴荷分配不均会被现场直接否掉。朝向约束。靠限制旋转集合实现rotations1表示完全不转rotations2表示只允许绕竖直轴转 90°。代码里不要试图用“事后检查高度有没有变大”来判朝向那个判断在多层堆叠时会失效。4.2 在求解循环里挂约束钩子约束必须挂在候选点过滤阶段不能等解算完了再校验。事后校验只能告诉你方案废了不能帮你找到合法方案。包里给的是注册式钩子from packing.constraints import add_constraint def support_ok(placed, item, bin_size, support_ratio0.7, eps1e-6): 候选点过滤底面接触比例达标才允许放置 base item.size[0] * item.size[1] if base 0: return False contact 0.0 for p in placed: # 只有顶面正好托住 item 底面的箱子才贡献接触面积 if abs((p.pos[2] p.size[2]) - item.pos[2]) eps: contact overlap_area_xy(p, item) return contact / base support_ratio def cog_ok(placed, item, bin_size, tol0.15): 整体重心投影不越界越界就拒绝这个候选点 total_w sum(p.weight for p in placed) item.weight if total_w 0: return True gx sum(p.weight * (p.pos[0] p.size[0] / 2) for p in placed) gy sum(p.weight * (p.pos[1] p.size[1] / 2) for p in placed) gx (gx item.weight * (item.pos[0] item.size[0] / 2)) / total_w gy (gy item.weight * (item.pos[1] item.size[1] / 2)) / total_w return (bin_size[0] * tol gx bin_size[0] * (1 - tol) and bin_size[1] * tol gy bin_size[1] * (1 - tol)) add_constraint(support, support_ok) # 三个钩子按注册顺序依次过滤 add_constraint(cog, cog_ok)两点经验钩子函数会被调用几十万次里面不要做深拷贝、不要遍历全量placed做排序。我一般会维护一个“当前各高度层顶面列表”的索引把 O(n) 的扫描压到 O(log n)。约束顺序有讲究。先过滤支撑最便宜一次面积计算再过滤重心要累加全量重量最后过滤重量上限。反过来会把大量时间花在注定被拒的候选点上。4.3 结果校验器三分钟确认解没违规校验器是独立于求解器的第二套代码两套代码同时错的概率远低于一套。至少覆盖五类校验项判据常见误报原因越界pos size ≤ bin_size eps容器尺寸含壁厚重叠三轴区间至少一轴不相交容差取值不当1e-9 级假重叠支撑接触面积占比 ≥ τ未考虑gap实际接触被间隙吃掉重量单容器总重 ≤max_weight清单里 weight 全填 0重心投影落在安全区单位混用导致重量比例失真def check_overlap(a, b, eps1e-6): # 三轴中只要有一轴分离就不重叠用 eps 吸收浮点误差 for i in range(3): if (a.pos[i] a.size[i] b.pos[i] eps or b.pos[i] b.size[i] a.pos[i] eps): return False return True校验跑完打印违规条数就行别抛异常中断。真实项目里我更希望看到“共 3 条违规其中 2 条是 gap 没算进支撑”这样才知道该改哪里。注意校验器使用的 eps 要比求解器里用的略大一点点。求解器用 1e-9 保精度校验器用 1e-6 挡噪声两边取同一个值反而容易互相打架。5. 避坑清单五种跑通却不可用的结果怎么排查下面这五条都是我在拆这类代码包时真实遇到过的共同点是程序不报错、装载率数字好看但结果拿去用就出问题。5.1 装载率 95% 但导出后货物重叠现象控制台显示装载率 0.95可视化看着也正常把坐标导出成 CSV 发给现场回来反馈“有两箱位置打架”。原因求解器内部判重叠用的是严格不等式加重叠容差浮点累加后两个箱子的边界差了 1e-7内部判为“刚好贴合”导出时按毫米取整就变成重叠 0.1 毫米。也有一种情况是可视化用的坐标和导出用的坐标一个取最小角、一个取中心点。解决导出前统一走一遍validate容差设 1e-3按毫米单位把所有小于该容差的贴合按gap重新推开同时确认导出函数用的是pos最小角而不是中心点。5.2 同一份数据跑两次结果不一样现象同样的实例连跑三次装载率分别是 0.883、0.871、0.889最优方案对不上。原因排序打平时用了字典遍历顺序或者候选点选优时用了随机 tie-break 但没固定种子也常见于多进程跑批结果按完成顺序合并。解决所有随机入口统一--seedsort_key排序时加第二关键字比如 id做稳定排序候选点比较时把坐标元组整体作为比较键不要只比距离。5.3 装载率涨了重心偏到一侧现象调大rotations后装载率从 84% 涨到 91%但方案里所有重货都堆在一侧。原因极值点启发式天然偏好“靠角落”放置会不断往同一个角塞货重心自然偏。如果不挂重心钩子这个偏好会被放大。解决挂上 4.2 里的重心钩子tol从 0.2 开始逐步收紧到 0.15同时把sort_key换成weight_desc跑一遍对比。重心约束会让装载率掉 24 个点这是必须付的成本。5.4 几百个箱子跑了十分钟还没出结果现象示例实例秒出换成三百多件的真实清单跑了十分钟没动静内存还在涨。原因极值点候选点集没做去重和剪枝每放一个箱子点数涨几倍最后变成几十万个点每个点都要过一遍约束钩子钩子里还有 O(n) 扫描。解决候选点按 (z, y, x) 排序后只保留前 200 个同一位置的候选点用网格哈希去重把坐标按 gap/2 取整做 key约束钩子里维护分层顶面索引。这三步通常能把耗时压到原来的十分之一。5.5 可视化没问题按层码放的现场装不起来现象图上看着挺整齐现场工人反馈“没法码中间那层是悬空的”。原因用的是纯极值点策略货和货之间形成了犬牙交错的结构纸面上利用率高但没有连续平面叉车和人工都没法作业。解决换层叠式--algo shelf或者给极值点加一条“同层高度对齐”的软约束优先把货物放在同层已用高度附近的点上。装载率会掉 35 个点但现场能装。这个取舍没有通用答案得看仓库的作业方式。6. 在贪心解上做二次优化模拟退火的落地参数极值点跑出来的解有很强的“先到先得”惯性谁先被放进去谁就占了角落后面的货只能绕。真正能再榨出几个点的做法不是换算法而是在已有解上做破坏-重建用模拟退火做接受准则。核心思路很朴素随机拿掉几个箱子用同样的贪心重新填回去如果填得更好就接受差一点也以一定概率接受避免卡在局部最优。import random, math, copy def anneal(inst, base, iters2000, t00.02, t10.001, k_remove5, seed42): rng random.Random(seed) # 固定种子跑批才能对比 cur, best copy.deepcopy(base), copy.deepcopy(base) for k in range(iters): t t0 * (t1 / t0) ** (k / iters) # 几何降温t0/t1 是起止温度 # 破坏随机挖掉 k_remove 个箱子保留其余布局 removed, partial destroy(cur, k_remove, rng) # 重建把挖掉的货按体积降序重新贪心插回可能开新容器 cand repair(partial, removed, inst, rng) delta cand.fill_rate - cur.fill_rate # 变好直接收变差按 Metropolis 准则以概率收 if delta 0 or rng.random() math.exp(delta / max(t, 1e-9)): cur cand if cur.fill_rate best.fill_rate: best copy.deepcopy(cur) return best参数怎么定我踩过的顺序是这样的iters取 10003000。少于 1000 基本没效果多于 3000 收益快速衰减多数实例在 1500 步左右就收敛了。t0不要按“装载率差值”直觉给 0.5那等于前 500 步全在接受劣解退化成随机游走。装载率是 01 的小数t00.02、t10.001这个量级更合适。k_remove取 38。太小跳不出局部最优太大等于每次推倒重来退火退了个寂寞。邻域一定要“重建”不要只做“交换两个箱子的顺序”。交换顺序对极值点启发式的扰动太弱因为候选点集变化很小。验证有没有真提升别只看最后那个数字。我会固定一组 1020 个实例分别跑纯贪心和退火记录装载率均值、最差值、耗时三项。均值涨 2 个点但最差值掉 5 个点说明参数不稳不能上线。这套对比脚本比退火本身更值得写。最后一条血泪经验退火跑出来的方案一定要再过一遍validate和重心校验。破坏-重建过程里最容易出现“为了塞进去把重货挪到顶层”这种事装载率涨了方案废了。从那以后我每次出最终方案都强制走一遍“校验 → 出图 → 人工看顶层和重心”这三步一步不省。希望帮到你。本文还有配套的精品资源点击获取

三维装箱算法实战：启发式、物理约束与装载率优化

相关推荐

Oracle SGA架构解析：Buffer Cache与Shared Pool优化实践

Oracle SGA架构与Buffer Cache优化实战

超声波风速风向传感器技术解析与应用

更多资讯

HiFloat4格式：大语言模型4-bit量化的高效解决方案

CLI工具开发与浏览器扩展认证集成实践

SAP函件类型管理的CDS视图实现与优化

Codex 秒级生成前端组件：从提示词到工作流实战

从语言到可编辑CAD模型：Text-to-CAD技术路线与工程实践解析

DeepSeek V4网卡加速技术解析与实战优化

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？