A hybrid heuristic algorithm for the 2D variable-sized bin packing problem |
| |
Authors: | Shaohui Hong Defu Zhang Hoong Chuin Lau XiangXiang Zeng Yain-Whar Si |
| |
Institution: | 1. Department of Computer Science, Xiamen University, Xiamen 361005, China;2. School of Information Systems, Singapore Management University, Singapore;3. Department of Computer and Information Science, University of Macau, Macau |
| |
Abstract: | In this paper, we consider the two-dimensional variable-sized bin packing problem (2DVSBPP) with guillotine constraint. 2DVSBPP is a well-known NP-hard optimization problem which has several real applications. A mixed bin packing algorithm (MixPacking) which combines a heuristic packing algorithm with the Best Fit algorithm is proposed to solve the single bin problem, and then a backtracking algorithm which embeds MixPacking is developed to solve the 2DVSBPP. A hybrid heuristic algorithm based on iterative simulated annealing and binary search (named HHA) is then developed to further improve the results of our Backtracking algorithm. Computational experiments on the benchmark instances for 2DVSBPP show that HHA has achieved good results and outperforms existing algorithms. |
| |
Keywords: | Packing Guillotine constraint Simulated annealing Heuristic |
本文献已被 ScienceDirect 等数据库收录! |