Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems

Zhang, Zhaoyi; Guo, Songshan; Zhu, Wenbin; Oon, Wee-Chong; Lim, Andrew

doi:10.5591/978-1-57735-516-8/IJCAI11-123

Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems

Zhaoyi Zhang, Songshan Guo, Wenbin Zhu, Wee-Chong Oon, Andrew Lim

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 699-703.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123

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 on the two- and three-dimensional Bin Packing Problems. In conjunction with a bin shuffling strategy for incremental improvement, our resultant algorithm outperforms all leading meta-heuristic approaches.

Zhaoyi Zhang, Songshan Guo, Wenbin Zhu, Wee-Chong Oon, and Andrew Lim. 2011. Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 699–703. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123

@inproceedings{ijcai2011p123,
  title     = {Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems},
  author    = {Zhang, Zhaoyi and Guo, Songshan and Zhu, Wenbin and Oon, Wee-Chong and Lim, Andrew},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {699--703},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-123},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123},
}

TY  - CPAPER
TI  - Space Defragmentation Heuristic for 2D and 3D Bin Packing Problems
AU  - Zhang, Zhaoyi
AU  - Guo, Songshan
AU  - Zhu, Wenbin
AU  - Oon, Wee-Chong
AU  - Lim, Andrew
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 699
EP  - 703
DO  - 10.5591/978-1-57735-516-8/IJCAI11-123
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123
ER  -