Iterated tabu search for the circular open dimension problem. Fu, Z., Huang, W., & Lü, Z. European Journal of Operational Research, 225(2):236-243, Elsevier B.V., 3, 2013.
Iterated tabu search for the circular open dimension problem [pdf]Paper  Iterated tabu search for the circular open dimension problem [link]Website  abstract   bibtex   
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. © 2012 Elsevier B.V. All rights reserved.

Downloads: 0