A goal-driven approach to the 2D bin packing and variable-sized bin packing problems |
| |
Authors: | Lijun Wei Wee-Chong Oon Wenbin Zhu Andrew Lim |
| |
Institution: | 1. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave., Kowloon Tong, Hong Kong;2. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong;3. School of InfoComm Technology, Ngee Ann Polytechnic, 535 Clementi Road, Singapore 599489, Singapore |
| |
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. |
| |
Keywords: | Packing 2D bin packing Goal-driven search Best-fit heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|