Geometry-Aware Tabu Search for Online Two-Dimensional Rectangular Bin Packing

Abstract

In the online two-dimensional rectangular bin packing problem (O-2DRBPP), items arrive sequentially and must be placed immediately without knowledge of future arrivals. Traditional online heuristics frequently fail because their shortsighted focus on immediate space utilization severely fragments the residual free space, constraining future placements. To overcome this limitation, we propose a Geometry-Aware Tabu Search (GTabu) algorithm that explicitly evaluates and preserves the geometric quality of leftover space. By integrating a fragmentation-aware objective function with geometry-sensitive scoring mechanisms, GTabu actively penalizes space splintering and consolidates unallocated area into large, contiguous rectangular regions. We evaluate GTabu against a First-Fit baseline across fully reproducible experimental setups featuring  bins and item dimensions sampled uniformly from . Testing incorporates deterministic single-stream instances under moderate demand ( ) and high multi-bin demand ( ), as well as a large-scale Monte Carlo benchmark across  independent stream realizations generated using NumPy’s default random generator (PCG64). The numerical results demonstrate that GTabu produces substantially more organized layouts, achieving an average reduction of  residual free regions and increasing the average contiguous open rectangle by  over First-Fit, while maintaining real-time decision speeds (   per item).