An iterated local search for the Book Scanning Problem
本文提出了一种具有自动配置参数的迭代局部搜索算法，并提供了一个包含 324 个实例的公开基准测试集来解决图书扫描问题，在证明了 21 个案例的最优性同时，实现了比现有方法更优的解质量。
原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，一个图书馆网络正在为一个大规模的数字化项目做准备。他们有一个严格的截止日期，拥有一支随时可以进行扫描的图书馆队伍，并且有数百万本书籍等待处理。挑战不仅在于拥有扫描仪，更在于时间表。每家图书馆必须在开始扫描前先进行登记，但一次只能有一家图书馆进行登记。一旦登记完成，图书馆便立即开始扫描其书籍，与其他图书馆并行工作。然而，每在等待登记上多花一天，就会损失一天的扫描时间。此外，许多书籍存在于多家不同的图书馆中。如果一本稀有书籍由三家不同的图书馆持有，无论物理上复制了多少次，该项目只计算一次扫描进度。目标是决定图书馆登记的顺序以及每家图书馆应该扫描哪些特定的书籍，从而在时间耗尽前实现数字化馆藏总价值的最大化。这是一个关于时间与选择的复杂谜题，早期的错误选择可能会浪费后期某家图书馆的潜力。
这个被称为“图书扫描问题”的具体谜题，曾是2020年一场重大竞赛的主题。虽然许多团队开发了定制化的解决方案来赢得那场比赛，但那些方案往往是针对特定测试用例量身定制的，因此无法轻易应用于新的情况。来自科索沃的一个研究小组现在开发了一种更通用的方法来解决这个问题。他们创建了一种名为“迭代局部搜索”的方法，它就像一个执着的探险家，试图寻找最佳的时间表。该方法并非仅仅猜测一个答案，而是从一个粗略的计划开始，然后通过不断进行微小的调整来观察结果是否有所改善。它尝试交换图书馆的顺序，移除贡献不大的图书馆，或者插入可能带来稀有书籍的新图书馆。如果某种改变导致得分降低，该方法有时仍会接受这种改变，就像徒步旅行者为了避开死胡同而有时会选择稍长的路径一样，希望能找到更好的路线。
研究人员在数百个不同的场景上测试了他们的方法，涵盖了从小型馆藏到包含两百万本书籍的庞大档案库。他们将自己的结果与原比赛中现有的最佳方案进行了对比。新方法证明是非常有效的，在大多数测试用例中，其得分高于其他六种方法的综合最佳水平。总计来看，它的得分比之前的最佳综合结果高出了2.362%。这看起来可能是一个很小的百分比，但在数字化数百万本书籍的背景下，这代表了文化遗产保存量显著的增长。研究人员还发现，他们的方法在处理那些图书馆登记时间和扫描速度差异极大的困难案例时表现尤为出色。在某些情况下，该方法找到了在数学上被证明是绝对最优的解，这意味着没有任何其他时间表能做得更好。
这项工作的一个关键发现是理解了该方法的哪些部分实际上最为重要。研究人员拆解了他们的系统以观察每个部分贡献了什么。他们发现，最重要的部分不是初始猜测或随机洗牌，而是改变实际参与工作的图书馆集合的能力。仅仅重新排列现有图书馆的顺序会有帮助，但用一个完全不同的图书馆进行替换对最终得分的影响最大。这表明，问题的难点在于决定哪些图书馆应该参与其中，而不仅仅是它们排队的先后顺序。该方法还展现出了极佳的稳定性；当在同一个问题上多次运行时，它每次都会产生几乎相同的结果，证明了它是一个可靠的工具而非偶然的运气。
这项研究并未声称解决了该问题的所有版本，也没有声称击败了原比赛中设置的所有纪录。事实上，在五个官方竞赛实例中，新方法略逊于那些为特定案例进行过人工调优的专家级专门化方案。然而，这种新方法的优势在于其灵活性。它对遇到的每种类型的问题都使用统一且一致的策略，而无需针对每个新的图书馆网络进行重新编程。研究人员还提供了一个公开的测试用例集及其结果，允许其他科学家验证他们的工作并在此基础上进行研究。通过将清晰的数学模型与鲁棒的搜索策略相结合，他们展示了一个通用的、具有适应性的方法如何能够与高度专业化的方法相竞争，为应对现实世界中复杂的规划问题提供了一种透明且可复现的方式。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。