BoxPacker 实战：四维装箱算法

BoxPacker 实战：四维装箱算法

【免费下载链接】BoxPacker4D bin packing / knapsack problem solver项目地址: https://gitcode.com/gh_mirrors/bo/BoxPacker

电商订单里 47 件商品，打包员要手动挑箱型、反复试错怎么塞，运费和面单数量都看它的脸色。BoxPacker是 PHP 写的一个四维装箱（bin packing）/ 背包问题求解器：给定物品的三维尺寸和重量，加上可用箱型清单，它自动算出用哪些箱、用几只、怎么摆，还顺手把每只箱子的重量摊匀，直接对接运费计算与面单打印。

BoxPacker 一句话讲清楚

一个 PHP 库（PHP 8.2+，MIT 协议），解决"4D"装箱问题：长宽高之外，重量是第四个约束，目标是用尽量少的箱把货装下。和普通 3D 装箱工具的区别有三点：支持按物品指定翻转规则；Box/Item是接口，你自己的商品、箱型实体可以直接传入，不必先转成库内数据结构，装完拿回来的也是你自己的对象；箱型可设库存上限。主流程入口见 src/Packer.php。

📦 智能装箱：核心能力拆解

空间搜索：把箱子当坐标系

单箱搜索由src/VolumePacker.php完成，它沿箱内坐标系逐个落子，剩余空间交给src/WorkingVolume.php记账：

• 每放入一件物品，空闲空间被重新划分子块，后续只搜索真正的"空地"，不做无谓碰撞判断
• 支持分层打包（src/LayerPacker.php），一层一平面地铺满再往上叠
• 外层Packer先按体积排序试箱型：装不下全部物品体积的小箱排在后面，省掉注定失败的计算

方向与堆叠约束

每件物品通过Rotation枚举声明翻转规则，特殊规则用接口挂接：

• KeepFlat：可转 90° 但不能侧躺，适合带"向上"标记的易碎品
• BestFit：任意方向摆放，Never则完全锁定姿态
• 实现 ConstrainedPlacementItem 的canBePacked()可写自定义规则，比如"每箱最多 4 节电池"；不实现时算法不受额外开销影响

重量平衡与箱型选择

• 装完后若箱子数在 2~12 之间，WeightRedistributor 会在箱对之间挪动物品，把每箱重量拉向平均值，避免"一箱压塌、一箱飘着"
• 库存有限的箱型用LimitedSupplyBox或setBoxQuantity()声明，算法不会超发
• packAllPermutations()能枚举全部可行装箱组合，方便你再按箱价挑最省的一套（箱型多时很慢）

5分钟上手：从安装到第一个装箱结果

git clone https://gitcode.com/gh_mirrors/bo/BoxPacker # 或者集成到自己项目 composer require dvdoug/boxpacker

最小可运行示例（TestBox/TestItem是仓库自带的测试实现，参数依次为外尺寸、空重、内尺寸、限重）：

use DVDoug\BoxPacker\Packer; use DVDoug\BoxPacker\Rotation; use DVDoug\BoxPacker\Test\TestBox; use DVDoug\BoxPacker\Test\TestItem; $packer = new Packer(); $packer->addBox(new TestBox('小箱', 300, 300, 10, 10, 296, 296, 8, 1000)); $packer->addItem(new TestItem('商品A', 250, 250, 12, 200, Rotation::KeepFlat), 2); foreach ($packer->pack() as $box) { echo $box->box->getReference(), '：', $box->items->count(), '件，共', $box->getWeight(), 'g'; }

更完整的用法（单箱试装、结果遍历）看 tests/ 与 docs/getting-started.rst。

落地场景：谁在用它

• 电商运费计算：订单确认后调一次pack()，拿到箱型、箱数、整箱重量，直接喂给承运商 API 询价，30 件订单一次算完，不再靠人肉估
• 履约中心打单：返回的装箱数就是面单数，每件商品落在哪只箱里都有坐标，贴错箱、漏件可以直接对账
• 仓储与托盘规划：同一套空间搜索引擎反过来用——给定集装箱内尺寸，算最多装得下哪些 SKU 组合，减少半空出仓

⚙️ 进阶与调优：超时、预算与异常

• 超时保护：$packer->setTimeoutChecker(new DefaultTimeoutChecker(5.0))，批量任务跑超 5 秒抛TimeoutException及时止损，实现见 src/DefaultTimeoutChecker.php
• 重量平衡预算：setMaxBoxesToBalanceWeight()（默认 12 只）控制平衡阶段触发上限，大件多箱订单调小可省时间
• 边界情况：某件商品放不进任何箱型时默认抛NoBoxesAvailableException；调throwOnUnpackableItem(false)可改为"能装先装"，未装下的用getUnpackedItems()取回人工处理

架构速览：核心模块一览

• Packer.php— 总入口，负责试箱、选最优箱、触发重量平衡
• VolumePacker.php— 单箱内的空间搜索与落子
• WorkingVolume.php— 剩余空间记账，空间搜索只查"空地"
• LayerPacker.php/LayerStabiliser.php— 分层铺底与层内排序
• WeightRedistributor.php— 跨箱重量再分配

社区与展望：如何参与

• 提 issue：实际项目里遇到旋转限制、特殊堆叠等边界情况，直接反馈场景和复现数据
• 提 PR：单测全部 PHPUnit，结构清晰，自定义排序器、新约束接口都可以增量贡献
• 补文档：docs/是 Sphinx 的 rst 文档，加一个行业用例示例的门槛很低

后续方向跟着项目现状走：packAllPermutations()全组合搜索天生耗时，值得做剪枝；自带的 visualiser/ 三维可视化（TypeScript + Vite）在交互和性能上还有明显空间。如果你在用 PHP 做电商或物流系统，想把手写 if-else 的装箱逻辑换成开箱即用的引擎，克隆下来跑一次pack()看看结果。

【免费下载链接】BoxPacker4D bin packing / knapsack problem solver项目地址: https://gitcode.com/gh_mirrors/bo/BoxPacker