Probability-Based Monotonic Basin-hopping Algorithm for Packing Equal Circles in a Rectangular Container

The problem of packing equal circles in a rectangular container refers to the task of placing a given number of non-overlapping equal circles into a fixed rectangular container while maximizing the radius of the circles. This problem is a well-known global optimization problem with a number of applications. To solve this challenging problem, we propose a new heuristic algorithm called the probability-based monotonic basin-hopping algorithm which includes a probability-based monotonic basin-hopping method and an adjustment method for the radius of circles. The performance of algorithm is tested on a number of popular benchmark instances and the experimental results show that the proposed algorithm is very efficient and improves the best-known solutions for 25 out of 51 benchmark instances tested.