（运筹学与控制论专业论文）网络选址中的若干模型和算法研究.pdf

li 铷鼍奎j滢”-f ；一；， n a n j i n gu n i v e r s i t yo f a e r o n a u t i c sa n da s t r o n a u t i c s 砀eg r a d u a t es c h o o l c o l l e g eo fs c i e n c e r e s e a r c ho ns o m em o d e l sa n d a l g o r i t h m si n n e t w o r kl o c a t i o nf i e l d a t h e s i si n m a t h e m a t i c s b y x u j i n - p e n g a d v i s e db y a s s o c i a t ep r o f e s s o rj i a n gj i a n l i n s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o rt h ed e g r e eo f m a s t e ro fs c i e n c e j a n u a r y , 2 0 1 0 5 2哪752舢8iiiii 唧y 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进 行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容外， 本学位论文的研究成果不包含任何他人享有著作权的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标 明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许 论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日期： 一 南京航空航天大学硕士学位论文 摘要 选址问题是运筹学中的经典问题之一，在生产生活甚至军事中都有着非常广泛的应用。网 络是大多数选址主体进行选址决策的载体，所以对网络选址的研究往往更有实际意义。 论文主要研究用改进的元启发式算法来求解网络选址中的若干模型，这些模型都是n p 一难 问题。论文的具体内容如f ：第一章介绍了课题研究的背景及选址问题的研究现状，并阐述了 本文的主要工作。第二章介绍了一些经典的网络选址问题。第三章介绍了一些元启发式算法。 第四章，针对规模较大的集合覆盖问题，提出改进的遗传算法进行求解。对遗传算法的改 进主要包括初始种群的产生、对不可行解和重复个体的处理、以及新的交义和变异方法的提出。 最后在数值实验中与其他算法进行了比较，并分析了算法改进的有效性。 第五章，针对规模较大的顶点旷中心问题，通过综合遗传算法和模拟退火算法的优点，提 出了一种单亲遗传和模拟退火的混合算法进行求解，并设计了自适应选择法和自适应基因重组 操作，最后在数值实验中与其他三种算法进行了比较，结果表明本章算法更有效。 第六章提出了一种多目标反p 一中心问题，并利用线性加权和法将其转化为单目标问题，然 后建立了其整数规划模型，并且尝试用单亲遗传模拟退火算法来求解。最后针对不同的权重， 分别进行了数值实验，并分析了算法的有效性。 第七章，针对广义最小生成树问题，设计了两种改进的元启发式算法米求解。在改进的禁 忌搜索算法中，通过在两种邻域进行搜索来避免陷入局部最优。最后通过数值实验对这两种算 法进行了比较，并验证了算法的有效性。 最后，总结全文，并指出了未来可行的研究方向。 关键词：网络选址问题，集合覆盖问题，顶点，中心问题，多目标反p 一中心问题，广义最小生 成树问题，n p - 难，元启发式算法 网络选址中的若干模型和算法研究 a b s t r a c t l o c a t i o np r o b l e mi so n eo fc l a s s i c a lp r o b l e m si nt h eo p e r a t i o n a lr e s e a r c h ，w h i c hi sw i d e l yu s e d i no u rp r o d u c t i o n ，d a i l yl i f ea n de v e nm i l i t a r y n e t w o r ki sc a r r i e ro fm o s to ft h el o c a t i o nd e c i s i o n s ， a n dt h e r e f o r et h es t u d yo nn e t w o r kl o c a t i o np r o b l e mi sm o r em e a n i n g f u lt h a no t h e rl o c a t i o np r o b l e m s t h i sp a p e rm a i n l ys t u d i e sa b o u tt h ea p p l i c a t i o no fi m p r o v e dm e t a - h e u r i s t i ca l g o r i t h m sf o rs o m e n e t w o r kl o c a t i o np r o b l e m s ，w h i c ha r en p - h a r d t h ew h o l ep a p e ri so r g a n i z e da sf o l l o w s ：c h a p t e r1 i n t r o d u c e st h eb a c k g r o u n do fs u b j e c tr e s e a r c ha n dt h ec u r r e n tr e s e a r c hs t a t e ，f o l l o w e db yt h em a i n r e s e a r c ho ft h i sp a p e r c h a p t e r2i n t r o d u c e ss o m et y p i c a ln e t w o r kp r o b l e m s c h a p t e r3i n t r o d u c e s s o m em e t a - h e u r i s t i ca l g o r i t h m s c h a p t e r4p r e s e n t sa ni m p r o v e dg e n e t i ca l g o r i t h mf o rl a r g e s c a l es e tc o v e r i n gp r o b l e m t h e i m p r o v e m e n t sf o rg e n e t i ca l g o r i t h mi n c l u d et h ef o l l o w i n ga s p e c t s ：f i r s t ，t h i sa l g o r i t h md e s i g n sa n e w w a yt og e n e r a t e i n i t i a l p o p u l a t i o n ；s e c o n d ，i tp r o p o s e sat e c h n o l o g yf o r i n f e a s i b l es o l u t i o n sa n d o v e r l a p p i n gi n d i v i d u a l s ；m 矾，i td e s i g n san e w c r o s s o v e ro p e r a t o ra n dt w ot y p e so fa d a p t i v em u l t i - b i t m u t a t i o no p e r a t o r s f i n a l l y , i nn u m e r i c a le x p e r i m e n t s ，t h i sa l g o r i t h mi sc o m p a r e dw i t ho t h e r a l g o r i t h m sa n dt h e nt h i sp a p e ra n a l y s i st h ee f f e c t i v e n e s so f t h i si m p r o v e da l g o r i t h m c h a p t e r5p r e s e n t san e wh y b r i da l g o r i t h mf o rs o l v i n gt h el a r g e - s c a l ev e r t e xp c e n t e rp r o b l e mb y c o m b i n i n gt h ea d v a n t a g e so fp a r t h e n o - g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m i t d e s i g n sa na d a p t i v es e l e c t i o na n da na d a p t i v eg e n er e c o m b i n a t i o no p e r a t o r e x p e r i m e n t a lr e s u l t ss h o w t h a tt h i sa l g o r i t h mi sm o r ee f f e c t i v et h a nt h eo t h e rt h r e ea l g o r i t h m s c h a p t e r6p r e s e n t sam u l t i - o b j e c t i v ea n t ip - c e n t e rp r o b l e ma n d t r a n s l a t e si ti n t oas i n g l eo b j e c t i v e p r o b l e mb yu s i n g t h el i n e a rw e i g h t e ds u mm e t h o d t h e n ，i t si n t e g e rp r o g r a m m i n gm o d e li s e s t a b l i s h e da n dp a r t h e n o g e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mi sp r o p o s e dt os o l v et h i sp r o b l e m a t l a s t ，w ec a r r yo u tt h en u m e r i c a le x p e r i m e n t sf o rd i f f e r e n tw e i g h t sa n de x p e r i m e n t a lr e s u l t ss h o wt h a t t h i sa l g o r i t h mi se f f i c i e n t c h a p t e r7d e s i g n st w oi m p r o v e dm e t a - h e u r i s t i ca l g o r i t h m st o s o l v eg e n e r a l i z e dm i n i m u m s p a n n i n gt r e ep r o b l e m t h i sp a p e rd e s i g n st w ok i n d so fn e i g h b o r h o o ds e a r c ht oa v o i df a l l i n gi n t o l o c a lo p t i m u mi nt h ei m p r o v e dt a b us e a r c ha l g o r i t h m f i n a l l y , t h et w oa l g o r i t h m sa r ec o m p a r e dw i t h e a c ho t h e ri nn u m e r i c a le x p e r i m e n t sa n de x p e r i m e n t a lr e s u l t ss h o wt h a tb o t ha l g o r i t h m sa r ee f f i c i e n t f i n a l l y , w es u m m a r i z ea n dp o i n to u ts o m ep o s s i b l ed i r e c t i o n so ff u t u r er e s e a r c h k e y w o r d s ：n e t w o r kl o c a t i o np r o b l e m ，s e tc o v e r i n gp r o b l e m , v e r t e xp c e n t e rp r o b l e m ，m u l t i - o b j e c t i v e i i 一 南京航空航天大学硕士学位论文 a n t ip - c e n t e rp r o b l e m , g e n e r a l i z e dm i n i m u ms p a n n i n gt r e e p r o b l e m ，n p h a r d ，m e t a - h e u r i s t i c a l g o r i t h m s i i i 网络选址中的若干模型和算法研究 目录 第一章绪论1 1 1 课题研究的背景1 1 2 选址问题的研究现状。2 1 3 研究的主要内容4 第二章网络选址问题的若干模型6 2 1 集合覆盖问题一6 2 2 最大覆盖问题6 2 3 矿中位问题一7 2 4 卢r 中心问是垂8 2 5 广义最小生成树问题9 第三章元启发式算法1 0 3 1 遗传算法1 0 3 2 模拟退火算法1 0 3 3 禁忌搜索算法1 1 3 4 变邻域搜索算法1 2 3 5 蚁群算法1 3 第四章求解集合覆盖问题的改进遗传算法1 4 4 1 改进的遗传算法：1 4 4 2 数值实验1 7 4 3 结论1 9 第五章求解顶点旷中心问题的单亲遗传模拟退火算法2 0 5 1 单亲遗传模拟退火算法2 0 5 2 数值实验2 3 5 3 结 仑2 5 第六章多目标反旷中心问题及其求解方法2 6 6 1 问题描述及模型建立2 6 6 2 单亲遗传模拟退火算法2 7 6 3 数值实验2 8 6 41 4 ；论3 0 第七章求解广义最小生成树问题的两种方法3 l 7 1 单亲遗传模拟退火算法3 1 7 2 改进的禁忌搜索算法3 2 7 3 数值实验3 4 7 4 结论3 5 结束语3 6 参考文献3 7 致谢。4 0 在学期间的研究成果及发表的学术论文。4 1 i v 南京航空航天大学硕十学位论文 图表清单 图2 1k = 5 ，n = 1 3 的广义最小生成树问题9 图4 1 本章改进遗传算法与在该算法基础上缺少某一改进的对比1 8 图5 1 实例p m e d 0 5 的三种算法对比示意图2 4 图5 2 实例p m e d l 5 的三种算法对比示意图2 4 图6 1 旯= 1 0 0 0 时的多目标反p 中心问题3 0 图6 2 见= 0 9 9 0 时的多目标反p 中心问题。3 0 图6 3 允= 0 9 8 5 时的多目标反p 中心问题3 0 图6 4 允= 0 9 8 0 时的多目标反p 中心问题3 0 图6 5 允= 0 0 0 0 时的多目标反p 中心问题3 0 表4 1 本章改进遗传算法与b e a s l e y 等【i6 】遗传算法实验结果对比1 7 表4 2 本章改进遗传算法与陈亮等【1 8 】遗传算法实验结果对比1 8 表5 1 本章p g a s a 算法与b s 【4 6 1 、a 4 7 、s a t 2 2 】的结果比较2 3 表5 2 本章混合算法与其他算法策略的结果比较2 4 表6 1 见取不同值情况下各最优目标函数值对比2 9 表7 1 本章p g a s a 算法与t s 算法的对比3 5 v 南京航空航天人学硕士学位论文 第一章绪论 1 1 课题研究的背景 1 9 0 9 年，来自德国的a l f r e dw e b e r 研究了如何在平面上确定一个仓库的位置使得仓库 与多个顾客之间的总距离最小的问题【1 】( 称为韦伯问题) ，正式开始了选址理论的研究。1 9 6 4 年，h a k i m i 在文酬2 】中提出了网络上的p 一中位问题和旷中心问题，这一篇具有里程碑意义 的论文大大激发了选址问题的理论研究，从而引起了一直持续到现在的研究热潮。 选址问题在生产生活、物流、区域规划甚至军事中都有着非常广泛的应用，如i 【厂、仓 库、急救中心、消防站、垃圾处理中心、物流中心、大型商场、超市、导弹仓库的选址等， 跨越经济、政治、社会、管理、心理及地质工程等多门学科。对于决策者，选址是最重要的 长期决策之一，选址的好坏直接影响设施的服务方式、服务质量、服务效率、服务成本等， 从而影响企业利润和市场竞争力，甚至决定了企业的命运。好的选址会给人民的生活带来便 利，降低成本，扩大利润和市场份额，提高服务效率和竞争力；差的选址往往会带来很大的 不便和损失，甚至是灾难，所以，选址问题的研究有着重大的经济、社会和军事意义。 选址问题的研究从上世纪六十年代发展到现在，吸引了许多领域的学者来参与研究，问 题的研究也呈现多样化，不同的评价标准会有不同的分类方式【3 】，总的来说有以下几种： ( 1 ) 离散选址和连续选址 这是针对网络选址而言的，当服务设施候选地点被限制在网络节点上的时候，这样的网 络选址问题称为离散选址问题，又称顶点选址问题；当服务设施候选地点可以在网络节点或 边上的任何位置时，这样的网络选址问题称为连续选址问题，也叫绝对选址问题。 ( 2 ) 树选址和一般图的选址 这是针对网络选址而言的，根据选址问题是在树上还是在一般网络上来分类。当选址问 题中的需求点和服务设施可以在某个生成树上进行时，称其为树选址问题，否则称为一般图 的选址问题。 ( 3 ) 带固定费用的选址问题和不带固定费用的选址问题 根据选址模型中是否考虑服务设施的建造成本来分类，当选址问题中要考虑服务设施建 造的初始成本时称为带固定费用的选址问题；否则称为不带固定费用的选址问题。 ( 4 ) 带容量限制的选址问题和不带容量限制的选址问题 根据服务设施的容量或服务能力是否受某种限制来分类。选址问题中的服务设施的服务 能力是有限制的选址问题称为带容量限制的选址问题；否则，选址问题中的服务设施的服务 能力是无限的，或不需要考虑它的限制时的选址问题称为不带容量限制的选址问题。 ( 5 ) 静态选址问题和动态选址问题 根据输入变量是否随着时间的不同而变化来分类。当设施建造成本、需求点的需求量、 网络选址中的若干模型和算法研究 服务设施的服务能力等输入变量在整个规划期内是不变的时候，称为静态选址问题：否则， 当这些输入变量在不同时期有所变化时，称为动态选址问题。 ( 6 ) 确定型选址问题和概率选址问题 根据输入数据是确定的还是服从某种随机分布概率而变化进行分类。当设施建造成本、 需求点的需求量、服务设施的服务能力等输入变量是确定常量的时候，称为确定型选址问题： 否则，当这些输入变量是服从某种随机分布概率而变化的时候的选址问题称为概率选址问 题。 ( 7 ) 单目标选址问题和多目标选址问题 根据目标函数是一个还是多个进行分类，研究多个因素之间的背反规律。当选址问题要 考虑多个目标，要分析不同目标之间的背反规律时，称为多目标选址问题；否则称为单目标 选址问题。 ( 8 ) 竞争选址问题和垄断选址问题 根据建造服务设施是否有同行业竞争来分类。选址决策的时候没有同行业竞争对手或不 考虑竞争对手的选址问题称为垄断选址问题；否则称为竞争选址问题。 1 2 选址问题的研究现状 在1 9 世纪6 0 年代中期以前，选址问题的理论研究工作是在几个不相关的领域内展开的， 并没有形成一个统一的理论。1 9 6 4 年，h a k i r n i 对选址问题进行了更加理论化的研究，考虑 了带有一般性的问题：在一个网络中选定一个或多个设施的位置，使得设施到需求点之间的 总距离或设施到各个需求点的最大距离最小。此后选址问题得到了广泛的研究，文献数目急 剧增多。文献 4 - 6 对选址问题有着较为系统的介绍。国内方面，文献 7 、 8 分别综述了 选址研究取得的一些成果。 选址研究中的典型问题，如韦伯问题、覆盖问题、p - 中位问题、矿中心问题、多目标选 址、竞争选址、不受欢迎的设施选址、选址一分配、选址一路线等，都是引起广泛关注和深入 研究的热点课题，研究的也较为成熟。由于很多选址问题都是n p - 难的，所以算法的研究有 很大的余地，现在的研究也大多集中在算法的设计与改进上，尤其是用元启发式算法求解选 址问题的研究。模型的研究主要是对已有模型的改进，使得更适合实际情况。 下面着重介绍集合覆盖问题、旷中心问题、多目标选址问题、不受欢迎的设施选址问题 等的国内外研究现状。 ( 1 ) 集合覆盖问题( s e tc o v e r i n gp r o b l e m ，简称s c p ) 覆盖问题分为集合覆盖问题和最大覆盖问题两类。集合覆盖问题即研究在满足覆盖所有 需求点的前提下，服务设施建造个数或建造费用最少的问题。集合覆盖问题最早一a r o t h 9 j 和t o r e g a s 1 0 1 于1 9 7 1 t g ，用于解决消防中心和救护车等的应急服务设施的选址问题。随后 p l a n e 和h e n d r i c k 】、d a s k i n 和s t e m 1 2 1 建立了服务设施个数最小和备用覆盖的顾客最大的双 目标集合覆盖问题。求解集合覆盖问题的方法方面，最近十几年来许多基于启发式的算法被 2 南京航空航天大学硕士学位论文 用于求解集合覆盖问题，f i s h e r _ ； l i k e d i a t l 3 】提出了基于对偶的启发式算法并用来解决最多有 2 0 0 个候选点、2 0 0 0 个需求点的集合覆盖问题；b e a s l e y f f 【l j o r n s t e n t l 4 】将次梯度优化法和拉格 朗日松弛算法结合起来求解这类问题。k a r p l 证明了集合覆盖问题是n p 一完全问题，即在多 项式时间内不能解决，且容易陷入局部最优。针对这一难题，国内外学者提出了诸如遗传算 法、贪婪算法、蚁群算法等近似求解方法来解决。b e a s l e y 和c h u 【l6 】给出了求解不带权重的集 合覆盖问题的遗传算法。张玉芬等【1 7 1 建立了一种类似于集合覆盖问题的应急服务设施选址 问题的模型，并用改进的遗传算法来解决。陈亮等f 1 8 j 通过对种群中的个体进行启发式改进， 以及遗传参数的选取，提出改进的遗传算法来解决集合覆盖问题。但上述算法在解决规模较 大的集合覆盖问题时不是很有效，不太容易得到全局最优解。 ( 2 ) 旷中心问题( p - c e n t e rp r o b l e m ) p 中心问题是指选定p 个位置建造服务设施，使得所有客户到最近设施距离中的最人值 最小，也就是说，使得最坏情况最优、最大损失最小。顶点p 中心问题是指服务设施备选点 的位置都位于网络图的顶点上。针对这仰难问题，早期的算法多是基于求解一系列集合 覆盖问题和广覆盖问题。当规模较大时，这些算法已不再有效，或者计算时间大大增加。国 内方面，黎青松等【伸1 对于中心问题的研究现状进行了综述，王开华等1 2 0 设计了一种改进置 换迭代法来解决网络p 中心问题。最近几年，多种元启发式算法被提出用于解决顶点p 一中心 问题，m l a d e n o v i c 等f 2 l 】提出禁总搜索和变邻域搜索来解决顶点p 中心问题，b f i y i i k b a s a r a n 等 【2 2 1 提出模拟退火算法来解决顶点p 中心问题。 ( 3 ) 多目标选址问题 通常情况下，不论是公共部门还是私人企业，由于资源所限，设施选址都不会只设定单 一目标，经常将运输( 交通成本) 、投资成本( 建设成本) 、客户服务水平( 在特定时间、距离 为客户提供服务) 、设施能力的“平衡利用”等目标综合考虑。构建此类模型最常用的方式 是将成本最小化作为总目标，将要实现的目标作为限制条件。h e l l e r t 8 】在1 9 8 9 年研究了医疗 服务设施的中位问题，平均运输成本最小已不是唯一目标，同时必须在特定时间内为病人提 供服务。r e v e l l e - 与l a p o r t e 2 3 1 所构建的模型中有两个目标：最小化成本与特定时间内最大程度 满足需求。 ( 4 ) 不受欢迎的设施选址问题 像变电站、垃圾处理站、化工厂、核电站等设施的选址就属于不受欢迎的设施选址问题。 他们的模型一般可以归结为反选址问题，比如说反r 中心问题【2 4 】、反p 一中位问题、反覆盖 问题等，它们的目标正好和对应的经典模型相反。 ( 5 ) 广义最小生成树问题( g e n e r a l i z e dm i n i m u ms p a n n i n gt r e ep r o b l e m ，简称g m s t ) 广义最小生成树问题最先由m y u n g 等网子1 9 9 5 年提出，并且证明它是n p 难的，而且 给出了求解这个问题的分支定界法。f e r e m a n s 等【2 6 l 对于g m s t 的8 个整数规划模型进行了 理论上的比较。f e r e m a n s 等【27 】提出了几类有效不等式以及分支切割法来解决g m s t 。d u i n 3 网络选址中的若干模型和算法研究 等f 2 8 1 把g m s t 转化为斯坦纳树( s t e i n e r t r e e ) f 口7 题，并利用一些专门的算法来解决。近年来， p o p 纠2 9 1 提出了g m s t 的一种新的整数规划模型。 对于g m s t ，当规模比较大时，得到最优解比较困难，这就使得一系列元启发式算法的 提出用来解决这个问题。f e r e m a n s 3 0 1 首先提出用禁忌搜索算法来求解g m s t 。p o p 3 1 】提出模 拟退火算法来解决g m s t 。随后h u 等【3 2 1 提出了改进的变邻域搜索算法来解决g m s t ，并与其 他的元启发式算法进行了比较。g o l d e n 等3 3 提出了一种局部搜索算法和遗传算法来解决 g m s t 。最近，w a n g 等【3 4 1 提出了一种改进的禁忌搜索算法来解决g m s t ，并表示他的算法比 文献 3 3 e p 的遗传算法要有效。t e m e l 等【3 5 1 提出了一种基于属性的禁忌搜索算法，并用这种 算法解决了g m s t 和l g m s t 。国内方面尚没有见到关于这类广义最小生成树问题的研究。 从以上的研究现状分析可以看出，国内对选址问题的研究尚未形成体系。优化模型研究 中根据基本选址模型进行简单应用推广研究的多，理论创新研究的少；模型研究中平面选址 研究的多，网络选址研究的少。在现实的选址决策中很多还是凭感觉，进行科学量化分析后 再进行选址决策的企事业组织很少，这与我国选址基础理论研究的落后是不无关系的。大多 数国内文献在算法上过于简化介绍，多数文献不给算法或算例，给出算法的文献中的绝大多 数没有对其效果进行充分的实验对比证明，给出实验数据的文献由于算例的规模过小，不足 以证明其在实际运用中的效果。对于大多数网络选址问题，寻找这类问题最优解的经典算法 就是分支定界法或割平面法等。然而，这些方法只能解决网络选址问题中的一些小规模的例 子，用这些经典的算法解决这类大规模的问题受到了计算机的内存和计算时间的限制。如前 文所述，很多网络选址问题模型己被证明是n p 一难问题，在当前的计算技术下难以求得最优 解，所以退而求其次，运用元启发式算法寻求决策问题的满意解，而不一定要得到最优解。 常用的元启发式算法在选址问题的国内文献中也都有所应用，比如模拟退火算法、蚁群算法、 禁忌搜索算法、遗传算法等。 1 3 研究的主要内容 本文主要研究了网络选址问题中的集合覆盖问题、顶点p 一中心问题、多目标反p 一中心问 题及广义最小生成树问题。虽然解决这些模型已经有了一些经典的算法，但由于这些问题属 于n p - 难问题，当规模比较大时，传统的算法不再有效或者计算时间大大增加，于是，元启 发式算法等近似求解法来解决这些问题就显得非常必要。本文针对这些模型提出改进的元启 发式算法来求解。 首先，在第二章介绍了一些经典的网络选址问题，包括集合覆盖问题、最大覆盖问题、 p - e f t 位问题、p 一中心问题、广义最小生成树问题。第三章介绍了一些元启发式算法，包括遗 传算法、模拟退火算法、禁忌搜索算法、变邻域搜索算法以及蚁群算法。 其次，针对规模较大的集合覆盖问题，本文提出改进的遗传算法进行求解。该算法对标 准遗传算法的改进主要表现在：1 ) 结合启发式算法和随机生成，设计了一种新的产生初始 4 一 南京航空航天大学硕士学位论文 种群的方法：2 ) 引入修补操作处理不可行解使其转换成可行解；3 ) 对重复个体进行处理再 利用；4 ) 对多点交叉进行推j 一，提出了一种新的交叉算子；5 ) 针对可行解和不可行解，采 取两种自适应多位变异操作。最后在数值实验中与其他算法进行了比较，并分析了算法改进 的有效性。 再次，针对规模较大的顶点p 一中心问题，通过综合遗传算法和模拟退火算法的优点，提 出了一种单亲遗传和模拟退火的混合算法来解决顶点p 一中心问题。该算法：1 ) 采用单亲遗 传算法，来简化遗传操作过程：2 ) 加入模拟退火策略，来增强局部优化能力；3 ) 提出自适 应选择法，根据个体的优劣及算法迭代情况来选择个体；4 ) 设计了自适应基因重组操作： 5 ) 采取最优保存策略，来避免最优解的丢失。最后在数值实验中与其他三种算法进行了比 较，结果表明本章算法更有效。 然后，结合实际情况，对旷中心问题进行推广，提出多目标反旷中心问题，并采用线性 加权和法将多目标问题转化为单目标问题来解决，给出了其整数规划模型，并且设计了相应 的单亲遗传模拟遐火混合算法来求解这个问题，最后给出了数值实验。 紧接着，针对广义最小生成树问题，设计了两种改进的元启发式算法来求解。在改进的 禁忌搜索算法中，通过在两种邻域进行搜索来避免陷入局部最优。最后通过数值实验对这两 种算法进行了比较，并验证了算法的有效性。 最后，总结全文，并且指出了研究：1 ：作的不足及未来的研究方向。 本文中所有数值实验的运行环境都是：计算机配置：p e n t i u m ( r ) ，1 8 6 g h z ，内存为 8 9 6 m b ，操作系统为w i n d o w sx p ，使用的编程软件是m a t l a b7 0 。本文中的算例除了第七章 求解广义最小生成树的一些算例以外，其他的算例都来自于o r - l i b r a r y ，这些数据可以 从网站h t t p ：p e o p l e b r u n e l a c u k - - m a s t j j b j e b i n f o h t m l 上下载得到。 5 网络选址中的若干模型和算法研究 第二章网络选址问题的若干模型 网络选址问题【6 】一般都采用混合整数规划模型来表示。网络选址阿题一般采用的距离是 图中的最短路，比如p 中位问题和p 中心问题及其衍生问题，也有采用的是，。模距离。有一 类设施选址以最大距离为标准，主要考虑服务的平衡，比如医院，消防站等一些应急设施的 选址，这类问题主要有集合覆盖问题、最大覆盖问题、p 中心问题；还有一类模型是以距离 之和为标准，主要考虑运输费用问题，像一些物流中心，超市等的选址问题，主要包却- 中位问题等：另外还有一类模型与前面两类不同，前两种模型主要确定各个设施的位置以及 顾客的分配情况，而这类模型与路径有关，如输油管道、天然气管道及自来水管道等的确定， 主要有广义最小生成树问题。下面将对以上模型逐一介绍。 2 1 集合覆盖问题 集合覆盖问题( s e tc o v e r i n gp r o b l e m ，简称s c p ) 是运筹学研究中典型的组合优化问题之 一，在人员调动、网络安全、资源分配、电路设计、运输车辆路径安排等领域都有广泛的应 用【3 6 1 。s c p 的一个典型应用描述如下：要在一个城市建造若干个消防队驻扎地，使得全城的 每一个建筑物都能在某个消防队的5 分钟车程内。在不同的地方建造驻扎地都有相应的代 价，那么在哪些地方建造驻扎地能满足上述条件且花费的总代价最低就成为待解决的问题。 类似的例子有超市、商场、物流中心等大型场所的选址问题。 设a = ( a f ，) 是一个给定的m 行n 歹o f o o - 1 矩阵，其中f m ，j n m = 1 ，2 ，m j ， n = 6 , 2 ，n 分别表示矩阵a 的行和列的集合。c = ( c ，) ，j n ，其中c j 表示列歹的代 价，有c ， 0 ，n 。如果a f = 1 ，说明行f 被列_ ，覆盖；如果a 移= 0 ，说明行f 没有被 列，覆盖。s c p 就是要找到这样一个列的集合x ( xs ) ，使得m 中的每一行都能被集合 x 中的至少一列覆盖，且x 中所有列的代价之和最小。s c p 的整数规划模型如下： 卫 m i n c ，x ， ( 2 1 ) i = z s i - t 口i _ 1 ， 一h j 户i 工， o ，1 ， f = 1 ，m ， _ ，= 1 ，l ( 2 2 ) ( 2 3 ) 目标函数( 2 1 ) 表示要求总代价之和最小：约束( 2 2 ) 表示矩阵彳的每一行都要被至少一列覆盖 到；约束( 2 3 ) 中，= 1 表示列包含在x 中，x ，= 0 表示列不在x 中。如果每一个 c ( j ) 都相等，那么就叫做不带权重的s c p ，反之则叫做带有权重的s c p 。 2 2 最大覆盖问题 6 南京航空航天大学硕士学位论文 从集合覆盖问题的模型中可以看出，集合覆盖问题是要求覆盖所有需求点的情况下确定 在哪里设立服务设施，和设立多少个服务设施的问题。集合覆盖问题有一个明显的特点，就 是没有考虑需求点的需求量的大小的差别。在许多应用场合，决策者发现有时在有限的资源 下为所有顾客建立服务设施是不可能的，这种情况下，决策目标就转变为在给定的资源下( 同 定的服务设施数目) 覆盖尽可能多的顾客需求，这样的问题就是最大覆盖问题。 最大覆盖问题( m a x i m u mc o v e r i n gp r o b l e m ，简称m c p ) 是研究在服务设施的数目和服务 半径已知的条件下，如何设立p 个服务设施使得可接受服务的需求最大的问题。同其它基本 问题一样，最大覆盖问题也是n p - 难问题。最大覆盖问题可以用以下模型表示： m a x h f z ， ( 2 4 ) f e u s t x ，- - z f 0 ， v u ，u ， ( 2 5 ) v j e n t o = p ， ( 2 6 ) v j e v t ， o ，1 ) ，v v j v ， ( 2 7 ) 乞 o ，1 ，v u f u ， ( 2 8 ) 其中：u ：表示需求点的集合；y ：表示设施备选点的集合；忽：表示需求点u ，的需求量； p ：表示要建设施的数目；以：表示需求点u f 到设施点p j 的距离；4 ：表示覆盖距离； n i = v jl 以d 。) ：表示能够覆盖需求点u f 的设施点集合。 目标函数( 2 4 ) 是求被覆盖的顾客的需求量之和的最大值；不等式约束( 2 5 ) 保证每个顾客 至少被一个设施所覆盖：等式约束( 2 6 ) 表明所要建立设施的数量。决策变量x ，= 1 表示在点 v ，建立设施，否则不建：决策变量z i = 1 表示点u ，被设施覆盖，否则z i = 0 。 2 3 p 一中位问题 ，中位问题白m e d i a np r o b l e m ) 是由h a k i m i q ：1 9 6 4 年首先定义的【2 】。p 一中位问题是指在 备选集里选定p 个点建造设施，使得需求点到离它最近设施的加权距离总和最小。矿中位问 题对模拟现实世界比如公共场所、仓库等的选址非常有用，目标是寻求最小费用。该问题是 n p 一难的。矿中位问题也可以这样描述：在有，1 个节点的图上选择p 个设施的位置，使得图上的 需求节点到最近设施的距离和最小。 p 一中位问题可用整数规划模型描述如下： m i n l 略均 ( 2 9 ) 工j = p ， v j e v z y 盯= 1 ， v u ，u ， v ，e y ( 2 1 0 ) ( 2 1 1 ) 7 网络选址中的若干模型和算法研究 一x j 0 ， 均 o ，1 ) ， x j 0 ，1 ) ， v u ，u ，v ，v ， v u ，u ，v ，v ， v v j v ， ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 其中：u ：表示需求点的集合；v ：表示设施备选点的集合；忽：表示需求点f 的需求量； p ：表示要建设施的数目；办：表示需求点u f 到设施点1 ，的距离。 目标函数( 2 9 ) 是求各个顾客到最近设施的加权距离和；等式约束( 2 1 0 ) 限定建设的设施 数量；等式约束( 2 1 1 ) 保证每个顾客的需求都可以得到满足；不等式约束( 2 1 2 ) 表明只有建好 的设施才能服务顾客。决策变量x ，= 1 表示在点v ，建立设施，否则不建；决策变量y 驴= 1 表 示顾客u ，被设施v ，