GENPACK: KPI-Guided Multi-Criteria Genetic Algorithm for Industrial 3D Bin Packing

1. Problem Definition

The paper addresses the Three-Dimensional Bin Packing Problem (3D-BPP) within an industrial logistics context. Unlike theoretical formulations that focus solely on minimizing the number of bins or maximizing volume utilization, the industrial version requires solutions that satisfy strict physical and operational constraints:

• Stability & Support: Items must be supported from below (surface support) and laterally (side support) to prevent collapse during transport.
• Balance: The Center of Gravity (CoG) must be centered to prevent tipping.
• Handling Feasibility: Solutions must be deployable on real-world pallets (e.g., Euro-pallets) with specific dimensions and weight limits.
• Scalability: The method must handle heterogeneous orders (varying item sizes and weights) typical of grocery and supply chain operations.

The Gap: Classical constructive heuristics (e.g., MaxRects, Bottom-Left) are fast but often produce unstable or unbalanced packings. Pure Metaheuristics (like Genetic Algorithms) offer flexibility but struggle with scalability, parameter sensitivity, and often fail to encode complex industrial Key Performance Indicators (KPIs) effectively.

2. Methodology: The GENPACK Pipeline

The authors propose GENPACK, a hybrid, three-stage pipeline designed to balance computational efficiency with industrial feasibility.

Stage 1: Constructive Initialization

• Approach: Uses constructive heuristics (specifically MaxRects) to rapidly generate an initial packing solution.
• Superitems: To reduce the search space, similar items are grouped into "superitems" (single, horizontal, or vertical stacks) before placement.
• Outcome: This stage packs a subset of items efficiently, leaving a set of residual items that the heuristic failed to place.

Stage 2: KPI-Guided Genetic Algorithm (GA)

The core innovation lies in the GA, which focuses exclusively on refining the residual items and optimizing the overall structure.

• Chromosome Representation: Uses a layer-based encoding. A chromosome is an ordered list of layers, where each layer contains items, their 2D coordinates, and height. This naturally enforces vertical stacking constraints.
• Fitness Function (Scalarized KPIs): Instead of a simple volume metric, the fitness function aggregates seven industrial KPIs into a single scalar score:
  1. Coverage: Percentage of residual items successfully packed.
  2. AbsDen (Absolute Density): Volume utilization within the used height.
  3. RelDen (Relative Density): Measures void reduction below the "upper envelope" of the stack.
  4. SideSup (Lateral Support): Fraction of vertical faces supported by neighbors (threshold >20%).
  5. SurfSup (Surface Support): Fraction of items with >75% base overlap with the layer below.
  6. TallItem: Penalty for tall, slender items placed off-center or high up.
  7. CoG2D: Balance of the Center of Gravity in the horizontal plane.
• Evolutionary Operators:
  • Selection: Tournament selection with adaptive pressure (increasing over generations).
  • Crossover: One-point crossover with layer preservation to maintain feasibility.
  • Mutation: Specialized operators aligned with specific KPIs (e.g., shifting tall items to the center to improve CoG, filling voids to improve density).
• Adaptive Scheduling: Crossover and mutation probabilities are dynamically adjusted to favor exploration early and exploitation later.

Stage 3: Post-Processing

• Directional Compaction: Iteratively shifts items toward the pallet origin to minimize voids.
• Fallback Placement: Attempts to place any remaining unplaced items using coarse grid searches and rotation.
• Validation: Removes overlapping items or those failing minimum support thresholds to ensure the final solution is 100% feasible.

3. Key Contributions

1. Hybrid Pipeline: A novel architecture combining fast constructive heuristics for initialization with GA-based refinement for residuals, solving the scalability issue of pure GAs.
2. KPI-Guided Fitness: A multi-criteria objective function that explicitly optimizes for industrial safety (stability, balance, support) rather than just volume.
3. Layer-Based Chromosome: A domain-specific encoding that preserves geometric feasibility during genetic operations.
4. Specialized Operators: Mutation and crossover strategies specifically designed to target industrial KPIs (e.g., improving lateral support or centering the CoG).
5. Real-World Benchmarking: Extensive evaluation on the BED-BPP dataset (1,500 real-world grocery orders), moving beyond synthetic benchmarks.

4. Experimental Results

The method was evaluated against classical heuristics (MaxRects, Extreme Point), learning-based methods (O3D-BPP-PCT, GOPT), and other industrial solvers (Sisyphus) on 1,500 orders.

• Space Utilization: GENPACK achieved up to 35% higher space utilization compared to heuristic baselines.
• Stability & Support:
  • Surface Support: Improved by 15–20% compared to baselines, crucial for preventing stack collapse.
  • Balance: Achieved the best Center of Gravity (CoG) alignment scores with the lowest variance.
• Robustness: GENPACK showed significantly lower variance across diverse order sizes compared to Deep Reinforcement Learning (DRL) methods, which exhibited high unpredictability.
• Runtime Trade-off:
  • Heuristics: ~0.02s – 14s.
  • DRL: ~0.25s – 2.8s.
  • GENPACK (+PP): ~29.2s (mean).
  • Significance: While slower, the runtime is acceptable for batch processing in warehouse operations where solution quality and safety outweigh millisecond latency.

5. Significance and Conclusion

The paper demonstrates that industrial 3D bin packing cannot be solved by speed or volume optimization alone. Pure heuristics fail on safety constraints, and pure learning-based methods struggle with generalization and constraint satisfaction on real-world data.

GENPACK successfully bridges this gap by:

• Prioritizing deployability (stability, balance) over raw speed.
• Providing a reproducible, KPI-driven framework that can be tuned for specific operational needs (e.g., prioritizing side support for fragile goods).
• Proving that a hybrid approach (Heuristic + GA + Post-processing) is the most effective strategy for heterogeneous, real-world palletization, yielding solutions that are safer, more balanced, and more space-efficient than current state-of-the-art methods.

The authors conclude that while the computational cost is higher, the resulting reduction in handling risks and improvement in downstream logistics efficiency make GENPACK a viable and superior solution for industrial deployment.