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)