Space defragmentation heuristic for 2D and 3D bin packing problems

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

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

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

13 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence
Publisher	AAAI Press/International Joint Conferences on Artificial Intelligence
Pages	699-704
Volume	1
ISBN (Electronic)	978-1-57735-516-8
ISBN (Print)	978-1-57735-513-7
DOIs	https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123
Publication status	Published - Jul 2011
Event	22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 - Barcelona, Catalonia, Spain Duration: 16 Jul 2011 → 22 Jul 2011

Conference

Conference	22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Place	Spain
City	Barcelona, Catalonia
Period	16/07/11 → 22/07/11

Access Output

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

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{2326a814e33646a88ac3b25ebc94637e,

title = "Space defragmentation heuristic for 2D and 3D bin packing problems",

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.",

author = "Zhaoyi Zhang and Songshan Guo and Wenbin Zhu and Wee-Chong Oon and Andrew Lim",

year = "2011",

month = jul,

doi = "10.5591/978-1-57735-516-8/IJCAI11-123",

language = "English",

isbn = "978-1-57735-513-7",

volume = "1",

pages = "699--704",

booktitle = "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence",

publisher = "AAAI Press/International Joint Conferences on Artificial Intelligence",

note = "22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 ; Conference date: 16-07-2011 Through 22-07-2011",

}

Zhang, Z, Guo, S, Zhu, W, Oon, W-C & Lim, A 2011, Space defragmentation heuristic for 2D and 3D bin packing problems. in Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. vol. 1, AAAI Press/International Joint Conferences on Artificial Intelligence, pp. 699-704, 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, Barcelona, Catalonia, Spain, 16/07/11. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-123

Space defragmentation heuristic for 2D and 3D bin packing problems. / Zhang, Zhaoyi; Guo, Songshan; Zhu, Wenbin et al.
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Vol. 1 AAAI Press/International Joint Conferences on Artificial Intelligence, 2011. p. 699-704.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - 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

PY - 2011/7

Y1 - 2011/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84876408853&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84876408853&origin=recordpage

U2 - 10.5591/978-1-57735-516-8/IJCAI11-123

DO - 10.5591/978-1-57735-516-8/IJCAI11-123

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-1-57735-513-7

VL - 1

SP - 699

EP - 704

BT - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence

PB - AAAI Press/International Joint Conferences on Artificial Intelligence

T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011

Y2 - 16 July 2011 through 22 July 2011

ER -

Space defragmentation heuristic for 2D and 3D bin packing problems

Abstract

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this