《元启发式算法在离散选址中的应用》由会员分享，可在线阅读，更多相关《元启发式算法在离散选址中的应用（43页珍藏版）》请在金锄头文库上搜索。
1、南京航空航天大学 硕士学位论文 元启发式算法在离散选址中的应用 姓名：王其涛 申请学位级别：硕士 专业：运筹学与控制论 指导教师：蒋建林 2010-12 南京航空航天大学硕士学位论文 I 摘 要 本文主要研究的是元启发式算法在设施选址问题中的应用。 首先，本文简单介绍了设施选址问题的背景、发展以及研究现状，介绍了一些经典的设施 选址问题的模型，包括p-中位问题、p-中心问题、集合覆盖问题，还介绍了竞争选址问题的 两个模型：最大市场份额模型和预先抢占市场模型。竞争选址问题是选址问题中比较有代表性 的问题，也是现实生活中常见的优化问题，它主要考虑了在市场上存在两个以上的同类产品或 服务的提供者，或
2、服务设施提供多个产品或服务的情况下的设施选址问题。选址问题，包括竞 争选址问题，其中很多都是NP-难问题，因此，对于这类问题，现有的算法很难找到一个最优 解，现在很多学者的思路是根据模型的特点，对算法不断的改进，以期望得到一个有效的解。 求解选址问题的算法有很多，本文简单介绍了几种常见的元启发式算法：禁忌搜索算法、模拟 退火算法、遗传算法、蚁群算法等。 其次，本文主要研究了三个模型。一是最大市场份额模型，本文在存在预算总成本的约束 下，讨论了距离和设施规模对决策者的影响，同时，本文提出了最大最小蚁群算法和禁忌搜索 算法相结合的求解方法；二是p不定的p-中位问题，模型在考虑设施的建设费用的同时，
3、提 出了新的设施建设费用的计算公式。在求解方法上，本文尝试了启发式算法、禁忌搜索算法和 遗传算法；三是经典的p-中位问题，本文对变邻域搜索算法进行了改进，在搜索局部最优解时 采用了蛛网搜索方法，提高了搜索的效率。 关键词：设施选址，竞争选址，NP-难，元启发式算法，最大市场份额，p-中位问题 元启发式算法在离散选址中的应用 II Abstract This paper mainly discusses the applications of meta-heuristic algorithms in facility location field. Firstly, we introduce t
4、he background, development and research status of facility location, and some classical facility location problems, including p-midian problem, p-center problem, set covering problem. Two competitive facility location problems are also presented. One is the maximal market capture model and the other
5、 is the preemptive capture location model. The competitive facility location problem is not only a typical facility location problem, but also a common optimization problem in real lives, which mainly consider two or more providers providering congeneric products or service, or the provider provider
6、ing multi-products or services. Many facility location problems including competitive facility location problems are NP-hard, and therefore for this type of problems it is difficult to find out their optimal solutions. Now, many scholastics are aimed at improving the algorithm according to the chara
7、cteristics of the models so that an efficient solution can be obtained. There are plenty of algorithms solving facility location problems, and in this paper we simply discuss several kinds of metaheuristic algorithms, which include tabu search, simulated annealing, genetic algorithm and ant colony o
8、ptimization etc. Secondly, we consider three facility location models in this paper. The first one is the maximal market capture model with the constraint of total budget cost. We discuss the influences of the distance and the scale of facility to the policymakers. Meanwhile, a hybrid method of maxi
9、min ant colony algorithm and tabu search is proposed for this model. The second model is p-median problem with p uncertain where the construting cost of facilities are considered and a new formula for the cost is used. This paper proposes a heuristic, a tabu search algorithm and a genetic algorithm
10、for solving this model. The third model is the classic p-median problem and a new variable neighborhood search algorithm is proposed which uses the nested neighborhood transform ideas in the neighborhood search and a cobweb search in finding out a local optimal solution. Keywords: Facility location;
11、 Competitive location; NP-hard; Meta-heuristic methods; Maximal market capture model; p-Median 南京航空航天大学硕士学位论文 V 图表清单 图 2.1 模拟退火算法的一般流程图12 图 2.2 遗传算法的一般流程图13 表3.1 不同 B 和组合下， 公司A的市场份额值及选址策略.19 表 4.1 VNS_G 和 VNS_S 两种方法的比较.25 表 4.2 VNS 和 G+I，TS_1，TS_2 四种方法的比较25 表 5.1 轮盘赌选择法的选择概率计算31 表 5.2 禁忌搜索算法和遗传算法的对比
12、32 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 （保密的学位论文在解密后适用本承诺书） 作者签名： 日 期： 南京航空航天大学硕士学位论文 1 引言 选址问题是运筹学中经典的问题之一，研究的内容十分广泛，从城市、产业带、经济技术 开发区、跨国公司分公司到
13、水利设施、销售网点、机场以及仓库、配送中心等的区域决策都是 选址研究的范畴。它涉及经济学、社会学、政治学、地理学、工程学、心理学、系统论、运筹 学等多门学科。 设施选址是众多选址问题中的一个重要的研究领域。1909 年，德国学者阿尔佛雷德韦伯 1(Alfred Weber)发表了第一篇选址论文，提出了著名的 Weber 问题，标志着设施选址问题的科 学研究正式开始。在其以后的 100 多年的历史中，很多学术工作者对选址问题进行了深入的研 究并取得了很多研究成果，推动了选址问题的发展。 在设施选址的研究中，形成了三个基本的选址问题：p-中位问题、p-中心问题和覆盖问 题。对于这三种基本的选址问题
14、的研究开始的比较早，建立的模型和设计的算法都比较完善， 也得到了很多的研究成果，为以后设施选址的深入发展提供了一个很好的理论基础。在基本选 址问题的基础上考虑其他因素就形成了扩展选址问题。扩展选址问题根据不同的分类标准，又 分成了很多小的问题，比如带固定费用和容量限制的选址问题2、截流问题3、Hub 问题4,5、 选址-分配问题6,7、随机选址问题8,9、竞争选址问题10,11、动态选址问题12,13等。由于很多选 址问题都是 NP-难问题，利用现有的算法很难找到问题的最优解，所以现阶段，对于选址问题 的研究主要集中在如何建立适当模型和设计有效的算法上，很少在理论上进行证明。 竞争选址是设施选
15、址中的一个很有代表性的问题，特别是随着市场经济的发展，竞争无处 不在，使得竞争选址问题受关注的程度越来越高。竞争选址问题指的是市场上存在两个或两个 以上的同类产品或者服务的提供者或设施，通过空间选址和设施设计达到最大化市场份额或者 最大化利润的目标。最早的竞争选址模型是由 Hotelling14在 1929 年提出来的，讨论了海滩上 两个卖冰激凌的小商贩的摊位选址问题，他假设顾客均匀分布在一维有限线性市场上，尽管市 场的形状过于简单，但是模型反映了竞争选址的一些性质，并给出了一些富有启发性的结果。 1986 年，Econimide15对原始的 Hotelling 模型进行了修改，假设产品具有二
16、维特性，除了位置 因素， 还有价格因素， 发现在非合作的策略下， 对称分布的双寡头公司竞争存在均衡价格。 1989 年， Friese 等16研究了网络上生产厂商的竞争选址问题， 并证明了存在选址产量均衡解； 1991 年，Labbe 和 Hakimi17在前者研究的基础上考虑了设施可以重新设置的情况；Rhim 等18考虑 了竞争生产企业同时进入和相继进入市场两种情形，建立了三阶段模型，首先做出第二、三阶 段产量和配送数量的选择，其次决定第一阶段的选址，并给出了企业同时进入选址时，均衡产 量存在的充分条件；2001 年，Plastria19对静态竞争选址问题进行了综述，考虑了区分竞争选址 元启发式算
