Iterated tabu search for the circular open dimension problem

This paper investigates the circular open dimension problem (CODP), which consists of packing a set of circles of known radii into a strip of fixed width and unlimited length without overlapping. The objective is to minimize the length of the strip. In this paper, CODP is solved by a series of sub‐problems, each corresponding to a fixed strip length. For each sub‐problem, an iterated tabu search approach, named ITS, is proposed. ITS starts from a randomly generated solution and attempts to gain improvements by a tabu search procedure. After that, if the obtained solution is not feasible, a perturbation operator is subsequently employed to reconstruct the incumbent solution and an acceptance criterion is implemented to determine whether or not accept the perturbed solution. As a supplementary method, the length of the strip is determined in monotonously decreasing way, with the aid of some post‐processing techniques. The search terminates and returns the best found solution after the allowed computation time has been elapsed. Computational experiments based on numerous well‐known benchmark instances show that ITS produces quite competitive results, with respect to the best known results, while the computational time remains reasonable for each instance.