Approaches for the On-Line Three-Dimensional Knapsack Problem with Buffering and Repacking

Abstract

The rapid growth of the e-commerce sector, particularly in Latin America, has highlighted the need for more efficient automated packing and distribution systems. This study presents heuristic algorithms to solve the online three-dimensional knapsack problem (OSKP), incorporating buffering and repacking strategies to optimize space utilization in automated packing environments. These strategies enable the system to handle the stochastic nature of item arrivals and improve container utilization by temporarily storing boxes (buffering) and rearranging already packed boxes (repacking) to enhance packing efficiency. Computational experiments conducted on specialized datasets from the existing literature demonstrate that the proposed heuristics perform comparably to state-of-the-art methodologies. Moreover, physical experiments were conducted on a robotic packing cell to determine the time that buffering and repacking implicate. The contributions of this paper lie in the integration of buffering and repacking into the OSKP, the development of tailored heuristics, and the validation of these heuristics in both simulated and real-world environments. The findings indicate that including buffering and repacking strategies significantly improves space utilization in automated packing systems. However, they significantly increase the time spent packing.

Keywords

• buffering
• repacking
• heuristics
• online packing problem