New heuristics for packing unequal circles into a circular container

作者：Huang WQ; Li Y^*; Li CM; Xu RC

来源：Computers & Operations Research, 2006, 33(8): 2125-2142.

DOI：10.1016/j.cor.2005.01.003

• circle packing problem
• combinatorial optimization
• heuristic

We propose two new heuristics to pack unequal circles into a two-dimensional circular container. The first one, denoted by A1.0, is a basic heuristic which selects the next circle to place according to the maximal hole degree rule. The second one, denoted by A1.5, uses a self look-ahead strategy to improve A1.0. We evaluate A1.0 and A1.5 on a series of instances up to 100 circles from the literature and compare them with existing approaches. We also study the behaviour of our approach for packing equal circles comparing with a specified approach in the literature. Experimental results show that our approach has a good performance in terms of solution quality and computational time for packing unequal circles.

• 出版日期2006-8
• 单位华中科技大学