A Hybrid Approach for the Circular Knapsack Packing Problem with Rectangular Items

This paper studies a circular knapsack packing problem of packing unequal rectangles into a circle to maximize the number or the area of items packed. To solve this problem, we propose a biased genetic algorithm with the decimal coding method instead of the random-key method. We propose a decoding procedure called place to transform the chromosome into a packing layout. The procedure place produces several initial layouts and repeatedly performs three steps for each layout to generate a complete layout based on the concept of contour. Computational experiments using benchmark instances show that the algorithm generally provides better solutions than state-of-the-art metaheuristic algorithms from the literature. The proposed approach produces 27 new best solutions out of 54 instances on benchmark instances.