kishorkukreja/awesome-supply-chain/3d-bin-packing

3D Bin Packing

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 --allocation it plans first, then advises on that plan. Pass --allocation (columns po,container) to advise on a plan the user already has, for example one from another load planner.
• --objective volume is the default and fills the most cubic metres. cartons maximises the number of extra cartons. value needs value_per_carton in the limits file.
• limits.csv (columns po,sku, plus optional max_extra, multiple and value_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.csv as 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:

1. Problem Objectives

• Minimize number of containers/bins used?
• Maximize utilization of fixed containers?
• Minimize shipping costs?
• Ensure load stability?

1. 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?)

1. Container Specifications

• Container dimensions: L x W x H
• Weight capacity limit?
• Multiple container types available?
• Unlimited containers or fixed quantity?

1. 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)?

1. 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:

1. Non-overlap: No two items in same bin overlap
2. Containment: All items fit within bin boundaries
3. Support: Items have adequate support from below
4. Weight: Total weight ≤ capacity
5. 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