快速排序与归并排序的模板

A Vertex Weighting-Based Double-Tabu Search Algorithm for the Classical p-Center Problem 一文的中文翻译。 p-中心问题（The p-center problem）是NP难问题，旨在从一组候选中心中选择p个中心以服务于所有客户，同时最小化每个客户与其分配的中心之间的最大距离。为解决这一具有挑战性的优化问题，我们将p-中心问题转化为一系列决策子问题，并提出了一种基于顶点加权的双禁忌搜索（VWDT）算法。该算法结合了顶点加权策略和一种结合了基于解和基于属性的禁忌策略的双禁忌搜索，以帮助搜索过程跳出局部最优陷阱。对文献中总共510个公开实例的计算实验表明，VWDT算法与最先进的算法相比具有高度竞争力。具体而言，VWDT算法改进了84个大型实例的先前最佳已知结果，并与其他所有实例的最佳结果持平。除了解决方案质量的改进外，VWDT算法在文献中的其他最先进的算法中，尤其是在一些大型实例上，要快得多。此外，我们还进行了额外的实验，以分析VWDT算法中关键组件（如顶点加权和双禁忌搜索策略）的影响。

禁忌搜索（TS）算法是解决作业车间调度问题（JSP）的最有效方法之一，而JSP是最难解决的NP完全问题之一。然而，对于JSP的禁忌搜索而言，邻域结构和移动评估策略在其有效性和效率方面起着核心作用。本文提出了一种新的增强型邻域结构，并将其应用于通过禁忌搜索方法解决作业车间调度问题。使用这种新的邻域结构，结合适当的移动评估策略和参数，我们在一组标准基准实例上测试了禁忌搜索方法，并在未解决的实例中发现了大量更好的上界。计算结果表明，对于矩形问题，我们的方法在解决方案质量和性能方面都优于其他所有方法。