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

发布时间：2018-04-13 15:45

本文选题：NP难问题 + P-中心问题　；参考：《华中科技大学》2015年硕士论文

【摘要】：由Hakami在1964年提出的P-center问题作为一个经典的NP难问题在物流设施规划,通信网络设计以及警局、医院、消防站等有公共服务标准要求的诸多行业中有广阔的应用前景。尤其是物流行业,作为电子商务的基石,随着电子商务的兴起,其地位的重要性日渐凸显。设施选址问题作为物流业的核心问题得到了国际学者的积极研究。P-center问题作为各类型选址问题的基础,是一个具有重大研究价值以及现实挑战性的课题。求解NP难问题的常用算法有三种:精确算法、近似算法和启发式优化算法。精确算法一定可以给出最优解,但是由于NP问题具有指数级的复杂度,通常只能使用精确算法解决小规模实例,大规模的问题实例则无法使用精确算法在可接受的时间范围内求解出最优解。近似算法虽能保证最坏情况下得到的解与最优解的误差在一定的范围内,但其实际计算结果却往往不能够令人满意。启发式优化算法往往能够在求解精度和求解时间上达到很好的平衡,因而成为一种广泛被学者研究的算法。本文以Pullan的PBS-1算法中的局部搜索算法为基础,提出一种基于禁忌搜索的GRASP(Greedy Randomized Adaptive Search Procedures)算法—TSGRASP。为了验证TSGRASP的效果,本文选取了148个P-center标准算例的进行测试,实验结果显示TSGRASP算法在11个算例的求解上找到了更优的解,而其他算例的求解结果至少可以和PBS-1算法持平。并且值得一提的是,相比PBS-1算法,TSGRASP算法在求解时间上也有明显的提高。实验结果表明,与当今国际上最优秀的算法相比较,本文所提出的TSGRASP算法在P-center问题的求解上非常具有竞争力。
[Abstract]:The P-center problem proposed by Hakami in 1964 as a classical NP-hard problem has a broad application prospect in logistics facilities planning, communication network design, police stations, hospitals, fire stations and many other industries with the requirements of public service standards.Especially the logistics industry, as the cornerstone of electronic commerce, with the rise of electronic commerce, the importance of its status is increasingly prominent.As the core problem of logistics industry, facility location problem has been actively studied by international scholars. P-center problem, as the basis of various types of location problems, is of great research value and practical challenge.There are three common algorithms for solving NP-hard problems: exact algorithm, approximate algorithm and heuristic optimization algorithm.The exact algorithm can give the optimal solution, but due to the exponential complexity of the NP problem, the exact algorithm can only be used to solve the small scale cases.Large-scale problem examples can not solve the optimal solution in an acceptable time range by using an exact algorithm.Although the approximate algorithm can guarantee the error between the solution and the optimal solution in a certain range in the worst case, the actual calculation results are often not satisfactory.Heuristic optimization algorithm is often able to achieve a good balance between precision and time, so it has become a widely studied algorithm.Based on the local search algorithm in Pullan's PBS-1 algorithm, a Tabu search based GRASP(Greedy Randomized Adaptive Search procedure algorithm (TSGRASP) is proposed in this paper.In order to verify the effectiveness of TSGRASP, 148 P-center standard examples are selected for testing. The experimental results show that the TSGRASP algorithm has found a better solution on 11 examples, while the other examples have at least the same results as the PBS-1 algorithm.And it is worth mentioning that compared with PBS-1 algorithm, TSGRASP algorithm also has significant improvement in solving time.The experimental results show that the TSGRASP algorithm proposed in this paper is very competitive in solving the P-center problem compared with the best algorithms in the world.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6

【参考文献】