An Adaptive Look-Ahead Strategy-Based Algorithm for the Circular Open Dimension Problem
An Adaptive Look-Ahead Strategy-Based Algorithm for the Circular Open Dimension Problem
复制标题
DOI：
--
复制
发表时间：
2010-11
期刊：
影响因子：
--
通讯作者：
H. Akeb;M. Hifi
中科院分区：
文献类型：
--
作者：
H. Akeb;M. Hifi
本文研究了切割与包装族中的一个著名的组合优化问题--圆形开维问题。我们给出一组已知半径的圆片（或圆）和一条固定宽度和无限长度的带。目的是确定包装所有圆形件的初始条带的最小长度。该问题近似解决了自适应前瞻策略为基础的算法，它结合了贪婪的程序，重新启动和单独的波束策略，和前瞻搜索。在一组基准实例上的运行实验表明了该方法的有效性。对于这些实例，所提出的算法改进了18个结果中的10个。关键字-射束搜寻、切割与包装、前瞻、最小局部距离定位、多起点策略。
In this paper, we study the circular open dimension problem, a well-known combinatorial optimization problem of the cutting and packing family. We are given a set of circular pieces (or circles) of known radii and a strip of fixed width and unlimited length. The objective is to determine the minimum length of the initial strip that packs all the circular pieces. The problem is approximately solved with an adaptive look-ahead strategy-based algorithm, which combines greedy procedures, restarting and separate beams strategies, and a look-ahead search. The running experiments show, on a set of benchmark instances of the literature, the effectiveness of the proposed method. For these instances, the proposed algorithm improves 10 results out of 18. Keywords-beam search, cutting and packing, look-ahead, minimum local-distance position, multi-start strategy.