A goal-driven approach to the 2D bin packing and variable-sized bin packing problems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

17 Scopus Citations
View graph of relations

Author(s)

  • Lijun Wei
  • Wee-Chong Oon
  • Wenbin Zhu
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)110-121
Journal / PublicationEuropean Journal of Operational Research
Volume224
Issue number1
Publication statusPublished - 1 Jan 2013

Abstract

In this paper, we examine the two-dimensional variable-sized bin packing problem (2DVSBPP), where the task is to pack all given rectangles into bins of various sizes such that the total area of the used bins is minimized. We partition the search space of the 2DVSBPP into sets and impose an order on the sets, and then use a goal-driven approach to take advantage of the special structure of this partitioned solution space. Since the 2DVSBPP is a generalization of the two-dimensional bin packing problem (2DBPP), our approach can be adapted to the 2DBPP with minimal changes. Computational experiments on the standard benchmark data for both the 2DVSBPP and 2DBPP shows that our approach is more effective than existing approaches in literature. © 2012 Elsevier B.V. All rights reserved.

Research Area(s)

  • 2D bin packing, Best-fit heuristic, Goal-driven search, Packing

Citation Format(s)

A goal-driven approach to the 2D bin packing and variable-sized bin packing problems. / Wei, Lijun; Oon, Wee-Chong; Zhu, Wenbin; Lim, Andrew.

In: European Journal of Operational Research, Vol. 224, No. 1, 01.01.2013, p. 110-121.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal