论文标题
自适应大型邻里搜索圆圈包装问题
Adaptive Large Neighborhood Search for Circle Bin Packing Problem
论文作者
论文摘要
我们解决了一个新的包装问题变体，称为圆圈包装问题（CBPP），该问题是在多个方形箱中找到圆形项目的密集包装，以最大程度地减少使用的垃圾箱的数量。为此，我们提出了一种自适应的大型邻里搜索（ALNS）算法，该算法使用我们的贪婪算法和角落占据动作（GACOA）来构建初始布局。贪婪的解决方案通常位于本地最佳陷阱中，ALN可以实现多个邻里搜索，这些邻居搜索取决于随机退火时间表，以避免陷入本地最小陷阱。具体而言，Alns将当前布局散发出来，以通过迭代重新分配一些圆圈，从搜索过程中以某种概率接受新布局，从而从本地最佳中跳出。使用模拟退火对搜索方向进行微调以达到全局最佳的方式进行自适应调整接受概率。我们在异质实例中针对GACOA进行了计算结果。 ALN始终在改善目标函数方面的表现始终优于Gacoa，在某些情况下，包装中使用的垃圾箱数量大大减少。
We address a new variant of packing problem called the circle bin packing problem (CBPP), which is to find a dense packing of circle items to multiple square bins so as to minimize the number of used bins. To this end, we propose an adaptive large neighborhood search (ALNS) algorithm, which uses our Greedy Algorithm with Corner Occupying Action (GACOA) to construct an initial layout. The greedy solution is usually in a local optimum trap, and ALNS enables multiple neighborhood search that depends on the stochastic annealing schedule to avoid getting stuck in local minimum traps. Specifically, ALNS perturbs the current layout to jump out of a local optimum by iteratively reassigns some circles and accepts the new layout with some probability during the search. The acceptance probability is adjusted adaptively using simulated annealing that fine-tunes the search direction in order to reach the global optimum. We benchmark computational results against GACOA in heterogeneous instances. ALNS always outperforms GACOA in improving the objective function, and in several cases, there is a significant reduction on the number of bins used in the packing.
