一、业务背景
在日本海外仓的仓储合箱服务中，系统需要把多个形状各异的商品装入一个纸箱。目标是：选择最小的纸箱，最大化空间利用率。
这是一个经典的三维装箱问题（3D Bin Packing），属于NP-hard问题，没有多项式时间的最优解。
我最早实现的方案是最大剩余空间法（一种贪心算法）：
python
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.heightdef 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%。
问题在于：贪心算法只做局部最优决策，没有全局视野。
三、遗传算法优化
我用遗传算法来搜索最优的装箱方案：
python
import randomimport copyclass 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.mutationrate = 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): # 选择（锦标赛选择） newpopulation = [] 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
四、性能对比
算法 平均空间利用率 平均计算时间
贪心算法 68% < 10ms
遗传算法（100代） 82% 500ms
遗传算法（500代） 87% 2.5s
在实际生产中，我选择遗传算法200代，在利用率和时间之间取得平衡——空间利用率达到84%，计算时间约1秒，用户完全可以接受。
五、总结
三维装箱问题的核心是搜索最优的商品排列顺序。贪心算法快但不优，遗传算法慢但能找到更好的解。对于合箱打包这种对实时性要求不那么高的场景（用户愿意等几秒），遗传算法是更好的选择。
