三维装箱算法优化从贪心到遗传的演进方法

一、业务背景

在日本海外仓的仓储合箱服务中，系统需要将多个形状各异的商品高效地装入一个纸箱。核心目标很简单：选择最小的纸箱，同时最大化空间利用率。这正是经典的三维装箱问题（3D Bin Packing），属于NP-hard难题，不存在多项式时间内的最优解。早期解决方案采用最大剩余空间法——一种贪心算法，其核心代码大致如下：

class Space:
    def __init__(self, x, y, z, width, depth, height):
        self.x = x
        self.y = y
        self.z = z
        self.width = width
        self.depth = depth
        self.height = height
    def get_volume(self):
        return self.width * self.depth * self.height

def pack_items(items, box):
    """贪心装箱"""
    spaces = [Space(0, 0, 0, box.width, box.depth, box.height)]
    for item in items:
        # 按体积降序排列空间
        spaces.sort(key=lambda s: s.get_volume(), reverse=True)
        placed = False
        for space in spaces:
            # 尝试所有旋转方向
            for rotation in get_rotations(item):
                if can_fit(rotation, space):
                    place_item(rotation, space)
                    split_space(space, rotation)
                    placed = True
                    break
            if placed:
                break
        if not placed:
            return False  # 装不下
    return True

二、贪心算法的问题

贪心算法虽然执行速度快，但结果往往不够理想。以一组测试数据为例：5个不同尺寸的商品，贪心算法选择的纸箱体积利用率仅为68%，而手工装箱却能轻松达到85%。问题根源在于：贪心算法只关注局部最优决策，缺乏全局视野——它无法预知后续还有哪些商品需要放置，因此常常将优质空间浪费在小件商品上，导致大件商品无处可放。

三、遗传算法优化

既然贪心算法存在局限，不妨换个思路——采用遗传算法来搜索最优的装箱方案。

import random
import copy

class GeneticPacker:
    def __init__(self, items, box_types, population_size=100, generations=500):
        self.items = items
        self.box_types = box_types
        self.population_size = population_size
        self.generations = generations
        self.mutation_rate = 0.05

    def solve(self):
        # 初始化种群：每个个体是一个装箱顺序
        population = []
        for _ in range(self.population_size):
            order = random.sample(self.items, len(self.items))
            box = self._select_box(order)
            population.append({
                'order': order,
                'box': box,
                'fitness': self._calculate_fitness(order, box)
            })

        for gen in range(self.generations):
            # 选择（锦标赛选择）
            new_population = []
            for _ in range(self.population_size // 2):
                parent1 = self._tournament_select(population)
                parent2 = self._tournament_select(population)

                # 交叉（顺序交叉）
                child1, child2 = self._crossover(parent1, parent2)

                # 变异
                if random.random() < self.mutation_rate:
                    self._mutate(child1)
                if random.random() < self.mutation_rate:
                    self._mutate(child2)

                # 评估
                box1 = self._select_box(child1)
                box2 = self._select_box(child2)
                new_population.append({
                    'order': child1,
                    'box': box1,
                    'fitness': self._calculate_fitness(child1, box1)
                })
                new_population.append({
                    'order': child2,
                    'box': box2,
                    'fitness': self._calculate_fitness(child2, box2)
                })

            population = new_population
            population.sort(key=lambda x: x['fitness'], reverse=True)

        return population[0]

    def _crossover(self, parent1, parent2):
        """顺序交叉（Order Crossover）"""
        size = len(parent1)
        start = random.randint(0, size - 2)
        end = random.randint(start + 1, size - 1)

        child1 = [None] * size
        child2 = [None] * size

        # 复制父1的一段到子1
        for i in range(start, end + 1):
            child1[i] = parent1[i]

        # 从父2填充剩余位置
        p2_idx = 0
        for i in range(size):
            if child1[i] is None:
                while parent2[p2_idx] in child1:
                    p2_idx += 1
                child1[i] = parent2[p2_idx]
                p2_idx += 1

        # 同样处理子2
        for i in range(start, end + 1):
            child2[i] = parent2[i]

        p1_idx = 0
        for i in range(size):
            if child2[i] is None:
                while parent1[p1_idx] in child2:
                    p1_idx += 1
                child2[i] = parent1[p1_idx]
                p1_idx += 1

        return child1, child2

遗传算法的核心思想在于：它不直接寻找“怎么放”，而是寻找“按什么顺序放”。每改变一种顺序，装箱结果就会截然不同。通过选择、交叉、变异等操作，种群一代代进化，最终收敛到接近最优的排列顺序。

四、性能对比

两种算法放在一起比较，差异十分明显：

在实际生产中，200代的遗传算法是一个不错的折中方案——空间利用率可达84%，计算时间约1秒，用户愿意等待。毕竟合箱打包场景对实时性要求并不苛刻，几秒钟的等待换来10%以上的空间节省，完全值得投入。

五、总结

三维装箱问题的本质，在于搜索最优的商品排列顺序。贪心算法速度快但结果不优，优势在于简单易实现；遗传算法计算较慢但能逼近全局最优，优势在于效果出色。对于合箱打包这类用户愿意等待几秒钟的场景，遗传算法显然是更合适的选择。当然，如果未来遇到实时性要求极高的场景（如生产线上的动态装箱），可能还需要考虑其他更高效的启发式算法，这将是另一个值得探讨的话题。

你是一名 AI 行业编辑，请围绕下面这条热点输出一份资讯解读：
热点：三维装箱算法优化从贪心到遗传的演进方法要求：
1. 先用一句话解释这条热点在讲什么
2. 再总结它为什么重要
3. 说明会影响哪些 AI 产品或内容方向
4. 最后给出 3 个适合资讯站使用的标题