This paper investigates the use of hybrid metaheuristics based on Ant Colony Optimization (ACO) for the strip packing problem. Here, a fixed set of rectangular items of fixed sizes have to be placed on a strip of fixed width and infinite height without overlaps and with the objective to minimize the height used. We analyze a commonly used basic placement heuristic (BLF) by itself and in a number of hybrid combinations with ACO. We compare versions that learn item order only, item rotation only, both independently, and rotations conditionally upon placement order. Our analysis shows that integrating a learning meta-heuristic provides a significant performance advantage over using the basic placement heuristic by itself. The experiments confirm that even just learning a placement order alone can provide significant performance improvements. Interestingly, learning item rotations provides at best a marginal advantage. The best hybrid algorithm presented in this paper significantly outperforms previously reported strip packing meta-heuristics.
History
Pagination
1207-1213
Location
Hong Kong, China
Start date
2008-06-01
End date
2008-06-06
ISBN-13
9781424418237
Language
eng
Publication classification
E1.1 Full written paper - refereed
Editor/Contributor(s)
[Unknown]
Title of proceedings
CEC 2008 : Proceedings of the 2008 IEEE Congress on Evolutionary Computation
Event
Evolutionary Computation. Congress (2008 : Hong Kong, China)