Shipping Packaging Algorithm

Last updated: February 20, 2026
Scope: Shipping::DeterminePackaging, Shipping::PackingCalculator, Item::ShippingBoxCalculator, Shipping::BoxCatalog, Packing model, Shipping::Md5HashItem, Shipping::PackagingImporter

---

Overview

The packaging system answers one question at shipment time:

Given these line items and this origin warehouse, what boxes do we ship them in?

It does so in two layers:

1. History lookup — check the packings table for a known solution that exactly matches (or contains) the order’s item fingerprint.
2. 3D bin packing — if no history exists and every item has complete shipping dimensions, compute a fresh multi-box solution using a First-Fit-Decreasing algorithm constrained to real warehouse box stock.

The result is a Shipping::PackingSolution carrying one or more Shipping::Container objects that downstream services (rate quoting, label generation, invoice insurance) consume to obtain box dimensions, weight, and billable weight.

---

Entry Point: Shipping::DeterminePackaging

File: app/services/shipping/determine_packaging.rb

Called from:

• Concerns::Models::ShipQuotable#retrieve_shipping_costs — at rate-quote time
• Shipment#packed_or_pre_packed? — to show the CRM pre-pack badge (with skip_calculator: true to avoid heavy computation on page render)

Signature

Shipping::DeterminePackaging.new.process(
  delivery:,
  md5_hash_override: nil,   # for testing/manual override
  store_id:          nil,   # reserved
  is_freight:        false, # routes to freight pallet logic instead
  skip_calculator:   false  # skip 3D packing and history fallback on UI paths
)
# => Shipping::PackingSolution

Resolution Order

packings table
    └─ exact MD5 match            ─→ return packing
    └─ exact relevant-MD5 match   ─→ return packing
    └─ nested-MD5 match           ─→ return subset of packing
    └─ no match
          ├─ multibox order (TBS-KIT, ships_in_single_box? == false)
          │    └─ individual per-item packing histories
          └─ single-origin order
               ├─ PackingCalculator (parcel, all dims present)
               ├─ individual per-item packing histories (fallback)
               └─ freight pallet calc (freight only)

Multibox vs. single-box paths

If any goods item !ships_in_single_box? (e.g. multi-box kit products), the order takes the multibox path:

• item_hash is built from packable_active_parent_lines_only
• The MD5 fingerprint covers kit-parent line items only
• On no match: tries get_individual_packings (one Packing per item)

Otherwise (most orders), the single-box path runs:

• item_hash is built from packable_active_lines (preloads :item, :catalog_item, parent: :catalog_item to avoid N+1)
• MD5 covers all packable goods line items after kit explosion
• On no match: PackingCalculator first, per-item histories second

---

MD5 Fingerprinting: Shipping::Md5HashItem

File: app/services/shipping/md5_hash_item.rb

Before querying the packings table, the order’s items are reduced to a deterministic string, then MD5-hashed. Two hashes are produced:

Hash	Contents
md5	All goods item IDs + quantities after kit explosion
relevant_md5	Same, but items contributing < 0.5% of total volume and < 0.2% of total weight are dropped

This allows a packing record learned from a large order to still be reused for the same order with trivially small add-on items.

Kit explosion is handled by Shipping::ItemKitExploder: kit parent IDs are replaced by their component item IDs and quantities so that two orders with the same physical items — one ordered as a kit, one as loose components — get the same fingerprint.

---

History Database: Packing Model

File: app/models/packing.rb
Table: packings

Schema

Column	Type	Purpose
md5	string(32), unique+service_type	Primary lookup key
relevant_md5	string	Secondary lookup key (ignores tiny items)
service_type	enum	parcel_service / freight_service
origin	enum	from_delivery, from_shipment, from_item, from_manual_entry
packdims	decimal[]	Array of [L, W, H, Weight, ContainerType] 5-tuples (one per box)
contents	jsonb	{ item_id => quantity } per box (single-box) or array of hashes (multi-box)
packdim_contents	jsonb	Denormalized combination of packdims + contents + per-box md5; enables nested-md5 matching
delivery_id	FK	Source delivery (if origin == from_delivery)
shipment_id	FK	Source shipment (if origin == from_shipment)
item_id	FK	Source item (if origin == from_item)

Origin precedence

from_delivery > from_shipment > from_manual_entry > from_item

Records derived from a real completed delivery are the most authoritative. The PackagingImporter and ItemMd5Extractor seed lower-priority records that are overwritten if a real shipment record arrives.

Nested-MD5 matching

The packdim_contents JSONB column is GIN-indexed. Each element stores the per-box item MD5, enabling a “does this exact item combination appear inside a larger multi-box packing?” query:

SELECT * FROM packings
WHERE packdim_contents @> '[{"md5": "<target_md5>"}]'

This allows a 5-box packing to satisfy a request for 1 box whose items are a strict subset of one of those boxes.

---

3D Bin Packing: Shipping::PackingCalculator

File: app/services/shipping/packing_calculator.rb

Called when no packing history exists and all goods items have complete shipping dimensions. Returns an array of Shipping::Container objects.

Algorithm: First-Fit-Decreasing

1. Expand each line item into individual Unit structs (one per unit of quantity), sorting by volume descending (largest first).
2. For each unit, find the first open bin that passes all guards (see below). If none fits, open a new bin.
3. Convert each bin to a Shipping::Container by snapping to the smallest valid real warehouse box.

Bin acceptance guards (all must pass)

fits_in_bin?(bin, unit)

Guard	Description
Bounding-box (O(n))	Each axis of the candidate bin must stay within MAX_SIDE (106”). Cheap early reject.
3D geometry	Item::ShippingBoxCalculator confirms all items actually fit in the snapped catalog box (guillotine-cut packer).
Surcharge escalation	Reject merge if the combined box incurs more carrier surcharges than either party would have separately. Score = count of dimension-based fees; see BoxCatalog.surcharge_score.
Dim-weight escalation	Reject merge if dim_billable_weight(combined_box) > dim_billable_weight(unit) + dim_billable_weight(bin) + BOX_CONSOLIDATION_BENEFIT. The credit (BOX_CONSOLIDATION_BENEFIT) represents the fixed per-box carrier overhead that is saved when two items share a box (residential surcharge, DAS, fuel on fixed fees — empirically ~$13–16/box at ~$2.72/lb → 8 lbs equivalent). Without this credit, the guard would incorrectly split items whose combined dim-weight increase is smaller than the per-box savings.

BOX_CONSOLIDATION_BENEFIT

BOX_CONSOLIDATION_BENEFIT = 8 (lbs) — the dim-weight credit allowed per consolidation decision. Derived empirically from 808 historical FedEx Ground residential shipments:

• Median effective per-lb rate (recent): $2.72/lb
• Per-box fixed overhead (residential delivery + DAS + fuel): ~$13–16/box
• Break-even: $14 / $2.72 ≈ 5 lbs; conservative value → 8 lbs

Zone sensitivity: At zone 1 (≤ 1-day FedEx Ground, e.g. local customers), the per-lb rate drops to ~$0.50–0.80/lb while per-box overhead stays ~$15–18. The break-even rises to ~20–30 lbs. The constant is calibrated for the typical zone 4–7 customer; zone 1 customers are better served by regional carriers (Speede Delivery, UPS Ground) where per-box fees are not additive in the same way.

Validated boundary conditions:

Scenario	Escalation	Result
mat roll (41×7×7, 15 lbs dw) + cable (37×3×2, 2 lbs dw) → 41×9×9 (24 lbs dw)	24 − 17 = 7 ≤ 8	ALLOW ✓
mat roll (41×7×7) + flex roll (19×4×4) → 41×11×11 (36 lbs dw)	36 − 19 = 17 > 8	REJECT ✓
two mat rolls → 44×16×16 (81 lbs dw)	81 − 30 = 51 > 8	REJECT ✓

Weight limit

PER_BOX_WEIGHT_LIMIT = 70 lbs (from Packaging::PER_PACKAGE_WEIGHT_LIMIT). A unit is rejected from a bin when bin.total_weight + unit.weight > 70.

Dimensional-weight divisor

DIM_WEIGHT_DIVISOR = 139 cu-in/lb. This is the FedEx/UPS/Purolator Ground standard. Used to compute billable weight for the dim-weight escalation guard.

Box snapping: catalog_box_for

def catalog_box_for(dims)
  Item::ShippingBoxCalculator.call(dims, candidate_boxes: @catalog, padding: 0) ||
    Item::ShippingBoxCalculator.call(dims)
end

Tries the warehouse catalog first (O(n)) with padding: 0 because the 2” carrier padding is already baked into the catalog box outer dimensions — adding it again would cause the calculator to search for a box 2” larger than necessary, potentially skipping the correct (tight-fitting) box. Falls back to the mathematical minimum-waste search (O(n³)) only when no catalog box fits. The fallback is rare and limited to unusual item combinations outside warehouse stock.

---

Box Geometry: Item::ShippingBoxCalculator

File: app/services/item/shipping_box_calculator.rb

Answers: What is the smallest valid box that holds this set of item shipping dimensions?

Returns [length, width, height] in descending order, or nil if no valid box exists.

Carrier constraints encoded

Constant	Value	Description
CARRIER_PADDING	2”	Added to each dimension; standard carrier air-gap requirement
MAX_SIDE	106” (pre-padding) → 108” outer	Absolute FedEx/UPS maximum single dimension
MAX_GIRTH	165”	UPS/USPS: length + 2×(width + height)
LONG_THRESHOLD	46”	> 46” triggers length-based carrier surcharge
WIDE_THRESHOLD	34”	> 34” triggers width-based carrier surcharge
GIRTH_THRESHOLD	130”	> 130” combined girth triggers large-package surcharge
PENALTY	1.5×	Score multiplier applied to boxes exceeding a surcharge threshold

Catalog mode (candidate_boxes:)

When PackingCalculator passes the warehouse catalog, ShippingBoxCalculator iterates boxes smallest-surcharge-first and returns the first one whose inner space (outer dims − 2” carrier padding) passes the 3D feasibility check.

Mathematical mode (no candidate_boxes:)

Full O(n³) search over (min_l..106) × (min_w..106) × (h_floor..106) space. A min_score = (box_volume − item_volume) × surcharge_penalty_factors ensures the result has the least waste while avoiding surcharge-triggering sizes. Used as a fallback only when the catalog search returns nil.

3D feasibility: guillotine-cut bin packer (can_pack?)

1. Start with one free space = the full box interior.
2. Sort items largest-volume-first (FFD).
3. For each item, find the smallest free space it fits in (any rotation).
4. Delete that space; split remainder into up to three non-overlapping guillotine sub-spaces (right, front, above).
5. Return false if any item cannot be placed.

The space list is mutated by value (spaces.delete(space)) — not by index — to avoid off-by-one errors when iterating a sorted view of the array.

---

Warehouse Box Catalog: Shipping::BoxCatalog

File: app/services/shipping/box_catalog.rb

Provides an ordered list of real carton sizes stocked in each warehouse, sorted to minimise carrier surcharges and dimensional weight.

Sources

1. US_STANDARD_BOXES / CA_STANDARD_BOXES — empirically derived from ~58,000 authoritative packing records (from_delivery / from_shipment) in production, split by origin warehouse address. Only sizes used ≥ 50 times are included. Refreshed from production data in February 2026.

2. WarehousePackage table — supplements the standard list with any carton sizes added to the DB but not yet in the hard-coded arrays.

Sort order

1. surcharge_score (ascending)   → fewest carrier fees first
2. volume (ascending)            → smallest dim-weight within each tier
3. longest dimension (ascending) → avoid length-based fees as tiebreaker

Surcharge scoring: BoxCatalog.surcharge_score(dims, country:)

Returns an integer 0–4 counting avoidable dimension-based carrier fees. Carrier-mix-aware:

Condition	US (FedEx 73% + UPS 15%)	CA (UPS 46% + Canpar 35% + Purolator 9% + CP 10%)
length > 48”	+1	+1
width > 30”	+1	+1
L+G > 130”	+1	+1 (Purolator large-pkg fee = $65, most expensive)
cubic > 17,280 cu-in	+1 (FedEx cubic)	(skipped — FedEx only 5% of CA)

Catalog boxes are annotated in US_STANDARD_BOXES / CA_STANDARD_BOXES when they exceed the width or L+G thresholds (e.g. [37, 31, 6] — width=31).

Caching

parcel_boxes is memoized per process in @us_parcel_boxes / @ca_parcel_boxes. Call Shipping::BoxCatalog.reset! in tests or after refreshing warehouse inventory.

---

Legacy Data Migration: Shipping::PackagingImporter

File: app/services/shipping/packaging_importer.rb

The legacy Packaging model stored warehouse-specific stacking rules: “N units of StoreItem X fit in WarehousePackage Y”. These records encode knowledge that cannot be derived purely from per-item shipping dimensions (e.g. 25 thermal sheets stacked flat in a 36×24×3 box).

PackagingImporter.process converts each multi-item Packaging record into one or more Packing records with origin: :from_item:

• Single-box tier: qty = 1…N (representative subset when N > 50)
• Multi-box tier: qty = 2N, 3N, 4N, 5N

Delivery-derived records (from_delivery, from_shipment) are never overwritten — they are authoritative. Item-derived records (from_item) are re-seeded on each importer run (idempotent via upsert).

---

UI Integration: Shipment#packed_or_pre_packed?

File: app/models/shipment.rb

Controls whether the CRM order page shows the pre-pack badge.

def packed_or_pre_packed?
  return true if packed?

  if suggested?
    packing_solution = Shipping::DeterminePackaging.new.process(
      delivery:,
      is_freight: delivery.ships_ltl_freight?,
      skip_calculator: true          # ← avoids running PackingCalculator on render
    )
    # Only history-backed solutions qualify for the badge
    %w[from_delivery from_item from_manual_entry].include?(packing_solution.source_type.to_s)
  end
end

skip_calculator: true is critical: without it, every order page render that lacks a packing history record would run the full 3D bin packing algorithm (~10ms of CPU per call, ×2 per page load = 20ms extra, and previously up to 7.5s when the mathematical fallback ran unconditionally).

---

Performance Characteristics

Code path	Typical query count	CPU
History hit (MD5 exact match)	4–6 SELECT	< 1 ms
History miss → PackingCalculator (catalog only)	6–8 SELECT + 1 WarehousePackage load	~10 ms
History miss → PackingCalculator (math fallback triggered)	same + O(n³) geometry	~50–200 ms
packed_or_pre_packed? with skip_calculator: true	4–6 SELECT	< 1 ms

N+1 hotspots addressed

The packaging flow touches several association chains that are N+1-prone. Key preloads in place:

Location	Associations preloaded	Reason
DeterminePackaging#process line 7	[:item, :direct_store_item, { catalog_item: :store_item }] on parent_lines	pack_at_kit_level, ships_in_single_box? checks
Delivery#packable_active_lines	:item, :catalog_item, parent: :catalog_item	active_lines_for_packaging checks catalog_item.pack_at_kit_level and parent.catalog_item.pack_at_kit_level
Delivery#calculate_declared_value	item: { supplier_items: :supplier_item_prices }	unit_value_for_commercial_invoice

---

Data Flow Diagram

Order / Delivery
      │
      ▼
Shipping::DeterminePackaging#process
      │
      ├─ 1. Build item_hash from packable line items
      │       │
      │       ▼
      │  Shipping::Md5HashItem ──→ md5, relevant_md5
      │
      ├─ 2. Query packings table (4 SELECT attempts)
      │       │
      │       ├─ exact md5           ─→  Packing#to_packages  ─→ PackingSolution
      │       ├─ relevant_md5        ─→  Packing#to_packages  ─→ PackingSolution
      │       ├─ nested md5          ─→  Packing#to_packages(md5) ─→ PackingSolution
      │       └─ nested relevant_md5 ─→  same
      │
      └─ 3. No history → PackingCalculator (parcel, skip_calculator=false)
                │
                ├─ BoxCatalog.parcel_boxes(country: :us/:ca)
                │       ├─ US_STANDARD_BOXES / CA_STANDARD_BOXES (hard-coded, ~58k packing history)
                │       └─ WarehousePackage.active (DB supplement)
                │
                ├─ Expand items × quantity → Units (sorted vol desc)
                │
                └─ FFD bin packing loop
                        │
                        ├─ fits_in_bin?(bin, unit)
                        │       ├─ Bounding-box guard (O(n))
                        │       ├─ Item::ShippingBoxCalculator  ← catalog first, math fallback
                        │       │       └─ can_pack?(l,w,h)  ← guillotine-cut 3D packer
                        │       ├─ Surcharge-escalation guard
                        │       └─ Dim-weight escalation guard
                        │
                        └─ build_container(bin) → Shipping::Container

---

Key Constants Quick Reference

Constant	Value	File	Meaning
PER_BOX_WEIGHT_LIMIT	70 lbs	packing_calculator.rb	Max weight per parcel box
DIM_WEIGHT_DIVISOR	139 cu-in/lb	packing_calculator.rb	FedEx/UPS/Purolator Ground dim-weight standard
BOX_CONSOLIDATION_BENEFIT	8 lbs	packing_calculator.rb	Per-box fixed overhead credit used in the dim-weight escalation guard. Empirically derived from 808 FedEx Ground shipments (~$14 fixed overhead / $2.72 per-lb rate ≈ 5 lbs break-even; conservative → 8 lbs).
CARRIER_PADDING	2”	shipping_box_calculator.rb	Minimum air gap on each side
MAX_SIDE	108” (106 + 2)	shipping_box_calculator.rb	Absolute carrier max single dimension
MAX_GIRTH	165”	shipping_box_calculator.rb	UPS/USPS L + 2(W+H) limit
HANDLING_LENGTH	48”	box_catalog.rb	FedEx/UPS additional-handling length threshold
HANDLING_WIDTH	30”	box_catalog.rb	FedEx/UPS additional-handling width threshold
LARGE_PKG_LG	130”	box_catalog.rb	Large-package surcharge L+G threshold
FEDEX_CUBIC_OS	17,280 cu-in	box_catalog.rb	FedEx cubic-oversize threshold (US only)