Deep Reinforcement Learning for Generalizable Multi-Knapsack Optimization in Retail Packaging

Abstract

Classical metaheuristics such as Particle Swarm Optimization (PSO), Genetic Algorithm (GA), and Simulated Annealing (SA) achieve high solution quality for the Multi-Constraint Multi-Knapsack Parcel Optimization Problem (MCMKPOP) but require full re-optimization whenever bin configurations change, making them impractical for dynamic retail environments. This paper proposes a deep reinforcement learning framework based on Proximal Policy Optimization (PPO) that maximizes total retail price across all bins subject to simultaneous budget and weight constraints, with three key architectural components: action masking to enforce feasibility, a shaped dense reward function to guide item-selection behavior at each step, and categorical feature embeddings to encode semantic product attributes. The agent is trained once on a fixed set of bin configurations and applied to unseen configurations without retraining. Experiments use a real-world dataset of 1,733 retail items collected from 18 Indonesian souvenir stores, allocated across 10 heterogeneous bins. On the training configuration, PPO achieves 99.68% of the total budget capacity (4,000,000 IDR), within 0.31 percentage points of SA and PSO, while requiring 0.30 seconds per inference compared to 82.26 seconds for SA and 45.99 seconds for PSO. Generalization experiments across 21 unseen bin configurations show a mean quality advantage of 0.43 percentage points over PSO re-optimization with a mean speedup of 24.5 times. An ablation study with Bonferroni-corrected Wilcoxon signed-rank tests confirms that action masking is indispensable (removal causes a 99.12 percentage point collapse), shaped reward contributes 1.28 percentage points, and categorical embeddings provide a statistically significant improvement of 0.12 percentage points (p < 0.001). These findings demonstrate that PPO can serve as a practical, generalizable solver for constrained multi-knapsack problems by trading a small quality margin for orders-of-magnitude reduction in deploymenttime computation.