Iterated Tabu Search Algorithm for Packing Unequal Circles in a Circle
This addresses a combinatorial optimization problem in packing theory, with incremental improvements over existing methods.
The paper tackles the problem of packing unequal circles in a circle by developing an Iterated Tabu Search algorithm, which discovered 14 and 16 better solutions than previous best-known records on two sets of test instances.
This paper presents an Iterated Tabu Search algorithm (denoted by ITS-PUCC) for solving the problem of Packing Unequal Circles in a Circle. The algorithm exploits the continuous and combinatorial nature of the unequal circles packing problem. It uses a continuous local optimization method to generate locally optimal packings. Meanwhile, it builds a neighborhood structure on the set of local minimum via two appropriate perturbation moves and integrates two combinatorial optimization methods, Tabu Search and Iterated Local Search, to systematically search for good local minima. Computational experiments on two sets of widely-used test instances prove its effectiveness and efficiency. For the first set of 46 instances coming from the famous circle packing contest and the second set of 24 instances widely used in the literature, the algorithm is able to discover respectively 14 and 16 better solutions than the previous best-known records.