Online risk-aware pattern adjustment for bin packing problem

The online bin packing problem, as a classic combinatorial optimisation problem, has long garnered attention and found applications across various fields. Recently, prediction-based methods have been employed to enhance online packing algorithms, achieving promising results. However, the online nature inevitably introduces prediction errors. These errors may mislead prediction-based planning, especially under dynamic distributions. Existing methods to mitigate the impact of prediction errors often hybridise with heuristics that have zero knowledge of the problem, which tend to be myopic and fail to fully utilise available information. To address these weaknesses, this paper improves the prediction-based online packing algorithm by dynamically identifying and correcting “risky” patterns that would otherwise be directly adopted. We propose a shadow-price-based method to measure pattern risks that may lead to performance drops. Moreover, this paper presents a strategy to fix risky patterns by solving a Stochastic Multiple Knapsack Problem. Experiments show that the proposed algorithm can enhance the performance of prediction-based online packing algorithms at limited time costs.