A hybrid beam search looking-ahead algorithm for the circular packing problem

作者：Akeb Hakim; Hifi Mhand^*

来源：Journal of Combinatorial Optimization, 2010, 20(2): 101-130.

DOI：10.1007/s10878-008-9191-8

• Packing
• Hybrid heuristic
• Beam search
• Looking-ahead strategy
• Minimum local-distance position
• Knapsack problems

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions LxW. Each piece's type i, i=1,aEuro broken vertical bar,m, is characterized by its radius r (i) and its demand b (i) . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level a"" of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level a"" are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.

• 出版日期2010-8