切割與包裝問題

工業切割問題是排箱問題的變體：

鋼鐵廠：如何切割鋼板才能讓廢料最少？
服裝廠：如何在布料上排列版型才能最省布？
木工廠：如何切割木板才能得到最多的成品？

2D 排箱 (2D Bin Packing)

from ortools.sat.python import cp_model

# === 矩形物品 ===
rectangles = [
    (3, 2),   # 物品 0
    (4, 3),   # 物品 1
    (2, 2),   # 物品 2
    (5, 2),   # 物品 3
    (3, 3),   # 物品 4
    (2, 4),   # 物品 5
    (4, 2),   # 物品 6
    (3, 4),   # 物品 7
]

bin_width = 10
bin_height = 10

num_items = len(rectangles)

model = cp_model.CpModel()

# 每個物品的位置與旋轉
x = [model.NewIntVar(0, bin_width, f"x_{i}") for i in range(num_items)]
y = [model.NewIntVar(0, bin_height, f"y_{i}") for i in range(num_items)]

# 是否旋轉
rotated = [model.NewBoolVar(f"rot_{i}") for i in range(num_items)]

# 寬與高（考慮旋轉）
w = [model.NewIntVar(0, bin_width, f"w_{i}") for i in range(num_items)]
h = [model.NewIntVar(0, bin_height, f"h_{i}") for i in range(num_items)]

for i in range(num_items):
    # 如果旋轉則寬高交換
    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_width)
    model.Add(y[i] + h[i] <= bin_height)

# 物品不重疊（使用 NoOverlap2D）
intervals_x = [model.NewIntervalVar(x[i], w[i], x[i] + w[i], f"ix_{i}") 
               for i in range(num_items)]
intervals_y = [model.NewIntervalVar(y[i], h[i], y[i] + h[i], f"iy_{i}")
               for i in range(num_items)]
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 排箱結果 ===")
    for i in range(num_items):
        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 ""
        print(f"物品 {i} ({rectangles[i]}): ({rx},{ry}) → ({rx+rw},{ry+rh}) {rot}")
    
    # 計算使用率
    total_area = bin_width * bin_height
    used_area = sum(rw * rh for i in range(num_items)
                    for rw, rh in [(solver.Value(w[i]), solver.Value(h[i]))])
    print(f"\n板材面積: {total_area}")
    print(f"使用面積: {used_area}")
    print(f"使用率: {used_area/total_area:.1%}")
else:
    print("找不到可行排法")

視覺化（Matplotlib）

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

fig, ax = plt.subplots(figsize=(8, 8))
ax.set_xlim(0, bin_width)
ax.set_ylim(0, bin_height)
ax.set_aspect('equal')
ax.set_title('2D 排箱結果')

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

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

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

應用場景

1. 鋼板切割（Nesting）

造船廠和航太公司使用 2D 排箱來優化金屬板切割。使用率提升 1% 每年就能節省數百萬美元。

2. 倉儲棧板裝載

最大化每個棧板上的紙箱數量，直接降低運輸成本和燃料消耗。

3. 晶片設計（VLSI）

在矽晶圓上放置數百萬個晶體管。這是極大規模的 2D 排箱問題，還附加了電子特性限制。

4. 家具製造

優化從標準尺寸木板切割家具零件的方式。典型工廠可節省 5-15% 的材料。

總結

| 面向 | 詳情 | |------|------| | 問題 | 在板材上放置矩形以最小化廢料 | | 方法 | 2D NoOverlap 限制 + 旋轉支援 | | CP-SAT | 適合 10-50 個矩形 | | 使用率 | 通常 75-90%（取決於組合） | | 旋轉 | 可提升 5-15% 使用率 | | 應用 | 木工、紡織、玻璃、金屬、包裝、晶片設計 |

Cutting & Packing：排箱問題的變體

切割與包裝問題是排箱問題（Bin Packing）的延伸。在排箱問題中，目標是「用最少箱子裝完所有物品」；在 Cutting & Packing 中，你要考慮更多實際限制。

三種常見的問題變體

| 問題 | 描述 | 應用場景 | |:----|:----|:--------| | 2D Packing | 將矩形物品放入矩形容器 | 貨櫃裝載、倉庫儲位分配 | | Cutting Stock | 從大板材切割出小矩形 | 木板裁切、金屬板切割、布料裁剪 | | Strip Packing | 在固定寬度無限長度的帶狀容器中排列 | 電路板佈局、排程問題 |

啟發式演算法

這些問題都是 NP-hard，大規模時無法求最佳解。常用的啟發式：

| 演算法 | 策略 | 速度 | 品質 | |:----|:----|:----|:----| | First Fit Decreasing | 物品由大到小，放進第一個能裝的容器 | 快 | 中 | | Bottom-Left | 每次放在最左下角空位 | 快 | 中 | | Guillotine Cut | 每次切一刀到底 | 中 | 中高 | | Maximal Rectangles | 維護最大空矩形列表 | 慢 | 高 |

課程總結

這堂組合最佳化課程你學到了排箱問題、工作排程、旅行推銷員問題（TSP）和 Cutting & Packing。這些 NP-hard 問題在物流、製造業、雲端資源分配中有廣泛的應用。