The 2-D Orthogonal Packing Problem with Multiple Levels of Prioritization: A Spatial Optimization Perspective

Abstract

This paper addresses two-dimensional orthogonal packing within a confined space, integrating bin packing principles with facility layout concepts to address scenarios in which items must not only fit but also be arranged according to spatial priorities. We embed a prioritization matrix into the bin packing framework, enabling items to be clustered with one another or pulled toward certain bin access points based on assigned priority weights. Unlike traditional bin packing, which focuses on space utilization alone, our approach balances proximity to bin access points and adjacency among functionally related items, extending the utility of bin packing to applications requiring more nuanced layout preferences.

We introduce a single mixed-integer linear programming (MILP) model and a complemen- tary sliding-window matheuristic that scales effectively to larger problem instances. Numerical experiments illustrate that this matheuristic approach consistently outperforms a direct MILP solve with a commercial solver in both runtime and solution quality, and also performs best among the adapted heuristic and metaheuristic alternatives considered in our study. This computational study underscores the flexibility and effectiveness of embedding multi-level priorities into orthogonal packing.