3DBinPacking — 三维装箱求解器

基于**遗传算法（GA）**的三维装箱（集装箱装载）求解器，核心算法由 **C++（pybind11 + OpenMP）**实现，Python 侧只需一行调用即返回完整装箱方案。

• PyPI 包名：3DBinPacking（pip install 3DBinPacking）
• 导入模块：packing_solver
• 发布形式：预编译二进制 wheel（.pyd / .so），不随包发布源码

功能特性

• 遗传算法全局搜索货物装载顺序 + 启发式三维装箱解码（多箱 First-Fit + 剩余空间分割）
• 多箱型选择：在候选箱型（如 20GP / 40GP）中按总成本最小自动选箱
• 优化目标综合：箱子成本、空间利用率、货物重心均衡、各箱重量均衡、超重惩罚
• 货物支持水平 90° 旋转（当长边超过可用宽度或长宽相等时自动禁止旋转）
• OpenMP 多线程并行评估个体适应度（threads 参数控制）
• 严格的输入校验：缺失字段、非法尺寸、装不进任何箱型的货物会抛出带定位信息的 ValueError
• 无第三方 Python 运行时依赖

安装

pip install 3DBinPacking

当前已发布的编译产物（wheel 与编译时的 Python 版本 + 平台严格绑定）：

依赖提示：

• Windows：需已安装 Microsoft Visual C++ Redistributable（多数机器已有）
• Linux：需系统装有 OpenMP 运行库 libgomp（Debian/Ubuntu：sudo apt install libgomp1）

其他 Python 版本 / 平台需要另行编译（见文末「本地编译」）。

快速开始

import packing_solver

input_data = {
    "binTable": [
        {"id": "20GP", "l": 590,  "w": 234, "h": 230, "cost": 1500, "weight_limit": 0,      "available": True},
        {"id": "40GP", "l": 1180, "w": 234, "h": 230, "cost": 2000, "weight_limit": 26500,  "available": True},
    ],
    "itemTable": [
        {"id": 0, "l": 113, "w": 109, "h": 110, "weight": 814.464, "factory": 1, "stackable": True},
        {"id": 1, "l": 113, "w": 109, "h": 110, "weight": 712.656, "factory": 1, "stackable": True},
        {"id": 2, "l": 120, "w": 107, "h": 220, "weight": 1337.57, "factory": 4, "stackable": False},
    ],
}

result = packing_solver.pack(input_data, pop_size=100, generations=50)
print(f"箱子数: {result['totalBins']}, 总成本: {result['cost']}, 空间利用率: {result['utilization']:.2%}")
for b in result["packingTable"]:
    print(f"  {b['binType']}: {b['itemCount']} 件, 利用率 {b['spaceUtilization']:.2%}, 重量 {b['currentWeight']:.1f}")

API

packing_solver.pack(input, ...)

返回：结果字典（见下方输出格式）。

输入格式

input = {
    "binTable": [   # 候选箱型列表，可省略（省略时用内置默认箱型 20GP/40GP）
        {
            "id": "40GP",          # 箱型编号（字符串）
            "l": 1180.0,           # 长
            "w": 234.0,            # 宽
            "h": 230.0,            # 高
            "cost": 2000,          # 每个箱子的成本（算法以总成本最小为主要目标）
            "weight_limit": 26500, # 载重上限（0 = 不限）
            "available": True,     # 是否可用；False 的箱型会被忽略
        },
    ],
    "itemTable": [   # 货物列表（必填，非空）
        {
            "id": 0,               # 货物编号（输出中通过 itemIndex 引用，0 起始）
            "l": 113.0,            # 长
            "w": 109.0,            # 宽
            "h": 110.0,            # 高
            "weight": 814.464,     # 重量
            "factory": 1,          # 工厂 / 批次编号（整数）
            "stackable": True,     # 是否允许堆叠
        },
    ],
}

内置默认箱型：20GP（590×234×230，成本 1500，不限重）、40GP（1180×234×230，成本 2000，限重 26500）。

输出格式

result = {
    "fitness": 1234.5,        # 综合适应度：成本 + 重心惩罚 + 重量均衡惩罚（越小越好）
    "cost": 2000,             # 使用箱子的总成本
    "utilization": 0.83,      # 整体空间利用率（已装货物体积 / 用箱总体积）
    "centerPenalty": 0.12,    # 重心偏离中心的惩罚项
    "weightPenalty": 0.0,     # 重量均衡惩罚项
    "sum20": 0,               # 使用的 20 尺箱数（binType 为 20GP/20）
    "sum40": 1,               # 使用的非 20 尺箱数（如 40GP），此处为 1
    "elapsedSeconds": 3.2,    # 求解耗时（秒）
    "totalBins": 1,           # 使用的箱子数
    "packingTable": [         # 每个使用中的箱子一条
        {
            "id": 3,                  # 内部箱子序号
            "binType": "40GP",        # 箱型编号
            "cost": 2000,
            "spaceUtilization": 0.83, # 本箱空间利用率
            "currentWeight": 2864.7,  # 本箱已装重量
            "centerOfGravity": (590.0, 117.0, 115.0),  # 本箱货物重心 (x, y, z)
            "itemCount": 3,           # 本箱货物件数
            "items": [                # 每件货物的摆放信息
                {"itemIndex": 0,      # 对应 itemTable 下标（从 0 开始）
                 "x": 0.0, "y": 0.0, "z": 0.0,   # 货物左下前角坐标（箱内 mm）
                 "rotation": 0},      # 旋转类型：0 = 不旋转，1 = 长宽对调
            ],
        },
    ],
}

坐标原点为集装箱左下前角，单位与输入一致。rotation=1 表示货物在水平面旋转 90°（长宽互换），itemIndex 直接对应 itemTable 的下标，货物是否全部装入看 totalBins 与所有 items 的并集。

错误处理

• 输入缺字段 / 尺寸或重量非正 / 货物装不进任何可用箱型 → 抛 ValueError（消息含具体条目位置）
• 求解器内部异常 → 抛 RuntimeError

算法说明

采用「遗传算法 + 启发式解码」框架：

1. 染色体编码货物装载顺序，GA 通过选择 / 交叉 / 变异搜索最优顺序
2. 解码器按顺序执行多箱 First-Fit 三维装载：依次尝试候选箱型与货物摆放旋转，以剩余空间法确定每个货物的位置
3. 适应度 = 用箱总成本 + 重心偏离惩罚 + 各箱重量不均衡惩罚（并考虑堆叠与工厂约束）
4. 达到 generations 或 time_limit 时返回历史最优解

本地编译（可选）

预编译 wheel 未覆盖你的平台 / Python 版本时，可从源码自行编译：

• 前置：CMake ≥ 3.15、C++17 编译器（Windows 用 MSVC；Linux 参考 WSL_BUILD_GUIDE.md）、OpenMP、pybind11 源码（放在项目根目录 pybind11/，或 pip install pybind11 后改用 find_package）
• 编译后会生成扩展模块（Windows：packing_solver.cpXXX-win_amd64.pyd；Linux：packing_solver.cpython-XXX-*-linux-gnu.so），复制到 dist_compiled/ 后运行 python build_wheel.py dist_compiled/<模块文件> dist 即可生成对应 wheel
• 发布打包一键脚本：bash release.sh（加 --test / --upload 上传）

License

木兰宽松许可证，第2版 (Mulan PSL v2)