学位论文 > 优秀研究生学位论文题录展示

网络选址中的若干模型和算法研究

作　者: 徐进澎
导　师: 蒋建林
学　校: 南京航空航天大学
专　业: 运筹学与控制论
关键词: 网络选址问题集合覆盖问题顶点p-中心问题多目标反p-中心问题广义最小生成树问题 NP-难元启发式算法
分类号: O221.4
类　型: 硕士论文
年　份: 2010年
下　载: 87次
引　用: 0次
阅　读: 论文下载

内容摘要

选址问题是运筹学中的经典问题之一,在生产生活甚至军事中都有着非常广泛的应用。网络是大多数选址主体进行选址决策的载体,所以对网络选址的研究往往更有实际意义。论文主要研究用改进的元启发式算法来求解网络选址中的若干模型,这些模型都是NP-难问题。论文的具体内容如下:第一章介绍了课题研究的背景及选址问题的研究现状,并阐述了本文的主要工作。第二章介绍了一些经典的网络选址问题。第三章介绍了一些元启发式算法。第四章,针对规模较大的集合覆盖问题,提出改进的遗传算法进行求解。对遗传算法的改进主要包括初始种群的产生、对不可行解和重复个体的处理、以及新的交叉和变异方法的提出。最后在数值实验中与其他算法进行了比较,并分析了算法改进的有效性。第五章,针对规模较大的顶点p-中心问题,通过综合遗传算法和模拟退火算法的优点,提出了一种单亲遗传和模拟退火的混合算法进行求解,并设计了自适应选择法和自适应基因重组操作,最后在数值实验中与其他三种算法进行了比较,结果表明本章算法更有效。第六章提出了一种多目标反p-中心问题,并利用线性加权和法将其转化为单目标问题,然后建立了其整数规划模型,并且尝试用单亲遗传模拟退火算法来求解。最后针对不同的权重,分别进行了数值实验,并分析了算法的有效性。第七章,针对广义最小生成树问题,设计了两种改进的元启发式算法来求解。在改进的禁忌搜索算法中,通过在两种邻域进行搜索来避免陷入局部最优。最后通过数值实验对这两种算法进行了比较,并验证了算法的有效性。最后,总结全文,并指出了未来可行的研究方向。

全文目录

摘要  4-5
Abstract  5-9
第一章绪论  9-14
  1.1 课题研究的背景  9-10
  1.2 选址问题的研究现状  10-12
  1.3 研究的主要内容  12-14
第二章网络选址问题的若干模型  14-18
  2.1 集合覆盖问题  14-15
  2.2 最大覆盖问题  15
  2.3 p-中位问题  15-16
  2.4 p-中心问题  16-17
  2.5 广义最小生成树问题  17-18
第三章元启发式算法  18-22
  3.1 遗传算法  18-19
  3.2 模拟退火算法  19
  3.3 禁忌搜索算法  19-20
  3.4 变邻域搜索算法  20-21
  3.5 蚁群算法  21-22
第四章求解集合覆盖问题的改进遗传算法  22-28
  4.1 改进的遗传算法  22-25
  4.2 数值实验  25-27
  4.3 结论  27-28
第五章求解顶点p-中心问题的单亲遗传模拟退火算法  28-34
  5.1 单亲遗传模拟退火算法  28-31
  5.2 数值实验  31-33
  5.3 结论  33-34
第六章多目标反p-中心问题及其求解方法  34-39
  6.1 问题描述及模型建立  34-35
  6.2 单亲遗传模拟退火算法  35-36
  6.3 数值实验  36-38
  6.4 结论  38-39
第七章求解广义最小生成树问题的两种方法  39-44
  7.1 单亲遗传模拟退火算法  39-40
  7.2 改进的禁忌搜索算法  40-42
  7.3 数值实验  42-43
  7.4 结论  43-44
结束语  44-45
参考文献  45-48
致谢  48-49
在学期间的研究成果及发表的学术论文  49

网络选址中的若干模型和算法研究

内容摘要

全文目录

相似论文