2d-bin-packing

2D 装箱问题

你是 2D 装箱和矩形排样优化方面的专家。你的目标是帮助将矩形物品装入 2D 箱子或板材，同时尽可能减少浪费、使用的箱子数量，或最大化空间利用率。

初步评估

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

1. 问题类型

   • 装入固定尺寸的箱子（最小化使用的箱子数量）？
   • 装入可变尺寸的箱子（最小化总面积）？
   • 单个大箱子（最大化利用率）？
   • 从板材上裁切（最小化浪费）？

2. 物品特征

   • 要装多少件物品？（几十、几百、几千件）
   • 物品尺寸：宽 × 高
   • 物品能否旋转？（是否允许旋转 90 度？）
   • 物品各不相同，还是有些物品相同？
   • 是否有物品优先级或分组要求？

3. 箱子／板材规格

   • 箱子尺寸：宽 × 高
   • 箱子尺寸固定还是可变？
   • 箱子数量不限还是有限？
   • 物品之间是否有边距／间距要求？

4. 裁切约束

   • 是否仅允许直线裁切？（横贯整张板材的直线裁切）
   • 是否允许自由排样？
   • 最多允许几道裁切工序？
   • 是否可以接受修边损耗？

5. 优化目标

   • 最小化使用的箱子数量？
   • 最小化总面积／材料成本？
   • 最大化利用率？
   • 最小化裁切复杂度？

---

2D 装箱问题框架

问题分类

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

• 将矩形物品装入数量最少的相同箱子
• 必须装入所有物品
• 物品不能重叠
• 物品通常与坐标轴对齐

2. 2D 条带装箱问题

• 宽度固定，高度最小化
• 单条带（高度无限的箱子）
• 最小化使用的总高度

3. 2D 下料问题

• 从较大的板材上裁切物品
• 最小化材料浪费
• 通常带有直线裁切约束

4. 矩形排样问题

• 将物品排入单个大矩形
• 最大化装入的物品数量
• 或最大化空间利用率

5. 二维背包问题

• 物品具有价值
• 在固定箱子中最大化总价值
• 物品可能无法全部装入

---

数学建模

基本 2D 装箱模型

决策变量：

• x_i、y_i = 物品 i 左下角的坐标
• b_i = 分配给物品 i 的箱子编号
• w_j = 如果使用箱子 j 则为 1，否则为 0
• r_i = 如果物品 i 旋转则为 1，否则为 0

目标函数： 最小化 ∑ w_j（最小化使用的箱子数量）

约束条件：

1. 不重叠：同一箱子中的物品不能重叠
2. 容纳：物品必须位于箱子边界内
3. 分配：每件物品必须且只能分配到一个箱子
4. 旋转（可选）：物品可旋转 90 度

复杂度：

• NP 难问题
• 不存在多项式时间的最优算法（除非 P=NP）
• 需要采用启发式或元启发式方法

---

算法和求解方法

精确方法

分支定界法

• 保证得到最优解
• 仅适用于小规模问题（少于 20–30 件物品）
• 时间复杂度为指数级

整数规划建模

from pulp import *

def solve_2d_bin_packing_ip(items, bin_width, bin_height, max_bins=None):
    """
    2D Bin Packing using Integer Programming

    Parameters:
    - items: list of (width, height) tuples
    - bin_width: width of each bin
    - bin_height: height of each bin
    - max_bins: maximum number of bins to consider

    Returns optimal packing solution

    Note: Only practical for small problems (<20 items)
    """

    n = len(items)
    if max_bins is None:
        max_bins = n  # Worst case: one item per bin

    bins = range(max_bins)
    item_ids = range(n)

    # Create problem
    prob = LpProblem("2D_Bin_Packing", LpMinimize)

    # Decision variables
    # x[i,b] = x coordinate of item i in bin b
    x = LpVariable.dicts("x",
                        [(i, b) for i in item_ids for b in bins],
                        lowBound=0, upBound=bin_width, cat='Continuous')

    # y[i,b] = y coordinate of item i in bin b
    y = LpVariable.dicts("y",
                        [(i, b) for i in item_ids for b in bins],
                        lowBound=0, upBound=bin_height, cat='Continuous')

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

    # w[b] = 1 if bin b is used
    w = LpVariable.dicts("use_bin", bins, cat='Binary')

    # Objective: minimize number of bins
    prob += lpSum([w[b] for b in bins]), "Total_Bins"

    # Constraints

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

    # 2. Item fits within bin boundaries
    for i in item_ids:
        for b in bins:
            prob += x[i,b] + items[i][0] <= bin_width + (1 - a[i,b]) * bin_width, \
                    f"Fit_Width_{i}_{b}"
            prob += y[i,b] + items[i][1] <= bin_height + (1 - a[i,b]) * bin_height, \
                    f"Fit_Height_{i}_{b}"

    # 3. Bin is used if any item assigned to it
    for b in bins:
        for i in item_ids:
            prob += a[i,b] <= w[b], f"Bin_Used_{i}_{b}"

    # 4. Non-overlapping constraints (simplified - full version more complex)
    # This is a simplified model; full non-overlap requires additional binary variables

    # Solve
    status = prob.solve(PULP_CBC_CMD(msg=1, timeLimit=300))

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

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

    for b in bins:
        if w[b].varValue > 0.5:
            bin_items = []
            for i in item_ids:
                if a[i,b].varValue > 0.5:
                    bin_items.append({
                        'item_id': i,
                        'x': x[i,b].varValue,
                        'y': y[i,b].varValue,
                        'width': items[i][0],
                        'height': items[i][1]
                    })
            solution['bins'].append(bin_items)

    return solution

启发式方法

降序高度优先适配（FFDH）

• 按高度从大到小对物品排序
• 将物品从左到右排入各层
• 物品无法放入时新开一层

def first_fit_decreasing_height(items, bin_width, bin_height):
    """
    First Fit Decreasing Height (FFDH) Algorithm

    Classic shelf-based packing heuristic
    - Sorts items by decreasing height
    - Packs items left-to-right on shelves
    - Opens new shelf/bin when needed

    Parameters:
    - items: list of (width, height, item_id) tuples
    - bin_width: bin width
    - bin_height: bin height

    Returns packing solution
    """

    # Sort by decreasing height, then decreasing width
    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)

    bins = []

    for item_width, item_height, item_id in sorted_items:
        placed = False

        # Try to place in existing bins
        for bin_idx, bin_data in enumerate(bins):
            shelves = bin_data['shelves']

            # Try each shelf
            for shelf in shelves:
                if (shelf['remaining_width'] >= item_width and
                    shelf['height'] >= item_height):
                    # Place on this shelf
                    x = bin_width - shelf['remaining_width']
                    y = shelf['y']

                    bin_data['items'].append({
                        'id': item_id,
                        'x': x,
                        'y': y,
                        'width': item_width,
                        'height': item_height
                    })

                    shelf['remaining_width'] -= item_width
                    placed = True
                    break

            if placed:
                break

            # Try to create new shelf in this bin
            if not placed:
                current_height = sum(s['height'] for s in shelves)
                if current_height + item_height <= bin_height:
                    # Create new shelf
                    new_shelf = {
                        'y': current_height,
                        'height': item_height,
                        'remaining_width': bin_width - item_width
                    }
                    shelves.append(new_shelf)

                    bin_data['items'].append({
                        'id': item_id,
                        'x': 0,
                        'y': current_height,
                        'width': item_width,
                        'height': item_height
                    })
                    placed = True
                    break

        # Need new bin
        if not placed:
            new_bin = {
                'items': [{
                    'id': item_id,
                    'x': 0,
                    'y': 0,
                    'width': item_width,
                    'height': item_height
                }],
                'shelves': [{
                    'y': 0,
                    'height': item_height,
                    'remaining_width': bin_width - item_width
                }]
            }
            bins.append(new_bin)

    return {
        'num_bins': len(bins),
        'bins': bins,
        'utilization': calculate_utilization(bins, bin_width, bin_height)
    }

def calculate_utilization(bins, bin_width, bin_height):
    """Calculate space utilization percentage"""
    total_item_area = 0
    for bin_data in bins:
        for item in bin_data['items']:
            total_item_area += item['width'] * item['height']

    total_bin_area = len(bins) * bin_width * bin_height
    return (total_item_area / total_bin_area * 100) if total_bin_area > 0 else 0

降序高度下一适配（NFDH）

• 与 FFDH 类似，但只考虑当前箱子
• 方法更简单，但效率较低

降序高度最佳适配（BFDH）

• 为每件物品尝试寻找最合适的层
• 利用率高于 FFDH

def best_fit_decreasing_height(items, bin_width, bin_height):
    """
    Best Fit Decreasing Height Algorithm

    Finds the shelf with minimum remaining space that fits the item
    """

    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)
    bins = []

    for item_width, item_height, item_id in sorted_items:
        best_bin = None
        best_shelf = None
        min_waste = float('inf')

        # Find best fitting shelf
        for bin_idx, bin_data in enumerate(bins):
            for shelf_idx, shelf in enumerate(bin_data['shelves']):
                if (shelf['remaining_width'] >= item_width and
                    shelf['height'] >= item_height):
                    waste = shelf['remaining_width'] - item_width
                    if waste < min_waste:
                        min_waste = waste
                        best_bin = bin_idx
                        best_shelf = shelf_idx

        if best_bin is not None:
            # Place on best shelf
            shelf = bins[best_bin]['shelves'][best_shelf]
            x = bin_width - shelf['remaining_width']
            y = shelf['y']

            bins[best_bin]['items'].append({
                'id': item_id,
                'x': x,
                'y': y,
                'width': item_width,
                'height': item_height
            })

            shelf['remaining_width'] -= item_width
        else:
            # Try to create new shelf or new bin
            placed = False
            for bin_idx, bin_data in enumerate(bins):
                shelves = bin_data['shelves']
                current_height = sum(s['height'] for s in shelves)

                if current_height + item_height <= bin_height:
                    new_shelf = {
                        'y': current_height,
                        'height': item_height,
                        'remaining_width': bin_width - item_width
                    }
                    shelves.append(new_shelf)

                    bin_data['items'].append({
                        'id': item_id,
                        'x': 0,
                        'y': current_height,
                        'width': item_width,
                        'height': item_height
                    })
                    placed = True
                    break

            if not placed:
                # Create new bin
                new_bin = {
                    'items': [{
                        'id': item_id,
                        'x': 0,
                        'y': 0,
                        'width': item_width,
                        'height': item_height
                    }],
                    'shelves': [{
                        'y': 0,
                        'height': item_height,
                        'remaining_width': bin_width - item_width
                    }]
                }
                bins.append(new_bin)

    return {
        'num_bins': len(bins),
        'bins': bins,
        'utilization': calculate_utilization(bins, bin_width, bin_height)
    }

直线裁切算法

• 使用直线裁切进行递归分割
• 每次裁切都贯穿整个矩形
• 常用于制造／裁切应用

class Rectangle:
    """Rectangle representation for guillotine algorithm"""
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height
        self.item_id = None

    def area(self):
        return self.width * self.height

    def fits(self, item_width, item_height):
        return self.width >= item_width and self.height >= item_height

def guillotine_algorithm(items, bin_width, bin_height, split_rule='shorter_leftover'):
    """
    Guillotine Algorithm with Free Rectangles

    Maintains list of free rectangles
    Places items and splits rectangles with guillotine cuts

    Parameters:
    - items: list of (width, height, id) tuples
    - bin_width, bin_height: bin dimensions
    - split_rule: 'shorter_leftover' or 'longer_leftover'

    Returns packing solution
    """

    # Sort items by area (largest first)
    sorted_items = sorted(items, key=lambda x: x[0] * x[1], reverse=True)

    bins = []

    for item_width, item_height, item_id in sorted_items:
        placed = False

        # Try rotation
        rotations = [(item_width, item_height, False)]
        rotations.append((item_height, item_width, True))  # 90-degree rotation

        for try_width, try_height, rotated in rotations:
            if placed:
                break

            # Try existing bins
            for bin_data in bins:
                free_rects = bin_data['free_rectangles']

                # Find best free rectangle
                best_rect_idx = None
                best_rect_score = float('inf')

                for idx, rect in enumerate(free_rects):
                    if rect.fits(try_width, try_height):
                        # Score: prefer smaller remaining area
                        score = rect.area() - (try_width * try_height)
                        if score < best_rect_score:
                            best_rect_score = score
                            best_rect_idx = idx

                if best_rect_idx is not None:
                    rect = free_rects.pop(best_rect_idx)

                    # Place item
                    bin_data['items'].append({
                        'id': item_id,
                        'x': rect.x,
                        'y': rect.y,
                        'width': try_width,
                        'height': try_height,
                        'rotated': rotated
                    })

                    # Split rectangle with guillotine cut
                    new_rects = split_rectangle(rect, try_width, try_height, split_rule)
                    free_rects.extend(new_rects)

                    placed = True
                    break

            if placed:
                break

        # Create new bin if not placed
        if not placed:
            new_bin = {
                'items': [{
                    'id': item_id,
                    'x': 0,
                    'y': 0,
                    'width': item_width,
                    'height': item_height,
                    'rotated': False
                }],
                'free_rectangles': []
            }

            # Add remaining free rectangles from split
            initial_rect = Rectangle(0, 0, bin_width, bin_height)
            new_rects = split_rectangle(initial_rect, item_width, item_height, split_rule)
            new_bin['free_rectangles'] = new_rects

            bins.append(new_bin)

    return {
        'num_bins': len(bins),
        'bins': bins,
        'utilization': calculate_utilization(bins, bin_width, bin_height)
    }

def split_rectangle(rect, used_width, used_height, split_rule):
    """
    Split rectangle after placing item

    Creates two new free rectangles using guillotine cut
    """

    new_rects = []

    remaining_width = rect.width - used_width
    remaining_height = rect.height - used_height

    if split_rule == 'shorter_leftover':
        # Horizontal cut if remaining width is shorter
        if remaining_width <= remaining_height:
            # Horizontal cut
            if remaining_width > 0:
                new_rects.append(Rectangle(
                    rect.x + used_width, rect.y,
                    remaining_width, rect.height
                ))
            if remaining_height > 0:
                new_rects.append(Rectangle(
                    rect.x, rect.y + used_height,
                    used_width, remaining_height
                ))
        else:
            # Vertical cut
            if remaining_height > 0:
                new_rects.append(Rectangle(
                    rect.x, rect.y + used_height,
                    rect.width, remaining_height
                ))
            if remaining_width > 0:
                new_rects.append(Rectangle(
                    rect.x + used_width, rect.y,
                    remaining_width, used_height
                ))

    return new_rects

最大空矩形算法

• 维护所有最大空矩形的列表
• 复杂度更高，但利用率更好
• 不受直线裁切约束

def maximal_rectangles_algorithm(items, bin_width, bin_height):
    """
    Maximal Rectangles Algorithm

    More sophisticated than guillotine - maintains all maximal free rectangles
    No guillotine constraint, allowing better packing

    This allows more flexible packing patterns
    """

    sorted_items = sorted(items, key=lambda x: x[0] * x[1], reverse=True)
    bins = []

    for item_width, item_height, item_id in sorted_items:
        placed = False

        # Try both orientations
        for try_width, try_height, rotated in [(item_width, item_height, False),
                                                 (item_height, item_width, True)]:
            if placed:
                break

            # Try existing bins
            for bin_data in bins:
                free_rects = bin_data['free_rectangles']

                # Find best free rectangle using Best Area Fit
                best_idx = None
                best_score = float('inf')
                best_x, best_y = 0, 0

                for idx, rect in enumerate(free_rects):
                    if rect.width >= try_width and rect.height >= try_height:
                        # Score: prefer tightest fit
                        leftover_x = rect.width - try_width
                        leftover_y = rect.height - try_height
                        score = min(leftover_x, leftover_y)

                        if score < best_score:
                            best_score = score
                            best_idx = idx
                            best_x = rect.x
                            best_y = rect.y

                if best_idx is not None:
                    # Place item
                    bin_data['items'].append({
                        'id': item_id,
                        'x': best_x,
                        'y': best_y,
                        'width': try_width,
                        'height': try_height,
                        'rotated': rotated
                    })

                    # Update free rectangles
                    placed_rect = Rectangle(best_x, best_y, try_width, try_height)
                    update_maximal_rectangles(free_rects, placed_rect)

                    placed = True
                    break

            if placed:
                break

        if not placed:
            # Create new bin
            initial_rect = Rectangle(0, 0, bin_width, bin_height)

            new_bin = {
                'items': [{
                    'id': item_id,
                    'x': 0,
                    'y': 0,
                    'width': item_width,
                    'height': item_height,
                    'rotated': False
                }],
                'free_rectangles': [initial_rect]
            }

            placed_rect = Rectangle(0, 0, item_width, item_height)
            update_maximal_rectangles(new_bin['free_rectangles'], placed_rect)

            bins.append(new_bin)

    return {
        'num_bins': len(bins),
        'bins': bins,
        'utilization': calculate_utilization(bins, bin_width, bin_height)
    }

def update_maximal_rectangles(free_rects, placed_rect):
    """
    Update list of maximal free rectangles after placing an item

    Split intersecting rectangles and remove non-maximal ones
    """

    new_rects = []

    for rect in free_rects[:]:
        if rectangles_intersect(rect, placed_rect):
            # Split this rectangle
            splits = split_intersecting_rectangle(rect, placed_rect)
            new_rects.extend(splits)
        else:
            new_rects.append(rect)

    # Remove non-maximal rectangles
    free_rects.clear()
    for rect in new_rects:
        is_maximal = True
        for other in new_rects:
            if rect != other and contains(other, rect):
                is_maximal = False
                break
        if is_maximal:
            free_rects.append(rect)

def rectangles_intersect(rect1, rect2):
    """Check if two rectangles intersect"""
    return not (rect1.x + rect1.width <= rect2.x or
                rect2.x + rect2.width <= rect1.x or
                rect1.y + rect1.height <= rect2.y or
                rect2.y + rect2.height <= rect1.y)

def contains(outer, inner):
    """Check if outer rectangle contains inner rectangle"""
    return (outer.x <= inner.x and
            outer.y <= inner.y and
            outer.x + outer.width >= inner.x + inner.width and
            outer.y + outer.height >= inner.y + inner.height)

def split_intersecting_rectangle(rect, placed):
    """Split rectangle by removing placed rectangle area"""
    splits = []

    # Create up to 4 new rectangles around the placed item

    # Left piece
    if placed.x > rect.x:
        splits.append(Rectangle(
            rect.x, rect.y,
            placed.x - rect.x, rect.height
        ))

    # Right piece
    if placed.x + placed.width < rect.x + rect.width:
        splits.append(Rectangle(
            placed.x + placed.width, rect.y,
            rect.x + rect.width - (placed.x + placed.width), rect.height
        ))

    # Bottom piece
    if placed.y > rect.y:
        splits.append(Rectangle(
            rect.x, rect.y,
            rect.width, placed.y - rect.y
        ))

    # Top piece
    if placed.y + placed.height < rect.y + rect.height:
        splits.append(Rectangle(
            rect.x, placed.y + placed.height,
            rect.width, rect.y + rect.height - (placed.y + placed.height)
        ))

    return splits

元启发式方法

用于 2D 排样的遗传算法

import random
import numpy as np

class GeneticAlgorithm2DBinPacking:
    """
    Genetic Algorithm for 2D Bin Packing

    Chromosome: permutation of items (packing order)
    Fitness: number of bins used (lower is better)
    """

    def __init__(self, items, bin_width, bin_height,
                 population_size=100, generations=200,
                 mutation_rate=0.1, crossover_rate=0.8):
        self.items = items
        self.bin_width = bin_width
        self.bin_height = bin_height
        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 (item permutation)"""
        return list(np.random.permutation(self.n_items))

    def decode_chromosome(self, chromosome):
        """
        Decode chromosome to packing solution
        Uses FFDH to pack items in the order specified by chromosome
        """
        ordered_items = [self.items[i] for i in chromosome]
        result = first_fit_decreasing_height(
            ordered_items, self.bin_width, self.bin_height
        )
        return result

    def fitness(self, chromosome):
        """
        Fitness function: number of bins used
        Lower is better
        """
        solution = self.decode_chromosome(chromosome)
        return solution['num_bins']

    def crossover(self, parent1, parent2):
        """
        Order Crossover (OX) for permutations
        """
        if random.random() > self.crossover_rate:
            return parent1.copy(), parent2.copy()

        size = len(parent1)

        # Select crossover points
        cx_point1 = random.randint(0, size - 2)
        cx_point2 = random.randint(cx_point1 + 1, size - 1)

        # Create offspring
        child1 = [-1] * size
        child2 = [-1] * size

        # Copy segments
        child1[cx_point1:cx_point2] = parent1[cx_point1:cx_point2]
        child2[cx_point1:cx_point2] = parent2[cx_point1:cx_point2]

        # Fill remaining positions
        self._fill_offspring(child1, parent2, cx_point2)
        self._fill_offspring(child2, parent1, cx_point2)

        return child1, child2

    def _fill_offspring(self, child, parent, start_pos):
        """Fill remaining positions in offspring"""
        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):
        """
        Swap mutation: swap two random positions
        """
        if random.random() < self.mutation_rate:
            pos1, pos2 = random.sample(range(len(chromosome)), 2)
            chromosome[pos1], chromosome[pos2] = chromosome[pos2], chromosome[pos1]
        return chromosome

    def tournament_selection(self, population, fitnesses, tournament_size=3):
        """Tournament selection"""
        tournament_indices = random.sample(range(len(population)), tournament_size)
        tournament_fitnesses = [fitnesses[i] for i in tournament_indices]
        winner_idx = tournament_indices[tournament_fitnesses.index(min(tournament_fitnesses))]
        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 solution
            min_fitness_idx = fitnesses.index(min(fitnesses))
            if fitnesses[min_fitness_idx] < self.best_fitness:
                self.best_fitness = fitnesses[min_fitness_idx]
                self.best_solution = self.decode_chromosome(population[min_fitness_idx])
                print(f"Generation {generation}: Best = {self.best_fitness} bins")

            # Create new population
            new_population = []

            # Elitism: keep best solution
            new_population.append(population[min_fitness_idx])

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

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

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

                new_population.extend([child1, child2])

            population = new_population[:self.population_size]

        return self.best_solution

# Usage example
def example_genetic_algorithm():
    """Example usage of genetic algorithm"""

    # Generate random items
    np.random.seed(42)
    n_items = 30
    items = [(random.randint(10, 50), random.randint(10, 50), i)
             for i in range(n_items)]

    bin_width = 100
    bin_height = 100

    # Run genetic algorithm
    ga = GeneticAlgorithm2DBinPacking(
        items, bin_width, bin_height,
        population_size=50,
        generations=100
    )

    solution = ga.solve()

    print(f"\nFinal Solution:")
    print(f"Number of bins: {solution['num_bins']}")
    print(f"Utilization: {solution['utilization']:.2f}%")

    return solution

模拟退火

import math
import random

def simulated_annealing_2d_packing(items, bin_width, bin_height,
                                    initial_temp=1000, cooling_rate=0.995,
                                    iterations=10000):
    """
    Simulated Annealing for 2D Bin Packing

    Neighborhood: swap two items in packing order
    """

    # Initial solution: random order + FFDH
    current_order = list(range(len(items)))
    random.shuffle(current_order)

    current_items = [items[i] for i in current_order]
    current_solution = first_fit_decreasing_height(
        current_items, bin_width, bin_height
    )
    current_cost = current_solution['num_bins']

    best_order = current_order.copy()
    best_solution = current_solution
    best_cost = current_cost

    temperature = initial_temp

    for iteration in range(iterations):
        # Generate neighbor: swap two items
        neighbor_order = current_order.copy()
        i, j = random.sample(range(len(items)), 2)
        neighbor_order[i], neighbor_order[j] = neighbor_order[j], neighbor_order[i]

        # Evaluate neighbor
        neighbor_items = [items[idx] for idx in neighbor_order]
        neighbor_solution = first_fit_decreasing_height(
            neighbor_items, bin_width, bin_height
        )
        neighbor_cost = neighbor_solution['num_bins']

        # Acceptance criterion
        delta = neighbor_cost - current_cost

        if delta < 0 or random.random() < math.exp(-delta / temperature):
            current_order = neighbor_order
            current_solution = neighbor_solution
            current_cost = neighbor_cost

            if current_cost < best_cost:
                best_order = current_order.copy()
                best_solution = current_solution
                best_cost = current_cost
                print(f"Iteration {iteration}: New best = {best_cost} bins")

        # Cool down
        temperature *= cooling_rate

    return best_solution

---

完整的 2D 装箱求解器

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import numpy as np

class TwoDimensionalBinPacker:
    """
    Comprehensive 2D Bin Packing Solver

    Supports multiple algorithms and visualization
    """

    def __init__(self, bin_width, bin_height):
        self.bin_width = bin_width
        self.bin_height = bin_height
        self.items = []
        self.solution = None

    def add_item(self, width, height, item_id=None):
        """Add item to pack"""
        if item_id is None:
            item_id = len(self.items)
        self.items.append((width, height, item_id))

    def add_items(self, items_list):
        """Add multiple items: list of (width, height) tuples"""
        for width, height in items_list:
            self.add_item(width, height)

    def solve(self, algorithm='ffdh', **kwargs):
        """
        Solve using specified algorithm

        Algorithms:
        - 'ffdh': First Fit Decreasing Height
        - 'bfdh': Best Fit Decreasing Height
        - 'guillotine': Guillotine algorithm
        - 'maxrects': Maximal Rectangles
        - 'genetic': Genetic Algorithm
        - 'simulated_annealing': Simulated Annealing
        """

        if algorithm == 'ffdh':
            self.solution = first_fit_decreasing_height(
                self.items, self.bin_width, self.bin_height
            )

        elif algorithm == 'bfdh':
            self.solution = best_fit_decreasing_height(
                self.items, self.bin_width, self.bin_height
            )

        elif algorithm == 'guillotine':
            self.solution = guillotine_algorithm(
                self.items, self.bin_width, self.bin_height
            )

        elif algorithm == 'maxrects':
            self.solution = maximal_rectangles_algorithm(
                self.items, self.bin_width, self.bin_height
            )

        elif algorithm == 'genetic':
            ga = GeneticAlgorithm2DBinPacking(
                self.items, self.bin_width, self.bin_height,
                **kwargs
            )
            self.solution = ga.solve()

        elif algorithm == 'simulated_annealing':
            self.solution = simulated_annealing_2d_packing(
                self.items, self.bin_width, self.bin_height,
                **kwargs
            )

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

        return self.solution

    def visualize(self, bin_indices=None, save_path=None):
        """
        Visualize packing solution

        Parameters:
        - bin_indices: list of bin indices to visualize (None = all)
        - save_path: path to save figure
        """

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

        bins = self.solution['bins']

        if bin_indices is None:
            bin_indices = range(len(bins))

        n_bins = len(bin_indices)
        cols = min(3, n_bins)
        rows = (n_bins + cols - 1) // cols

        fig, axes = plt.subplots(rows, cols, figsize=(5*cols, 5*rows))
        if n_bins == 1:
            axes = [axes]
        else:
            axes = axes.flatten() if n_bins > 1 else [axes]

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

        for idx, bin_idx in enumerate(bin_indices):
            ax = axes[idx]
            bin_data = bins[bin_idx]

            # Draw bin boundary
            ax.add_patch(patches.Rectangle(
                (0, 0), self.bin_width, self.bin_height,
                fill=False, edgecolor='black', linewidth=2
            ))

            # Draw items
            for item_idx, item in enumerate(bin_data['items']):
                color = colors[item['id'] % 20]

                rect = patches.Rectangle(
                    (item['x'], item['y']),
                    item['width'], item['height'],
                    facecolor=color, edgecolor='black',
                    linewidth=1, alpha=0.7
                )
                ax.add_patch(rect)

                # Add item ID label
                cx = item['x'] + item['width'] / 2
                cy = item['y'] + item['height'] / 2
                ax.text(cx, cy, str(item['id']),
                       ha='center', va='center',
                       fontsize=8, fontweight='bold')

            ax.set_xlim(0, self.bin_width)
            ax.set_ylim(0, self.bin_height)
            ax.set_aspect('equal')
            ax.set_title(f'Bin {bin_idx + 1}')
            ax.set_xlabel('Width')
            ax.set_ylabel('Height')
            ax.grid(True, alpha=0.3)

        # Hide empty subplots
        for idx in range(len(bin_indices), len(axes)):
            axes[idx].axis('off')

        plt.suptitle(
            f'2D Bin Packing Solution\n'
            f'Bins Used: {self.solution["num_bins"]} | '
            f'Utilization: {self.solution["utilization"]:.1f}%',
            fontsize=14, fontweight='bold'
        )

        plt.tight_layout()

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

        plt.show()

    def get_statistics(self):
        """Get detailed statistics about the solution"""

        if self.solution is None:
            return None

        total_item_area = sum(w * h for w, h, _ in self.items)
        total_bin_area = self.solution['num_bins'] * self.bin_width * self.bin_height

        stats = {
            'num_items': len(self.items),
            'num_bins': self.solution['num_bins'],
            'bin_size': (self.bin_width, self.bin_height),
            'total_item_area': total_item_area,
            'total_bin_area': total_bin_area,
            'utilization': self.solution['utilization'],
            'waste_percentage': 100 - self.solution['utilization'],
            'bins': []
        }

        for bin_idx, bin_data in enumerate(self.solution['bins']):
            bin_item_area = sum(
                item['width'] * item['height']
                for item in bin_data['items']
            )
            bin_area = self.bin_width * self.bin_height

            stats['bins'].append({
                'bin_id': bin_idx,
                'num_items': len(bin_data['items']),
                'used_area': bin_item_area,
                'total_area': bin_area,
                'utilization': (bin_item_area / bin_area * 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("=" * 60)
        print("2D BIN PACKING SOLUTION")
        print("=" * 60)
        print(f"Items to pack: {stats['num_items']}")
        print(f"Bin dimensions: {stats['bin_size'][0]} x {stats['bin_size'][1]}")
        print(f"Bins used: {stats['num_bins']}")
        print(f"Overall utilization: {stats['utilization']:.2f}%")
        print(f"Waste percentage: {stats['waste_percentage']:.2f}%")
        print()

        print("Bin Details:")
        print("-" * 60)
        for bin_stat in stats['bins']:
            print(f"Bin {bin_stat['bin_id'] + 1}: "
                  f"{bin_stat['num_items']} items, "
                  f"{bin_stat['utilization']:.1f}% utilization")


# Example usage
if __name__ == "__main__":
    # Create packer
    packer = TwoDimensionalBinPacker(bin_width=100, bin_height=100)

    # Add items
    np.random.seed(42)
    items = [
        (30, 40), (25, 35), (50, 20), (40, 30),
        (20, 25), (35, 45), (15, 30), (25, 20),
        (40, 40), (30, 30), (20, 40), (35, 25),
        (45, 35), (25, 25), (30, 35), (20, 30)
    ]
    packer.add_items(items)

    # Solve using different algorithms
    print("Testing FFDH algorithm:")
    solution_ffdh = packer.solve(algorithm='ffdh')
    packer.print_solution()

    print("\nTesting Guillotine algorithm:")
    solution_guillotine = packer.solve(algorithm='guillotine')
    packer.print_solution()

    # Visualize
    packer.visualize()

---

工具和库

Python Libraries

rectpack

from rectpack import newPacker

def pack_with_rectpack(items, bin_width, bin_height):
    """Use rectpack library for 2D packing"""
    packer = newPacker()

    # Add bins
    for i in range(len(items)):  # Add enough bins
        packer.add_bin(bin_width, bin_height)

    # Add items
    for i, (w, h, item_id) in enumerate(items):
        packer.add_rect(w, h, rid=item_id)

    # Pack
    packer.pack()

    # Extract results
    bins_used = len([b for b in packer if b])

    return {
        'num_bins': bins_used,
        'packer': packer
    }

binpack - 简单的 1D/2D 装箱

py2dbp - 2D 装箱算法

OR-Tools - Google 的优化库

Commercial Software

• CutLogic 2D：专业切割优化
• Cutting Optimization Pro：切割与排样
• OptiCut：板材优化软件
• MaxCut：下料优化

---

常见挑战与解决方案

挑战：物品无法高效装箱

问题：

• 利用率低（<70%）
• 使用的箱子过多
• 出现形状不规则的空隙

解决方案：

• 允许旋转 90 度
• 尝试不同的排序策略
• 使用元启发式算法（GA、SA）
• 策略性地组合小物品
• 考虑预先对尺寸相近的物品分组

挑战：闸刀式约束过于严格

问题：

• 闸刀式切割浪费空间
• 需要更灵活的装箱方式

解决方案：

• 使用最大矩形算法
• 允许有限的非闸刀式排样
• 采用多阶段切割方法
• 优化阶段顺序

挑战：需要实时装箱

问题：

• 物品动态到达
• 需要快速得出方案
• 无法重新安排已放置的物品

解决方案：

• 使用快速在线算法（FFDH、NFDH）
• 为预期到达的物品预留空间
• 设置定期重新优化时段
• 采用混合在线/离线方法

挑战：小物品数量很多

问题：

• 数千件微小物品
• 组合爆炸
• 计算速度慢

解决方案：

• 预先对相似物品聚类
• 采用分层方法
• 通过基于时间的停止条件限制搜索时间
• 并行处理

---

输出格式

2D 装箱报告

执行摘要：

• 已装箱物品：150 件
• 使用箱子：12 张板材（每张 100cm x 100cm）
• 利用率：87.3%
• 浪费率：12.7%
• 算法：采用 GA 优化的闸刀式切割

装箱详情：

箱子	物品数	已用面积	利用率	浪费率
1	15	8,750 cm²	87.5%	12.5%
2	13	9,100 cm²	91.0%	9.0%
3	14	8,450 cm²	84.5%	15.5%

切割排样示例（箱子 1）：

+------------------+
|  A   |  B  | C  |
|------+-----+----|
|  D   | E  F|  G |
|------+-----+----|
|  H   |  I  |  J |
+------------------+

物品列表：

物品 ID	宽度	高度	箱子	位置 (x,y)	已旋转
A001	40	30	1	(0, 0)	否
A002	25	30	1	(40, 0)	否
A003	20	30	1	(65, 0)	是

成本分析：

• 每张板材的材料成本：$50
• 材料总成本：$600
• 浪费成本：$76（12.7%）
• 完美装箱可节省：$76

---

需要询问的问题

如果需要更多背景信息：

1. 箱子/板材的尺寸是多少？
2. 需要装箱多少件物品？它们的尺寸是多少？
3. 物品可以旋转 90 度吗？
4. 是否有闸刀式切割约束？
5. 优化目标是什么？（减少箱子数量、减少浪费、最大化价值）
6. 物品之间是否需要留出间距？
7. 物品是否有优先级或必须装入的要求？
8. 这是一次性问题还是周期性生产？

---

相关技能

• 1d-cutting-stock：适用于一维下料问题
• 3d-bin-packing：适用于三维装箱
• pallet-loading：适用于托盘装载优化
• container-loading-optimization：适用于集装箱装箱
• strip-packing：适用于条带装箱问题
• guillotine-cutting：适用于闸刀式切割约束
• nesting-optimization：适用于不规则形状排样
• knapsack-problems：适用于基于价值的装箱