利用基于禁忌搜索的grasp算法求解p-center问题.docx

独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除文中已经标明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名:
日期: 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
本论文属于
保密□,在 年解密后适用本授权书。
不保密□。
(请在以上方框内打“√”)
学位论文作者签名: 指导教师签名:
日期: 年 月 日 日期: 年 月 日
摘 要
由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 问题的求解上非常具有竞争力。
关键词:NP 难问题,P-中心问题,禁忌算法,局部搜索
ABSTRACT
As a classic NP hard problem put forward by Hakami in 1964, P-center problem has broad application prospects in the logistics facilities planning, work design, and location of the police station, hospital, fire station and other industries which have public service standards. Especially as the foundation of merce, with the development of merce the logistics industry, the P-center problem became more and more important. The facility location problem, which is the core of the logistics industry got widely studied by international scholars. As the basis of each type of location problem, p-center problem is a challenging topic and have great research value.
There are three kinds of algorithm to solve a NP hard problem: the exact algorithm, the approximation algorithm and the