简介：面向物流仓储、制造业排产及算法学习者的三维装箱（3D-Bin-Packing）Java 实现资料，聚焦在有限体积标准箱约束下最大化空间利用率的组合优化问题。资源以 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 目录里有什么：模块职责与调用链

这类包的目录组织基本是同一套骨架，拆开后我一般按下面这张表对号入座，缺哪块心里就有数了：

调用链很线性：load_instance → packer.pack → validate → plot / export。真正值得读的只有heuristics和constraints两块，其余是胶水代码，看一遍知道签名就够了。

2.2 一次装箱的数据结构：Item、Bin、Placement 与坐标约定

先看数据结构，因为后面所有坑都从这里冒出来。核心三个类：

from dataclasses import dataclass from typing import Tuple @dataclass(frozen=True) 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/6：1 完全不转，2 只允许绕 z 轴转 90°，6 允许任意翻转。取 6 装载率最高，但可能把“不可倒置”的货放倒。
• --gap是货物之间的安全间隙，必须和容器同单位。现场装卸要留手的空间，0.5～2 厘米是常见值，取 0 会让结果好看但装不进去。
• --seed别省。贪心本身确定性较强，但排序打平、候选点排序一旦掺了随机，不固定种子就没法复现，也没法对比两次改动谁更好。

第一张图出来之后先别急着调算法，盯着图看三件事：有没有箱子悬空、有没有明显的大块空洞、顶层是不是被一两个大件把空间锁死了。这三眼比看装载率数字有用得多。

3. 算法选型：贪心、层叠、极值点三条路怎么选

包里的算法不止一个，选错路线比调错参数损失大得多。同一批货，层叠式可能只装到 72%，极值点能到 88%，但极值点的候选点维护开销是前者的好几倍。选型要看货物尺寸分布和现场作业方式，不是看谁的名字高级。

3.1 精确解为什么不现实：规模与复杂度的硬边界

三维装箱是 NP-hard，这点不用证明，只要看解空间：n 个货物有 n! 种装载顺序，每个货物最多 6 种朝向，再加上容器内的连续坐标，变量数量随规模指数增长。用 CP-SAT 或 MIP 建模，把坐标离散化成网格、给每个货物一个“落在哪个格点”的 0-1 变量，几十个货物加一个容器还能在几分钟内跑出最优解；上百个货物时，光是模型构建就能把内存吃满。

所以工程上的分层很清楚：

我的习惯是：先用极值点跑出基准解，把这个装载率当成“这个实例大概能到多少”的心理锚点，再去调参数或上局部搜索。上来就写遗传算法，多半是在给一个本身只有 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_size=inst.bin.size, sort_key="volume_desc", # 也可 maxside_desc / height_desc，见 3.4 rotations=6, # 允许的朝向数：1 / 2 / 6 gap=0.5, # 货物之间的安全间隙，与容器同单位 support_ratio=0.7, # 底面至少 70% 有支撑才允许放 max_weight=inst.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_key="volume_desc"决定放货顺序，体积降序是最稳的默认值。大件先放，小件才有缝隙可填；反过来先放小件，大件最后往往找不到连续空间。
• support_ratio是后面第 4 章要讲的物理约束入口，这里先给 0.7。取 1.0 表示必须完全被支撑（现场最安全，装载率会掉 3～8 个点），取 0 等于允许悬空。
• pack返回的是多容器解，不是单个容器内的布局。判读装载率时要看清分母：是所有容器体积之和，还是单个容器体积。这个口径不同，数字能差一倍。
• validate一定要跑。启发式为了速度会在候选点过滤上用近似判断，浮点误差累积后可能出现 1e-9 级别的“假重叠”，校验器用容差过滤掉，不然导出时会看到两个箱子贴在一起。

3.4 参数怎么调：排序策略、旋转集合与间隙

参数不多，但敏感度差别很大。按我实际调过的经验排个序：

排序策略值得单独说一句：volume_desc和maxside_desc在不同实例上互有胜负，差 3 个点很常见。我的做法是同一批实例把三种排序都跑一遍，记下装载率，挑最稳的那个作为默认，而不是每次都重新扫。旋转集合则要看货：纸箱类大多可以六向翻，家电、带压缩机的设备只能立着放，这时rotations=2不是妥协，是硬约束。

4. 把物理约束加进去：重心、承压与不可翻转

只判“不重叠”的装箱结果，在纸面上永远漂亮，在现场永远不能用。真正决定方案能不能落地的是三条：箱子底面积够不够被支撑、整车重心偏不偏、有没有货被放倒。这三条不加，装载率再高也只是数字游戏。

4.1 三条约束的数学表达

支撑约束。箱子 i 放在高度 z 上，下方所有顶面与该高度重合的箱子提供的接触面积之和，除以 i 的底面积，要大于阈值 τ：

support(i) = Σ_j area_xy(i ∩ j) / area_xy(i) ≥ τ

τ 取 1.0 是最保守的“完全支撑”，实际常用 0.7～0.85，因为小件搁在大件边缘一点点是允许的，只要不形成悬臂。

重心约束。整体重心在 xy 平面的投影要落在安全区内：

G = Σ w_i · c_i / Σ w_i ， 要求 G_xy ∈ 容器底面内缩 tol 后的矩形

c_i是每个箱子的几何中心。tol取 0.1～0.15 表示重心不能超出中心区 10%～15% 的范围。这条对整车配载尤其关键，轴荷分配不均会被现场直接否掉。

朝向约束。靠限制旋转集合实现，rotations=1表示完全不转，rotations=2表示只允许绕竖直轴转 90°。代码里不要试图用“事后检查高度有没有变大”来判朝向，那个判断在多层堆叠时会失效。

4.2 在求解循环里挂约束钩子

约束必须挂在候选点过滤阶段，不能等解算完了再校验。事后校验只能告诉你方案废了，不能帮你找到合法方案。包里给的是注册式钩子：

from packing.constraints import add_constraint def support_ok(placed, item, bin_size, support_ratio=0.7, eps=1e-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, tol=0.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 结果校验器：三分钟确认解没违规

校验器是独立于求解器的第二套代码，两套代码同时错的概率远低于一套。至少覆盖五类：

def check_overlap(a, b, eps=1e-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 但没固定种子；也常见于多进程跑批，结果按完成顺序合并。

解决：所有随机入口统一--seed；sort_key排序时加第二关键字（比如 id）做稳定排序；候选点比较时把坐标元组整体作为比较键，不要只比距离。

5.3 装载率涨了，重心偏到一侧

现象：调大rotations后装载率从 84% 涨到 91%，但方案里所有重货都堆在一侧。

原因：极值点启发式天然偏好“靠角落”放置，会不断往同一个角塞货，重心自然偏。如果不挂重心钩子，这个偏好会被放大。

解决：挂上 4.2 里的重心钩子，tol从 0.2 开始逐步收紧到 0.15；同时把sort_key换成weight_desc跑一遍对比。重心约束会让装载率掉 2～4 个点，这是必须付的成本。

5.4 几百个箱子跑了十分钟还没出结果

现象：示例实例秒出，换成三百多件的真实清单，跑了十分钟没动静，内存还在涨。

原因：极值点候选点集没做去重和剪枝，每放一个箱子点数涨几倍，最后变成几十万个点；每个点都要过一遍约束钩子，钩子里还有 O(n) 扫描。

解决：候选点按 (z, y, x) 排序后只保留前 200 个；同一位置的候选点用网格哈希去重（把坐标按 gap/2 取整做 key）；约束钩子里维护分层顶面索引。这三步通常能把耗时压到原来的十分之一。

5.5 可视化没问题，按层码放的现场装不起来

现象：图上看着挺整齐，现场工人反馈“没法码，中间那层是悬空的”。

原因：用的是纯极值点策略，货和货之间形成了犬牙交错的结构，纸面上利用率高，但没有连续平面，叉车和人工都没法作业。

解决：换层叠式（--algo shelf），或者给极值点加一条“同层高度对齐”的软约束：优先把货物放在同层已用高度附近的点上。装载率会掉 3～5 个点，但现场能装。这个取舍没有通用答案，得看仓库的作业方式。

6. 在贪心解上做二次优化：模拟退火的落地参数

极值点跑出来的解有很强的“先到先得”惯性：谁先被放进去，谁就占了角落，后面的货只能绕。真正能再榨出几个点的做法不是换算法，而是在已有解上做破坏-重建，用模拟退火做接受准则。核心思路很朴素：随机拿掉几个箱子，用同样的贪心重新填回去，如果填得更好就接受，差一点也以一定概率接受，避免卡在局部最优。

import random, math, copy def anneal(inst, base, iters=2000, t0=0.02, t1=0.001, k_remove=5, seed=42): 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取 1000～3000。少于 1000 基本没效果，多于 3000 收益快速衰减，多数实例在 1500 步左右就收敛了。
• t0不要按“装载率差值”直觉给 0.5，那等于前 500 步全在接受劣解，退化成随机游走。装载率是 0～1 的小数，t0=0.02、t1=0.001这个量级更合适。
• k_remove取 3～8。太小跳不出局部最优，太大等于每次推倒重来，退火退了个寂寞。
• 邻域一定要“重建”，不要只做“交换两个箱子的顺序”。交换顺序对极值点启发式的扰动太弱，因为候选点集变化很小。

验证有没有真提升，别只看最后那个数字。我会固定一组 10～20 个实例，分别跑纯贪心和退火，记录装载率均值、最差值、耗时三项。均值涨 2 个点但最差值掉 5 个点，说明参数不稳，不能上线。这套对比脚本比退火本身更值得写。

最后一条血泪经验：退火跑出来的方案一定要再过一遍validate和重心校验。破坏-重建过程里最容易出现“为了塞进去把重货挪到顶层”这种事，装载率涨了，方案废了。从那以后我每次出最终方案，都强制走一遍“校验 → 出图 → 人工看顶层和重心”这三步，一步不省。希望帮到你。

本文还有配套的精品资源，点击获取