2D切断と包装

🔥 Vibe プロンプト

「8つの矩形[3x2,4x3,2x2,5x2,3x3,2x4,4x2,3x4]を10x10の箱に配置。回転可。配置を最適化。」

2Dカッティング＆パッキングとは？

2Dカッティングは、矩形部品をシート上に配置して廃棄物を最小化する問題です。製造業における基本的な最適化問題：

| 産業 | 応用 | |------|------| | 🪵 木工 | 家具部品用の板材カット | | 👕 繊維 | 布地へのパターン配置 | | 🥫 包装 | 配送用箱のレイアウト設計 | | 🪟 ガラス | 在庫シートからの窓ガラス切断 | | 🛠️ 金属加工 | 鋼板からのレーザー切断部品 |

CP-SATによる実装

from ortools.sat.python import cp_model

# 矩形: (幅, 高さ)
rectangles = [(3,2),(4,3),(2,2),(5,2),(3,3),(2,4),(4,2),(3,4)]
bin_w, bin_h = 10, 10
n = len(rectangles)

model = cp_model.CpModel()

# 変数: 位置(x,y) と 回転フラグ
x = [model.NewIntVar(0, bin_w, f'x_{i}') for i in range(n)]
y = [model.NewIntVar(0, bin_h, f'y_{i}') for i in range(n)]
rotated = [model.NewBoolVar(f'rot_{i}') for i in range(n)]

# 幅と高さ（回転を考慮）
w = [model.NewIntVar(0, bin_w, f'w_{i}') for i in range(n)]
h = [model.NewIntVar(0, bin_h, f'h_{i}') for i in range(n)]

for i in range(n):
    model.Add(w[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i].Not())
    model.Add(w[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i])
    model.Add(h[i] == rectangles[i][1]).OnlyEnforceIf(rotated[i].Not())
    model.Add(h[i] == rectangles[i][0]).OnlyEnforceIf(rotated[i])
    model.Add(x[i] + w[i] <= bin_w)
    model.Add(y[i] + h[i] <= bin_h)

# 非重複制約（2D NoOverlap）
intervals_x = [model.NewIntervalVar(x[i], w[i], x[i]+w[i], f'ix_{i}') for i in range(n)]
intervals_y = [model.NewIntervalVar(y[i], h[i], y[i]+h[i], f'iy_{i}') for i in range(n)]
model.AddNoOverlap2D(intervals_x, intervals_y)

# 求解
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 30
status = solver.Solve(model)

# 結果
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 2D配置結果 ===")
    used_area = 0
    for i in range(n):
        rx = solver.Value(x[i])
        ry = solver.Value(y[i])
        rw = solver.Value(w[i])
        rh = solver.Value(h[i])
        rot = " (回転)" if solver.Value(rotated[i]) else ""
        used_area += rw * rh
        print(f"矩形{i} ({rectangles[i][0]}x{rectangles[i][1]}): pos=({rx},{ry}) size=({rw}x{rh}){rot}")
    
    total_area = bin_w * bin_h
    print(f"\n総面積: {total_area}")
    print(f"使用面積: {used_area}")
    print(f"使用率: {used_area/total_area*100:.1f}%")
    print(f"廃棄率: {(total_area-used_area)/total_area*100:.1f}%")

Matplotlibによる可視化

import matplotlib.pyplot as plt
import matplotlib.patches as patches

fig, ax = plt.subplots(figsize=(8,8))
ax.set_xlim(0, bin_w); ax.set_ylim(0, bin_h)
ax.set_aspect('equal')
ax.set_title('2D 配置結果')

colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#96CEB4', '#FFEAA7', '#DDA0DD', '#98D8C8', '#F7DC6F']

for i in range(n):
    rx, ry = solver.Value(x[i]), solver.Value(y[i])
    rw, rh = solver.Value(w[i]), solver.Value(h[i])
    rect = patches.Rectangle((rx,ry), rw, rh, linewidth=2, edgecolor='black', facecolor=colors[i], alpha=0.7)
    ax.add_patch(rect)
    ax.text(rx+rw/2, ry+rh/2, str(i), ha='center', va='center', fontsize=12, fontweight='bold')

plt.grid(True, alpha=0.3)
plt.show()

現実の応用

1. ネスティング最適化

造船・航空宇宙企業は、金属シートからの不規則形状切断にこれを使用。使用率1%の改善で年間数百万ドルの節約になります。

2. パレット積載

各パレット上の箱数を最大化。直接的な配送コストと燃料消費の削減につながります。

3. VLSIチップ設計

シリコンウェハー上に数百万のトランジスタを配置。これは極めて大規模な2Dパッキング問題です。

4. 家具製造

標準サイズの木材パネルから家具部品を切断する最適化。一般的な工場では5-15%の材料節約が可能です。

まとめ

| 項目 | 詳細 | |------|------| | 問題 | シート上に矩形を配置して廃棄物最小化 | | 手法 | 2D NoOverlap制約 + 回転対応 | | CP-SAT | 10-50個の矩形に最適 | | 使用率 | 通常75-90%（形状により変動） | | 回転 | 使用率を5-15%改善可能 | | 応用 | 木工、繊維、ガラス、金属、包装、VLSI |