简介这份资源围绕三维装箱3D-Bin-Packing这一经典组合优化问题给出基于Java的最佳适应BestFit实现示例面向学习算法设计、数据结构与物流仓储装箱场景的开发者。压缩包共313个文件约923KB以txt说明与数据、java源码、class编译文件、xml/fxml配置及css/html界面文件为主另含jar与测试类便于直接运行、阅读和二次改造。已有6741人学习下载说明其在中高级算法练习与项目复盘中具有一定参考价值。读者可借此梳理按体积排序、遍历已有箱子、剩余空间判断与开新箱等关键流程并延伸到搜索遍历、条件循环、内存管理、NP难问题复杂度分析、单元测试和模块化文档等知识点形成从模型到实现的完整认知。1. 从一次发货报价说起3D-Bin-Packing.zip 里到底装了什么假设你手上有一批长方体货物尺寸从几厘米的小件到一米多的大件混在一起要装进规格固定的纸箱或者集装箱。人工排一遍大概要半小时而且排出来的方案通常还剩一大截空隙。这个时候你真正想知道的不是「怎么塞」而是「最少要几个箱子、每个箱子怎么摆」。这份3D-Bin-Packing.zip干的就是这件事读入容器尺寸和一串物品的三维长宽高用启发式算法算出一套不重叠、不越界的摆放坐标再画一张三维图让你肉眼验收。它的代码量不大但把数据模型、排序策略、极值点放置、碰撞检测、结果校验、可视化这几层拆得很清楚适合两类人一是刚接触三维装箱、想找份能跑通的最小实现照着改的开发者二是手里有真实装箱业务、需要拿一份可读代码当底座做二次封装的人。后面就按「先看结构、再看算法、再跑起来、最后动手改」的顺序把它拆开。2. 工程结构总览从 data 到 solver 再到 viz 的三段式分层这份代码最值得先看的地方不是算法而是它没有把算法和 IO 搅在一起。整个包按职责切成三层数据层只负责定义物品和容器的形状求解层只跟抽象的 Box 列表打交道表现层负责读 JSON、打日志、画图。三层之间靠 dataclass 传递对象不传裸数组。这种切法在装箱项目里不是强迫症而是刚需——因为装箱算法你迟早要换可能是启发式换遗传算法也可能启发式换整数规划求解器如果数据结构跟算法焊死换一次就得重写一遍。2.1 目录树与各层职责解压之后大致是下面这个结构不同版本的目录名可能略有出入但分层逻辑一致3D-Bin-Packing/ ├── data/ │ ├── sample_small.json # 十几件物品的小样本调参用 │ ├── sample_mixed.json # 大小件混合考验排序策略 │ └── sample_tight.json # 接近满载考验剪枝 ├── src/ │ ├── model.py # Box / Item / Placement 三个数据类 │ ├── loader.py # JSON 读取与字段校验 │ ├── packer.py # 极值点主循环核心入口 │ ├── heuristic.py # 排序与候选点打分策略 │ ├── validator.py # 事后校验越界、重叠、漏装 │ └── visualize.py # matplotlib 3D 立方体渲染 ├── tests/ │ └── test_packer.py # 小规模随机用例与不变量断言 ├── run.py # 命令行入口 ├── requirements.txt └── README.mdmodel.py是整个项目的地基packer.py是唯一需要精读的文件validator.py是很多人会忽略但最该保留的部分。我见过太多装箱脚本算完直接输出坐标从来不复核结果上线之后发现两个箱子在某个坐标轴上差了 0.0001 就被判成重叠或者某个物品干脆没被装进去却不出现在日志里。校验器存在的意义就是让这类问题在本地跑的时候就暴露而不是等到仓库现场。2.2 数据模型三个 dataclass 撑起整个项目核心数据类通常长这样字段不多但每个字段的位置都决定后面代码好不好写from dataclasses import dataclass, field from typing import List dataclass(frozenTrue) class Box: 容器单位统一由调用方保证项目内部不做单位换算 id: int w: float # x 方向宽 h: float # y 方向高 d: float # z 方向深 property def volume(self) - float: return self.w * self.h * self.d dataclass class Item: id: int w: float h: float d: float allow_rotation: bool True # 是否允许六向翻转 property def volume(self) - float: return self.w * self.h * self.d dataclass class Placement: 一次放置结果物品 id 左下后角坐标 实际摆好后的尺寸 item_id: int x: float y: float z: float w: float h: float d: float box_id: int 0三个类里最关键的是Placement。注意它记的不是物品原始尺寸而是摆好之后的尺寸——因为一旦允许旋转物品的 w/h/d 就变成了三个数的某种排列后面做碰撞检测必须用排列后的值否则你算出来的重叠判断全是错的。这是新手第一版最容易翻车的地方拿原始尺寸去做相交检测物品转了 90 度之后判定就彻底失真。坐标系我一般固定在左下后角为原点x 向右、y 向上、z 向前。定死一个约定比定哪个更重要因为候选点的派生逻辑、可视化时的立方体绘制、以及后面接入业务系统导出的三维坐标全都要跟它对齐。项目里如果没写清楚建议第一件事就是在model.py顶部补一行注释把这个约定钉住。2.3 配置入口哪些参数值得暴露出来run.py里通常暴露这么几个参数别小看它们装箱效果差异有一半来自这几行参数含义常见取值影响--data输入 JSON 路径data/sample_small.json决定规模--sort排序策略volume / max_edge / none大件优先通常更省箱--no-rotate关闭旋转布尔开关关闭后可行性骤降--max-bins箱子数上限10超限直接失败而不是死循环--plot输出三维图布尔开关调试期必开--sort这个参数是整份代码里性价比最高的旋钮。同一个数据集按体积降序和按最大边降序最后的箱子数和利用率能差出十几个百分点而且哪个更好跟你的物品尺寸分布强相关——大件少、小件多的时候最大边降序往往更稳反过来大件占主导时体积降序更省。这种东西没有理论最优只能拿自己的数据跑一遍对比。3. 核心算法拆解从物品排序到极值点更新的完整装箱链路求解层用的是极值点法Extreme Point-based思路一句话概括维护一组「还可以往里放东西的候选角点」每放一个物品就删掉被它挡住的点、派生三个新角点然后下一个物品在所有「候选点 × 所有朝向」的组合里挑一个评分最高的。这个方法的好处是解的质量比单纯的分层法好代码量又远小于整数规划出问题的时候还能一步步打日志看清楚它为什么这么放。3.1 第一步排序与朝向枚举排序决定了大件先占位置还是小件先填空隙朝向枚举决定了搜索空间的大小import itertools from typing import List, Tuple from src.model import Item def sort_items(items: List[Item], key: str volume) - List[Item]: 先放大件是通用经验大件可选位置少留到最后容易无处可放 if key volume: return sorted(items, keylambda it: it.volume, reverseTrue) if key max_edge: return sorted(items, keylambda it: max(it.w, it.h, it.d), reverseTrue) if key footprint: return sorted(items, keylambda it: it.w * it.d, reverseTrue) return list(items) # none保持输入顺序用于对照实验 def orientations(item: Item) - List[Tuple[float, float, float]]: 返回去重后的朝向列表允许旋转时最多 6 种不允许时只有 1 种 if not item.allow_rotation: return [(item.w, item.h, item.d)] seen set() for p in itertools.permutations((item.w, item.h, item.d)): seen.add(tuple(round(v, 6) for v in p)) # 四舍五入去重避免浮点导致重复 return list(seen)sort_items里那个footprint策略是我加的按底面积排序在「高度受限、箱子矮」的场景下比按体积更合理——一个又细又高的柱状件体积不小但底面积小先放它反而占住了底层的黄金位置。你可以把三种策略都跑一遍看哪个箱子数少、利用率高再固化成默认值。orientations里round(v, 6)这个处理别省。物品如果是个正方体itertools.permutations会生成 6 个完全相同的三元组不去重的话每个候选点都要重复试 6 遍性能直接掉一个量级而如果尺寸是浮点数直接用set又因为精度问题去不干净所以先 round 再去重。这是纯工程细节但对跑大样本的体感影响很大。3.2 第二步可行性判断与 AABB 碰撞检测放一个物品进去之前要过两关出不出界、跟已放的重不重叠。两关都是纯几何代码短但容差必须处理好EPS 1e-6 def in_bounds(box, x, y, z, w, h, d) - bool: 出界判断注意是 而不是 贴边放置是合法的 return (x -EPS and y -EPS and z -EPS and x w box.w EPS and y h box.h EPS and z d box.d EPS) def hit(a: Placement, x, y, z, w, h, d) - bool: AABB 相交三个轴上的投影区间全部重叠才算真相交 if abs(x w - a.x) EPS or abs(a.x a.w - x) EPS: return False # x 轴刚好贴面不算重叠 if abs(y h - a.y) EPS or abs(a.y a.h - y) EPS: return False if abs(z d - a.z) EPS or abs(a.z a.d - z) EPS: return False return (x a.x a.w and x w a.x and y a.y a.h and y h a.y and z a.z a.d and z d a.z) def can_place(box, placed, x, y, z, w, h, d) - bool: if not in_bounds(box, x, y, z, w, h, d): return False for p in placed: if hit(p, x, y, z, w, h, d): return False return Truehit开头那三个贴面判断是血泪经验换来的。浮点数算坐标两个物品紧贴放置时一个的右边界会算成12.000000000000002另一个的左边界是11.999999999999998直接用开区间判断就会判定成重叠于是算法明明放得下却死活放不进去日志里还看不出原因。加一个EPS容差、并且把「恰好贴面」显式判成不相交这个坑就填了。另一边in_bounds用 box.w EPS也是同一个道理宁可放过一点点越界也不能因为精度把合法方案判死。注意EPS不要设太大。设成 1e-3 的时候如果数据单位是米等于允许 1 毫米的越界真装箱是能装进去的但如果单位是毫米1e-3 就毫无意义。容差要跟你的数据量级匹配。3.3 第三步主循环——候选点 × 朝向的打分与选择下面是整份代码的心脏逻辑是「对当前物品遍历所有候选点和朝向挑第一个/最好的那个放进去放不进就开新箱」def place_one(item, box, placed, points): 在给定箱子内为单个物品找最佳落点找不到返回 (None, points) best None best_score None for (px, py, pz) in points: for (w, h, d) in orientations(item): if not can_place(box, placed, px, py, pz, w, h, d): continue # 打分贴边越紧、高度越低越好这是 DBLF 的核心思想 score (pz, py, px) # z 优先其次 y最后 x if best_score is None or score best_score: best_score score best (px, py, pz, w, h, d) if best is None: return None, points px, py, pz, w, h, d best node Placement(item.id, px, py, pz, w, h, d, box.id) return node, update_points(points, node, placed) def pack(items, box, sort_keyvolume): placed, points, result [], [(0.0, 0.0, 0.0)], [] for item in sort_items(items, sort_key): node, points place_one(item, box, placed, points) if node is None: break # 单箱模式到此为止多箱模式在这里开新箱 placed.append(node) result.append(node) return result, placed打分函数(pz, py, px)就是「最深、最低、最左」的字典序业内叫 DBLFDeepest Bottom Left Fill。为什么不是简单的「能放就放」因为候选点的遍历顺序会影响结果如果先试的永远是原点附近物品会全部堆在角落靠里的空间全浪费。用字典序排序相当于每次都挑最靠里那个落点把空间从外往里挤剩下的空隙更集中、更好利用。这里有个可以改的地方score目前是纯位置排序完全没考虑物品放进去之后会不会在角落留下一条永远填不上的缝。进阶做法是把分数改成「放置后新增的不可用体积」或者「与已放物品的接触面积」接触面积越大越稳定也越省空间。改这一行就是最轻量的算法调优不用动主循环。3.4 第四步候选点的派生与剪枝每放一个物品候选点集合就要更新删掉被新物品挡住的旧点加上三个新派生点。def update_points(points, node, eps1e-6): 放置后更新候选极值点先排除被占据的再派生三个新角点 alive [] for (x, y, z) in points: inside (node.x - eps x node.x node.w eps and node.y - eps y node.y node.h eps and node.z - eps z node.z node.d eps) if not inside: alive.append((x, y, z)) # 立方体的三个可见角点正好是下一个物品可能的落点 alive.extend([ (node.x node.w, node.y, node.z), (node.x, node.y node.h, node.z), (node.x, node.y, node.z node.d), ]) # 去重 return list({(round(x, 6), round(y, 6), round(z, 6)) for (x, y, z) in alive})这段的复杂度是全项目最高的候选点数量随物品数增长每放一个物品要跟所有已放物品比一次最坏情况是 O(n²)再乘上每个物品的 6 种朝向几百件物品就跑不动了。所以实际代码里通常还会加一层剪枝——把明显被其他候选点「支配」的点删掉。所谓支配就是点 A 在三个轴上都比点 B 更靠里x、y、z 都更小那 B 永远轮不到被用可以放心扔掉。def prune(points): 支配剪枝A 在三个轴上都 B则 B 无意义 pts sorted(points) kept [] for p in pts: dominated False for q in kept: if q[0] p[0] and q[1] p[1] and q[2] p[2]: dominated True break if not dominated: kept [k for k in kept if not (p[0] k[0] and p[1] k[1] and p[2] k[2])] kept.append(p) return kept剪枝这层是性能和效果之间的权衡。不剪几百件物品要跑几十秒但方案质量好剪了速度能快一个量级但某些原本能装下的方案可能被删掉。我一般的做法是物品数小于 100 不剪大于 500 必剪中间看情况。这个阈值没有普适答案得拿自己的数据集跑一遍才知道拐点在哪。4. 跑起来环境、数据格式、命令行与结果验证算法读得再明白跑不起来也白搭。这一节按顺序把环境、数据、命令、结果四件事走一遍每一步都给出出错时该看哪里。4.1 环境准备与依赖这份代码的依赖很轻主力就三个numpy做数值计算matplotlib做三维可视化pytest跑测试。Python 版本建议 3.9 以上因为 dataclass 的frozen和一些类型注解特性在老版本上有兼容问题。# 建议先建虚拟环境别直接往系统 Python 里装 python -m venv .venv source .venv/bin/activate # Windows 下是 .venv\Scripts\activate pip install -r requirements.txt pip install -e . # 如果项目带 setup.py装成可编辑包最后那行pip install -e .很多人会漏。如果项目里有setup.py或者pyproject.toml装上之后src就是一个正经的包from src.model import Box在任何目录下都能 import。不装的话你从tests/目录里跑测试就会直接报ModuleNotFoundError: No module named src。这个问题下面还会再提一次因为它出现的频率实在太高。如果你的环境里matplotlib装完跑图时报后端相关的错加一行MPLBACKENDAgg把后端切成无界面模式只出图不弹窗服务器和 CI 里都能用。4.2 输入数据格式JSON 里到底该写什么数据层读的 JSON 结构一般是这样字段命名各家不同但语义就这几个{ container: { id: 0, w: 60, h: 50, d: 40 }, items: [ { id: 1, w: 20, h: 15, d: 10, allow_rotation: true }, { id: 2, w: 30, h: 10, d: 10, allow_rotation: true }, { id: 3, w: 12, h: 12, d: 60, allow_rotation: false } ] }三个字段值得说container只允许一个因为这是单箱模式如果要算「最少几个箱子」正确做法是外层套一层循环每次装完一个箱子就把已装物品从列表里剔掉再开下一个直到装完或者超过--max-bins。allow_rotation设成false的物品第一件里那根 60 长的杆子就只能在深方向躺着这经常是算法「明明放得下却放不进去」的真正原因——数据里写死了不许转代码里却在拼命试六个朝向试完发现都被orientations挡回去了看起来就像什么都没发生。loader.py里一定要做字段校验缺字段、负数、尺寸为 0 都要在读取阶段就抛明确的异常。我见过一个数据集里混进了一个w: 0的物品算法怎么跑都装不进去日志里只显示「未放置物品 1 件」查了两个小时才发现是数据的问题。4.3 命令行调用与输出解读跑通最小闭环的命令通常是这一条python run.py --data data/sample_small.json --sort volume --plot执行完之后终端会打一份摘要格式大致是[bins] used 1 [util] 87.3% (filled 24500.0 / 28000.0) [items] placed 12 / 12 [valid] no overlap, no overflow, no missing四行里每一行都有用。used是最终用了几个箱子util是体积利用率注意这是几何体积比不是重量利用率实际装货会因为形状空隙比这个数字低不少placed是最该盯的一行如果分子小于分母说明有物品没装进去这时候别急着调参先去--plot的图里看是哪个物品、卡在什么位置。# 批量对比三种排序策略选出在自己数据上最省箱的那个 for s in volume max_edge footprint none; do echo sort$s python run.py --data data/sample_mixed.json --sort $s --no-plot done这个循环是我每次拿到新数据集时的固定动作四组结果摆一起看哪个箱子数少、利用率高、耗时能接受就用哪个当默认值。none那一组是用来做对照的如果它跟最优策略差距不到 2%说明你的数据本身就比较好装没必要为了几个百分点上复杂策略。4.4 结果验证把 validator 当成必跑项可视化图好看归好看但真正能证明方案合法的是校验器。validator.py要覆盖三类检查每一类都得有明确输出def validate(placements, box, items): errors [] # 1) 越界 for p in placements: if (p.x -1e-6 or p.y -1e-6 or p.z -1e-6 or p.x p.w box.w 1e-6 or p.y p.h box.h 1e-6 or p.z p.d box.d 1e-6): errors.append(fitem {p.item_id} out of container) # 2) 两两重叠 for i in range(len(placements)): for j in range(i 1, len(placements)): if hit(placements[i], placements[j].x, placements[j].y, placements[j].z, placements[j].w, placements[j].h, placements[j].d): errors.append(fitem {placements[i].item_id} overlaps {placements[j].item_id}) # 3) 漏装 placed_ids {p.item_id for p in placements} for it in items: if it.id not in placed_ids: errors.append(fitem {it.id} not placed) return errors三类检查里漏装最容易被忽略因为它不会报错只会让利用率数字悄悄变低。很多人看到利用率 70% 就去调排序策略其实是有一件大货根本没被放进去。把漏装做成硬断言errors非空就退出码非零接到 CI 里跑最好。--plot出来的三维图适合看整体形态如果发现所有物品都堆在角落、另一半箱子空空如也说明候选点更新有问题如果发现物品东一块西一块、中间全是碎缝说明打分函数太贪心该考虑接触面积了。图是给人看的校验是给机器看的两个都留着。5. 常见问题排查跑不通、装不进去、利用率上不去5.1 环境与数据层的坑现象一ModuleNotFoundError: No module named src。原因很直接——你站在tests/目录里执行python test_packer.pyPython 的模块搜索路径里只有当前目录项目根目录不在里面src自然找不到。解决方式三选一回到项目根目录用python -m pytest tests/跑或者pip install -e .把项目装成包或者在脚本顶部加sys.path.insert(0, str(Path(__file__).parents[1]))。第三种是治标前两种是治本我一般要求项目里必须有第一种能用。现象二读 JSON 报KeyError: d或者某一维是null。原因通常是不同来源的数据字段名不统一有的用depth、有的用length、有的用height表达同一个意思。装箱里「高」和「深」搞反是灾难性的因为约束是y h box.h一旦 y 和 z 互换越界判断就全错了但算法不会报错只是所有物品都装不进去。解决方式在loader.py里做一层字段映射把length映射到w、width映射到d之前先打印一行「检测到字段 X按 Y 处理」让自己看得见这次映射做了什么别默默转换。现象三跑小样本几毫秒跑真实数据卡死。原因在候选点数量上。100 件物品时候选点大概几百个1000 件时可能上万每个物品都要遍历「候选点 × 朝向 × 已放物品」三重循环复杂度直接上天。解决办法按性价比排序先把orientations的去重做掉能省 6 倍再加 3.4 节那个支配剪枝最后限制候选点总数比如只保留打分最靠前的 200 个。三招做完千件规模通常在十几秒以内。5.2 算法与结果层的坑现象四校验器报「重叠」但图上看起来严丝合缝。这是浮点精度问题不是算法错。两个物品贴面放置时坐标算出来是29.999999999999996和30.000000000000004开区间判断就把它们判成相交了。解决办法是把碰撞检测里所有比较换成带容差的形式并且显式处理「贴面」这种边界情况——就像 3.2 节hit函数开头那三个abs(...) EPS的判断。另一个常见来源是坐标从 JSON 读进来是整数、在 Python 里参与乘法后变成浮点如果你的数据本身很规整可以在放置完成后统一 round 到 4 位小数再存。现象五结果每次跑都不一样同一份数据两次利用率差 5%。原因在候选点的容器类型上。如果用set存候选点for循环的迭代顺序在不同进程之间是不保证一致的尤其是元素是浮点元组的时候遍历顺序一变先试到的可行解就变贪心算法的结果自然跟着变。解决方式候选点用 list 存并且在派生前排一次序points.sort(keylambda p: (p[2], p[1], p[0]))把顺序钉死。装箱本身是确定性的贪心只要输入和遍历顺序固定结果必须可复现跑出随机性一定是代码里有没定序的容器。现象六利用率只有 60% 出头怎么调参都上不去。先别怀疑算法按这个顺序排查第一看placed是不是等于总数有漏装先解决漏装第二看是不是大件被排到了最后——如果你的数据里有一件占体积 40% 的大货按体积降序它一定排第一但如果你用的是--sort none它可能排到第 200 个才轮到那时候空间已经被切碎了第三才是看打分函数把(pz, py, px)换成「与已放物品接触面积最大」的评分通常能再提三到五个百分点。这三步走完还是上不去那大概率是数据本身的形状空隙就大几何上限摆在那儿不是代码的问题。提示调参之前先固定数据集和随机种子每次都拿同一份数据对比。换数据换参数一起换你永远不知道是哪个改动起了作用。6. 二次开发改造换约束、换算法、接业务接口原版代码是个干净的启发式实现真接到业务里缺的一般是三样东西物理约束、接口、以及一份能证明改完没改坏的测试。加承重与支撑约束是最常见的改造。现实里的货不能悬空放底面至少要有一定比例被支撑住。改动点在can_place里加一层检查def support_ratio(x, y, z, w, d, placed, eps1e-6): 计算底面被已放物品覆盖的面积比例y0 时视为被箱底完全支撑 if y eps: return 1.0 area 0.0 for p in placed: if abs(p.y p.h - y) eps: # 只看顶面刚好对齐的那些 continue ox max(0.0, min(x w, p.x p.w) - max(x, p.x)) oz max(0.0, min(z d, p.z p.d) - max(z, p.z)) area ox * oz return area / (w * d)把它挂到can_place里阈值设 0.8 左右低于这个比例就拒绝放置。这层一加利用率通常会掉 3 到 8 个百分点但方案能真的落地。改造完记得在tests/里补一条用例给定一个故意悬空的场景断言算法不会把物品放在那儿。换算法有两条路。一条是把place_one里的贪心打分换成遗传算法的适应度评估外层用random打乱排序、跑几十代取最优代码量不大但耗时翻几十倍适合离线出方案另一条是直接用 OR-Tools 的 CP-SAT 建模把每个物品的每个朝向定义成布尔变量加不重叠约束小规模30 件以内能拿到真正的最优解缺点是规模一大就解不动。我的建议是两条都留着小单走 CP-SAT大单走启发式用--solver参数切换。接业务接口最省事的方式是包一层 Flask把pack()的结果序列化成 JSON 返回。这里有个细节返回的坐标要带上单位而且要在接口文档里写清楚坐标系是「左下后角为原点」。不写清楚前端画出来的图和算法算出来的完全对不上然后两边开始互相甩锅这种扯皮我经历过不止一次。改造点入口位置改动量收益支撑约束packer.can_place30 行方案可落地分组约束同单相邻heuristic.sort_items50 行拣货效率CP-SAT 求解器新增solver_cpsat.py150 行小规模最优HTTP 接口新增api.py80 行系统集成随机化测试tests/test_packer.py60 行改动不回归最后那行测试值得单独说。装箱代码的特点是「改一行坏一片」而且坏法很隐蔽——不报错只是利用率掉两个点你不跑对比根本发现不了。我从那以后每次动packer.py之前都强制先把sample_mixed.json跑一遍存个基线改完再跑一遍箱子数、利用率、耗时三个数字摆一起对比任何一个异常就回滚查原因。这个习惯救过我很多次也希望帮到你。本文还有配套的精品资源点击获取