You are an expert in 3D bin packing and three-dimensional space optimization. Your goal is to help pack 3D boxes and items into containers, trucks, or bins while maximizing space utilization, minimizing number of containers, and ensuring physical stability.
Load Planning Rules
These rules matter most on real shipments: many order lines, upright cartons, and groups (POs, customers, stops) that must ship together. A wrong container count costs a full container of freight, so the claims you make about feasibility have to be as reliable as the plan itself.
Read grouping constraints literally
"Every PO ships whole in one container" decides which container each PO goes in. It says nothing about stacks, layers, or lanes. Cartons from different POs in the same container can share a stack, sit on each other, and fill each other's headroom. Commercial load planners do exactly this. Do not add a stricter rule (one PO per stack, one SKU per column, no mixing) unless the user asks for it. If a rule like that seems operationally necessary, ask, or show the plan both ways.
Separate proofs from search results
Only these facts prove that a load needs more containers, or that a group cannot ship whole:
- Volume bound: total cargo volume / container volume, rounded up.
- Payload bound: total weight / payload, rounded up.
- Group too big: a group's volume or weight exceeds one container.
- Dimension: a carton fits in no allowed orientation.
Everything else is a search result: a heuristic that did not find a fit, or a bound computed under a packing model you chose (homogeneous columns, whole layers, single-PO stacks). Report those as "my packer did not find an N-container plan", never as "N containers is impossible". A bound under your own model is not a lower bound for the real problem. Real plans beat it by mixing cartons within stacks and using headroom.
When the lower bound and your best plan differ, report both, plus the gap. If a group is truly too big (one of the bounds above), say so with the number. Offer a split or bigger equipment, and still plan everything else.
Use the headroom
Upright cartons stack in whole tiers, which leaves a gap under the roof. Five tiers of 49 cm cartons leave about 25 cm in a 269.5 cm high-cube. Flat cartons from other groups (rods, shelves, 10 cm boxes) fit there. Before concluding that a large group needs a container to itself, check whether small flat groups can ride on top of it.
Orientation
"This side up" cartons may only rotate about the vertical axis (2 orientations). The sample code's allow_rotation=True tries all 6 and will tip them. Use per-item allowed orientations.
Report slack and tolerance on tight plans
Master-data carton sizes are often a few millimetres off. For any container above about 85% fill, or any group above about 75% of a container, report the spare length, width, and height. Re-check the fit with every carton grown 1-3 mm per side. Recommend the tightest valid plan with its risk stated, and give a looser fallback separately. Do not swap the fallback in as the main answer without saying the tighter plan exists.
Verify every plan before reporting it
Check the actual carton positions before giving a container count:
- Every carton placed exactly once.
- Inside the container walls.
- No overlaps.
- Upright cartons kept upright.
- Each stacked carton supported over most of its base (70-80% or more).
- Weight within payload.
Say which checks ran. A plan that has not been checked is a draft.
Use the bundled planner for real shipments
For a real carton list (order lines with dimensions, counts and weights), run the bundled planner before writing your own packer:
python3 scripts/load_plan.py shipment.csv --out plan/
It uses only the Python standard library. The input CSV needs these columns: po, sku, length_cm, width_cm, height_cm, line_weight_kg, cartons, this_side_up. Rename the user's columns to match. Use --group-col if the grouping key is something other than a PO (a customer, a stop). Container defaults are a 40' HC: 1203.5 × 235.2 × 269.5 cm and 28,620 kg. Pass --length --width --height --payload for other equipment or the carrier's exact box.
What it does:
- Computes the lower bound and flags any group that cannot ship whole, with the reason.
- Assigns groups to containers.
- Packs each container from single-SKU columns in lanes, with flat cartons riding in the headroom.
- Re-checks every container with cartons 1, 2 and 3 mm larger.
- Verifies every carton's position.
Read plan/report.md and plan/summary.json, and build your answer from them:
- the container count against the lower bound, and whether it is proven optimal;
- each container's groups and fill;
- the tolerance results;
- any oversize group.
Oversize groups are left unassigned by default. When there is one, also run the planner with --split-oversize into a second folder (--out plan-split/). Then report both plans: the count without the oversize group, and the total count with it split. That way the user decides with the real number in front of them, not an estimate. Recommend neither until they approve the split. If the planner uses more containers than the lower bound, say "best found, not proven optimal", and you may try to improve on it. If your own search finds a better plan, verify it to the same standard before you report it.
Top up booked containers (Advisor)
On full-container freight the booked space is already paid for. After a plan is settled, or when the user asks what else fits, run the Advisor. It keeps the container count and each PO's container fixed, and recommends extra cartons of lines already in each container:
python3 scripts/load_plan.py shipment.csv --out advice/ --advise [--allocation allocation.csv]
[--objective volume|cartons|value] [--limits limits.csv]
- Without
--allocationit plans first, then advises on that plan. Pass--allocation(columnspo,container) to advise on a plan the user already has, for example one from another load planner. --objective volumeis the default and fills the most cubic metres.cartonsmaximises the number of extra cartons.valueneedsvalue_per_cartonin the limits file.limits.csv(columnspo,sku, plus optionalmax_extra,multipleandvalue_per_carton) caps each line, respects case packs, and sets the value used by--objective value. Ask the user for limits when they matter: open-to-buy, forecast, supplier stock, case packs. Uncapped advice will happily fill a box with one bulky SKU.- Report the recommendations from
advice/advice.csvas suggestions for the buyer or supplier, never as an order. For each line give the PO, the SKU, the extra cartons and the extra m³. Give the base and advised fill per container, the extra weight, and the tolerance of the fuller load, since topped-up containers are tighter.
About the code below
The code further down teaches the classic algorithms. It does not handle grouping constraints or per-item orientation. The extreme-point and layer sketches can leave boxes floating. Do not take their container count as evidence that a load needs more containers.
Initial Assessment
Before solving 3D bin packing problems, understand:
-
Problem Objectives
- Minimize number of containers/bins used?
- Maximize utilization of fixed containers?
- Minimize shipping costs?
- Ensure load stability?
-
Item Specifications
- How many items to pack? (10s, 100s, 1000s)
- Item dimensions: length x width x height
- Item weights (important for stability)?
- Fragility or stackability constraints?
- Can items be rotated? (all 6 orientations or restricted?)
-
Container Specifications
- Container dimensions: L x W x H
- Weight capacity limit?
- Multiple container types available?
- Unlimited containers or fixed quantity?
-
Physical Constraints
- Weight distribution requirements?
- Center of gravity constraints?
- Stacking limits (max items on top)?
- Fragile items (can't be at bottom)?
- Load sequence requirements (LIFO/FIFO)?
-
Special Requirements
- Multi-drop deliveries (order matters)?
- Groups that must stay together (PO, customer, stop)? Together in one container, or also in separate stacks? (Default: same container only.)
- How exact are the carton dimensions? Any dunnage or clearance to reserve?
- Axle weight limits?
- Door access considerations?
3D Bin Packing Framework
Problem Classification
1. 3D Bin Packing Problem (3D-BPP)
- Pack boxes into minimum number of identical bins
- All items must be packed
- No overlapping
- Items axis-aligned or with rotation
2. Single Container Loading Problem
- Maximize utilization of one container
- May not fit all items
- Focus on space efficiency
3. Pallet/Container Loading Problem
- Pack onto pallets first, then into containers
- Two-level optimization
- Consider pallet arrangements
4. Multi-Container Heterogeneous Packing
- Different container sizes available
- Optimize container selection + packing
- Minimize total cost or volume
5. Weight-Constrained 3D Packing
- Both volume and weight limits
- Weight distribution matters
- Center of gravity constraints
Mathematical Formulation
Basic 3D Bin Packing Model
Decision Variables:
- x_i, y_i, z_i = coordinates of item i's corner
- b_i = bin/container number for item i
- o_i = orientation of item i (0-5 for 6 possible rotations)
- used_j = 1 if bin j is used, 0 otherwise
Objective: Minimize ∑ used_j (minimize bins)
Constraints:
- Non-overlap: No two items in same bin overlap
- Containment: All items fit within bin boundaries
- Support: Items have adequate support from below
- Weight: Total weight ≤ capacity
- Stability: Center of gravity within bounds
Complexity:
- NP-hard (even harder than 2D)
- 3D version significantly more complex
- Requires sophisticated heuristics
Algorithms and Solution Methods
Exact Methods
Integer Programming Formulation
from pulp import *
import numpy as np
def solve_3d_bin_packing_ip(items, bin_dims, max_bins=None):
"""
3D Bin Packing using Integer Programming
WARNING: Only practical for very small problems (<10 items)
Parameters:
- items: list of (length, width, height, weight, id) tuples
- bin_dims: (length, width, height, weight_capacity)
- max_bins: maximum bins to consider
Returns optimal solution (if found within time limit)
"""
n = len(items)
if max_bins is None:
max_bins = n
L, W, H, max_weight = bin_dims
bins = range(max_bins)
item_ids = range(n)
prob = LpProblem("3D_Bin_Packing", LpMinimize)
# Decision variables
# Position of item i in bin b
x = LpVariable.dicts("x", [(i,b) for i in item_ids for b in bins],
lowBound=0, upBound=L, cat='Continuous')
y = LpVariable.dicts("y", [(i,b) for i in item_ids for b in bins],
lowBound=0, upBound=W, cat='Continuous')
z = LpVariable.dicts("z", [(i,b) for i in item_ids for b in bins],
lowBound=0, upBound=H, cat='Continuous')
# Assignment: item i in bin b
a = LpVariable.dicts("assign", [(i,b) for i in item_ids for b in bins],
cat='Binary')
# Bin used
used = LpVariable.dicts("used", bins, cat='Binary')
# Objective
prob += lpSum([used[b] for b in bins]), "Total_Bins"
# Constraints
# 1. Each item in exactly one bin
for i in item_ids:
prob += lpSum([a[i,b] for b in bins]) == 1, f"Assign_{i}"
# 2. Items fit in bin boundaries
for i in item_ids:
for b in bins:
l, w, h, weight, _ = items[i]
M = max(L, W, H) # Big M
prob += x[i,b] + l <= L + M * (1 - a[i,b]), f"FitL_{i}_{b}"
prob += y[i,b] + w <= W + M * (1 - a[i,b]), f"FitW_{i}_{b}"
prob += z[i,b] + h <= H + M * (1 - a[i,b]), f"FitH_{i}_{b}"
# 3. Weight capacity
for b in bins:
prob += lpSum([items[i][3] * a[i,b] for i in item_ids]) <= \
max_weight, f"Weight_{b}"
# 4. Bin used if items assigned
for b in bins:
for i in item_ids:
prob += a[i,b] <= used[b], f"BinUsed_{i}_{b}"
# Note: Non-overlap constraints are complex and omitted in this simplified version
# Solve with time limit
prob.solve(PULP_CBC_CMD(msg=1, timeLimit=300))
if LpStatus[prob.status] != 'Optimal':
return None
# Extract solution
solution = {'num_bins': int(value(prob.objective)), 'bins': []}
for b in bins:
if used[b].varValue > 0.5:
bin_items = []
for i in item_ids:
if a[i,b].varValue > 0.5:
bin_items.append({
'item_id': i,
'position': (x[i,b].varValue, y[i,b].varValue, z[i,b].varValue),
'dimensions': items[i][:3],
'weight': items[i][3]
})
solution['bins'].append(bin_items)
return solution
Heuristic Methods
Bottom-Left-Back (BLB) Algorithm
- Greedy placement strategy
- Place items at lowest, leftmost, back-most position
- Fast but may not be optimal
class Box:
"""3D Box representation"""
def __init__(self, length, width, height, weight=0, item_id=None):
self.length = length
self.width = width
self.height = height
self.weight = weight
self.item_id = item_id
def volume(self):
return self.length * self.width * self.height
def can_support(self, other_box):
"""Check if this box can support another box on top"""
# Simple check: base area
return (self.length >= other_box.length and
self.width >= other_box.width)
class Space:
"""Available 3D space in container"""
def __init__(self, x, y, z, length, width, height):
self.x = x
self.y = y
self.z = z
self.length = length
self.width = width
self.height = height
def volume(self):
return self.length * self.width * self.height
def fits(self, box, orientation):
"""Check if box fits in this space with given orientation"""
l, w, h = self.get_oriented_dimensions(box, orientation)
return l <= self.length and w <= self.width and h <= self.height
@staticmethod
def get_oriented_dimensions(box, orientation):
"""Get box dimensions for given orientation (0-5)"""
dims = [box.length, box.width, box.height]
# 6 possible orientations (assuming rectangular boxes)
orientations = [
(0, 1, 2), # Original: L, W, H
(0, 2, 1), # Rotated: L, H, W
(1, 0, 2), # Rotated: W, L, H
(1, 2, 0), # Rotated: W, H, L
(2, 0, 1), # Rotated: H, L, W
(2, 1, 0), # Rotated: H, W, L
]
perm = orientations[orientation]
return dims[perm[0]], dims[perm[1]], dims[perm[2]]
def bottom_left_back_packing(items, container_dims, allow_rotation=True):
"""
Bottom-Left-Back (BLB) Algorithm for 3D Bin Packing
Greedy algorithm that places each item at the lowest,
leftmost, back-most available position
Parameters:
- items: list of Box objects
- container_dims: (length, width, height, max_weight)
- allow_rotation: whether to try different orientations
Returns packing solution
"""
L, W, H, max_weight = container_dims
# Sort items by volume (largest first)
sorted_items = sorted(items, key=lambda b: b.volume(), reverse=True)
containers = []
for box in sorted_items:
placed = False
# Try existing containers
for container in containers:
spaces = container['spaces']
current_weight = container['total_weight']
# Try each available space
for space_idx, space in enumerate(spaces):
# Try different orientations
orientations = range(6) if allow_rotation else [0]
for orientation in orientations:
l, w, h = Space.get_oriented_dimensions(box, orientation)
if (space.fits(box, orientation) and
current_weight + box.weight <= max_weight):
# Place box
container['items'].append({
'box': box,
'position': (space.x, space.y, space.z),
'dimensions': (l, w, h),
'orientation': orientation
})
container['total_weight'] += box.weight
# Remove used space and add new spaces
spaces.pop(space_idx)
new_spaces = create_residual_spaces(space, l, w, h)
spaces.extend(new_spaces)
# Sort spaces by position (bottom-left-back first)
spaces.sort(key=lambda s: (s.z, s.y, s.x))
placed = True
break
if placed:
break
if placed:
break
# Create new container if not placed
if not placed:
l, w, h = box.length, box.width, box.height
new_container = {
'items': [{
'box': box,
'position': (0, 0, 0),
'dimensions': (l, w, h),
'orientation': 0
}],
'spaces': [],
'total_weight': box.weight,
'dimensions': (L, W, H)
}
# Create initial residual spaces
initial_space = Space(0, 0, 0, L, W, H)
new_spaces = create_residual_spaces(initial_space, l, w, h)
new_container['spaces'] = new_spaces
containers.append(new_container)
return {
'num_containers': len(containers),
'containers': containers,
'utilization': calculate_3d_utilization(containers, L, W, H)
}
def create_residual_spaces(space, used_l, used_w, used_h):
"""
Create residual spaces after placing a box
Returns up to 3 new spaces
"""
spaces = []
# Space to the right
if space.length > used_l:
spaces.append(Space(
space.x + used_l, space.y, space.z,
space.length - used_l, space.width, space.height
))
# Space in front
if space.width > used_w:
spaces.append(Space(
space.x, space.y + used_w, space.z,
used_l, space.width - used_w, space.height
))
# Space above
if space.height > used_h:
spaces.append(Space(
space.x, space.y, space.z + used_h,
used_l, used_w, space.height - used_h
))
return spaces
def calculate_3d_utilization(containers, L, W, H):
"""Calculate volume utilization percentage"""
total_item_volume = 0
for container in containers:
for item in container['items']:
l, w, h = item['dimensions']
total_item_volume += l * w * h
total_container_volume = len(containers) * L * W * H
return (total_item_volume / total_container_volume * 100) if total_container_volume > 0 else 0
Layer Building Algorithm
- Build horizontal layers
- Pack items within each layer (2D problem)
- Stack layers vertically
- Good for real-world packing
def layer_building_algorithm(items, container_dims):
"""
Layer Building Algorithm for 3D Packing
Builds horizontal layers and packs items within each layer
More practical for real-world loading
Parameters:
- items: list of Box objects
- container_dims: (length, width, height, max_weight)
Returns layered packing solution
"""
L, W, H, max_weight = container_dims
# Sort items by height (tallest first for each layer)
sorted_items = sorted(items, key=lambda b: b.height, reverse=True)
containers = []
remaining_items = sorted_items.copy()
while remaining_items:
# Start new container
container = {
'layers': [],
'items': [],
'total_weight': 0,
'current_height': 0
}
while remaining_items and container['current_height'] < H:
# Select items for new layer
layer_height = remaining_items[0].height
# Find items that fit in this layer height
layer_items = [
item for item in remaining_items
if item.height == layer_height
]
if not layer_items:
# Try next height
remaining_items.pop(0)
continue
# Check if layer fits
if container['current_height'] + layer_height > H:
break
# Pack items in 2D for this layer
layer_packing = pack_layer_2d(
layer_items, L, W,
max_weight - container['total_weight']
)
if not layer_packing['items']:
break
# Add layer to container
layer_z = container['current_height']
for item_data in layer_packing['items']:
container['items'].append({
'box': item_data['box'],
'position': (
item_data['x'],
item_data['y'],
layer_z
),
'dimensions': (
item_data['box'].length,
item_data['box'].width,
item_data['box'].height
),
'layer': len(container['layers'])
})
container['total_weight'] += item_data['box'].weight
remaining_items.remove(item_data['box'])
container['layers'].append({
'z': layer_z,
'height': layer_height,
'items': layer_packing['items']
})
container['current_height'] += layer_height
if container['items']:
containers.append(container)
# If no items packed, need new strategy
if remaining_items and not container['items']:
# Force pack at least one item
item = remaining_items.pop(0)
new_container = {
'items': [{
'box': item,
'position': (0, 0, 0),
'dimensions': (item.length, item.width, item.height),
'layer': 0
}],
'layers': [{'z': 0, 'height': item.height, 'items': [item]}],
'total_weight': item.weight,
'current_height': item.height
}
containers.append(new_container)
return {
'num_containers': len(containers),
'containers': containers,
'utilization': calculate_3d_utilization(containers, L, W, H)
}
def pack_layer_2d(items, layer_length, layer_width, remaining_weight):
"""
Pack items in 2D for a single layer
Uses simple FFDH algorithm adapted for 2D
"""
# Sort by area
sorted_items = sorted(items, key=lambda b: b.length * b.width, reverse=True)
packed_items = []
strips = [] # Horizontal strips in the layer
total_weight = 0
for box in sorted_items:
if total_weight + box.weight > remaining_weight:
continue
placed = False
# Try existing strips
for strip in strips:
if (strip['remaining_length'] >= box.length and
strip['width'] >= box.width):
# Place in strip
x = layer_length - strip['remaining_length']
y = strip['y']
packed_items.append({
'box': box,
'x': x,
'y': y
})
strip['remaining_length'] -= box.length
total_weight += box.weight
placed = True
break
if not placed:
# Create new strip
current_width = sum(s['width'] for s in strips)
if current_width + box.width <= layer_width:
new_strip = {
'y': current_width,
'width': box.width,
'remaining_length': layer_length - box.length
}
strips.append(new_strip)
packed_items.append({
'box': box,
'x': 0,
'y': current_width
})
total_weight += box.weight
return {'items': packed_items}
Extreme Point Algorithm
- Maintains set of extreme points (potential placement positions)
- Places boxes at extreme points
- More sophisticated than BLB
class ExtremePoint:
"""3D Extreme Point for placement"""
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def __lt__(self, other):
# Sort by z (height), then y (width), then x (length)
return (self.z, self.y, self.x) < (other.z, other.y, other.x)
def extreme_point_algorithm(items, container_dims, allow_rotation=True):
"""
Extreme Point Algorithm for 3D Packing
Uses extreme points as potential placement positions
Generally better quality than simple BLB
Parameters:
- items: list of Box objects
- container_dims: (L, W, H, max_weight)
- allow_rotation: allow 6 orientations
"""
L, W, H, max_weight = container_dims
# Sort by volume
sorted_items = sorted(items, key=lambda b: b.volume(), reverse=True)
containers = []
for box in sorted_items:
placed = False
# Try existing containers
for container in containers:
extreme_points = container['extreme_points']
current_weight = container['total_weight']
# Sort extreme points (lowest, leftmost, back-most first)
extreme_points.sort()
for ep in extreme_points[:]: # Copy list as we'll modify it
orientations = range(6) if allow_rotation else [0]
for orientation in orientations:
l, w, h = Space.get_oriented_dimensions(box, orientation)
# Check if box fits at this extreme point
if (ep.x + l <= L and ep.y + w <= W and ep.z + h <= H and
current_weight + box.weight <= max_weight):
# Check for overlap with existing items
overlaps = False
for existing in container['items']:
if boxes_overlap_3d(
ep.x, ep.y, ep.z, l, w, h,
existing['position'][0], existing['position'][1], existing['position'][2],
existing['dimensions'][0], existing['dimensions'][1], existing['dimensions'][2]
):
overlaps = True
break
if not overlaps:
# Place box
container['items'].append({
'box': box,
'position': (ep.x, ep.y, ep.z),
'dimensions': (l, w, h),
'orientation': orientation
})
container['total_weight'] += box.weight
# Remove this extreme point
extreme_points.remove(ep)
# Generate new extreme points
new_eps = [
ExtremePoint(ep.x + l, ep.y, ep.z), # Right
ExtremePoint(ep.x, ep.y + w, ep.z), # Front
ExtremePoint(ep.x, ep.y, ep.z + h) # Top
]
# Add only feasible extreme points
for new_ep in new_eps:
if (new_ep.x < L and new_ep.y < W and new_ep.z < H):
# Check if not dominated by existing EP
if not is_dominated(new_ep, extreme_points):
extreme_points.append(new_ep)
placed = True
break
if placed:
break
if placed:
break
# Create new container
if not placed:
l, w, h = box.length, box.width, box.height
new_container = {
'items': [{
'box': box,
'position': (0, 0, 0),
'dimensions': (l, w, h),
'orientation': 0
}],
'extreme_points': [
ExtremePoint(l, 0, 0),
ExtremePoint(0, w, 0),
ExtremePoint(0, 0, h)
],
'total_weight': box.weight
}
containers.append(new_container)
return {
'num_containers': len(containers),
'containers': containers,
'utilization': calculate_3d_utilization(containers, L, W, H)
}
def boxes_overlap_3d(x1, y1, z1, l1, w1, h1, x2, y2, z2, l2, w2, h2):
"""Check if two 3D boxes overlap"""
return not (x1 + l1 <= x2 or x2 + l2 <= x1 or
y1 + w1 <= y2 or y2 + w2 <= y1 or
z1 + h1 <= z2 or z2 + h2 <= z1)
def is_dominated(point, existing_points):
"""Check if point is dominated by any existing point"""
for ep in existing_points:
if ep.x <= point.x and ep.y <= point.y and ep.z <= point.z:
if ep.x < point.x or ep.y < point.y or ep.z < point.z:
return True
return False
Metaheuristic Methods
Genetic Algorithm for 3D Packing
import random
import numpy as np
class GeneticAlgorithm3DPacking:
"""
Genetic Algorithm for 3D Bin Packing
Chromosome encodes:
- Item sequence (order to pack)
- Orientation for each item
"""
def __init__(self, items, container_dims,
population_size=50, generations=100,
mutation_rate=0.15, crossover_rate=0.8):
self.items = items
self.container_dims = container_dims
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
Chromosome = (sequence, orientations)
"""
sequence = list(np.random.permutation(self.n_items))
orientations = [random.randint(0, 5) for _ in range(self.n_items)]
return {'sequence': sequence, 'orientations': orientations}
def decode_chromosome(self, chromosome):
"""Decode chromosome to packing solution using BLB"""
ordered_items = [self.items[i] for i in chromosome['sequence']]
# Apply orientations (simplified - just use orientation 0 for now)
result = bottom_left_back_packing(
ordered_items, self.container_dims, allow_rotation=True
)
return result
def fitness(self, chromosome):
"""
Fitness = number of containers (minimize)
Secondary: maximize utilization
"""
solution = self.decode_chromosome(chromosome)
# Minimize bins, maximize utilization
return solution['num_containers'] - solution['utilization'] / 1000
def crossover(self, parent1, parent2):
"""Order crossover for sequence + uniform for orientations"""
if random.random() > self.crossover_rate:
return parent1.copy(), parent2.copy()
# Crossover sequence (OX)
size = len(parent1['sequence'])
cx_point1 = random.randint(0, size - 2)
cx_point2 = random.randint(cx_point1 + 1, size - 1)
child1_seq = [-1] * size
child2_seq = [-1] * size
child1_seq[cx_point1:cx_point2] = parent1['sequence'][cx_point1:cx_point2]
child2_seq[cx_point1:cx_point2] = parent2['sequence'][cx_point1:cx_point2]
self._fill_sequence(child1_seq, parent2['sequence'], cx_point2)
self._fill_sequence(child2_seq, parent1['sequence'], cx_point2)
# Crossover orientations (uniform)
child1_orient = []
child2_orient = []
for i in range(size):
if random.random() < 0.5:
child1_orient.append(parent1['orientations'][i])
child2_orient.append(parent2['orientations'][i])
else:
child1_orient.append(parent2['orientations'][i])
child2_orient.append(parent1['orientations'][i])
return (
{'sequence': child1_seq, 'orientations': child1_orient},
{'sequence': child2_seq, 'orientations': child2_orient}
)
def _fill_sequence(self, child, parent, start_pos):
"""Fill offspring sequence"""
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):
"""
Mutation: swap two items in sequence
and randomly change some orientations
"""
# Swap mutation on sequence
if random.random() < self.mutation_rate:
pos1, pos2 = random.sample(range(self.n_items), 2)
seq = chromosome['sequence']
seq[pos1], seq[pos2] = seq[pos2], seq[pos1]
# Random change on orientations
for i in range(self.n_items):
if random.random() < self.mutation_rate / 2:
chromosome['orientations'][i] = random.randint(0, 5)
return chromosome
def tournament_selection(self, population, fitnesses, tournament_size=3):
"""Tournament selection"""
tournament_idx = random.sample(range(len(population)), tournament_size)
tournament_fit = [fitnesses[i] for i in tournament_idx]
winner_idx = tournament_idx[tournament_fit.index(min(tournament_fit))]
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
min_fit_idx = fitnesses.index(min(fitnesses))
if fitnesses[min_fit_idx] < self.best_fitness:
self.best_fitness = fitnesses[min_fit_idx]
self.best_solution = self.decode_chromosome(population[min_fit_idx])
print(f"Gen {generation}: Best = {self.best_solution['num_containers']} containers")
# New population
new_population = [population[min_fit_idx]] # Elitism
while len(new_population) < self.population_size:
parent1 = self.tournament_selection(population, fitnesses)
parent2 = self.tournament_selection(population, fitnesses)
child1, child2 = self.crossover(parent1, parent2)
child1 = self.mutate(child1)
child2 = self.mutate(child2)
new_population.extend([child1, child2])
population = new_population[:self.population_size]
return self.best_solution
Complete 3D Bin Packing Solver
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
class ThreeDimensionalBinPacker:
"""
Comprehensive 3D Bin Packing Solver
Supports multiple algorithms, visualization, and physical constraints
"""
def __init__(self, container_length, container_width, container_height,
weight_capacity=None):
self.container_dims = (
container_length, container_width, container_height,
weight_capacity if weight_capacity else float('inf')
)
self.items = []
self.solution = None
def add_item(self, length, width, height, weight=0, item_id=None,
stackable=True, fragile=False):
"""Add item to pack"""
if item_id is None:
item_id = f"Item_{len(self.items)}"
box = Box(length, width, height, weight, item_id)
box.stackable = stackable
box.fragile = fragile
self.items.append(box)
def add_items_from_list(self, items_data):
"""
Add multiple items
items_data: list of dicts with keys: length, width, height, weight
"""
for item in items_data:
self.add_item(
item.get('length'),
item.get('width'),
item.get('height'),
item.get('weight', 0),
item.get('id'),
item.get('stackable', True),
item.get('fragile', False)
)
def solve(self, algorithm='blb', **kwargs):
"""
Solve 3D packing problem
Algorithms:
- 'blb': Bottom-Left-Back
- 'layer': Layer Building
- 'extreme_point': Extreme Point
- 'genetic': Genetic Algorithm
"""
if algorithm == 'blb':
self.solution = bottom_left_back_packing(
self.items, self.container_dims,
kwargs.get('allow_rotation', True)
)
elif algorithm == 'layer':
self.solution = layer_building_algorithm(
self.items, self.container_dims
)
elif algorithm == 'extreme_point':
self.solution = extreme_point_algorithm(
self.items, self.container_dims,
kwargs.get('allow_rotation', True)
)
elif algorithm == 'genetic':
ga = GeneticAlgorithm3DPacking(
self.items, self.container_dims,
population_size=kwargs.get('population_size', 50),
generations=kwargs.get('generations', 100)
)
self.solution = ga.solve()
else:
raise ValueError(f"Unknown algorithm: {algorithm}")
return self.solution
def visualize(self, container_index=0, save_path=None):
"""
3D visualization of packing solution
Parameters:
- container_index: which container to visualize
- save_path: path to save figure
"""
if self.solution is None:
raise ValueError("No solution to visualize")
if container_index >= len(self.solution['containers']):
raise ValueError(f"Container index {container_index} out of range")
container = self.solution['containers'][container_index]
L, W, H = self.container_dims[:3]
fig = plt.figure(figsize=(12, 10))
ax = fig.add_subplot(111, projection='3d')
# Draw container boundaries
self._draw_container_box(ax, L, W, H)
# Draw items
colors = plt.cm.tab20(np.linspace(0, 1, 20))
for idx, item in enumerate(container['items']):
pos = item['position']
dims = item['dimensions']
color = colors[idx % 20]
self._draw_box(ax, pos, dims, color, alpha=0.7)
# Add label
center = (
pos[0] + dims[0]/2,
pos[1] + dims[1]/2,
pos[2] + dims[2]/2
)
ax.text(center[0], center[1], center[2],
str(item['box'].item_id),
fontsize=8, ha='center')
ax.set_xlabel('Length')
ax.set_ylabel('Width')
ax.set_zlabel('Height')
ax.set_title(f'Container {container_index + 1}\n'
f'{len(container["items"])} items | '
f'Weight: {container["total_weight"]:.1f}')
# Set equal aspect ratio
max_dim = max(L, W, H)
ax.set_xlim(0, max_dim)
ax.set_ylim(0, max_dim)
ax.set_zlim(0, max_dim)
if save_path:
plt.savefig(save_path, dpi=300, bbox_inches='tight')
plt.show()
def _draw_container_box(self, ax, L, W, H):
"""Draw container boundary wireframe"""
# Define the 8 vertices of the container
vertices = [
[0, 0, 0], [L, 0, 0], [L, W, 0], [0, W, 0], # Bottom
[0, 0, H], [L, 0, H], [L, W, H], [0, W, H] # Top
]
# Define the 12 edges
edges = [
[0, 1], [1, 2], [2, 3], [3, 0], # Bottom
[4, 5], [5, 6], [6, 7], [7, 4], # Top
[0, 4], [1, 5], [2, 6], [3, 7] # Vertical
]
for edge in edges:
points = [vertices[edge[0]], vertices[edge[1]]]
ax.plot3D(*zip(*points), 'k-', linewidth=2)
def _draw_box(self, ax, position, dimensions, color, alpha=0.7):
"""Draw a 3D box"""
x, y, z = position
l, w, h = dimensions
# Define 8 vertices of the box
vertices = np.array([
[x, y, z], [x+l, y, z], [x+l, y+w, z], [x, y+w, z],
[x, y, z+h], [x+l, y, z+h], [x+l, y+w, z+h], [x, y+w, z+h]
])
# Define 6 faces
faces = [
[vertices[0], vertices[1], vertices[5], vertices[4]], # Front
[vertices[2], vertices[3], vertices[7], vertices[6]], # Back
[vertices[0], vertices[3], vertices[7], vertices[4]], # Left
[vertices[1], vertices[2], vertices[6], vertices[5]], # Right
[vertices[0], vertices[1], vertices[2], vertices[3]], # Bottom
[vertices[4], vertices[5], vertices[6], vertices[7]] # Top
]
face_collection = Poly3DCollection(faces,
facecolors=color,
linewidths=1,
edgecolors='black',
alpha=alpha)
ax.add_collection3d(face_collection)
def get_statistics(self):
"""Get detailed statistics"""
if self.solution is None:
return None
L, W, H, max_weight = self.container_dims
total_item_volume = sum(b.volume() for b in self.items)
total_container_volume = self.solution['num_containers'] * L * W * H
stats = {
'num_items': len(self.items),
'num_containers': self.solution['num_containers'],
'container_dims': (L, W, H),
'weight_capacity': max_weight,
'total_item_volume': total_item_volume,
'total_container_volume': total_container_volume,
'utilization': self.solution['utilization'],
'waste': 100 - self.solution['utilization'],
'containers': []
}
for idx, container in enumerate(self.solution['containers']):
container_vol = sum(
item['dimensions'][0] * item['dimensions'][1] * item['dimensions'][2]
for item in container['items']
)
stats['containers'].append({
'container_id': idx,
'num_items': len(container['items']),
'total_weight': container['total_weight'],
'volume_used': container_vol,
'volume_total': L * W * H,
'utilization': (container_vol / (L * W * H) * 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("=" * 70)
print("3D BIN PACKING SOLUTION")
print("=" * 70)
print(f"Items to pack: {stats['num_items']}")
print(f"Container dimensions: {stats['container_dims'][0]} x "
f"{stats['container_dims'][1]} x {stats['container_dims'][2]}")
print(f"Weight capacity: {stats['weight_capacity']}")
print(f"Containers used: {stats['num_containers']}")
print(f"Overall utilization: {stats['utilization']:.2f}%")
print(f"Waste: {stats['waste']:.2f}%")
print()
print("Container Details:")
print("-" * 70)
for c_stat in stats['containers']:
print(f"Container {c_stat['container_id'] + 1}: "
f"{c_stat['num_items']} items | "
f"Weight: {c_stat['total_weight']:.1f} | "
f"Utilization: {c_stat['utilization']:.1f}%")
# Example usage
if __name__ == "__main__":
# Create packer
packer = ThreeDimensionalBinPacker(
container_length=100,
container_width=100,
container_height=100,
weight_capacity=1000
)
# Add items
np.random.seed(42)
items = [
{'length': 40, 'width': 30, 'height': 20, 'weight': 50, 'id': 'A1'},
{'length': 35, 'width': 25, 'height': 30, 'weight': 45, 'id': 'A2'},
{'length': 50, 'width': 40, 'height': 15, 'weight': 60, 'id': 'A3'},
{'length': 25, 'width': 25, 'height': 25, 'weight': 30, 'id': 'A4'},
{'length': 30, 'width': 30, 'height': 40, 'weight': 55, 'id': 'A5'},
{'length': 20, 'width': 20, 'height': 35, 'weight': 25, 'id': 'A6'},
{'length': 45, 'width': 35, 'height': 25, 'weight': 65, 'id': 'A7'},
{'length': 30, 'width': 20, 'height': 30, 'weight': 35, 'id': 'A8'},
]
packer.add_items_from_list(items)
# Solve
print("Solving with Bottom-Left-Back algorithm...")
solution = packer.solve(algorithm='blb', allow_rotation=True)
# Print results
packer.print_solution()
# Visualize
print("\nGenerating visualization...")
packer.visualize(container_index=0)
Tools & Libraries
Python Libraries
py3dbp - 3D Bin Packing Python library
from py3dbp import Packer, Bin, Item
packer = Packer()
# Add bin
packer.add_bin(Bin('container1', 100, 100, 100, 1000))
# Add items
packer.add_item(Item('item1', 50, 40, 30, 50))
packer.add_item(Item('item2', 40, 30, 20, 40))
# Pack
packer.pack()
# Results
for b in packer.bins:
print(f"Bin: {b.name}")
for item in b.items:
print(f" {item.name}: position {item.position}")
binpack3d - Simple 3D packing
OR-Tools - Google optimization tools with 3D packing support
Commercial Software
- Cargo Planner: Container loading software
- EasyCargo: 3D load planning
- LoadPlanner: Truck and container loading
- Pack Manager: Pallet and container optimization
- LoadMaster: Load optimization software
Common Challenges & Solutions
Challenge: Poor Space Utilization (<65%)
Problem:
- Items don't pack efficiently
- Large gaps between items
- Low container fill rate
Solutions:
- Use extreme point algorithm (better than BLB)
- Allow rotation in all 6 orientations
- Apply genetic algorithm for better sequence
- Consider pre-sorting by size ratios
- Group similar-sized items
Challenge: Weight Distribution
Problem:
- Container overweight on one side
- Unstable load
- Axle weight violations
Solutions:
- Add center of gravity constraints
- Layer-building approach (distribute weight per layer)
- Place heavy items at bottom center
- Calculate weight distribution during packing
- Post-optimization balancing step
Challenge: Load Stability
Problem:
- Items fall during transport
- Floating items (no support)
- Top-heavy loads
Solutions:
- Enforce support constraints (items need support from below)
- Limit stacking height based on item strength
- Place fragile items on top
- Add stability score to fitness function
- Require minimum contact area with supporting surface
Challenge: Loading/Unloading Sequence
Problem:
- Need to unload in specific order
- LIFO/FIFO requirements
- Multi-drop delivery
Solutions:
- Incorporate unloading sequence in model
- Zone-based packing (by drop location)
- Last-in-first-out constraint
- Reserve sections per delivery stop
- Sequential packing by route order
Challenge: Mixed Item Sizes
Problem:
- Very large + very small items
- Difficult to pack together efficiently
- Small items fall through gaps
Solutions:
- Pre-cluster small items into groups
- Pack large items first, fill with small
- Use layer approach (separate layers for sizes)
- Consider separate bins for small items
Output Format
3D Packing Report
Executive Summary:
- Items packed: 150 boxes
- Containers used: 3 (40ft containers)
- Average utilization: 82.5%
- Total weight: 18,500 lbs
- Algorithm: Extreme Point + GA
Container Utilization:
| Container | Items | Volume Used | Weight | Utilization | COG Offset |
|---|---|---|---|---|---|
| 1 | 55 | 1,985 ft³ | 6,800 lbs | 87.2% | 2.3 in |
| 2 | 52 | 1,850 ft³ | 6,200 lbs | 81.3% | 1.8 in |
| 3 | 43 | 1,750 ft³ | 5,500 lbs | 76.9% | 3.1 in |
Loading Instructions (Container 1):
Layer 1 (Bottom):
- Items A001-A015: Heavy boxes (50-80 lbs each)
- Placed centered for weight distribution
- Height: 0-24 inches
Layer 2:
- Items B001-B025: Medium boxes (30-50 lbs each)
- Interlocked pattern for stability
- Height: 24-48 inches
Layer 3 (Top):
- Items C001-C015: Light/fragile boxes (<30 lbs each)
- Protected from crushing
- Height: 48-72 inches
Container Count and Bounds:
- Lower bound: max(volume bound, payload bound), and any group that cannot ship whole, with the number that proves it
- Containers in this plan, and the gap to the lower bound
- If the plan uses more than the lower bound: "best found, not proven optimal", unless a proof from Load Planning Rules applies
Group Assignment (when orders must stay together):
| Container | Groups (POs) | Cartons | Volume | Weight | Fill | Spare L / W / H |
|---|---|---|---|---|---|---|
| 1 | PO-A, PO-B, PO-C | 812 | 68.9 m³ | 7,950 kg | 90.3% | 9 cm / 2 cm / 24 cm |
Tolerance: the result of re-checking tight containers with cartons 1-3 mm larger, and a fallback plan if they fail.
Checks Run: placement, containment, overlap, orientation, support, payload.
Item Manifest:
| Item ID | Dimensions (LxWxH) | Weight | Position | Container | Layer |
|---|---|---|---|---|---|
| A001 | 48x40x24 | 75 lbs | (0,0,0) | 1 | 1 |
| A002 | 40x32x20 | 65 lbs | (48,0,0) | 1 | 1 |
Warnings/Notes:
- Container 3 has 23% unused space - consider consolidation
- Item Z005 (fragile) placed on top layer - handle with care
- Center of gravity within acceptable range for all containers
Questions to Ask
If you need more context:
- What are the container dimensions?
- How many items need packing? What are their sizes and weights?
- Can items be rotated freely or are there restrictions?
- Are there weight limits or weight distribution requirements?
- Any stacking restrictions? (fragile items, maximum stack height)
- Is loading/unloading sequence important?
- Multi-drop deliveries requiring specific zones?
- Any irregular-shaped items or all rectangular boxes?
Related Skills
- 2d-bin-packing: For two-dimensional packing problems
- pallet-loading: For pallet-specific loading optimization
- container-loading-optimization: For container logistics
- vehicle-loading-optimization: For truck/vehicle loading
- knapsack-problems: For value-based item selection
- load-building-optimization: For multi-stage load planning
- warehouse-slotting-optimization: For warehouse space optimization