利用基于禁忌搜索的GRASP算法求解P-center问题

摘要

由Hakami在1964年提出的P-center问题作为一个经典的NP难问题在物流设施规划，通信网络设计以及警局、医院、消防站等有公共服务标准要求的诸多行业中有广阔的应用前景。尤其是物流行业，作为电子商务的基石，随着电子商务的兴起，其地位的重要性日渐凸显。设施选址问题作为物流业的核心问题得到了国际学者的积极研究。P-center问题作为各类型选址问题的基础，是一个具有重大研究价值以及现实挑战性的课题。
　　求解NP难问题的常用算法有三种：精确算法、近似算法和启发式优化算法。精确算法一定可以给出最优解，但是由于NP问题具有指数级的复杂度，通常只能使用精确算法解决小规模实例，大规模的问题实例则无法使用精确算法在可接受的时间范围内求解出最优解。近似算法虽能保证最坏情况下得到的解与最优解的误差在一定的范围内，但其实际计算结果却往往不能够令人满意。
　　启发式优化算法往往能够在求解精度和求解时间上达到很好的平衡，因而成为一种广泛被学者研究的算法。本文以Pullan的PBS-1算法中的局部搜索算法为基础，提出一种基于禁忌搜索的GRASP(Greedy Randomized Adaptive Search Procedures)算法—TS&GRASP。为了验证TS&GRASP的效果，本文选取了148个P-center标准算例的进行测试，实验结果显示TS&GRASP算法在11个算例的求解上找到了更优的解，而其他算例的求解结果至少可以和PBS-1算法持平。并且值得一提的是，相比 PBS-1算法，TS&GRASP算法在求解时间上也有明显的提高。实验结果表明，与当今国际上最优秀的算法相比较，本文所提出的TS&GRASP算法在P-center问题的求解上非常具有竞争力。