The evolution of rectangular bin packing problem—A review of research topics, applications, and cited papers

Abstract

Bin packing problem (BPP) is one of the fastest-growing research issues within the field of combinatorial optimization. Over the last years, several studies carried out various BPP variants, mathematical models, and proposed methods to the BPPs. The classical BPP consists of packing a set of rectangular items in a minimum number of rectangular bins while respecting some constraints. Throughout the years, an improved typology was introduced by Wäscher et al. (2007), providing an excellent instrument for the organization and categorization criteria that defined the problem categories different from those of Dyckhoff (1990). Several early literature reviews have been conducted on various aspects of related packing problem variants. The contribution of this paper is to provide a comprehensive and refined taxonomy intended for BPPs. In addition to that, it is an up-to-date review based on a chronological taxonomy of the literature and depicts further research horizons. This systematic review allowed us to identify other characteristics and constraints, based on Wäscher’s original ideas, mainly distinguished according to real cases studies. The detailed analysis provides a valuable framework for understanding the research gaps for future studies that should be acknowledged while proposing and solving new extensions.

Boukthir Haddar

Assistant professor

Boukthir HADDAR is an assistant professor of computer science at National School of Electronics and Telecommunications of Sfax - Tunisia. His research interests include decision aid algorithms, optimization, linear programming and artificial intelligence.