使用迭代 taboo 搜索解决圆形开放维度问题

"本文主要探讨了圆形开放维度问题（CODP），该问题涉及到在固定宽度且无限长度的条形带上无重叠地放置一组已知半径的圆，目标是最小化条形带的长度。作者提出了一个迭代禁忌搜索（ITS）方法来解决此问题。该方法从随机生成的解决方案开始，尝试通过禁忌搜索过程进行改进。如果得到的解决方案不可行，将使用扰动算子重构当前解决方案，并应用接受准则来决定是否接受被扰动的解。这个过程会持续进行，直到找到可行解或达到允许的计算时间限制。实验结果显示，ITS在处理CODP时表现出色，能有效找到高质量解。" 在这篇研究论文中，作者关注的是一个物流与优化领域的经典问题——圆形开放维度问题（CODP）。CODP的核心在于如何在有限宽度但无限长度的空间中有效地安排一系列已知大小的圆，以使得整体占用的长度最小，同时确保所有圆之间不发生重叠。这个问题在实际应用中可能涉及到货物包装、仓储布局等场景。 论文提出了一种名为迭代禁忌搜索（Iterated Tabu Search, ITS）的优化算法。禁忌搜索是一种局部搜索策略，它通过避免近期探索过的解决方案（即“禁忌列表”）来鼓励算法跳出局部最优解，从而探索更广阔的解决方案空间。在ITS中，首先从随机生成的初始解开始，然后利用禁忌搜索进行迭代优化。每次迭代中，如果得到的解不符合问题约束（即不可行解），则通过扰动算子对当前解进行调整，以生成新的候选解。这里，扰动算子可能是随机改变部分圆的位置或者大小，以破坏原有结构并尝试寻找新的可行解。 接下来，论文引入了一个接受准则，用于判断是否接受由扰动算子产生的新解。这个接受准则可能基于模拟退火算法中的Metropolis准则或其他类似规则，允许在一定条件下接受可能导致当前解恶化的新解，以保持算法的全局探索能力。在没有找到可行解或者达到预设的计算时间限制之前，这一过程将持续进行。 通过实验，作者展示了ITS在解决CODP问题上的效能。实验结果表明，该方法能够在保证找到可行解的同时，有效地收敛到高质量的解，证明了ITS对于CODP的有效性和可行性。这篇论文为圆形开放维度问题提供了一个新的优化工具，并为相似问题的求解提供了有价值的参考。