El Desafío del Empaque en Contenedores: Optimizando Espacios en contenedores con Ingenio
Bin Packing explicado paso a paso: algoritmos, complejidad, código Python y cuándo usar cada estrategia.
El problema de embalaje en contenedores (bin packing) es uno de los desafíos clásicos de la optimización combinatoria. Aparece en logística, planificación de servidores en la nube, corte de materiales y hasta en la asignación de anuncios publicitarios.
En este artículo veremos cuatro algoritmos para resolverlo, sus garantías teóricas, código Python listo para usar y una comparativa real para que elijas el correcto según tu escenario.
¿Qué es el Bin Packing y por qué es difícil?
Dado un conjunto de ítems con tamaños y contenedores de capacidad fija, el objetivo es usar el mínimo número de contenedores posible.
- Entrada: lista de tamaños (ej.
[4, 8, 1, 2, 5, 3]) y capacidad C (ej.10). - Salida: asignación de ítems a contenedores que minimice el total.
Variantes: 1D (peso/volumen lineal), 2D (ancho × alto) y 3D. Este artículo se enfoca en 1D, la base de todas las demás.
First Fit Decreasing (FFD)
Idea: ordena los ítems de mayor a menor y coloca cada uno en el primer contenedor donde quepa. Si no cabe en ninguno, abre uno nuevo.
(11/9)·OPT + 1 contenedores, donde OPT es el óptimo teórico. En la práctica suele estar muy cerca del óptimo real.
def first_fit_decreasing(items, bin_capacity): # Paso 1: ordenar de mayor a menor sorted_items = sorted(items, reverse=True) bins = [] # lista de contenedores, cada uno es una lista de ítems for item in sorted_items: placed = False # Paso 2: buscar el primer contenedor con espacio for b in bins: if item <= bin_capacity - sum(b): b.append(item) placed = True break # Paso 3: si no cabe en ninguno, crear contenedor nuevo if not placed: bins.append([item]) return len(bins), bins # Ejemplo items = [4, 8, 1, 2, 5, 3] bin_capacity = 10 n, bins = first_fit_decreasing(items, bin_capacity) print(f"Contenedores usados: {n}") # → 3 print(f"Distribución: {bins}") # → [[8], [5, 4], [3, 2, 1]]
Best Fit
Idea: en lugar del primer contenedor que quepa, elige el que deje la menor capacidad restante después de colocar el ítem. Minimiza el espacio desperdiciado.
def best_fit(items, bin_capacity): bins = [] # cada elemento es (capacidad_restante, [ítems]) for item in items: best_idx = -1 min_remaining = bin_capacity + 1 # Buscar el contenedor con menor espacio sobrante for i, (rem, _) in enumerate(bins): if item <= rem and rem - item < min_remaining: best_idx = i min_remaining = rem - item if best_idx != -1: rem, content = bins[best_idx] bins[best_idx] = (rem - item, content + [item]) else: bins.append((bin_capacity - item, [item])) result = [content for _, content in bins] return len(result), result # Ejemplo n, bins = best_fit(items, bin_capacity) print(f"Contenedores usados: {n}") # → 3 print(f"Distribución: {bins}") # → [[8, 2], [5, 4], [3, 1]]
Next Fit
Idea: mantiene un solo contenedor abierto (el último). Si el ítem cabe, lo coloca ahí. Si no, cierra ese contenedor y abre uno nuevo. Nunca vuelve a contenedores anteriores.
def next_fit(items, bin_capacity): bins = [] current = [] # contenedor abierto actual current_sum = 0 # espacio usado en el contenedor actual for item in items: if item <= bin_capacity - current_sum: current.append(item) current_sum += item else: bins.append(current) current = [item] current_sum = item if current: bins.append(current) return len(bins), bins # Ejemplo n, bins = next_fit(items, bin_capacity) print(f"Contenedores usados: {n}") # → 4 print(f"Distribución: {bins}") # → [[4, 8], [1, 2, 5], [3]] — depende del orden
Algoritmos Genéticos
Idea: en lugar de seguir una regla fija, exploramos muchas soluciones posibles y las hacemos "evolucionar" mediante selección, cruce y mutación. Son metaheurísticas: no garantizan el óptimo, pero encuentran soluciones de alta calidad en problemas grandes donde las heurísticas clásicas fallan.
import random def evaluate(order, items, bin_capacity): # Aplica Next Fit sobre el orden dado y cuenta contenedores bins = 1 used = 0 for idx in order: size = items[idx] if used + size <= bin_capacity: used += size else: bins += 1 used = size return bins def crossover(p1, p2): # Order Crossover (OX): preserva el orden relativo n = len(p1) a, b = sorted(random.sample(range(n), 2)) child = [-1] * n child[a:b] = p1[a:b] remaining = [x for x in p2 if x not in child[a:b]] idx = 0 for i in range(n): if child[i] == -1: child[i] = remaining[idx] idx += 1 return child def mutate(individual, rate=0.1): ind = individual[:] if random.random() < rate: i, j = random.sample(range(len(ind)), 2) ind[i], ind[j] = ind[j], ind[i] return ind def genetic_algorithm(items, bin_capacity, pop_size=100, generations=200, mut_rate=0.15): n = len(items) population = [random.sample(range(n), n) for _ in range(pop_size)] for gen in range(generations): # Evaluar fitness (menor número de bins = mejor) scores = [(evaluate(ind, items, bin_capacity), ind) for ind in population] scores.sort(key=lambda x: x[0]) # Seleccionar élite (top 20%) elite_count = pop_size // 5 new_pop = [ind for _, ind in scores[:elite_count]] # Generar descendencia por cruce + mutación while len(new_pop) < pop_size: p1, p2 = random.sample(new_pop[:elite_count], 2) child = crossover(p1, p2) child = mutate(child, mut_rate) new_pop.append(child) population = new_pop best = min(population, key=lambda ind: evaluate(ind, items, bin_capacity)) return evaluate(best, items, bin_capacity), best # Ejemplo num_bins, best_order = genetic_algorithm(items, bin_capacity) print(f"Contenedores (GA): {num_bins}") # → típicamente 3
Comparativa de Algoritmos
First Fit Decreasing
El estándar. Buen equilibrio entre calidad y velocidad. Garantía matemática comprobada.
Best Fit
Minimiza espacio desperdiciado. Útil cuando cada contenedor es caro.
Next Fit
Ultra rápido. Ideal para streaming o memoria limitada. Peor calidad.
Genéticos
Para problemas grandes o 2D/3D. Requiere tuning. No garantiza óptimo.
| Algoritmo | Tiempo | Calidad | Memoria | Cuándo usar |
|---|---|---|---|---|
| FFD | Rápido | ⭐⭐⭐⭐ | Baja | Caso general, baseline obligatorio |
| Best Fit | Medio | ⭐⭐⭐⭐ | Media | Contenedores caros, muchos ítems |
| Next Fit | Muy rápido | ⭐⭐ | Mínima | Streaming, tiempo real, memoria limitada |
| Genéticos | Lento | ⭐⭐⭐⭐⭐ | Alta | Instancias grandes, 2D/3D, óptimo cercano |
Resultados con el mismo ejemplo
Para los ítems [4, 8, 1, 2, 5, 3] con capacidad 10:
| Algoritmo | Bins | Distribución | Espacio desperdiciado |
|---|---|---|---|
| FFD | 3 | [8], [5, 4], [3, 2, 1] | 2 + 1 + 4 = 7 |
| Best Fit | 3 | [8, 2], [5, 4], [3, 1] | 0 + 1 + 6 = 7 |
| Next Fit | 4 | [4], [8], [1, 2, 5], [3] | 6 + 2 + 2 + 7 = 17 |
| Genético | 3 | Variable (≈ óptimo) | ≈ 6-7 |
Conclusión y Recomendaciones
El bin packing es un problema fundamental que aparece en más lugares de los que parece: desde camiones de reparto hasta asignación de máquinas virtuales en AWS.
- Empieza siempre con FFD. Es rápido, simple y tiene garantía matemática. Si la solución es suficiente, detente ahí.
- Usa Best Fit si cada contenedor tiene un costo significativo y necesitas exprimir cada byte.
- Next Fit solo en sistemas embebidos o streaming donde la memoria es crítica.
- Genéticos cuando el problema crece (100+ ítems) o cuando trabajas en 2D/3D.
¿Tienes un caso real para aplicar estos algoritmos? ¡Déjalo en los comentarios! 👇
