Feasible Approaches For Solving The Arbitrary Sized Circle Packing Problem

NP-hard problems are widely encountered in practical applications. However, due to the extremely large solution space of NP-hard problems, there has not been any algorithm that guarantees to obtain the global optimal solution within polynomial time. Unfortunately, it seems that this kind of algorithm does not exist, unless P=NP. Therefore, heuristic approaches which attempt to obtain approximate solutions instead of the global optimal one within reasonable time become the only feasible approaches for solving NP-hard problems.This paper attempts to develop effective heuristics for solving NP-hard problems, especially for the two-dimensional Arbitrary Sized Circle Packing Problem (ACP). ACP is concerned about how to pack a number of arbitrary sized circles into a large container without overlapping, with the aim to minimize the container size. As a typical NP-hard problem, ACP should deal with both continuous and combinatory optimization problems. This paper develops an efficient continuous optimization method and several effective combinatory optimization strategies. Based on them, a hybrid heuristic algorithm named GP-TS is proposed for solving ACP, whose framework can be described as follows:(1) Randomly generate an initial solution, and then use the continuous optimization method to reach a local optimal configuration. (2) Call a tabu search procedure named TS to iteratively update the incumbent configuration with its best neighboring configuration. (3) If the obtained configuration is not high-quality enough, execute a global perturbation operator to reconstruct the incumbent configuration without destroying its structure too much. (4) Launch a new round of TS procedure for further optimization again. (5) Based on simulating annealing strategy, implement an acceptance criterion to determine whether or not accept the incumbent configuration. (6) Repeat steps 3-5 until a feasible solution which strictly satisfies all the constraints has been found, or some other stop criterion is met.GP-TS firstly divides the search procedure into three stages and respectively implements effective search methods for each stage, including a continuous optimization method, a tabu search procedure (a special variant of neighborhood search) and a global perturbation operator. In contrast, the previously proposed approaches for solving ACP can be classified into two categories:(1) Constructive approaches which attempt to pack all the circles one by one into the container according to some constructive rule. (2) Perturbation-based approaches which divide the search procedure into only two stages: continuous optimization and global perturbation. Apparently, the framework of GP-TS is very different from previous approaches. Analyses show that GP-TS is efficient and robust that it can exploit the tradeoff between continuous optimization, neighborhood search and global optimization.The key components of GP-TS are respectively introduced, including the continuous optimization method, the tabu search procedure, the global perturbation operator, the acceptance criterion and the stop criterions. In addition, several auxiliary methods which attempt to improve GP-TS are also described. Computational experiments based on 4 sets of 66 representative instances show that GP-TS succeeds in improving 43 and matching 19 best known results within reasonable time, it only fails to match 4 best known results. Although the runtime can only be used as an auxiliary evaluation criterion, the comparion in terms of both solution quality and runtime still undoubtedly demonstrates the effectiveness of GP-TS.Finally, several principles for solving NP-hard problems are summarized. Due to the fact that NP-hard problems are generally essentially equivalent with each other, we believe that the principles and the methods proposed in this paper would be helpful for solving other NP-hard problems.