guillotine-cutting

ギロチンカット

ギロチンカット最適化と制約付き切断パターンの専門家として、製造現場でよく使われるシャー、ギロチンカッター、のこぎり、パネルソーによる切断など、すべてのカットをギロチンカット（端から反対側の端までまっすぐに切る方法）で行う必要がある切断問題の解決を支援します。

初期評価

ギロチンカットの問題を解く前に、次の点を確認します。

1. 切断制約

   • すべてのカットをギロチンカット（端から端まで）にする必要がありますか？
   • どのような段階構成ですか？（2段階、3段階、無制限）
   • 水平カットと垂直カットを組み合わせられますか？
   • 希望する切断順序はありますか？
   • 許可される段階数の上限はありますか？

2. 設備の特性

   • どのような切断設備を使いますか？（ギロチンシャー、パネルソー、CNCルーター）
   • 設備のベッドサイズ／容量はどれくらいですか？
   • 設備で材料を回転できますか？
   • 切断精度／公差はどれくらいですか？
   • 1カットあたりの段取り時間はどれくらいですか？

3. 材料とアイテム

   • 板材／素材の寸法はどれくらいですか？
   • アイテムの寸法はどれくらいですか？（ギロチンカットではすべて長方形です）
   • 必要なアイテムの数量はいくつですか？
   • アイテムを90度回転できますか？
   • 材料の木目方向に関する制約はありますか？

4. 最適化の目標

   • 使用する板材の枚数を最小化しますか？
   • カット数を最小化しますか？
   • 切断時間を最小化しますか？
   • 材料の利用率を最大化しますか？
   • 複数の目標のバランスを取りますか？

5. 実務上の考慮事項

   • カットの最小長さはありますか？
   • ピースの最小サイズはありますか？
   • カーフ（のこ刃の幅）はどれくらいですか？
   • 切断順序を記録する必要がありますか？
   • リアルタイム最適化とバッチ最適化のどちらですか？

---

ギロチンカットのフレームワーク

ギロチンカットについて

定義： ギロチンカットとは、長方形の一方の端から反対側の端まで完全にまっすぐ切り、長方形を2つの小さな長方形に分割するカットです。

特性：

• カットは辺のいずれかと平行である必要があります
• カットは材料を完全に横断します
• 2つの長方形の小片ができます
• 部分的なカットやL字型のカットはできません

ギロチンカットと非ギロチンカットの比較：

Guillotine Cut:                 Non-Guillotine:
┌────────────┐                 ┌────────────┐
│            │                 │ ┌──┐       │
│            │                 │ │  │       │
├────────────┤ ✓               │ └──┘   ┌──┤ ✗
│            │                 │        │  │
│            │                 │        └──┘
└────────────┘                 └────────────┘

問題の分類

1. 2段階ギロチンカット

• 第1段階： 板材をストリップ状に切断します（水平または垂直）
• 第2段階： ストリップをアイテムに切断します（第1段階に対して垂直）
• 最も制約が厳しい一方で、最も簡単です
• 産業用パネルソーでよく使われます

2. 3段階ギロチンカット

• 第1段階： 板材を区画に切断します
• 第2段階： 区画をストリップ状に切断します
• 第3段階： ストリップをアイテムに切断します
• 2段階より柔軟です
• より高い利用率を実現できます

3. N段階ギロチンカット

• 任意の段階数に対応します
• 各カットで長方形を分割します
• 再帰的な構造です
• カットをツリーで表現します

4. 無制限ギロチンカット

• 段階数に制限はありません
• すべてのカットをギロチンカットにする必要があります
• ギロチンカットの方式の中で最も柔軟です
• 最適化はより困難です

5. 厳密ギロチンカット

• トリムによる廃材は許可されません
• アイテムで長方形を隙間なく満たす必要があります
• 非常に制約が厳しい方式です
• 実務ではまれです

---

数学的定式化

2段階ギロチンカット問題

与えられるもの：

• W × H = 板材の寸法
• アイテム：{(w₁, h₁, d₁), (w₂, h₂, d₂), ..., (wₙ, hₙ, dₙ)}
  • wᵢ、hᵢ = アイテムの寸法
  • dᵢ = 必要数量

決定変数：

• 第1段階のストリップパターン
• 第2段階でストリップ内に配置するアイテムパターン
• 各パターンの使用回数

第1段階（ストリップ）： 水平ストリップの場合：

• ストリップの高さ h
• この高さのストリップの本数
• 制約：Σ(高さ) ≤ H

第2段階（ストリップ内のアイテム）： 各ストリップについて：

• ストリップの高さに収まるアイテム
• ストリップ幅に対する1次元の切断ストック問題
• 制約：Σ(幅) ≤ W

目的： 使用する板材の枚数を最小化します

計算量：

• 一般的な2次元切断より扱いやすいものの、依然としてNP困難です
• 段階の制約により解空間が小さくなります
• ストリップ詰めには1次元アルゴリズムを使用できます

---

アルゴリズムと解法

方法1：動的計画法による2段階ギロチンカット

import numpy as np
from typing import List, Tuple, Dict

class TwoStageGuillotine:
    """
    Two-Stage Guillotine Cutting Solver

    Stage 1: Cut sheet into horizontal strips
    Stage 2: Cut strips into items using 1D algorithm

    This is practical and widely used in industry
    """

    def __init__(self, sheet_width, sheet_height, kerf=0):
        """
        Initialize solver

        Parameters:
        - sheet_width: sheet width
        - sheet_height: sheet height
        - kerf: saw kerf (material lost per cut)
        """
        self.sheet_width = sheet_width
        self.sheet_height = sheet_height
        self.kerf = kerf
        self.items = []

    def add_item(self, width, height, quantity, item_id=None):
        """Add rectangular item"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'width': width,
            'height': height,
            'quantity': quantity,
            'area': width * height
        })

    def generate_strip_types(self):
        """
        Generate all feasible strip types

        A strip type is defined by its height
        """

        # Get unique heights from items
        unique_heights = set()

        for item in self.items:
            # Can use item in normal or rotated orientation
            unique_heights.add(item['height'])
            unique_heights.add(item['width'])

        # Filter heights that fit in sheet
        strip_types = [h for h in unique_heights if h <= self.sheet_height]

        return sorted(strip_types)

    def solve_1d_cutting_for_strip(self, strip_height, strip_width):
        """
        Solve 1D cutting stock for items that fit in a strip

        Returns best patterns for this strip type
        """

        # Get items that can fit in this strip height
        eligible_items = []

        for item in self.items:
            # Try both orientations
            if item['height'] <= strip_height:
                eligible_items.append({
                    'id': item['id'],
                    'length': item['width'],
                    'height': item['height'],
                    'quantity': item['quantity'],
                    'rotated': False
                })

            if item['width'] <= strip_height and item['width'] != item['height']:
                eligible_items.append({
                    'id': item['id'] + '_rot',
                    'length': item['height'],
                    'height': item['width'],
                    'quantity': item['quantity'],
                    'rotated': True
                })

        if not eligible_items:
            return []

        # Generate 1D patterns using dynamic programming
        patterns = self._generate_1d_patterns_dp(eligible_items, strip_width)

        return patterns

    def _generate_1d_patterns_dp(self, items, width):
        """
        Generate 1D cutting patterns using dynamic programming

        For each item type, find maximum number that fits
        """

        patterns = []

        # Simple patterns: one item type per pattern
        for item in items:
            max_fit = int(width / (item['length'] + self.kerf))
            if max_fit > 0:
                pattern = {
                    'items': {item['id']: max_fit},
                    'waste': width - (max_fit * item['length'] + (max_fit - 1) * self.kerf)
                }
                patterns.append(pattern)

        # Combined patterns: two item types
        for i, item1 in enumerate(items):
            for item2 in items[i:]:
                # Try different combinations
                for n1 in range(int(width / (item1['length'] + self.kerf)) + 1):
                    remaining = width - (n1 * item1['length'] + max(0, n1-1) * self.kerf)
                    n2 = int(remaining / (item2['length'] + self.kerf))

                    if n1 + n2 > 0:
                        pattern = {
                            'items': {},
                            'waste': 0
                        }

                        if n1 > 0:
                            pattern['items'][item1['id']] = n1

                        if n2 > 0:
                            pattern['items'][item2['id']] = n2

                        used = (n1 * item1['length'] + n2 * item2['length'] +
                               (n1 + n2 - 1) * self.kerf)
                        pattern['waste'] = width - used

                        if pattern not in patterns:
                            patterns.append(pattern)

        return patterns

    def solve_master_problem(self, strip_types, strip_patterns):
        """
        Solve master problem: select strips to pack into sheets

        This is simplified - full implementation uses integer programming
        """

        from pulp import *

        # Create problem
        prob = LpProblem("Two_Stage_Guillotine", LpMinimize)

        # Variables: number of each strip type pattern to use
        strip_vars = {}
        for strip_height in strip_types:
            for pattern_idx, pattern in enumerate(strip_patterns[strip_height]):
                var_name = f"strip_h{strip_height}_p{pattern_idx}"
                strip_vars[(strip_height, pattern_idx)] = LpVariable(
                    var_name, lowBound=0, cat='Integer'
                )

        # Objective: minimize number of sheets
        # Approximate: sum of strip heights / sheet height
        prob += lpSum(
            strip_vars[(h, p)] * h / self.sheet_height
            for h in strip_types
            for p in range(len(strip_patterns[h]))
        )

        # Demand constraints
        for item in self.items:
            item_id = item['id']

            # Sum across all strips and patterns
            prob += lpSum(
                strip_vars[(h, p)] * pattern['items'].get(item_id, 0) +
                strip_vars[(h, p)] * pattern['items'].get(item_id + '_rot', 0)
                for h in strip_types
                for p, pattern in enumerate(strip_patterns[h])
            ) >= item['quantity'], f"Demand_{item_id}"

        # Solve
        prob.solve(PULP_CBC_CMD(msg=0))

        # Extract solution
        solution = {
            'status': LpStatus[prob.status],
            'strip_usage': {}
        }

        for (h, p), var in strip_vars.items():
            if var.varValue and var.varValue > 0.5:
                if h not in solution['strip_usage']:
                    solution['strip_usage'][h] = []

                solution['strip_usage'][h].append({
                    'pattern_index': p,
                    'pattern': strip_patterns[h][p],
                    'quantity': int(var.varValue)
                })

        return solution

    def pack_strips_into_sheets(self, strip_usage):
        """
        Pack strips into sheets using FFD height

        Returns list of sheets with their strips
        """

        # Expand strips
        strips_to_pack = []

        for strip_height, patterns in strip_usage.items():
            for pattern_info in patterns:
                for _ in range(pattern_info['quantity']):
                    strips_to_pack.append({
                        'height': strip_height,
                        'pattern': pattern_info['pattern']
                    })

        # Sort by decreasing height
        strips_to_pack.sort(key=lambda s: s['height'], reverse=True)

        # Pack into sheets (FFD)
        sheets = []

        for strip in strips_to_pack:
            placed = False

            # Try existing sheets
            for sheet in sheets:
                if sheet['remaining_height'] >= strip['height']:
                    sheet['strips'].append(strip)
                    sheet['remaining_height'] -= strip['height']
                    placed = True
                    break

            # Need new sheet
            if not placed:
                sheets.append({
                    'strips': [strip],
                    'remaining_height': self.sheet_height - strip['height']
                })

        # Calculate utilization
        for sheet in sheets:
            used_area = 0
            for strip in sheet['strips']:
                # Calculate items in strip
                strip_used = 0
                for item_id, count in strip['pattern']['items'].items():
                    # Get item dimensions (need to look up)
                    # Simplified here
                    strip_used += count * 100  # Placeholder

                used_area += strip_used * strip['height']

            sheet['utilization'] = (used_area / (self.sheet_width * self.sheet_height) * 100)

        return sheets

    def solve(self):
        """
        Solve two-stage guillotine cutting problem

        Returns: cutting plan with sheets and patterns
        """

        print("Solving Two-Stage Guillotine Cutting...")

        # Step 1: Generate strip types
        strip_types = self.generate_strip_types()
        print(f"Strip types: {len(strip_types)}")

        # Step 2: For each strip type, generate 1D patterns
        strip_patterns = {}

        for strip_height in strip_types:
            patterns = self.solve_1d_cutting_for_strip(strip_height, self.sheet_width)
            strip_patterns[strip_height] = patterns
            print(f"Strip height {strip_height}: {len(patterns)} patterns")

        # Step 3: Solve master problem
        master_solution = self.solve_master_problem(strip_types, strip_patterns)

        if master_solution['status'] != 'Optimal':
            print(f"Warning: Status = {master_solution['status']}")

        # Step 4: Pack strips into sheets
        sheets = self.pack_strips_into_sheets(master_solution['strip_usage'])

        print(f"\nSolution: {len(sheets)} sheets needed")

        return {
            'num_sheets': len(sheets),
            'sheets': sheets,
            'strip_patterns': strip_patterns,
            'status': master_solution['status']
        }


# Example usage
def example_two_stage_guillotine():
    """Example: Two-stage guillotine cutting"""

    solver = TwoStageGuillotine(
        sheet_width=2440,
        sheet_height=1220,
        kerf=3
    )

    # Add items
    solver.add_item(800, 600, 12, 'A')
    solver.add_item(1000, 500, 10, 'B')
    solver.add_item(600, 400, 15, 'C')
    solver.add_item(1200, 300, 8, 'D')

    # Solve
    solution = solver.solve()

    print(f"\nSheets: {solution['num_sheets']}")

    return solution

方法2：再帰的なギロチン分割

class RecursiveGuillotinePartitioning:
    """
    Recursive Guillotine Partitioning

    Recursively subdivides rectangle with guillotine cuts
    Can represent any guillotine cutting pattern

    Uses tree structure to represent cutting plan
    """

    def __init__(self, width, height):
        """
        Initialize with rectangle dimensions

        Parameters:
        - width: rectangle width
        - height: rectangle height
        """
        self.width = width
        self.height = height
        self.root = None

    class CutNode:
        """Node in guillotine cut tree"""

        def __init__(self, x, y, width, height):
            self.x = x
            self.y = y
            self.width = width
            self.height = height

            # Cut information
            self.is_cut = False
            self.cut_position = None
            self.cut_horizontal = None  # True=horizontal, False=vertical

            # Children (if cut)
            self.left_child = None   # or bottom child
            self.right_child = None  # or top child

            # Item assignment (if leaf)
            self.item = None

    def make_cut(self, node, position, horizontal=True):
        """
        Make guillotine cut at node

        Parameters:
        - node: CutNode to cut
        - position: cut position (relative to node origin)
        - horizontal: True for horizontal cut, False for vertical

        Returns: (left/bottom child, right/top child)
        """

        if node.is_cut:
            raise ValueError("Node already cut")

        node.is_cut = True
        node.cut_position = position
        node.cut_horizontal = horizontal

        if horizontal:
            # Horizontal cut: divide into bottom and top
            node.left_child = self.CutNode(
                node.x, node.y,
                node.width, position
            )

            node.right_child = self.CutNode(
                node.x, node.y + position,
                node.width, node.height - position
            )

        else:
            # Vertical cut: divide into left and right
            node.left_child = self.CutNode(
                node.x, node.y,
                position, node.height
            )

            node.right_child = self.CutNode(
                node.x + position, node.y,
                node.width - position, node.height
            )

        return node.left_child, node.right_child

    def assign_item(self, node, item_id, item_width, item_height):
        """
        Assign item to a leaf node

        Parameters:
        - node: leaf node
        - item_id: item identifier
        - item_width, item_height: item dimensions
        """

        if node.is_cut:
            raise ValueError("Cannot assign item to cut node")

        if item_width > node.width or item_height > node.height:
            raise ValueError("Item doesn't fit in node")

        node.item = {
            'id': item_id,
            'width': item_width,
            'height': item_height,
            'waste_width': node.width - item_width,
            'waste_height': node.height - item_height
        }

    def generate_cutting_sequence(self, node=None):
        """
        Generate cutting sequence from tree

        Returns list of cuts in execution order (depth-first)
        """

        if node is None:
            node = self.root

        if not node.is_cut:
            return []

        cuts = []

        # Add this cut
        cuts.append({
            'position': (node.x, node.y),
            'size': (node.width, node.height),
            'cut_position': node.cut_position,
            'horizontal': node.cut_horizontal,
            'cut_line': (
                (node.x, node.y + node.cut_position,
                 node.x + node.width, node.y + node.cut_position)
                if node.cut_horizontal else
                (node.x + node.cut_position, node.y,
                 node.x + node.cut_position, node.y + node.height)
            )
        })

        # Recursively add children cuts
        if node.left_child:
            cuts.extend(self.generate_cutting_sequence(node.left_child))

        if node.right_child:
            cuts.extend(self.generate_cutting_sequence(node.right_child))

        return cuts

    def visualize_cut_tree(self, save_path=None):
        """
        Visualize guillotine cut pattern

        Shows all cuts and items
        """

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

        fig, ax = plt.subplots(figsize=(12, 10))

        # Draw sheet boundary
        ax.add_patch(patches.Rectangle(
            (0, 0), self.width, self.height,
            fill=False, edgecolor='black', linewidth=3
        ))

        # Draw all cuts
        cuts = self.generate_cutting_sequence()

        for idx, cut in enumerate(cuts):
            x1, y1, x2, y2 = cut['cut_line']
            color = 'red' if cut['horizontal'] else 'blue'
            ax.plot([x1, x2], [y1, y2],
                   color=color, linewidth=2, alpha=0.7)

            # Label cut
            mid_x = (x1 + x2) / 2
            mid_y = (y1 + y2) / 2
            ax.text(mid_x, mid_y, f"{idx+1}",
                   fontsize=10, fontweight='bold',
                   bbox=dict(boxstyle='circle', facecolor='white'))

        # Draw items
        items = self._collect_items(self.root)

        colors = plt.cm.tab10(np.linspace(0, 1, 10))

        for idx, item_info in enumerate(items):
            node = item_info['node']
            item = item_info['item']

            color = colors[idx % 10]

            ax.add_patch(patches.Rectangle(
                (node.x, node.y),
                item['width'], item['height'],
                facecolor=color, edgecolor='black',
                linewidth=1.5, alpha=0.5
            ))

            # Label item
            cx = node.x + item['width'] / 2
            cy = node.y + item['height'] / 2
            ax.text(cx, cy, item['id'],
                   ha='center', va='center',
                   fontsize=11, fontweight='bold')

        ax.set_xlim(-50, self.width + 50)
        ax.set_ylim(-50, self.height + 50)
        ax.set_aspect('equal')
        ax.set_xlabel('Width', fontsize=12)
        ax.set_ylabel('Height', fontsize=12)
        ax.set_title('Guillotine Cutting Pattern\n'
                    'Red=Horizontal cuts, Blue=Vertical cuts',
                    fontsize=14, fontweight='bold')
        ax.grid(True, alpha=0.3)

        # Legend
        ax.text(0.02, 0.98, f"Total cuts: {len(cuts)}",
               transform=ax.transAxes,
               verticalalignment='top',
               bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))

        plt.tight_layout()

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

        plt.show()

    def _collect_items(self, node):
        """Collect all items from tree"""

        if node is None:
            return []

        if node.item:
            return [{'node': node, 'item': node.item}]

        items = []

        if node.left_child:
            items.extend(self._collect_items(node.left_child))

        if node.right_child:
            items.extend(self._collect_items(node.right_child))

        return items


# Example usage
def example_recursive_guillotine():
    """Example: Build guillotine cut tree"""

    # Create partitioner for 2400x1200 sheet
    gp = RecursiveGuillotinePartitioning(2400, 1200)

    # Create root node
    gp.root = gp.CutNode(0, 0, 2400, 1200)

    # Make first horizontal cut at 600
    bottom, top = gp.make_cut(gp.root, 600, horizontal=True)

    # Cut bottom into two vertical sections
    left1, right1 = gp.make_cut(bottom, 1200, horizontal=False)

    # Cut top into two vertical sections
    left2, right2 = gp.make_cut(top, 800, horizontal=False)

    # Assign items to leaves
    gp.assign_item(left1, 'A', 1200, 600)
    gp.assign_item(right1, 'B', 1200, 600)
    gp.assign_item(left2, 'C', 800, 600)
    gp.assign_item(right2, 'D', 1600, 600)

    # Get cutting sequence
    cuts = gp.generate_cutting_sequence()

    print("Cutting Sequence:")
    for idx, cut in enumerate(cuts):
        direction = "Horizontal" if cut['horizontal'] else "Vertical"
        print(f"Cut {idx+1}: {direction} at position {cut['cut_position']}")

    # Visualize
    gp.visualize_cut_tree()

    return gp

方法3：3段階ギロチンカットアルゴリズム

class ThreeStageGuillotine:
    """
    Three-Stage Guillotine Cutting

    More flexible than two-stage

    Stage 1: Cut sheet into large sections
    Stage 2: Cut sections into strips
    Stage 3: Cut strips into items
    """

    def __init__(self, sheet_width, sheet_height):
        self.sheet_width = sheet_width
        self.sheet_height = sheet_height
        self.items = []

    def add_item(self, width, height, quantity, item_id=None):
        """Add item"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'width': width,
            'height': height,
            'quantity': quantity
        })

    def solve(self):
        """
        Solve three-stage problem

        This is more complex - simplified implementation
        """

        # Stage 1: Decide on section cuts
        # Stage 2: For each section, decide on strip cuts
        # Stage 3: For each strip, pack items

        # This requires sophisticated algorithm
        # Typically uses dynamic programming or column generation

        # Placeholder for full implementation
        pass

---

ギロチンカットアルゴリズムの比較

アルゴリズムの比較

アルゴリズム	最適性	速度	複雑さ	最適な用途
二段階 DP	良好	高速	中程度	標準的な製造
三段階	より良好	中速	高い	複雑な品目の組み合わせ
再帰ツリー	柔軟	低速	高い	カスタム要件
列生成	最高	低速	非常に高い	高価な材料

---

実践上の考慮事項

ギロチンカットの利点

1. 設備との適合性

   • ほとんどの切断設備では、自然にギロチンカットが行われます
   • パネルソーやギロチンシャーは、この方式で動作します
   • ツールパスのプログラミングがより簡単です

2. 運用の簡便さ

   • 実行が容易です
   • セットアップ変更が少なくて済みます
   • 切断工程が速くなります

3. 安全性

   • 直線カットは複雑な経路より安全です
   • 材料の取り扱いが容易です
   • 切断片の安定性が向上します

ギロチン制約の欠点

1. 利用率の低下

   • 通常、ギロチンカットではない場合と比べて利用率が5～10％低くなります
   • 制約により無駄が増えます

2. 柔軟性の制限

   • 常に最適な詰め込みを実現できるとは限りません
   • 品目の組み合わせによっては、うまく詰め込めません

---

ツールとライブラリ

ソフトウェア

• CutList Optimizer：ギロチンカットに特化
• OptiCut：ギロチン制約に対応
• Cutting Optimization Pro：ギロチンモードを搭載

---

確認事項

1. すべてのカットをギロチンカットにする必要がありますか？
2. どのような切断設備を使用しますか？
3. 二段階と三段階のどちらが許容されますか？
4. 品目の寸法と数量はどれくらいですか？
5. 品目を回転できますか？
6. 材料費と廃材の影響はどの程度ですか？

---

関連スキル

• 2d-cutting-stock：一般的な2D切断向け
• 1d-cutting-stock：帯状の1D切断向け
• trim-loss-minimization：廃材の削減向け
• nesting-optimization：非長方形形状向け