第一章绪论
1.1设施选址研究综述
.1设施选址研究的意义
设施选址是个古老而又新鲜的问题。随着经济的发展，城市规划与设施建设越来越受到管理层的重视。作为个体与社会联系之纽带的设施，从个人角度来说，它影响
到人们能否享受到服务以及服务质量的好坏;从社会角度来讲，它对于城市经济、产业布局、环境保护等方面都具有非常重要的战略性意义。
理论上，设施选址问题研究的是在规划区域内如何选定一个或多个设施的地理位置使得既定目标最优，它在生产、生活、物流、军事中都有着广泛的应用，如仓库、
超市、快餐店、加油站、物流中心、医院、电厂、消防站、垃圾填埋场、核电站的选址等。
应用中的选址决策需要选址的理论研究合理解释其决策行为，为其奠定坚实的理论基础，更需要深入的研究为未来重大的选址决策指明方向。科学、合理的设施选址
可以有效地节约资源、降低成本，确保提供优质的服务，优化网络结构和空间布局，提高经济效益和社会效益。
.1.2设施选址研究的发展历程
古代的选址决策往往以经验、制度甚至迷信思想为依据，缺乏科学性。1909年德国学者Weber< I]第一篇选址论文的发表标志设施选址问题的科学研究正式开始。在其
发展的百年历史中，各时期研究的侧重点各有不同，按时间可分为三个阶段[f2] . (1)零散研究阶段(19091960's)
该阶段主要是经济学者研究解决生产、生活中的各种实际问题，内容较为零散。早在1909年德国经济学家Weber为解决单个仓库选址，使得仓库到多个顾客间的总
距离最小的问题，在欧氏空间里建立了1一中值选址问题模型，这就是著名的Weber问题【I]。另一位早期研究设施选址问题的学者Hotelling在其1929年发表的论文[[3]中
考虑海滩上两个买冰淇淋的小商贩在一条线段上的竞争选址问题。随后Smithiesf4],Stevens}s}对此问题进行了更深入的研究。1956年区域经济学家Isard还从土地利用、
投入产出等角度入手对工业区位的选择进行分析。上世纪50年代，越来越多的研究者偏重于设施选址的实际应用，包括产品销售网点的分布与设计、消防设施选址、固
体废料处理点选址、电话网络程控交换设备选址、铁路货运编组站选址等。
(2)系统研究阶段(1960's} 1980's)
1964年，Hakimi首先提出了网络P一中位问题，解决在通信网络中设置多个交换机的位置和在高速公路上确定多个警察局点的问题。该论文是设施选址研究系统发展
的里程碑。此后，选址问题被引入一个更宽广的领域，包括急救设施选址阁、交通枢纽选址[f}l、变电站选址[}8l等，掀起了自那以后一直持续到现在的研究热潮，研究方法
也更集中于运筹学、拓扑学。
(3)不确定性问题和竞争问题研究阶段(1980's至今)
进入上世纪80年代，随着市场变化的加剧，实际生产、生活中运输时间、需求量、需求的空间分布以及设施建设成本等输入变量的不确定性加强，此外，商业经济的发
展带来的选址竞争，造成以往静态、确定性的选址模型与方法己不能适应选址研究的发展，随机选址问题和竞争选址问题成为众多学者关注的焦点。
1985年Domschke和Drex1}9}列出了1500多篇关于设施选址的文献，此后选址方面的文献日益丰富起来。Louveaux}l0}, Mirchandani等[‘’]、Weaver与Church[ 12}等学者在对
不确定中值问题研究时均将运输时间与需求设为随机变量;Berman与Odoni}l3} ,
Berman与Leblanc}}}将运输时间或运输成本设为不确定系统变量，研究随机网络的交通问题【lad; Larson}}s]首先将排队论应用在选址模型中，主要研究紧急救助组织的车辆区
位与服务范围，作者假设区内、区际间呼救时间呈Poisson概率分布、服务时间服从指数分布，构建了一个多服务者排队系统;Brandeau与Chiu} 16}研究单个设施的随机排
队选址问题，考虑排队与交通时间延迟情况下服务客户的最短反应时间;Silva和Serra}l}]研究了以平均时间(总时间等于旅行时间加等待时间)最小为目标的模型，并用
蚁群算法得到了问题的精确解。竞争选址方面的综述见本章第二节。
此外，Cooper提出了选址一分配问题的研究思路，并给出了精确极值和启发式两种算法来解决该类问题ya>’”]。Eiselt}20}综述了选址模型在不同领域的应用，Brimberg
和ReVelle}21]解决了ReVelle与Laporte}22}在综述中指出了选址领域具有挑战性的问题之一—投资回报率最大的问题。Current}23> > Yang}2a]综述了最新的选址进展。
至今，选址问题的研究已有百年的历史，从最初的单一设施选址到多个设施选址，从直线、平面上的布局到网络上的规划，从确定的参数到随机的分布，来源于实践的
参考文献
Weber, A. On the location of industries[M]. Chicago: University of Chicago Press, 1909
王非，徐渝，李毅学.离散设施选址问题研究综述[[J].运筹与管理，2006, 15, (5): 64-69
Hotelling, H. Stability in competition[J]. Economics Journal, 1929, 39: 41-57
Smithies, A. Optimum Location in Spatial Competition[J]. The Journal of Political Economy,
1941, 49, (3): 423-439
Stevens, B H. An application of game theory to a problem in location strategy[J]. Papers in
Regional Science,1961, 7, (1): 143-157
Toregas, C, Swain, R, ReVelle, C. The location of emergency service facilities[J]. Operations
Research, 1971, 19, (7): 1363-1373
Berman, O, LeBlanc, B. Location-relocation of mobile facilities on a stochastic network[J].
Transportation Science, 1984, 18, (4): 315-330
Hochbaum, D S. Heuristics for the fixed cost median problem[月.Mathematical programming,
1982, 22, (1): 148-162
Domschke, W, Drexl, A. 'ADD-heuristics' starting procedures for capacitated plant location
models[J]. European Journal ofqperational Research, 1985, 21, (1): 47-53
Louveaux, F V Discrete stochastic location models[J]. Annals of Operations Research, 1986, 6,
(4): 23-34
Mirchandani, P B, Oudjit, A, Wong, R T. 'Multidimensional' extensions and a nested dual
approach for the m-median problem[J]. European Journal of Operational Research, 1985, 21,
(1): 121-137
Weaver, J R, Church, R L. Computational procedures for location problems on stochastic
networks[J]. Transportation Science, 1983, 17, (2): 168-180
Berman, O, Odoni, A R. Locating mobile facilities on a network with Markovian properties[J].
Networks, 1982, 12: 73-86
Owen, H S, Daskin, M S. Strategic facility location: a review[J]. European Journal of
Operational Research, 1998, 129, (11): 423-447
Larson, R. A hypercube queuing model for facility location and redistricting in urban
emergency services[J]. Computers and Operations Research, 1974, 1:67-95
Brandeau, M L, Chiu, S S. A unified family of single-server queuing location models[J].
Operations Research, 1990, 38: 1034-1044
Silva, F, Serra, D. Locating emergency services with different priorities: the priority queuing
covering location[J]. Journal of the Operational Research Society, 2007, in press
Cooper, L. Heuristic Methods for Location-Allocation Problems[J]. SIAM Review, 1964, 6, (1):
1一18
Cooper, L. Location-Allocation Problems[J]. Operations Research, 1963, 11, (3): 331-344
Eiselt, H A. Location Modeling in Practice[J]. American Journal of Mathematical and
Management Science, 1992, 12: 3-18
Brimberg, J, ReVelle, C. The maximum return-on-investment plant location problem[J]. Journal
of the Operational Research, 2000, 51:729-735
ReVelle, C, Laporte, G The plant location problem: New models and research prospects[J].
[l1[21[3][4]
摘要 5-7
ABSTRACT 7-8
第一章 绪论 14-28
1.1 设施选址研究综述 14-20
1.1.1 设施选址研究的意义 14
1.1.2 设施选址研究的发展历程 14-16
1.1.3 选址研究的目标 16
1.1.4 选址研究中的经典问题 16-18
1.1.5 选址问题的求解算法 18-20
1.2 竞争选址问题 20-26
1.2.1 竞争选址研究的意义 20
1.2.2 竞争选址研究的发展历程 20-22
1.2.3 影响竞争选址的要素 22-25
1.2.4 竞争选址研究中的经典模型 25-26
1.3 本文的创新点与结构安排 26-28
第二章 基于Voronoi图的平面区域划分和节点选址问题 28-40
2.1 问题的提出 28
2.2 研究背景 28-29
2.3 平面单连通域的区域划分和节点选址模型 29-37
2.3.1 Voronoi图和Delaunay三角网 29-30
2.3.2 模型的构建与分析 30-32
2.3.3 模型解的性质 32-34
2.3.4 数值算例 34
2.3.5 类似于“地图着色”的信道分配方案 34-35
2.3.6 基于最小生成树算法的连通性与抗毁性研究 35-37
2.4 平面复连通域的区域划分和节点选址模型 37-39
2.4.1 模型的构建与分析 37-38
2.4.2 蒙特卡罗仿真 38-39
2.5 小结 39-40
第三章 连锁超市竞争选址定价问题 40-58
3.1 问题的提出 40-41
3.2 研究背景 41-43
3.2.1 影响超市选址相关因素 41-42
3.2.2 决定顾客光顾行为的经典理论与模型 42-43
3.3 顾客随机光顾行为下的网络选址定价博弈模型 43-45
3.4 模型解的定义与解的性质 45-50
3.5 模型的混合启发式算法(LPGH)设计 50-52
3.5.1 禁忌搜索算法的参数设置 50-51
3.5.2 LPGH流程 51-52
3.6 数值算例及分析 52-57
3.6.1 数值算例 52-56
3.6.2 对于管理层的启示 56-57
3.7 小结 57-58
第四章 竞争选址定价的双形式博弈问题 58-62
4.1 问题的提出 58
4.2 研究背景 58-59
4.3 竞争选址定价的双形式博弈模型的构建 59-61
4.3.1 竞争选址定价的双形式博弈模型 59-61
4.3.2 模型的求解方法及分析 61
4.4 小结 61-62
第五章 物流网络中的路线规划和车辆调度问题 62-71
5.1 问题的提出 62
5.2 研究背景 62-64
5.3 物流网络中的路线规划和车辆调度模型 64-67
5.4 模型算法设计 67-70
5.4.1 蚁群算法 67-68
5.4.2 利用罚函数改进的蚁群算法 68-70
5.5 小结 70-71
第六章 结论与展望 71-73
6.1 结论 71
6.2 未来研究的展望 71-73
参考文献 73-80
致谢 80-81
攻读硕士期间发表的论文和参与科研项目 81-82
作者和导师简介