A divide-conquer quasi-physical and quasi-human algorithm for the circle and rectangle orthogonal packing problem with equilibrium constraints

The circle and rectangle orthogonal packing problem with equilibrium constraints (ECROPP) belongs to NP-hard problems. This paper proposes a divide-conquer QPQH (DCQPQH) algorithm for this problem. A mathematical model is built for the divide-conquer solution of ECROPP. And then on the basis of the embedding depths between two rectangles and between the circle and rectangle, an elastic potential energy function of the system is given. Then, the DCQPQH algorithm is presented through a combination of the divide-conquer strategy and QPQH algorithm based on the elastic potential energy function. Because the combination makes the proposed DCQPQH algorithm inherit excellent properties of QPQH and the advantage of the divide-conquer solution, its solution accuracy and computational efficiency are improved. The numerical experiments show that performances of the proposed DCQPQH algorithm are superior to those of the existing algorithms.