Space defragmentation for packing problems |
| |
Authors: | Wenbin Zhu Zhaoyi Zhang Wee-Chong Oon Andrew Lim |
| |
Institution: | 1. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong;2. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong;3. Department of Logistics and Maritime Studies, Faculty of Business, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;4. Department of Computer Science, School of Information Science and Technology, Zhong Shan (Sun Yat-Sen) University, Guangzhou, Guangdong, PR China |
| |
Abstract: | One of main difficulties of multi-dimensional packing problems is the fragmentation of free space into several unusable small parts after a few items are packed. This study proposes a defragmentation technique to combine the fragmented space into a continuous usable space, which potentially allows the packing of additional items. We illustrate the effectiveness of this technique using the two- and three-dimensional bin packing problem, where the aim is to load all given items (represented by rectangular boxes) into the minimum number of identical bins. Experimental results based on well-known 2D and 3D bin packing data sets show that our defragmentation technique alone is able to produce solutions approaching the quality of considerably more complex meta-heuristic approaches for the problem. In conjunction with a bin shuffling strategy for incremental improvement, our resultant algorithm outperforms all leading meta-heuristic approaches based on the commonly used benchmark data by a significant margin. |
| |
Keywords: | Packing 2D/3D bin packing Space defragmentation Bin shuffling Comparability graph Visibility graph |
本文献已被 ScienceDirect 等数据库收录! |
|