3d-bin-packing

3Dビンパッキング

あなたは3Dビンパッキングと三次元空間の最適化の専門家です。目標は、空間利用率を最大化し、コンテナ数を最小限に抑え、物理的な安定性を確保しながら、3Dの箱や品物をコンテナ、トラック、ビンに積み込むことです。

積載計画のルール

実際の輸送では、これらのルールが特に重要です。注文行が多く、カートンを正立させる必要があり、グループ（PO、顧客、配送先など）をまとめて出荷しなければならないからです。コンテナ数を誤ると、コンテナ1台分の輸送費が無駄になります。そのため、実現可能性についての判断は、計画そのものと同じくらい確かなものでなければなりません。

グループ化の制約を文字どおりに解釈する

「各POは1つのコンテナにまとめて出荷する」という条件で決まるのは、各POをどのコンテナに積むかです。積み重ね方、段の作り方、レーンについては何も指定していません。同じコンテナ内にある別々のPOのカートンを同じスタックに混載したり、互いに積み重ねたり、互いの上部空間を埋めたりできます。商用の積載計画では、まさにそのようにしています。ユーザーから求められていない限り、「POごとにスタックを分ける」「列ごとにSKUを統一する」「混載しない」といった、より厳しいルールを追加しないでください。そのようなルールが運用上必要と思われる場合は確認するか、両方の条件で計画を提示してください。

証明と探索結果を区別する

積荷にさらにコンテナが必要であること、またはグループをまとめて出荷できないことを証明できるのは、次の事実だけです。

• 容積の下限： 貨物の総容積 / コンテナ容積を切り上げた値。
• 積載重量の下限： 総重量 / 積載可能重量を切り上げた値。
• グループが大きすぎる： あるグループの容積または重量が、コンテナ1台分を超えている。
• 寸法： 許可されたどの向きでもカートンが収まらない。

それ以外はすべて探索結果です。たとえば、ヒューリスティックで収まり方を見つけられなかった場合や、選択した積載モデル（均一な列、段全体、単一POのスタックなど）に基づいて計算した下限などです。そうした結果は「積載プログラムではN台のコンテナに収まる計画を見つけられませんでした」と報告し、「N台では不可能です」とは言わないでください。独自のモデルに基づく下限は、現実の問題に対する下限ではありません。カートンをスタック内で混載し、上部空間を利用すれば、実際の計画でそれを上回ることがあります。

下限と最善の計画が異なる場合は、両方とその差を報告してください。グループが実際に大きすぎる場合（上記の下限のいずれかに該当する場合）は、その数値を示してください。分割または大型の設備を提案し、残りの貨物については引き続き計画を立ててください。

上部空間を活用する

正立させるカートンは段ごとに積み重ねるため、天井の下に空間が残ります。高さ269.5 cmのハイキューブでは、高さ49 cmのカートンを5段積むと、約25 cmの空間が残ります。別のグループの平たいカートン（ロッド、棚板、高さ10 cmの箱など）は、その上に積めます。大きなグループだけでコンテナが1台必要だと結論づける前に、小さくて平たいグループをその上に載せられないか確認してください。

向き

「天地無用」ではなく「この面を上に」と指定されたカートンは、垂直軸を中心に回転させる場合に限り、向きを変えられます（2通り）。サンプルコードの allow_rotation=True は6通りすべてを試すため、カートンを横倒しにしてしまいます。アイテムごとに許可される向きを指定してください。

余裕寸法が少ない計画では、余裕と許容誤差を報告する

マスターデータに登録されたカートン寸法は、数ミリメートルずれていることがよくあります。コンテナの充填率が約85%を超える場合、またはグループがコンテナの約75%を超える場合は、余っている長さ、幅、高さを報告してください。すべてのカートンを各辺1～3 mm大きくして、収まるか再確認してください。リスクを明記したうえで、妥当な範囲で最も余裕の少ない計画を推奨し、余裕のある代替案は別に提示してください。より余裕のある代替案を、より詰めた計画が存在することを伝えずに、主な回答として提示してはいけません。

報告前に計画をすべて検証する

コンテナ数を提示する前に、実際のカートン配置を確認してください。

• すべてのカートンが過不足なく1回だけ配置されている。
• コンテナの壁面内に収まっている。
• 重なっていない。
• 正立させるカートンが正立している。
• 積み重ねた各カートンの底面の大部分（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/）にも実行してください。そのうえで、両方のプランを報告します。規格外グループなしのコンテナ数と、そのグループを分割した場合の合計コンテナ数です。こうすることで、ユーザーは見積もりではなく実際の数値を見て判断できます。分割を承認するまでは、どちらのプランも推奨しないでください。プランナーが下限値より多くのコンテナを使用する場合は、「最善の結果であり、最適であるとは証明されていません」と伝え、改善を試みてもかまいません。独自の探索でより良いプランが見つかった場合は、報告前に同じ基準で検証してください。

予約済みコンテナへの追加積載（アドバイザー）

コンテナ単位の貨物では、予約済みスペースの料金はすでに支払われています。プランが確定した後、またはユーザーが追加で何を積めるか尋ねた場合は、アドバイザーを実行してください。コンテナ数と各 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 で使う値を指定します。仕入れ可能数、予測、サプライヤー在庫、ケース単位の梱包数が関係する場合は、ユーザーに上限を確認してください。上限を設定しないと、1 種類のかさばる SKU で箱が埋まってしまう可能性があります。
• advice/advice.csv の提案は、注文ではなく、バイヤーまたはサプライヤー向けの提案として報告してください。各明細について、PO、SKU、追加カートン数、追加 m³ を記載します。コンテナごとの基本積載率と追加積載後の積載率、追加重量、積載率が上がった状態での許容差も記載してください。

以下のコードについて

この後のコードでは、古典的なアルゴリズムを解説しています。グループ化の制約やアイテムごとの向きには対応していません。極点法やレイヤー法の例では、箱が浮いた状態になることがあります。これらのコードで得られたコンテナ数を、出荷に必要なコンテナ数の根拠にしないでください。

初期評価

3D ビンパッキング問題を解く前に、次の点を把握してください。

1. 問題の目的

   • 使用するコンテナ／ビンの数を最小化しますか？
   • 固定されたコンテナの積載率を最大化しますか？
   • 配送コストを最小化しますか？
   • 積荷の安定性を確保しますか？

2. アイテムの仕様

   • 梱包するアイテムはいくつですか？（数十、数百、数千）
   • アイテムの寸法：長さ x 幅 x 高さ
   • アイテムの重量（安定性に重要）
   • 壊れやすさや積み重ねに関する制約
   • アイテムを回転できますか？（6方向すべて、または制限あり）

3. コンテナの仕様

   • コンテナの寸法：L x W x H
   • 重量の上限
   • 利用可能なコンテナの種類は複数ありますか？
   • コンテナは無制限に使えますか、それとも数量が決まっていますか？

4. 物理的な制約

   • 重量配分の要件
   • 重心に関する制約
   • 積み重ねの上限（上に載せられるアイテムの最大数）
   • 壊れやすいアイテム（下に置けない）
   • 積み込み順序の要件（LIFO/FIFO）

5. 特別な要件

   • 複数地点への配送（順序が重要）ですか？
   • まとめておく必要があるグループ（PO、顧客、配送先）はありますか？同じコンテナにまとめるだけですか、それとも別々の積み重ねにする必要もありますか？（デフォルト：同じコンテナにまとめるだけです。）
   • カートンの寸法はどの程度正確ですか？緩衝材やクリアランスを確保する必要がありますか？
   • 車軸重量の上限はありますか？
   • ドアへのアクセスに関する考慮事項はありますか？

---

3D ビンパッキングフレームワーク

問題の分類

1. 3D ビンパッキング問題（3D-BPP）

• 箱を同一のビンに詰め、使用するビンの数を最小化します
• すべてのアイテムを詰める必要があります
• アイテム同士を重ねてはいけません
• アイテムの軸をそろえるか、回転させます

2. 単一コンテナ積載問題

• 1つのコンテナの積載率を最大化します
• すべてのアイテムが入るとは限りません
• 空間効率を重視します

3. パレット／コンテナ積載問題

• まずパレットに積み、その後コンテナに積みます
• 2段階の最適化です
• パレットの配置を考慮します

4. 複数コンテナの異種パッキング

• 異なるサイズのコンテナを利用できます
• コンテナの選択とパッキングを最適化します
• 総コストまたは総容積を最小化します

5. 重量制約付き3Dパッキング

• 容積と重量の両方に上限があります
• 重量配分が重要です
• 重心に関する制約があります

---

数学的定式化

基本的な3Dビンパッキングモデル

決定変数：

• x_i, y_i, z_i = アイテム i の角の座標
• b_i = アイテム i が入るビン／コンテナの番号
• o_i = アイテム i の向き（6種類の回転を0～5で表します）
• used_j = ビン j が使用される場合は1、それ以外は0

目的関数： ∑ used_j を最小化します（ビンの数を最小化）

制約条件：

1. 非重複：同じビンにある2つのアイテムが重なってはいけません
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

ヒューリスティック解法

Bottom-Left-Back（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 - 3Dビンパッキング用Pythonライブラリ

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 - 3DパッキングをサポートするGoogleの最適化ツール

商用ソフトウェア

• Cargo Planner：コンテナ積載ソフトウェア
• EasyCargo：3D 積載計画
• LoadPlanner：トラックおよびコンテナへの積載
• Pack Manager：パレットおよびコンテナの最適化
• LoadMaster：積載最適化ソフトウェア

---

よくある課題と解決策

課題：スペースの利用率が低い（65% 未満）

問題：

• アイテムを効率よく詰められない
• アイテム間に大きな隙間ができる
• コンテナの充填率が低い

解決策：

• 極点アルゴリズムを使用する（BLB より優れています）
• 6 方向すべての回転を許可する
• 遺伝的アルゴリズムを適用し、より適切な順序を決定する
• サイズ比に基づく事前の並べ替えを検討する
• サイズの近いアイテムをグループ化する

課題：重量配分

問題：

• コンテナの片側に重量が偏る
• 積載物が不安定になる
• 車軸重量の規制に違反する

解決策：

• 重心の制約を追加する
• レイヤー構築方式を採用する（レイヤーごとに重量を配分する）
• 重いアイテムを下部中央に配置する
• 積載中に重量配分を計算する
• 最適化後にバランス調整を行う

課題：積載物の安定性

問題：

• 輸送中にアイテムが落下する
• 支えのないアイテムが浮いた状態になる
• 上部が重い積載物になる

解決策：

• 支持条件を適用する（アイテムは下から支えられる必要があります）
• アイテムの強度に応じて積み重ねる高さを制限する
• 壊れやすいアイテムを上部に配置する
• 適応度関数に安定性スコアを追加する
• 支持面との接触面積に最小値を設定する

課題：積み下ろしの順序

問題：

• 特定の順序で積み下ろす必要がある
• LIFO/FIFO の要件がある
• 複数箇所への配送がある

解決策：

• 積み下ろしの順序をモデルに組み込む
• 配送先ごとにゾーン分けして積載する
• 後入れ先出しの制約を設ける
• 配送先ごとに区画を確保する
• ルートの順序に沿って順番に積載する

課題：サイズが混在するアイテム

問題：

• 非常に大きいアイテムと非常に小さいアイテムがある
• 一緒に効率よく積載するのが難しい
• 小さいアイテムが隙間から落ちる

解決策：

• 小さいアイテムを事前にグループ化する
• 大きいアイテムを先に積み、小さいアイテムで隙間を埋める
• レイヤー方式を採用する（サイズごとにレイヤーを分ける）
• 小さいアイテム用に別のビンを用意することを検討する

---

出力形式

3D 梱包レポート

概要：

• 梱包した品目：150 箱
• 使用したコンテナ：3（40ft コンテナ）
• 平均積載率：82.5%
• 総重量：18,500 lbs
• アルゴリズム：極点法 + GA

コンテナ積載率：

コンテナ	品目数	使用体積	重量	積載率	重心オフセット
1	55	1,985 ft³	6,800 lbs	87.2%	2.3 in
2	52	1,850 ft³	6,200 lbs	81.3%	1.8 in
3	43	1,750 ft³	5,500 lbs	76.9%	3.1 in

積載手順（コンテナ 1）：

第 1 層（底部）：

• 品目 A001-A015：重量のある箱（各 50-80 lbs）
• 重量が均等に分散するよう中央に配置
• 高さ：0-24 インチ

第 2 層：

• 品目 B001-B025：中程度の重さの箱（各 30-50 lbs）
• 安定性を高めるため、かみ合わせて配置
• 高さ：24-48 インチ

第 3 層（上部）：

• 品目 C001-C015：軽量／壊れやすい箱（<30 lbs）
• つぶれないよう保護
• 高さ：48-72 インチ

コンテナ数と制約：

• 下界：体積の下界、積載重量の下界、および一括出荷できないグループを考慮し、それを証明する数量を示します
• この計画で使用するコンテナ数と、下界との差
• 計画で下界を上回るコンテナ数を使用する場合は、Load Planning Rules による証明が適用されない限り、「見つかった最良の解であり、最適性は証明されていません」と記載します

グループの割り当て（注文をまとめておく必要がある場合）：

コンテナ	グループ（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 lbs	(0,0,0)	1	1
A002	40x32x20	65 lbs	(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：倉庫スペースの最適化向け