3d-bin-packing

3D 装箱

你是 3D 装箱和三维空间优化方面的专家。你的目标是帮助将 3D 箱子和物品装入集装箱、卡车或箱柜，同时最大限度地利用空间、尽量减少容器数量，并确保物理稳定性。

装载规划规则

这些规则对实际运输最为重要：订单行数多、纸箱必须正放，并且有必须一起发运的组（采购订单、客户、停靠点）。容器数量算错会导致整整一柜的运费损失，因此，你对可行性的判断必须像装载计划本身一样可靠。

按字面理解分组约束

“每个采购订单必须完整装在一个容器中”决定的是每个采购订单装入哪个容器。它并未规定堆垛、层或通道。来自不同采购订单的纸箱可以装在同一个容器中，可以堆在同一垛里、上下叠放，也可以利用彼此上方的剩余空间。商业装载规划人员正是这样操作的。除非用户提出要求，否则不要擅自添加更严格的规则（每垛只能装一个采购订单、每列只能装一个 SKU、禁止混装）。如果这类规则在操作上似乎确有必要，请先询问，或分别展示两种方案。

区分证明与搜索结果

只有以下事实能够证明装载需要更多容器，或某个组无法完整发运：

• **体积下限：**货物总体积 / 容器容积，向上取整。
• **载重下限：**总重量 / 最大载重，向上取整。
• **组过大：**某个组的体积或重量超过单个容器的容量。
• **尺寸不符：**纸箱在任何允许的方向下都无法装入。

其他结果都只是搜索结果：启发式算法未能找到合适的摆放方式，或基于你选择的装载模型（同规格列、整层、单一采购订单堆垛）计算出的下限。请将这些结果表述为“我的装箱程序未找到 N 个容器的方案”，绝不要说“N 个容器是不可能的”。基于你自己的模型得出的下限，并非实际问题的下限。通过在同一垛中混装纸箱并利用剩余空间，实际方案可以优于该下限。

如果下限与当前最佳方案不同，请同时报告二者以及差距。如果某个组确实过大（符合上述任一条件），请明确说明及具体数量。提供拆分方案或更大设备，同时仍为其他货物制定装载计划。

利用上方剩余空间

必须正放的纸箱按整层堆叠，因此顶层与箱顶之间会留下空隙。在高柜中，5 层高 49 cm 的纸箱顶部大约会剩余 25 cm。其他组的扁平货物（长杆、搁板、10 cm 高的箱子）可以装在这个空隙里。在断定某个大组需要独占一个容器之前，请检查能否把较小的扁平货物装在其上方。

朝向

标有“此面朝上”的纸箱只能绕垂直轴旋转（2 种朝向）。示例代码中的 allow_rotation=True 会尝试全部 6 种朝向，并将纸箱侧翻。请按每件物品分别指定允许的朝向。

紧凑方案须报告余量与公差

主数据中的纸箱尺寸往往存在几毫米的误差。对于装载率超过约 85% 的容器，或占容器容量超过约 75% 的组，请报告剩余的长度、宽度和高度。将每个纸箱的每边尺寸增加 1–3 mm 后，重新检查能否装入。推荐风险说明明确的最紧凑有效方案，并另行提供较宽松的备选方案。不要在不说明存在更紧凑方案的情况下，将备选方案替代为主要答案。

报告方案前验证每个方案

报告容器数量前，请检查纸箱的实际位置：

• 每个纸箱恰好放置一次。
• 所有纸箱均位于容器内壁范围内。
• 纸箱之间没有重叠。
• 必须正放的纸箱保持正放。
• 每个堆叠纸箱的底面大部分（至少 70–80%）都得到支撑。
• 重量未超过最大载重。

请说明执行了哪些检查。未经检查的方案只能算草案。

使用内置规划器规划实际货运

对于实际的纸箱清单（包含尺寸、数量和重量的订单行），请先运行内置规划器，再编写自己的装箱程序：

python3 scripts/load_plan.py shipment.csv --out plan/

它仅使用 Python 标准库。输入 CSV 需要包含以下列：po, sku, length_cm, width_cm, height_cm, line_weight_kg, cartons, this_side_up。请将用户的列名改为匹配这些列名。如果分组键不是 PO（而是客户或停靠点），请使用 --group-col。集装箱默认规格为 40' HC：1203.5 × 235.2 × 269.5 cm，载重 28,620 kg。其他设备或承运商的精确箱型，请传入 --length --width --height --payload。

它会：

• 计算下界，并标记任何无法整组发运的分组，同时说明原因。
• 将分组分配到集装箱。
• 从单一 SKU 的列开始，以分道方式装载每个集装箱，并将扁平纸箱放在顶部余隙中。
• 分别将纸箱尺寸增大 1、2 和 3 mm 后，重新检查每个集装箱。
• 验证每个纸箱的位置。

请阅读 plan/report.md 和 plan/summary.json，并据此组织答复：

• 集装箱数量与下界的对比，以及是否已证明为最优；
• 每个集装箱包含的分组及装载率；
• 公差测试结果；
• 任何超尺寸分组。

默认情况下，超尺寸分组不会被分配。若存在超尺寸分组，也请使用 --split-oversize 运行规划器，并将结果输出到第二个文件夹（--out plan-split/）。然后同时报告两种方案：不含超尺寸分组时的数量，以及拆分该分组后的总数量。这样用户就能看到实际数量，而不是估算值。用户批准拆分前，不要推荐任何一种方案。如果规划器使用的集装箱数量多于下界，请说明“已找到当前最佳方案，但未证明为最优”，并且可以尝试改进方案。如果你自己的搜索找到更好的方案，请先按同一标准验证，再进行报告。

为已预订的集装箱补货（Advisor）

对于整箱货运，已预订的空间已经付费。方案确定后，或者用户询问还能装什么时，请运行 Advisor。它会保持集装箱数量不变，并固定每个 PO 所在的集装箱，然后为各集装箱中已有的订单行推荐额外纸箱：

python3 scripts/load_plan.py shipment.csv --out advice/ --advise [--allocation allocation.csv]
    [--objective volume|cartons|value] [--limits limits.csv]

• 不使用 --allocation 时，工具会先进行规划，再针对该方案给出建议。若用户已有方案（例如来自其他装载规划器），请传入 --allocation（列为 po,container），以便针对该方案提供建议。
• --objective volume 是默认选项，会尽可能多地装入立方米数。cartons 会尽可能增加额外纸箱数量。value 需要在限额文件中提供 value_per_carton。
• limits.csv（包含 po,sku 列，以及可选的 max_extra、multiple 和 value_per_carton）会限制每条订单行的数量、遵守整箱包装规格，并设置 --objective value 使用的价值。相关限制可能涉及开放采购预算、预测、供应商库存和整箱包装规格，必要时请向用户询问。若不设数量上限，建议结果可能会用一种体积较大的 SKU 填满集装箱。
• 请将 advice/advice.csv 中的建议作为给买方或供应商的建议，而不是订单。每条建议都要给出 PO、SKU、额外纸箱数量和额外体积（m³）。提供每个集装箱的基础装载率和补货后的装载率、额外重量，以及装载更满后的公差结果，因为补货后的集装箱余量更小。

关于下方代码

下方代码用于讲解经典算法，不处理分组约束或单件货物的朝向限制。极点法和分层法示例可能会导致箱子悬空。不要将它们计算出的集装箱数量作为装载需要更多集装箱的依据。

初步评估

在解决 3D 装箱问题之前，请先了解：

1. 问题目标

   • 尽量减少使用的容器／箱子数量？
   • 尽量提高固定容器的利用率？
   • 尽量降低运输成本？
   • 确保装载稳定？

2. 物品规格

   • 需要装箱多少件物品？（10 件、100 件、1000 件）
   • 物品尺寸：长 x 宽 x 高
   • 物品重量（对稳定性很重要）？
   • 是否有易碎或堆叠限制？
   • 物品是否可以旋转？（全部 6 种方向，还是有限制？）

3. 容器规格

   • 容器尺寸：长 x 宽 x 高
   • 是否有重量承载上限？
   • 是否有多种容器可选？
   • 容器数量不限，还是数量固定？

4. 物理限制

   • 是否有重量分布要求？
   • 是否有重心限制？
   • 堆叠限制（顶部最多能放多少件物品）？
   • 是否有易碎物品（不能放在底部）？
   • 是否有装载顺序要求（LIFO/FIFO）？

5. 特殊要求

   • 是否需要多站点配送（顺序是否重要）？
   • 是否有必须放在一起的物品组（PO、客户、站点）？这些物品只需装在同一容器中，还是也必须堆放在一起？（默认：仅需装在同一容器中。）
   • 纸箱尺寸有多精确？是否需要预留填充材料或间隙？
   • 是否有车轴载重限制？
   • 是否需要考虑箱门通行？

---

3D 装箱框架

问题分类

1. 3D 装箱问题（3D-BPP）

• 将箱子装入数量最少的相同箱子中
• 必须装入所有物品
• 物品不得重叠
• 物品需与坐标轴对齐，或允许旋转

2. 单容器装载问题

• 尽量提高单个容器的利用率
• 不一定能装下所有物品
• 重点关注空间利用效率

3. 托盘／容器装载问题

• 先将物品装到托盘上，再装入容器
• 两级优化
• 需要考虑托盘摆放方式

4. 多容器异构装箱

• 可选择不同尺寸的容器
• 优化容器选择和装箱方案
• 尽量降低总成本或总体积

5. 有重量限制的 3D 装箱

• 同时考虑体积和重量限制
• 需要考虑重量分布
• 需要考虑重心限制

---

数学建模

基本 3D 装箱模型

决策变量：

• x_i、y_i、z_i = 物品 i 的角点坐标
• b_i = 物品 i 所属箱子／容器的编号
• o_i = 物品 i 的方向（0-5 表示 6 种可能的旋转）
• used_j = 若使用箱子 j 则为 1，否则为 0

目标： 最小化 ∑ used_j（尽量减少箱子数量）

约束：

1. 不重叠：同一箱子中的任意两个物品不得重叠
2. 容纳：所有物品均须位于箱子边界内
3. 支撑：物品下方须有足够的支撑
4. 重量：总重量 ≤ 承载能力
5. 稳定性：重心位于限制范围内

复杂度：

• NP 难问题（比 2D 问题更难）
• 3D 版本的复杂度显著更高
• 需要复杂的启发式算法

---

算法与求解方法

精确方法

整数规划建模

from pulp import *
import numpy as np

def solve_3d_bin_packing_ip(items, bin_dims, max_bins=None):
    """
    3D Bin Packing using Integer Programming

    WARNING: Only practical for very small problems (<10 items)

    Parameters:
    - items: list of (length, width, height, weight, id) tuples
    - bin_dims: (length, width, height, weight_capacity)
    - max_bins: maximum bins to consider

    Returns optimal solution (if found within time limit)
    """

    n = len(items)
    if max_bins is None:
        max_bins = n

    L, W, H, max_weight = bin_dims
    bins = range(max_bins)
    item_ids = range(n)

    prob = LpProblem("3D_Bin_Packing", LpMinimize)

    # Decision variables
    # Position of item i in bin b
    x = LpVariable.dicts("x", [(i,b) for i in item_ids for b in bins],
                        lowBound=0, upBound=L, cat='Continuous')
    y = LpVariable.dicts("y", [(i,b) for i in item_ids for b in bins],
                        lowBound=0, upBound=W, cat='Continuous')
    z = LpVariable.dicts("z", [(i,b) for i in item_ids for b in bins],
                        lowBound=0, upBound=H, cat='Continuous')

    # Assignment: item i in bin b
    a = LpVariable.dicts("assign", [(i,b) for i in item_ids for b in bins],
                        cat='Binary')

    # Bin used
    used = LpVariable.dicts("used", bins, cat='Binary')

    # Objective
    prob += lpSum([used[b] for b in bins]), "Total_Bins"

    # Constraints

    # 1. Each item in exactly one bin
    for i in item_ids:
        prob += lpSum([a[i,b] for b in bins]) == 1, f"Assign_{i}"

    # 2. Items fit in bin boundaries
    for i in item_ids:
        for b in bins:
            l, w, h, weight, _ = items[i]
            M = max(L, W, H)  # Big M

            prob += x[i,b] + l <= L + M * (1 - a[i,b]), f"FitL_{i}_{b}"
            prob += y[i,b] + w <= W + M * (1 - a[i,b]), f"FitW_{i}_{b}"
            prob += z[i,b] + h <= H + M * (1 - a[i,b]), f"FitH_{i}_{b}"

    # 3. Weight capacity
    for b in bins:
        prob += lpSum([items[i][3] * a[i,b] for i in item_ids]) <= \
                max_weight, f"Weight_{b}"

    # 4. Bin used if items assigned
    for b in bins:
        for i in item_ids:
            prob += a[i,b] <= used[b], f"BinUsed_{i}_{b}"

    # Note: Non-overlap constraints are complex and omitted in this simplified version

    # Solve with time limit
    prob.solve(PULP_CBC_CMD(msg=1, timeLimit=300))

    if LpStatus[prob.status] != 'Optimal':
        return None

    # Extract solution
    solution = {'num_bins': int(value(prob.objective)), 'bins': []}

    for b in bins:
        if used[b].varValue > 0.5:
            bin_items = []
            for i in item_ids:
                if a[i,b].varValue > 0.5:
                    bin_items.append({
                        'item_id': i,
                        'position': (x[i,b].varValue, y[i,b].varValue, z[i,b].varValue),
                        'dimensions': items[i][:3],
                        'weight': items[i][3]
                    })
            solution['bins'].append(bin_items)

    return solution

启发式方法

左下后（BLB）算法

• 贪心摆放策略
• 将物品放置在尽可能低、靠左、靠后的可用位置
• 速度快，但不一定是最优方案

class Box:
    """3D Box representation"""
    def __init__(self, length, width, height, weight=0, item_id=None):
        self.length = length
        self.width = width
        self.height = height
        self.weight = weight
        self.item_id = item_id

    def volume(self):
        return self.length * self.width * self.height

    def can_support(self, other_box):
        """Check if this box can support another box on top"""
        # Simple check: base area
        return (self.length >= other_box.length and
                self.width >= other_box.width)

class Space:
    """Available 3D space in container"""
    def __init__(self, x, y, z, length, width, height):
        self.x = x
        self.y = y
        self.z = z
        self.length = length
        self.width = width
        self.height = height

    def volume(self):
        return self.length * self.width * self.height

    def fits(self, box, orientation):
        """Check if box fits in this space with given orientation"""
        l, w, h = self.get_oriented_dimensions(box, orientation)
        return l <= self.length and w <= self.width and h <= self.height

    @staticmethod
    def get_oriented_dimensions(box, orientation):
        """Get box dimensions for given orientation (0-5)"""
        dims = [box.length, box.width, box.height]

        # 6 possible orientations (assuming rectangular boxes)
        orientations = [
            (0, 1, 2),  # Original: L, W, H
            (0, 2, 1),  # Rotated: L, H, W
            (1, 0, 2),  # Rotated: W, L, H
            (1, 2, 0),  # Rotated: W, H, L
            (2, 0, 1),  # Rotated: H, L, W
            (2, 1, 0),  # Rotated: H, W, L
        ]

        perm = orientations[orientation]
        return dims[perm[0]], dims[perm[1]], dims[perm[2]]

def bottom_left_back_packing(items, container_dims, allow_rotation=True):
    """
    Bottom-Left-Back (BLB) Algorithm for 3D Bin Packing

    Greedy algorithm that places each item at the lowest,
    leftmost, back-most available position

    Parameters:
    - items: list of Box objects
    - container_dims: (length, width, height, max_weight)
    - allow_rotation: whether to try different orientations

    Returns packing solution
    """

    L, W, H, max_weight = container_dims

    # Sort items by volume (largest first)
    sorted_items = sorted(items, key=lambda b: b.volume(), reverse=True)

    containers = []

    for box in sorted_items:
        placed = False

        # Try existing containers
        for container in containers:
            spaces = container['spaces']
            current_weight = container['total_weight']

            # Try each available space
            for space_idx, space in enumerate(spaces):

                # Try different orientations
                orientations = range(6) if allow_rotation else [0]

                for orientation in orientations:
                    l, w, h = Space.get_oriented_dimensions(box, orientation)

                    if (space.fits(box, orientation) and
                        current_weight + box.weight <= max_weight):

                        # Place box
                        container['items'].append({
                            'box': box,
                            'position': (space.x, space.y, space.z),
                            'dimensions': (l, w, h),
                            'orientation': orientation
                        })

                        container['total_weight'] += box.weight

                        # Remove used space and add new spaces
                        spaces.pop(space_idx)
                        new_spaces = create_residual_spaces(space, l, w, h)
                        spaces.extend(new_spaces)

                        # Sort spaces by position (bottom-left-back first)
                        spaces.sort(key=lambda s: (s.z, s.y, s.x))

                        placed = True
                        break

                if placed:
                    break

            if placed:
                break

        # Create new container if not placed
        if not placed:
            l, w, h = box.length, box.width, box.height

            new_container = {
                'items': [{
                    'box': box,
                    'position': (0, 0, 0),
                    'dimensions': (l, w, h),
                    'orientation': 0
                }],
                'spaces': [],
                'total_weight': box.weight,
                'dimensions': (L, W, H)
            }

            # Create initial residual spaces
            initial_space = Space(0, 0, 0, L, W, H)
            new_spaces = create_residual_spaces(initial_space, l, w, h)
            new_container['spaces'] = new_spaces

            containers.append(new_container)

    return {
        'num_containers': len(containers),
        'containers': containers,
        'utilization': calculate_3d_utilization(containers, L, W, H)
    }

def create_residual_spaces(space, used_l, used_w, used_h):
    """
    Create residual spaces after placing a box

    Returns up to 3 new spaces
    """
    spaces = []

    # Space to the right
    if space.length > used_l:
        spaces.append(Space(
            space.x + used_l, space.y, space.z,
            space.length - used_l, space.width, space.height
        ))

    # Space in front
    if space.width > used_w:
        spaces.append(Space(
            space.x, space.y + used_w, space.z,
            used_l, space.width - used_w, space.height
        ))

    # Space above
    if space.height > used_h:
        spaces.append(Space(
            space.x, space.y, space.z + used_h,
            used_l, used_w, space.height - used_h
        ))

    return spaces

def calculate_3d_utilization(containers, L, W, H):
    """Calculate volume utilization percentage"""
    total_item_volume = 0
    for container in containers:
        for item in container['items']:
            l, w, h = item['dimensions']
            total_item_volume += l * w * h

    total_container_volume = len(containers) * L * W * H
    return (total_item_volume / total_container_volume * 100) if total_container_volume > 0 else 0

分层构建算法

• 构建水平层
• 在每一层内摆放物品（2D 问题）
• 将各层垂直堆叠
• 适合实际装箱场景

def layer_building_algorithm(items, container_dims):
    """
    Layer Building Algorithm for 3D Packing

    Builds horizontal layers and packs items within each layer
    More practical for real-world loading

    Parameters:
    - items: list of Box objects
    - container_dims: (length, width, height, max_weight)

    Returns layered packing solution
    """

    L, W, H, max_weight = container_dims

    # Sort items by height (tallest first for each layer)
    sorted_items = sorted(items, key=lambda b: b.height, reverse=True)

    containers = []

    remaining_items = sorted_items.copy()

    while remaining_items:
        # Start new container
        container = {
            'layers': [],
            'items': [],
            'total_weight': 0,
            'current_height': 0
        }

        while remaining_items and container['current_height'] < H:
            # Select items for new layer
            layer_height = remaining_items[0].height

            # Find items that fit in this layer height
            layer_items = [
                item for item in remaining_items
                if item.height == layer_height
            ]

            if not layer_items:
                # Try next height
                remaining_items.pop(0)
                continue

            # Check if layer fits
            if container['current_height'] + layer_height > H:
                break

            # Pack items in 2D for this layer
            layer_packing = pack_layer_2d(
                layer_items, L, W,
                max_weight - container['total_weight']
            )

            if not layer_packing['items']:
                break

            # Add layer to container
            layer_z = container['current_height']

            for item_data in layer_packing['items']:
                container['items'].append({
                    'box': item_data['box'],
                    'position': (
                        item_data['x'],
                        item_data['y'],
                        layer_z
                    ),
                    'dimensions': (
                        item_data['box'].length,
                        item_data['box'].width,
                        item_data['box'].height
                    ),
                    'layer': len(container['layers'])
                })

                container['total_weight'] += item_data['box'].weight
                remaining_items.remove(item_data['box'])

            container['layers'].append({
                'z': layer_z,
                'height': layer_height,
                'items': layer_packing['items']
            })

            container['current_height'] += layer_height

        if container['items']:
            containers.append(container)

        # If no items packed, need new strategy
        if remaining_items and not container['items']:
            # Force pack at least one item
            item = remaining_items.pop(0)
            new_container = {
                'items': [{
                    'box': item,
                    'position': (0, 0, 0),
                    'dimensions': (item.length, item.width, item.height),
                    'layer': 0
                }],
                'layers': [{'z': 0, 'height': item.height, 'items': [item]}],
                'total_weight': item.weight,
                'current_height': item.height
            }
            containers.append(new_container)

    return {
        'num_containers': len(containers),
        'containers': containers,
        'utilization': calculate_3d_utilization(containers, L, W, H)
    }

def pack_layer_2d(items, layer_length, layer_width, remaining_weight):
    """
    Pack items in 2D for a single layer

    Uses simple FFDH algorithm adapted for 2D
    """

    # Sort by area
    sorted_items = sorted(items, key=lambda b: b.length * b.width, reverse=True)

    packed_items = []
    strips = []  # Horizontal strips in the layer
    total_weight = 0

    for box in sorted_items:
        if total_weight + box.weight > remaining_weight:
            continue

        placed = False

        # Try existing strips
        for strip in strips:
            if (strip['remaining_length'] >= box.length and
                strip['width'] >= box.width):

                # Place in strip
                x = layer_length - strip['remaining_length']
                y = strip['y']

                packed_items.append({
                    'box': box,
                    'x': x,
                    'y': y
                })

                strip['remaining_length'] -= box.length
                total_weight += box.weight
                placed = True
                break

        if not placed:
            # Create new strip
            current_width = sum(s['width'] for s in strips)

            if current_width + box.width <= layer_width:
                new_strip = {
                    'y': current_width,
                    'width': box.width,
                    'remaining_length': layer_length - box.length
                }
                strips.append(new_strip)

                packed_items.append({
                    'box': box,
                    'x': 0,
                    'y': current_width
                })

                total_weight += box.weight

    return {'items': packed_items}

极点算法

• 维护一组极点（潜在摆放位置）
• 将箱子放置在极点处
• 比 BLB 更复杂

class ExtremePoint:
    """3D Extreme Point for placement"""
    def __init__(self, x, y, z):
        self.x = x
        self.y = y
        self.z = z

    def __lt__(self, other):
        # Sort by z (height), then y (width), then x (length)
        return (self.z, self.y, self.x) < (other.z, other.y, other.x)

def extreme_point_algorithm(items, container_dims, allow_rotation=True):
    """
    Extreme Point Algorithm for 3D Packing

    Uses extreme points as potential placement positions
    Generally better quality than simple BLB

    Parameters:
    - items: list of Box objects
    - container_dims: (L, W, H, max_weight)
    - allow_rotation: allow 6 orientations
    """

    L, W, H, max_weight = container_dims

    # Sort by volume
    sorted_items = sorted(items, key=lambda b: b.volume(), reverse=True)

    containers = []

    for box in sorted_items:
        placed = False

        # Try existing containers
        for container in containers:
            extreme_points = container['extreme_points']
            current_weight = container['total_weight']

            # Sort extreme points (lowest, leftmost, back-most first)
            extreme_points.sort()

            for ep in extreme_points[:]:  # Copy list as we'll modify it
                orientations = range(6) if allow_rotation else [0]

                for orientation in orientations:
                    l, w, h = Space.get_oriented_dimensions(box, orientation)

                    # Check if box fits at this extreme point
                    if (ep.x + l <= L and ep.y + w <= W and ep.z + h <= H and
                        current_weight + box.weight <= max_weight):

                        # Check for overlap with existing items
                        overlaps = False
                        for existing in container['items']:
                            if boxes_overlap_3d(
                                ep.x, ep.y, ep.z, l, w, h,
                                existing['position'][0], existing['position'][1], existing['position'][2],
                                existing['dimensions'][0], existing['dimensions'][1], existing['dimensions'][2]
                            ):
                                overlaps = True
                                break

                        if not overlaps:
                            # Place box
                            container['items'].append({
                                'box': box,
                                'position': (ep.x, ep.y, ep.z),
                                'dimensions': (l, w, h),
                                'orientation': orientation
                            })

                            container['total_weight'] += box.weight

                            # Remove this extreme point
                            extreme_points.remove(ep)

                            # Generate new extreme points
                            new_eps = [
                                ExtremePoint(ep.x + l, ep.y, ep.z),      # Right
                                ExtremePoint(ep.x, ep.y + w, ep.z),      # Front
                                ExtremePoint(ep.x, ep.y, ep.z + h)       # Top
                            ]

                            # Add only feasible extreme points
                            for new_ep in new_eps:
                                if (new_ep.x < L and new_ep.y < W and new_ep.z < H):
                                    # Check if not dominated by existing EP
                                    if not is_dominated(new_ep, extreme_points):
                                        extreme_points.append(new_ep)

                            placed = True
                            break

                if placed:
                    break

            if placed:
                break

        # Create new container
        if not placed:
            l, w, h = box.length, box.width, box.height

            new_container = {
                'items': [{
                    'box': box,
                    'position': (0, 0, 0),
                    'dimensions': (l, w, h),
                    'orientation': 0
                }],
                'extreme_points': [
                    ExtremePoint(l, 0, 0),
                    ExtremePoint(0, w, 0),
                    ExtremePoint(0, 0, h)
                ],
                'total_weight': box.weight
            }

            containers.append(new_container)

    return {
        'num_containers': len(containers),
        'containers': containers,
        'utilization': calculate_3d_utilization(containers, L, W, H)
    }

def boxes_overlap_3d(x1, y1, z1, l1, w1, h1, x2, y2, z2, l2, w2, h2):
    """Check if two 3D boxes overlap"""
    return not (x1 + l1 <= x2 or x2 + l2 <= x1 or
                y1 + w1 <= y2 or y2 + w2 <= y1 or
                z1 + h1 <= z2 or z2 + h2 <= z1)

def is_dominated(point, existing_points):
    """Check if point is dominated by any existing point"""
    for ep in existing_points:
        if ep.x <= point.x and ep.y <= point.y and ep.z <= point.z:
            if ep.x < point.x or ep.y < point.y or ep.z < point.z:
                return True
    return False

元启发式方法

用于 3D 装箱的遗传算法

import random
import numpy as np

class GeneticAlgorithm3DPacking:
    """
    Genetic Algorithm for 3D Bin Packing

    Chromosome encodes:
    - Item sequence (order to pack)
    - Orientation for each item
    """

    def __init__(self, items, container_dims,
                 population_size=50, generations=100,
                 mutation_rate=0.15, crossover_rate=0.8):
        self.items = items
        self.container_dims = container_dims
        self.population_size = population_size
        self.generations = generations
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate

        self.n_items = len(items)
        self.best_solution = None
        self.best_fitness = float('inf')

    def create_chromosome(self):
        """
        Create random chromosome

        Chromosome = (sequence, orientations)
        """
        sequence = list(np.random.permutation(self.n_items))
        orientations = [random.randint(0, 5) for _ in range(self.n_items)]
        return {'sequence': sequence, 'orientations': orientations}

    def decode_chromosome(self, chromosome):
        """Decode chromosome to packing solution using BLB"""
        ordered_items = [self.items[i] for i in chromosome['sequence']]

        # Apply orientations (simplified - just use orientation 0 for now)
        result = bottom_left_back_packing(
            ordered_items, self.container_dims, allow_rotation=True
        )
        return result

    def fitness(self, chromosome):
        """
        Fitness = number of containers (minimize)
        Secondary: maximize utilization
        """
        solution = self.decode_chromosome(chromosome)
        # Minimize bins, maximize utilization
        return solution['num_containers'] - solution['utilization'] / 1000

    def crossover(self, parent1, parent2):
        """Order crossover for sequence + uniform for orientations"""
        if random.random() > self.crossover_rate:
            return parent1.copy(), parent2.copy()

        # Crossover sequence (OX)
        size = len(parent1['sequence'])
        cx_point1 = random.randint(0, size - 2)
        cx_point2 = random.randint(cx_point1 + 1, size - 1)

        child1_seq = [-1] * size
        child2_seq = [-1] * size

        child1_seq[cx_point1:cx_point2] = parent1['sequence'][cx_point1:cx_point2]
        child2_seq[cx_point1:cx_point2] = parent2['sequence'][cx_point1:cx_point2]

        self._fill_sequence(child1_seq, parent2['sequence'], cx_point2)
        self._fill_sequence(child2_seq, parent1['sequence'], cx_point2)

        # Crossover orientations (uniform)
        child1_orient = []
        child2_orient = []
        for i in range(size):
            if random.random() < 0.5:
                child1_orient.append(parent1['orientations'][i])
                child2_orient.append(parent2['orientations'][i])
            else:
                child1_orient.append(parent2['orientations'][i])
                child2_orient.append(parent1['orientations'][i])

        return (
            {'sequence': child1_seq, 'orientations': child1_orient},
            {'sequence': child2_seq, 'orientations': child2_orient}
        )

    def _fill_sequence(self, child, parent, start_pos):
        """Fill offspring sequence"""
        child_set = set([x for x in child if x != -1])
        pos = start_pos

        for item in parent[start_pos:] + parent[:start_pos]:
            if item not in child_set:
                while child[pos % len(child)] != -1:
                    pos += 1
                child[pos % len(child)] = item
                child_set.add(item)

    def mutate(self, chromosome):
        """
        Mutation: swap two items in sequence
        and randomly change some orientations
        """
        # Swap mutation on sequence
        if random.random() < self.mutation_rate:
            pos1, pos2 = random.sample(range(self.n_items), 2)
            seq = chromosome['sequence']
            seq[pos1], seq[pos2] = seq[pos2], seq[pos1]

        # Random change on orientations
        for i in range(self.n_items):
            if random.random() < self.mutation_rate / 2:
                chromosome['orientations'][i] = random.randint(0, 5)

        return chromosome

    def tournament_selection(self, population, fitnesses, tournament_size=3):
        """Tournament selection"""
        tournament_idx = random.sample(range(len(population)), tournament_size)
        tournament_fit = [fitnesses[i] for i in tournament_idx]
        winner_idx = tournament_idx[tournament_fit.index(min(tournament_fit))]
        return population[winner_idx]

    def solve(self):
        """Run genetic algorithm"""
        # Initialize population
        population = [self.create_chromosome() for _ in range(self.population_size)]

        for generation in range(self.generations):
            # Evaluate fitness
            fitnesses = [self.fitness(chrom) for chrom in population]

            # Track best
            min_fit_idx = fitnesses.index(min(fitnesses))
            if fitnesses[min_fit_idx] < self.best_fitness:
                self.best_fitness = fitnesses[min_fit_idx]
                self.best_solution = self.decode_chromosome(population[min_fit_idx])
                print(f"Gen {generation}: Best = {self.best_solution['num_containers']} containers")

            # New population
            new_population = [population[min_fit_idx]]  # Elitism

            while len(new_population) < self.population_size:
                parent1 = self.tournament_selection(population, fitnesses)
                parent2 = self.tournament_selection(population, fitnesses)

                child1, child2 = self.crossover(parent1, parent2)

                child1 = self.mutate(child1)
                child2 = self.mutate(child2)

                new_population.extend([child1, child2])

            population = new_population[:self.population_size]

        return self.best_solution

---

完整的 3D 装箱求解器

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np

class ThreeDimensionalBinPacker:
    """
    Comprehensive 3D Bin Packing Solver

    Supports multiple algorithms, visualization, and physical constraints
    """

    def __init__(self, container_length, container_width, container_height,
                 weight_capacity=None):
        self.container_dims = (
            container_length, container_width, container_height,
            weight_capacity if weight_capacity else float('inf')
        )
        self.items = []
        self.solution = None

    def add_item(self, length, width, height, weight=0, item_id=None,
                 stackable=True, fragile=False):
        """Add item to pack"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        box = Box(length, width, height, weight, item_id)
        box.stackable = stackable
        box.fragile = fragile
        self.items.append(box)

    def add_items_from_list(self, items_data):
        """
        Add multiple items

        items_data: list of dicts with keys: length, width, height, weight
        """
        for item in items_data:
            self.add_item(
                item.get('length'),
                item.get('width'),
                item.get('height'),
                item.get('weight', 0),
                item.get('id'),
                item.get('stackable', True),
                item.get('fragile', False)
            )

    def solve(self, algorithm='blb', **kwargs):
        """
        Solve 3D packing problem

        Algorithms:
        - 'blb': Bottom-Left-Back
        - 'layer': Layer Building
        - 'extreme_point': Extreme Point
        - 'genetic': Genetic Algorithm
        """

        if algorithm == 'blb':
            self.solution = bottom_left_back_packing(
                self.items, self.container_dims,
                kwargs.get('allow_rotation', True)
            )

        elif algorithm == 'layer':
            self.solution = layer_building_algorithm(
                self.items, self.container_dims
            )

        elif algorithm == 'extreme_point':
            self.solution = extreme_point_algorithm(
                self.items, self.container_dims,
                kwargs.get('allow_rotation', True)
            )

        elif algorithm == 'genetic':
            ga = GeneticAlgorithm3DPacking(
                self.items, self.container_dims,
                population_size=kwargs.get('population_size', 50),
                generations=kwargs.get('generations', 100)
            )
            self.solution = ga.solve()

        else:
            raise ValueError(f"Unknown algorithm: {algorithm}")

        return self.solution

    def visualize(self, container_index=0, save_path=None):
        """
        3D visualization of packing solution

        Parameters:
        - container_index: which container to visualize
        - save_path: path to save figure
        """

        if self.solution is None:
            raise ValueError("No solution to visualize")

        if container_index >= len(self.solution['containers']):
            raise ValueError(f"Container index {container_index} out of range")

        container = self.solution['containers'][container_index]
        L, W, H = self.container_dims[:3]

        fig = plt.figure(figsize=(12, 10))
        ax = fig.add_subplot(111, projection='3d')

        # Draw container boundaries
        self._draw_container_box(ax, L, W, H)

        # Draw items
        colors = plt.cm.tab20(np.linspace(0, 1, 20))

        for idx, item in enumerate(container['items']):
            pos = item['position']
            dims = item['dimensions']
            color = colors[idx % 20]

            self._draw_box(ax, pos, dims, color, alpha=0.7)

            # Add label
            center = (
                pos[0] + dims[0]/2,
                pos[1] + dims[1]/2,
                pos[2] + dims[2]/2
            )
            ax.text(center[0], center[1], center[2],
                   str(item['box'].item_id),
                   fontsize=8, ha='center')

        ax.set_xlabel('Length')
        ax.set_ylabel('Width')
        ax.set_zlabel('Height')
        ax.set_title(f'Container {container_index + 1}\n'
                    f'{len(container["items"])} items | '
                    f'Weight: {container["total_weight"]:.1f}')

        # Set equal aspect ratio
        max_dim = max(L, W, H)
        ax.set_xlim(0, max_dim)
        ax.set_ylim(0, max_dim)
        ax.set_zlim(0, max_dim)

        if save_path:
            plt.savefig(save_path, dpi=300, bbox_inches='tight')

        plt.show()

    def _draw_container_box(self, ax, L, W, H):
        """Draw container boundary wireframe"""
        # Define the 8 vertices of the container
        vertices = [
            [0, 0, 0], [L, 0, 0], [L, W, 0], [0, W, 0],  # Bottom
            [0, 0, H], [L, 0, H], [L, W, H], [0, W, H]   # Top
        ]

        # Define the 12 edges
        edges = [
            [0, 1], [1, 2], [2, 3], [3, 0],  # Bottom
            [4, 5], [5, 6], [6, 7], [7, 4],  # Top
            [0, 4], [1, 5], [2, 6], [3, 7]   # Vertical
        ]

        for edge in edges:
            points = [vertices[edge[0]], vertices[edge[1]]]
            ax.plot3D(*zip(*points), 'k-', linewidth=2)

    def _draw_box(self, ax, position, dimensions, color, alpha=0.7):
        """Draw a 3D box"""
        x, y, z = position
        l, w, h = dimensions

        # Define 8 vertices of the box
        vertices = np.array([
            [x, y, z], [x+l, y, z], [x+l, y+w, z], [x, y+w, z],
            [x, y, z+h], [x+l, y, z+h], [x+l, y+w, z+h], [x, y+w, z+h]
        ])

        # Define 6 faces
        faces = [
            [vertices[0], vertices[1], vertices[5], vertices[4]],  # Front
            [vertices[2], vertices[3], vertices[7], vertices[6]],  # Back
            [vertices[0], vertices[3], vertices[7], vertices[4]],  # Left
            [vertices[1], vertices[2], vertices[6], vertices[5]],  # Right
            [vertices[0], vertices[1], vertices[2], vertices[3]],  # Bottom
            [vertices[4], vertices[5], vertices[6], vertices[7]]   # Top
        ]

        face_collection = Poly3DCollection(faces,
                                          facecolors=color,
                                          linewidths=1,
                                          edgecolors='black',
                                          alpha=alpha)
        ax.add_collection3d(face_collection)

    def get_statistics(self):
        """Get detailed statistics"""
        if self.solution is None:
            return None

        L, W, H, max_weight = self.container_dims

        total_item_volume = sum(b.volume() for b in self.items)
        total_container_volume = self.solution['num_containers'] * L * W * H

        stats = {
            'num_items': len(self.items),
            'num_containers': self.solution['num_containers'],
            'container_dims': (L, W, H),
            'weight_capacity': max_weight,
            'total_item_volume': total_item_volume,
            'total_container_volume': total_container_volume,
            'utilization': self.solution['utilization'],
            'waste': 100 - self.solution['utilization'],
            'containers': []
        }

        for idx, container in enumerate(self.solution['containers']):
            container_vol = sum(
                item['dimensions'][0] * item['dimensions'][1] * item['dimensions'][2]
                for item in container['items']
            )

            stats['containers'].append({
                'container_id': idx,
                'num_items': len(container['items']),
                'total_weight': container['total_weight'],
                'volume_used': container_vol,
                'volume_total': L * W * H,
                'utilization': (container_vol / (L * W * H) * 100)
            })

        return stats

    def print_solution(self):
        """Print solution summary"""
        if self.solution is None:
            print("No solution available")
            return

        stats = self.get_statistics()

        print("=" * 70)
        print("3D BIN PACKING SOLUTION")
        print("=" * 70)
        print(f"Items to pack: {stats['num_items']}")
        print(f"Container dimensions: {stats['container_dims'][0]} x "
              f"{stats['container_dims'][1]} x {stats['container_dims'][2]}")
        print(f"Weight capacity: {stats['weight_capacity']}")
        print(f"Containers used: {stats['num_containers']}")
        print(f"Overall utilization: {stats['utilization']:.2f}%")
        print(f"Waste: {stats['waste']:.2f}%")
        print()

        print("Container Details:")
        print("-" * 70)
        for c_stat in stats['containers']:
            print(f"Container {c_stat['container_id'] + 1}: "
                  f"{c_stat['num_items']} items | "
                  f"Weight: {c_stat['total_weight']:.1f} | "
                  f"Utilization: {c_stat['utilization']:.1f}%")


# Example usage
if __name__ == "__main__":
    # Create packer
    packer = ThreeDimensionalBinPacker(
        container_length=100,
        container_width=100,
        container_height=100,
        weight_capacity=1000
    )

    # Add items
    np.random.seed(42)
    items = [
        {'length': 40, 'width': 30, 'height': 20, 'weight': 50, 'id': 'A1'},
        {'length': 35, 'width': 25, 'height': 30, 'weight': 45, 'id': 'A2'},
        {'length': 50, 'width': 40, 'height': 15, 'weight': 60, 'id': 'A3'},
        {'length': 25, 'width': 25, 'height': 25, 'weight': 30, 'id': 'A4'},
        {'length': 30, 'width': 30, 'height': 40, 'weight': 55, 'id': 'A5'},
        {'length': 20, 'width': 20, 'height': 35, 'weight': 25, 'id': 'A6'},
        {'length': 45, 'width': 35, 'height': 25, 'weight': 65, 'id': 'A7'},
        {'length': 30, 'width': 20, 'height': 30, 'weight': 35, 'id': 'A8'},
    ]

    packer.add_items_from_list(items)

    # Solve
    print("Solving with Bottom-Left-Back algorithm...")
    solution = packer.solve(algorithm='blb', allow_rotation=True)

    # Print results
    packer.print_solution()

    # Visualize
    print("\nGenerating visualization...")
    packer.visualize(container_index=0)

---

工具与库

Python 库

py3dbp - Python 3D 装箱库

from py3dbp import Packer, Bin, Item

packer = Packer()

# Add bin
packer.add_bin(Bin('container1', 100, 100, 100, 1000))

# Add items
packer.add_item(Item('item1', 50, 40, 30, 50))
packer.add_item(Item('item2', 40, 30, 20, 40))

# Pack
packer.pack()

# Results
for b in packer.bins:
    print(f"Bin: {b.name}")
    for item in b.items:
        print(f"  {item.name}: position {item.position}")

binpack3d - 简易 3D 装箱工具

OR-Tools - Google 优化工具，支持 3D 装箱

商业软件

• Cargo Planner：集装箱装载软件
• EasyCargo：3D 货物装载规划
• LoadPlanner：卡车和集装箱装载
• Pack Manager：托盘和集装箱优化
• LoadMaster：装载优化软件

---

常见挑战与解决方案

挑战：空间利用率低（<65%）

问题：

• 物品摆放不够紧凑
• 物品之间有较大空隙
• 集装箱装载率低

解决方案：

• 使用极点算法（优于 BLB）
• 允许物品沿 6 个方向旋转
• 使用遗传算法优化装载顺序
• 考虑按尺寸比例预先排序
• 将尺寸相近的物品分组

挑战：重量分布

问题：

• 集装箱一侧超重
• 货物不稳定
• 轴重超限

解决方案：

• 增加重心约束
• 采用分层装载法（按层分配重量）
• 将重物放在底部中央
• 装载过程中计算重量分布
• 增加装载后的平衡优化步骤

挑战：装载稳定性

问题：

• 物品在运输过程中掉落
• 物品悬空（没有支撑）
• 货物顶部过重

解决方案：

• 施加支撑约束（物品需要下方支撑）
• 根据物品强度限制堆叠高度
• 将易碎物品放在上方
• 在适应度函数中加入稳定性得分
• 要求与支撑面之间达到最小接触面积

挑战：装卸顺序

问题：

• 需要按特定顺序卸货
• 有后进先出（LIFO）/先进先出（FIFO）要求
• 多站点配送

解决方案：

• 在模型中纳入卸货顺序
• 按卸货地点分区装载
• 采用后进先出约束
• 为每个配送停靠点预留区域
• 按路线顺序依次装载

挑战：物品尺寸混杂

问题：

• 物品尺寸差异很大
• 难以高效地一起装载
• 小物品会从空隙中掉落

解决方案：

• 将小物品预先聚类成组
• 先装载大件物品，再用小件填充
• 采用分层装载法（不同尺寸分别装载）
• 考虑为小物品单独设置货箱

---

输出格式

3D 装箱报告

执行摘要：

• 已装箱物品：150 箱
• 使用集装箱：3 个（40 英尺集装箱）
• 平均利用率：82.5%
• 总重量：18,500 磅
• 算法：极点 + GA

集装箱利用率：

集装箱	物品数	已用体积	重量	利用率	重心偏移
1	55	1,985 ft³	6,800 磅	87.2%	2.3 英寸
2	52	1,850 ft³	6,200 磅	81.3%	1.8 英寸
3	43	1,750 ft³	5,500 磅	76.9%	3.1 英寸

装载说明（集装箱 1）：

第 1 层（底部）：

• 物品 A001-A015：重型箱子（每箱 50-80 磅）
• 居中摆放，以均衡重量分布
• 高度：0-24 英寸

第 2 层：

• 物品 B001-B025：中型箱子（每箱 30-50 磅）
• 采用交错摆放方式，以确保稳固
• 高度：24-48 英寸

第 3 层（顶部）：

• 物品 C001-C015：轻型／易碎箱子（每箱 <30 磅）
• 避免受到挤压
• 高度：48-72 英寸

集装箱数量与边界：

• 下界：max（体积边界、载荷边界），以及任何无法整组运输的组，并给出可证明该结论的数量
• 本方案使用的集装箱数量，以及与下界的差距
• 如果本方案使用的集装箱数量超过下界，则注明“当前为已找到的最佳方案，尚未证明为最优”，除非装载规划规则适用某项证明

组分配（订单必须保持在一起时）：

集装箱	组（PO）	纸箱数	体积	重量	装载率	剩余 L / W / H
1	PO-A, PO-B, PO-C	812	68.9 m³	7,950 kg	90.3%	9 cm / 2 cm / 24 cm

**容差：**将紧密装载的集装箱按纸箱尺寸增加 1-3 mm 重新检查后的结果，以及检查未通过时的备用方案。

**已运行的检查：**摆放、容纳、重叠、朝向、支撑、载荷。

物品清单：

物品 ID	尺寸（LxWxH）	重量	位置	集装箱	层
A001	48x40x24	75 磅	(0,0,0)	1	1
A002	40x32x20	65 磅	(48,0,0)	1	1

警告／备注：

• 集装箱 3 有 23% 的未用空间——请考虑合并装载
• 物品 Z005（易碎）放在顶层——请小心搬运
• 所有集装箱的重心均在可接受范围内

---

需要询问的问题

如果需要更多背景信息：

1. 集装箱的尺寸是多少？
2. 需要装箱的物品有多少？它们的尺寸和重量是多少？
3. 物品能否自由旋转，还是有相关限制？
4. 是否有重量限制或重量分布要求？
5. 是否有堆叠限制？（易碎物品、最大堆叠高度）
6. 装卸顺序是否重要？
7. 是否需要多站配送并指定特定区域？
8. 是否有不规则形状的物品，还是全部都是矩形箱子？

---

相关技能

• 2d-bin-packing：用于二维装箱问题
• pallet-loading：用于托盘专用装载优化
• container-loading-optimization：用于集装箱物流
• vehicle-loading-optimization：用于卡车／车辆装载
• knapsack-problems：用于基于价值的物品选择
• load-building-optimization：用于多阶段装载规划
• warehouse-slotting-optimization：用于仓库空间优化