A Hybrid Genetic Algorithms and Tabu Search for Solving an Irregular Shape Strip Packing Problem

Abstract

This paper presents a packing algorithm to solve an irregular shape strip packing problem. The polygons are packed in strip material, which limits a bin width but not limits a bin length. The objective of a packing algorithm is to minimize a bin length. This paper proposes a hybrid method of genetic algorithms and tabu search to solve a packing problem. Initially, a hybrid method behaves like regular genetic algorithms. After that, a hybrid method is self adapting until it behaves like a tabu search. This paper compares results generated by a hybrid method with genetic algorithms and tabu search. The experiment data is the 13 pieces convex-type polygon and duplicate, triplicate and quadruplicate. The experiment shows that a hybrid method generates better result than genetic algorithms about 2.56% to 4.69% and a hybrid method generates better result than tabu search about 0.26% to 2.78%.