Greedy algorithms for packing unequal circles into a rectangular container

Abstract

In this paper, we study the problem of packing unequal circles into a two-dimensional rectangular container. We solve this problem by proposing two greedy algorithms. The first algorithm, denoted by B1.0, selects the next circle to place according to the maximum-hole degree rule, that is inspired from human activity in packing. The second algorithm, denoted by B1.5, improves B1.0 with a self-look-ahead search strategy. The comparisons with the published methods on several instances taken from the literature show the good performance of our approach.

Keywords:

• circle packing problem
• combinatorial optimization
• greedy algorithm
• heuristic

Acknowledgements

We are thankful to Stoyan, Yaskov, Hifi and M'Hallah for the use of their instances and results, and to two anonymous referees for their helpful comments and suggestions. This work is supported by ‘China national, 973 program (G1998030600)’ and ‘Programme de Recherches Avancées de Coopérations Franco-Chinoises (PRA SI02-04)’.