连续设施选址：模型、方法与应用

张 苏， 吴晨晨， 蒋建林， 吕一兵

(1.南开大学 商学院，天津 300071； 2.天津理工大学 理学院，天津 300384; 3.南京航空航天大学 理学院,江苏 南京 210016; 4.长江大学 信息与数学学院,湖北 荆州 434023)

0 引言

早在17世纪早期Pierrede Fermat提出如下问题：平面上有坐标已知的三点，如何在平面上寻找到第四个点使得该点到给定三点的距离和达到最小？该问题即为选址领域中具有重要地位的Fermat问题(Fermat problem)。1909年Alfred Weber将Fermat问题推广到有多个给定点且每个给定点都赋予权重(代表其需求)的情形，因而该问题常被称为Fermat-Weber问题或Weber 问题。一般来说，设施选址领域中将上述给定点称为顾客(customer)，而将需要选址的点称为设施(facility)。尽管Weber问题似乎是有正式记载的最早的选址问题，但实际上设施选址一直伴随着人类历史的发展，它对人类的生活和生产活动有着重要而深刻的影响。

许多学科都存在着各式各样的选址问题，不同学科对问题的描述不尽相同。综合不同学科的描述可得到设施选址最本质的定义为：给定某个度量空间及其中的顾客位置，在该空间中为新设施选址使得由设施和顾客确定的某种目标达到最优。设施选址在现实生活中占据极其重要的地位，甚至具有战略意义。半个多世纪以来随着数学工具特别是优化技术被引入到设施选址中，该领域进入到了蓬勃发展的时期。人们对不同应用领域的设施选址问题进行了深入的研究和分析，建立了优化模型并研究其理论性质，提出了有效的数值算法求解模型并将研究结果应用于解决实际问题。

设施选址问题可以按不同方式进行分类。按照度量空间的拓扑结构设施问题可分为连续选址、离散选址、网络选址。连续选址中新设施可以在度量空间的某连续区域上进行选址。连续选址在选址领域中的研究历史最为悠久，前面提到的Weber问题即为其中的典型问题。离散选址是在度量空间中给定的一系列离散点上进行选址，而网络选址则是在给定图或网络的顶点或边上选址。就求解技术而言连续选址主要采用连续优化的方法如线性与非线性规划进行求解，而离散选址和网络选址由于包含了0-1变量多采用组合优化的方法和(混合)整数规划进行求解。连续选址、离散选址和网络选址在现实生活中均有着重要的应用，它们可用于解决不同情形下的实际问题。本文将对连续选址的模型、算法和应用等方面的研究工作进行回顾、总结并给出一些展望。需要指出的是，离散选址和网络选址的理论和应用研究方面也都取得了大量的重要成果，相关工作请读者们参考[1～5]及其中的文献。

本文将按照如下结构展开连续设施选址工作的论述。第一章介绍连续设施选址中的几个要素；第二章和第三章分别给出连续设施选址中的一些经典模型和拓展模型；第四章概述连续选址中某些重要方法和技术；第五章将简述连续选址在实际生活中的应用；最后一章则对全文进行总结并给出研究展望。

1 连续设施选址中的几个要素

本章将详细介绍连续设施选址中的几个关键元素，包括：新设施个数、距离度量函数、目标函数。其它影响选址决策的重要元素，如设施容量、土地费用、税收政策等，我们在此将不一一赘述。

1.1 新设施个数

设施选址中新设施的个数m(m∈N)可能为1也可能大于1。当m=1时，此时问题一般称为单设施选址(single-source location)问题；而当m≥2时，问题则被称为多设施选址(multi-source location或者multi-facility location)问题。相比于单设施选址问题，多设施选址问题的求解会更加困难，这主要体现在如下几方面：

设施的服务对象。多设施选址中需要考虑顾客到哪个设施获取服务。为方便求解，我们常假设顾客到最近的设施获得服务。然而这一假设并非在所有情形下都成立，如当顾客具有偏好、不同设施提供不同类型的服务等情形。

设施的容量约束。某些情况下顾客所需的服务量是有要求的但设施的容量(即设施能提供的服务量)却是有限的，此时则需考虑设施的容量约束。带设施容量约束的选址问题求解是非常困难的。

设施间的互动。在多设施情形下不同设施间可能存在着相互作用或互动(facility interaction)，此时需在优化问题的目标中引入反映设施间距离的项。

设施数m的确定。某些选址问题中设施数是给定的，但在另一些问题中设施数却是内生变量，需要由选址问题本身在考虑各方面因素(如设施的固定费用、资金预算、选址目的等)后确定。

1.2 距离度量函数

选址领域有各种各样的距离度量函数。范数是一种重要的距离度量函数，因其满足正定性、齐次性和次可加性其度量的距离比较真实地反映了实际距离。lp-范数是连续选址中常用的距离度量函数：当p=1时该范数可以度量l1-距离(也称为Manhattan距离)，该距离常用于表示城市内两点间的距离；当p=2时该范数可以度量欧几里得距离，它表示了两点间的直线距离；当p=∞时该范数度量的距离常被称为Chebyshev距离。某些推广的lp-范数也常用于度量设施和顾客间的距离，比如加权lp-范数(weightedlp-norm，即klp-范数)、加权和lp-范数(weighted sumlp-norm，lbp-范数)等。

当连续设施选址中的顾客在度量空间中占有较大范围时，则不应被简单地视为点而应为区域，于是设施和顾客之间的距离就变为了点和区域的距离。点和区域的距离有多种度量方式，比如点到区域的最近距离、平均距离、最远距离等。文献[6,7]研究了顾客到设施最近距离意义下的选址模型[8,9]，研究了平均距离意义下的选址问题，而[10,11]则讨论了最远距离下的问题。进一步地，当顾客和距离均为所处空间内的区域时，此时距离则应为区域和区域间的距离，上述的最近距离、平均距离和最远距离也需推广到区域间的相应距离，甚至是一些更复杂的距离，如Hausdorff距离[12]。

设施并非总是在Rn空间内选择合适的位置(特别地n=2时即为平面选址)，有时需要考虑在地球表面的某一区域内进行选址。当该区域范围较大时，其不能简单地视为平面的一部分，于是相应的问题就变为了球面选址问题。度量球面上两点间的距离常采用测地线距离，即两点所在的大圆上两点的距离。测地线距离在度量球面上大尺度距离时会更接近于真实值，但测地线距离显然比平面上范数度量的距离更加复杂。球面选址的理论分析和算法设计方面也取得了大量的研究成果，如[13～15]。

由范数度量的距离具有对称性，即由点A到点B的距离等于由B到A的距离。但是距离具有对称性并非在所有情形下都是成立的，比如：交通中同一道路不同向的拥堵情况、海洋中顺洋流和逆洋流航行、高空顺气流和逆气流飞行中都体现出距离的非对称性。当范数定义中的齐次性减弱为正齐次性时，范数将退化为gauge。连续选址中常用gauge度量非对称距离。尽管非对称距离的连续选址研究也取得了一系列成果，但相比于对称距离的选址研究却要少得多。关于非对称距离的研究成果读者们请参考[16,17]。

不同的距离度量函数有着各自的优缺点和适用范围，因此描述实际选址问题时需要我们充分发掘问题的特性以选择合适的距离度量函数，这样才能使得建立的数学模型更符合实际问题，基于该模型的理论、算法与应用研究也才更有意义和价值。

1.3 目标函数

设施选址的目标函数大致可分为拉式目标(pull objective)、推式目标(push objective)和推拉式目标(push-pull objective)三类[18,19]。当设施为顾客所期望(desirable)的类型(如超市、银行、消防站等)时顾客总是希望设施离自己越近越好，因而往往采用拉式目标，如最小化顾客与设施间的距离和、最大化市场占有率等；当设施属于被顾客排斥(undesirable)的类型(如有污染的工厂、垃圾处理站等)时顾客则希望设施离自己越远越好，此时常采用推式目标，如最大化顾客与设施间的距离和、最小化被覆盖的顾客数等；还有些情形下设施的类型介于desirable和undesirable之间，此时问题中将存在吸引和排斥两个相互矛盾或对立的因素，这类选址问题常采用推拉式目标。

Minisum函数是一种常用的拉式目标：最小化顾客与设施间的(加权)距离和，相应的选址问题称为minisum问题。Weber问题即为minisum问题，其设施数m=1。设施数m>1的问题被称为多设施minisum问题，其中包含两类重要问题：multi-facility Weber问题和multi-source Weber问题。Minimax 函数是另一种常用的拉式目标：最小化顾客与设施间的最大距离，相应的模型称为minimax问题。因为该模型关注最远的顾客所以在某种程度上体现了公平性。当m=1时相应的minimax问题为单设施选址问题；而对于m>1的多设施minimax问题其顾客与设施间距离常为顾客与最近设施间的距离。覆盖问题也是使用拉式目标的重要问题。覆盖问题包含最大覆盖和最小(费用)覆盖两类问题：前者是在设施数给定的情形下让设施覆盖尽可能多的顾客，而后者则是在设施个数为变量时用最少的设施覆盖所有的顾客。

与拉式目标类似，maxisum函数和maximin 函数是两种重要的推式目标。Maxisum问题寻求顾客与设施间的距离和达到最大，而maximin则是使得顾客与设施间的最近距离最大化。当设施数m>1时，推式目标的多设施模型可分为max-min-min、max-sum-min、max-min-sum、max-sum-sum等几类，其中第三层的min/sum表示给定顾客到所有设施间的最小距离或距离和。弥散模型(dispersion model)也是一种具有推式目标的重要模型。该模型仅考虑新设施间的最大距离(这也是将其命名为弥散模型的原因)。弥散模型的目标函数也有前述四类，此时第三层的min/sum表示给定设施到其他设施间的最小距离或距离和。即使是单设施推式目标的选址问题一般也是非凸的，求解这类问题时常用到全局优化和计算几何方法。

由于推拉式目标中存在着吸引和排斥两种对立的因素，推拉式目标的选址问题常可建模为双目标优化。于是双目标优化的方法和技术则可有效地用来求解推拉式目标的选址问题，比如：(1) 应用多目标优化的Pareto理论求出Pareto前沿面和Pareto有效点；(2) 给定推式目标的界并将之作为约束条件优化拉式目标；(3)给定拉式目标的界并将之作为约束条件优化推式目标；(4)利用线性加权技术将双目标问题转化为单目标问题求解。

2 连续设施选址经典模型

本章将介绍连续选址中的几种经典模型，这些模型在连续选址领域占据着重要地位。首先，这些模型来源于实际问题，因此其本身就具有重要的应用性；同时基于这些模型可建立大量的更具实用性的选址模型，故这些模型也被称为连续设施选址的基础模型(fundamental models)。

2.1 Weber问题

尽管Weber问题为凸优化问题，其目标函数却是不可微的，如当‖·‖为l2-范数时所有的顾客点处均不可微。选址领域将这一现象称为奇异情形(singular case)。由于Weber问题在连续选址中的重要地位，该模型得到了深入和广泛的研究。学者们提出了数值方法或计算几何方法对其进行求解，同时也将其进行了各种各样的推广。在诸多求解方法中以Weiszfeld方法[20]最为著名。文献[21]证明了该方法本质上为Weber问题的最速下降法，并且分析了该方法的收敛性和收敛速度。进一步地，文献[22]将该方法推广到了求闭凸集约束的Weber问题。为使得Weiszfeld方法能够有效处理奇异情形，一些改进的Weiszfeld方法也不断地被提出[23,24]。 关于Weber问题更丰富的理论与算法结果以及其推广模型的研究请参考[25]。

2.2 Minimax问题

2.3 Multi-facility Weber问题

Multi-facility Weber问题(简写为MFWP)是一种重要的多设施minisum模型，其中每个设施提供的服务类型不同因而顾客需到各个设施处获取服务，同时不同设施间存在着互动(facility interaction)。MFWP的数学模型为：

其中xi为第i个设施的位置，wij为第j个顾客到第i个设施距离的权重，vil为设施xi与xl距离的权重。

与Weber问题一样，MFWP也是凸优化问题且不具备可微性(奇异情形)。Miehle算法是求解l2-范数下MFWP最早的算法，它可以看作是Weiszfeld算法在多设施选址问题上的推广。Miehle算法也存在着与Weiszfeld 算法相同的问题，即不能有效地处理奇异情形，因此其产生的迭代序列可能发散或收敛到非最优解。Hyperboloid approximation procedure(HAP)则是将小正数ε引入到MFWP 的目标函数使其光滑化后再运用类似Miehle的方法求解光滑化问题。HAP可能是目前求解l2-范数下MFWP最标准的算法，其优点在于算法简单易实现，但其缺点也是显而易见的：需选择合适的正数ε。最近文献[28]考虑了一种推广的MFWP，其中的设施带有约束且gauge被用作为距离度量函数。文献基于变分不等式的框架对该问题进行了研究并提出了数值算法：首先将该模型等价地转化为变分不等式，然后基于该变分不等式的特殊结构设计投影算法求解该变分不等式从而得到推广MFWP的最优解。基于变分不等式的方法可有效地处理奇异情形且不需引入小正数ε。

2.4 Multi-source Weber问题

尽管MSWP看似简单，但它却是非凸非光滑的NP-hard问题[29,30]。众多学者对该问题的理论进行了广泛的探讨和研究并提出了有效的数值算法[31]。 在这些算法中最为重要的当属起源于1964年的交替选址-分配类方法。注意到解决MSWP需完成两个任务：确定m个设施的位置以及将n个顾客分配给m个设施。如果顾客已经分配给了m个设施(此时每个设施服务的顾客将形成一个cluster，于是所有顾客就分为了m个clusters)，若针对该顾客分配方式中的每个cluster求解一个单设施的Weber问题则可得到此分配方式下的最优设施位置(选址步)；同样当确定了m个设施的位置后，最优的顾客分配方式应为所有的顾客均到离它最近的设施处获得dj的服务量(分配步)。正是基于如上结论，交替选址-分配类方法设计了每步迭代均包含一次选址步和一次分配步并将选址步和分配步交替进行的迭代格式。在应用某些简单的技术后，文献[16]证明了交替选址-分配类方法能够收敛到MSWP的局部最优解。关于交替选址-分配类方法读者们可参考[32,33]及其中的文献。

2.5 Multi-facility minimax问题

3 连续设施选址拓展模型

本章将简单介绍连续设施选址领域中几类拓展模型。这几类拓展模型中的每一类都是连续选址的重要研究方向。当然除了这几类模型外，连续选址中还有其它重要的拓展模型，如层级选址、动态选址、选址-库存等。关于本章介绍的拓展模型和其他重要拓展模型更详细的研究成果请参考[36,37]。

3.1 不确定设施选址(Facility Location under Uncertainty)

大量设施选址问题考虑的是长期的战略决策。在此期间，情况会发生改变，比如顾客的需求水平、运输的时间或成本、顾客的位置、商品的价格等。因此设施选址时有必要在模型中提前考虑不确定性，以便作出更好的决策。不确定设施选址模型的关键点在于不确定性如何表示。不确定性可用不确定参数来表示，不确定参数既可能是离散型随机变量也可能是连续型随机变量。当概率分布信息可得时，我们一般运用随机规划的模型和算法来考虑随机设施选址问题；当概率分布信息不可得时，鲁棒优化技术可被用来求解鲁棒设施选址问题。

建模时需要考虑决策者对待风险的态度，常用的态度包括风险中性和风险厌恶两种态度。风险中性的决策者考虑的是极小化期望成本或极大化期望收益；而风险厌恶的决策者常使用凹效用函数作为目标，比如寻求极小化最大成本的解。另一个需要考虑的因素为决策为事前决策还是事后决策。前者为当前所做的决策，必须在不确定性揭示之前实施；后者为不确定性揭示之后做出的决策，通常作为对不确定性参数观测值的反应。在设施选址问题中，确定设施位置属于事前决策，这是战略决策的一种自然属性；而分配或分布的决策则取决于问题的特点，它既可能是事前决策也可能是事后决策。

不确定设施选址一般会根据实际问题的特点综合使用多种不确定优化工具。比如文献[38]运用了鲁棒优化求解多阶段带不确定需求的网络设施选址问题，其中使用了箱形和椭球形的不确定集。文献[39]考虑了带容量限制的不确定多设施选址问题，其中将缺货的概率上限作为机会约束。文献中采用了不同的鲁棒优化模型解决该问题。文献[40]考虑了中断风险下的可靠性设施选址问题，其目标为最小化开设成本和包含正常情形和中断情形的期望运输成本。

3.2 枢纽选址(Hub Location)

枢纽是起点和终点之间信息传递的战略性设施。如何在起点和终点之间建立合适的枢纽以便降低服务成本同时提高服务质量，引起了专家学者们的关注。这类选址问题被称为枢纽选址问题。当枢纽建成之后，运输网络就不需要在所有起点/终点之间直接连接，只需要通过枢纽进行运输。为满足起点和终点之间的运输需求，枢纽选址问题涉及起点/终点对之间的人员、商品和信息流动等因素。

在枢纽选址问题中，O’Kelly做出了很多奠基性的重要工作，读者们请参见[41～43]。

3.3 竞争选址(Competitive Location)

当建立新设施时决策者需要考虑很多因素，其中重要的一点为已经在市场中存在的竞争者，此时的选址问题被称为竞争选址问题。

文献[44]首先将竞争机制引入到选址问题中，其中的顾客均匀分布在长度为l的线段上。两个具有竞争性的公司在线段上均开设一个设施为顾客提供相同的产品服务。公司除了需要决策各自设施的位置，还需要决策产品的价格。文献[44]从博弈论的角度给出了该竞争选址问题的纳什均衡点。然而，纳什均衡点在实际中并不稳定：当选址决策或者选址的参数发生细微的扰动，均衡就会被破坏。于是另一种序列竞争选址模型应运而生，即在竞争中竞争的参与者们分别以领导者和跟随者的身份进行斯塔克伯格博弈。文献[45]讨论了平面上跟随者增加一个设施的斯塔克伯格博弈。文献[46]考虑了3个设施的序列选址问题：领导者拥有一个已经存在的设施，跟随者需要建立一个新的设施，之后领导者接着再建立一个设施。文献[47]考虑了一个领导者和多个跟随者的情形。

3.4 厌恶型选址(Obnoxious Facility Location)

很多选址模型的目标函数为最小化。当设施是服务型设施，这样的设置自然是合理的。然而对于另一些设施如垃圾处理站、污水处理厂、核反应堆等顾客则希望这些设施离自己越远越好，即这些设施为厌恶型设施，此时目标函数则变为最大化。

Maxisum厌恶型选址问题与minisum问题相反，需要设置m个设施使得顾客和距离其最近的设施距离和最大。文献[48]考虑了平面上单设施的maxisum厌恶型选址问题。文献[49]考虑了权重有正有负情况下平面上单设施minisum问题，其中的方法可以用于求解maxisum厌恶型选址问题。 Maximin厌恶型选址问题是指最大化顾客到设施的最小距离。文献[50]考虑了平面和球面上单设施maximin厌恶型选址问题。文献[51]研究了l1-范数下单设施maximin厌恶型选址问题，并提出基于线性规划的搜索算法对其进行求解。

此外，顾客对医院、消防站这类设施抱有的是半厌恶的心理，这样就产生了半厌恶型选址问题(参见[52,53])。

3.5 选址-路径(Location-Routing)

选址-路径问题是设施选址问题与路径选择问题的组合。对于制造商和供应商而言，一个关键的问题是如何将产品从仓库分发给位置分散的客户。仓库的位置以及产品的配送路径是影响管理者成本的两个关键因素。因此，确定仓库位置并规划产品配送路径的同时优化构成了选址-路径问题。

早期的连续选址-路径问题通过将两个决策独立处理的启发式方法进行求解：首先求解minisum问题确定仓库的位置，再固定仓库的位置解决多仓库的车辆路径问题[54]。文献[55]将连续选址-路径问题分解为确定仓库位置和规划车辆路径两种操作，并将两种操作交替地迭代进行。文献[56]使用神经网络模型求解连续空间中的单仓库选址-路径问题。文献[57]提出迭代启发式方法求解飞机场的选址-路径问题。文献[58]首次提出了带有取货和送达时间限制的连续选址-路径问题，并利用可变邻域搜索算法求解。

4 连续设施选址常用方法与技术

大量的方法和技术被应用于连续设施选址中求解各种各样的选址问题，而本章仅列出其中几类有代表性的方法，包括：共轭对偶、全局优化、不确定优化、变分不等式、维诺图。

4.1 共轭对偶(Conjugate Duality)

考虑设施选址(原始)问题的如下优化模型形式:

(原始问题)ming0(x0)

s.t.gi(xi)≤0,i∈I,(显式约束)

x0∈C0,xi∈Ci,i∈I,(隐式约束)

x=(x0,xI)∈χ,(锥约束))

(1)

其中gi(xi),i∈{0}∪I是定义在凸集Ci上的闭凸函数，χ为闭凸锥。根据共轭对偶理论，其对偶问题如下:

i∈I,x*∈γ

(2)

可见共轭对偶理论得到的是最小-最小对偶，而非一般的最小-最大对偶。在满足某些可行性和相对内点的条件下[60]，优化问题的最优性条件表达如下:

x0*∈∂g0(x0)

(3)

其中∂gi(xi)表示在xi点gi的次梯度集合。

文献[61]对拓展的多设施选址问题分析了其共轭对偶结果，并以此作为最优性条件。文献[62]在共轭对偶的框架下讨论了带几何约束的线性和非线性单设施minimax问题，并给出了无约束线性minimax问题的对偶问题最优解的几何表示。文献[63]进一步考虑了带扰动最小时间的非线性minimax问题，并在特定的情形下给出了其最优解的理论性质。

4.2 全局优化(Global Optimization)

连续设施选址中存在相当多的非凸模型。导致模型非凸的因素有很多：设施位置的约束具有非凸性；距离度量函数关于设施位置非凸；目标函数为设施位置的非凸函数；模型整体具有非凸性(如MSWP)。正因为非凸选址模型的普遍性，全局优化方法与技术[64～66]在其中具有极为重要的作用。本节仅讨论几种典型的连续选址全局优化方法。

分支定界法。分支定界法是求解(混合)整数规划的重要方法，在离散和网络选址中有着广泛的应用。相对来说，分支定界法在连续选址中的应用要比在离散和网络选址中少。连续选址的分支定界法也包含了分支和定界两个操作：前者将可行域或包含可行域的区域划分为小区域；后者对小区域判断是否删除该小区域或者将其继续划分为更小的区域。分支定界法在连续设施选址中主要表现为Big Square Small Square(BSSS)方法[67]，该方法将选址区域划分为长方形小区域。为了使得BSSS方法计算效率更高或适用范围更广，各种推广的BSSS方法不断地被提出[68～70]。

Lipschitz优化。当连续选址模型的函数满足Lipschitz条件且Lipschitz常数已知时可采用Lipschitz优化求解该模型。Lipschitz优化的思想是生成包含最优目标函数值的区间并不断缩短该区间直至其长度小于给定的精度。由此可见，该方法的迭代过程中需不断更新最优目标函数值的上界和下界。Lipschitz优化的难点在于：(1)Lipschitz常数不容易确定；(2)更新最优目标函数值下界时一般需求解非凸优化问题。

Polyhedralannexation(PA)方法。PA也是求解凹优化问题的重要方法之一，它可被视为OA方法求解凹优化问题的对偶，因此其也具有与OA方法相同的理论收敛性。与OA方法相比，PA方法不需要计算函数的梯度或次梯度(OA中引入直线l时往往需要求函数g(x)的梯度或次梯度)，但是需计算一系列凸优化子问题。

分解方法。大量的优化问题常包含两类变量x和y，即变量为(x,y)。当固定变量y时，优化问题变为仅关于x的易解的优化问题(比如线性规划、凸优化或规模较小的NP-hard问题)。分解方法利用优化问题的这一性质将原问题降为一系列低维的简单问题进行求解。列生成算法被用于求解某些连续设施选址问题，该方法可以被看作为一类特殊的分解方法。

4.3 不确定优化(Optimization under Uncertainty)

在某些设施选址问题中，如果需求不确定但决策者仍希望满足各种可能的需求，此时得到的解将会使得设施的容量大大高于正常的需求水平而造成浪费。一种解决方案为只需要保证一定的服务水平，也就是在某个给定的概率下设施的容量满足总需求即可，于是我们将会考虑带机会约束的设施选址问题。机会约束可被视为选址系统的某种可靠性的度量。

如何定义情景也是不确定优化中的重要问题。有时候情景来源于某些驱动因素(如经济趋势或技术变革)，显然这些驱动因素将影响着模型的输入。一般来说，驱动因素和不确定参数之间是高度相关的。决策者只有在完全理解这些驱动因素后才能够生成情景的完备定义[72]。

4.4 变分不等式方法(Variational Inequality Approach)

变分不等式(variational inequality，VI)是近几十年优化领域研究的热点之一。它一方面可以描述经济、交通、管理领域中大量的均衡问题，另一方面又可刻画约束优化的一阶必要性条件，因此吸引了运筹与优化学者们极大的关注。经过几十年的快速发展，VI无论在理论还是算法上都已经相当成熟同时它在其它领域也已得到了广泛的应用[73～80]。尽管相比于其它选址方法，变分不等式是一类较新的方法，但经过十余年的发展它已成为研究连续设施选址不可或缺的工具之一。

变分不等式方法求解连续设施选址问题的思路为：将凸选址问题或子问题通过原始-对偶等技术转化为等价的变分不等式并基于其特殊结构设计有效的变分不等式求解算法。变分不等式方法求解设施选址问题的优点包括如下方面：(1)基于变分不等式成熟的理论和算法，变分不等式方法为连续设施选址的研究提供了一个不同于以往但非常有效的研究框架；(2)在变分不等式算法设计框架下，变分不等式方法可基于VI问题的特殊结构提出有效的新算法；(3)在变分不等式算法分析框架下，变分不等式方法易于证明新算法的收敛性质；(4)变分不等式方法能同时为设施选址问题提供原始最优解和对偶最优解；(5)变分不等式方法能够有效地解决连续设施选址中的奇异情形。

文献[81]可能是将变分不等式方法应用于连续设施选址研究的首项工作。该文献针对lp-范数下带凸约束的Weber问题提出了变分不等式的投影方法求解该问题。文献[32]针对带凸约束的MSWP 提出了一种新的交替选址-分配方法：选址步利用变分不等式方法设计新算法进行求解；分配步利用最近分配原则将顾客分配给最近设施。该交替选址-分配方法被证明可求得MSWP的局部最优解。文献[82]考虑了不同区域采用不同距离度量函数的Weber问题。由于该问题为非凸优化问题，文献[82]将其划分为3个子问题并对其中2个较复杂的子问题设计了变分不等式方法进行求解。通过从3个子问题的最优解中选择最好的解可求得该非凸Weber问题的全局最优解。文献[28]研究了gauge距离下带凸约束的推广MFWP问题，并在变分不等式框架下提出了新的投影算法(该算法可被看作为非对称PPA方法)求解该问题。

4.5 维诺图(Voronoi Diagrams)

给定平面上的m个点X={x1,…,xm}，根据距离最近的原则将平面划分成m个多边形V1,…,Vm，这样的划分叫做维诺图。构成维诺图的多边形被称为维诺多边形，而点的集合X被称为生成集，其中的点被称为生成点。维诺多边形的数学表达为：Vi=∩j:j≠i{x∈R2|‖x-xi‖<‖x-xj‖}。根据定义，如果点x在Vi内，则xi为最靠近它的生成点。计算几何中设计了很多高效算法计算维诺图，其中两种主要的方法为分治法(divide-and-conquer method)和递增法(incremental method)[83]。分治法在最坏情形和平均情形下计算时间均为O(mlogm)，而递增法在最坏情形下计算时间为O(m2)，平均计算时间为O(m)。

维诺图是一种非常简单的几何构造，它在各个领域具有大量的应用。维诺图的生成取决于距离度量函数，不同的度量函数生成不同的维诺图。计算几何中构造维诺图的高效数值方法可被用来求解连续设施选址问题。特别地，多设施minisum问题和minimax问题均可以运用维诺图求解。算法的一般框架为:

由算法的一般框架可见求解设施选址问题的每步迭代中均使用到维诺图。文献[84]提出了一个带动态需求的混合型设施选址模型，并证明对于n个顾客和m个设施的c轮次问题，基于维诺图的算法的计算复杂度为O(c(n2+m)logn)。文献[85]考虑了两类多设施厌恶选址问题，提出基于维诺图和二元线性规划的启发式算法，其计算时间要比一些常用的非线性求解器要少得多。文献[86]将维诺图的概念进行了推广，引入带部分重叠区域的维诺图。关于维诺图在设施选址问题上的更多应用可参见文献[87]。

5 连续设施选址的应用

在经济生活和公共服务的选址中广泛存在着成本和利润的平衡。公司需要衡量能否通过增加设施而减少服务成本，政府需要衡量在何地建立设施可更好地服务民众。在不同的实际应用场景中公司或政府均需要综合考虑不同因素对选址的影响。以下从商业应用和公共服务两方面介绍设施选址的应用。

5.1 商业应用

银行是现代经济中不可或缺的金融机构。随着银行业务的发展，银行的分销渠道，如信贷信用卡、电话-互联网银行、自动柜员机(ATM)等日益成熟。此外，银行需要通过建立分行维持和发展客户并开展业务。据统计，摩根大通、BB&T等国际银行都在快速增加自己的分行数目以提升竞争力。在银行选址中，需要考虑地址的商业属性、客户群体分布、具有竞争性的其他金融机构等因素。处理银行选址的常见方法有数学规划、元启发式算法等。具体的研究可参见[88]。

由于电商行业的全球配送，“物流园”在现代物流业中发挥着越来越重要的作用。物流园通常包括仓库、配送中心和物流相关公司/办公室。物流园遍布世界各地，包括 美国伯灵顿北部物流园区、中国深圳平湖物流园区、荷兰阿姆斯特丹物流园区等。物流园大多坐落在大城市的郊区，同时还需要考虑交通的便利性以及仓储成本等因素，因此在物流园中存在着各种设施选址问题。具体研究可参见[89]。

森林是一种广泛的自然资源，通常分布在数百万公顷的土地上，因而林业是最受空间因素支配的自然资源产业。林产品供应链不仅仅是一条供应链，更是一条价值链。林产品供应链的长期、中期和短期各类规划中均存在着重要的选址问题。林业选址中考虑的因素很多，如生态系统管理的战略、林产品的产地、运输点等。具体的研究可参见[90]。

5.2 公共服务

选址研究中的模型和算法长期以来一直应用于公共设施的规划。以下仅以交通传感器和消防站为例说明设施选址在公共服务中的应用。

根据中国公安部交管局发布的数据显示，2017年全国汽车保有量达2.17亿辆，而且车辆数量还在逐年增长。这样的增长虽然提高了道路运输网络的利用率，但同时也带来了拥堵和不安全因素。美国联邦公路管理局的数据显示全球每年交通事故导致的人员伤亡以百万计。事实证明，采用智能交通系统(ITS)可显著提高交通安全、减少交通拥堵。ITS使用先进的通信技术、传感器技术和计算机技术解决交通问题并提高人货流动的效率。ITS系统中需要安装大量传感器以便进行事故检测和交通管理。传感器的安装即为典型的选址问题，其中需要考虑传感器的覆盖范围、传感器数量以及交通状况等因素。具体研究可参见[91,92]。

由于特殊的社会属性，消防站的选址变得非常重要。首先，消防站非常注重响应速度。快速的响应意味着救援人员能在尽可能短的时间内到达现场从而更有效地挽救生命和财产安全。其次，消防站建设的固定成本非常庞大，同时其使用过程中的人力成本也很巨大，这些都涉及到切实的财政问题。在消防站选址时需综合考虑各种成本投入、位置的辐射范围、周边设施等因素。具体研究可参见[93,94]。

6 总结与展望

本文对连续设施选址进行了综述，主要介绍了连续设施选址的要素、经典模型、拓展模型、方法与技术以及连续设施选址在现实生活中的一些应用。期望通过本文的介绍，感兴趣的读者们能够对连续设施选址具备一定的了解并建立连续选址研究的基本框架，同时为其开展该领域的研究打好初步的基础。

连续选址研究的展望主要包括如下三方面：

(1)模型。设施选址的研究本质上为实际问题驱动的研究，因此选址模型的建立应尽可能地反映实际选址问题的特点和需求。

模型的整合与拓展。连续设施选址的经典模型或基础模型具有极其重要的地位。然而基于便于求解的考虑，这些模型可能忽略实际问题中的某些重要因素。对基础模型进行整合或拓展并形成更丰富且更适用于实际应用场景的整合模型或拓展模型将是连续选址模型方面的重要工作之一。

模型的目标函数和参数。实际的连续选址问题中常存在多个决策目标，这些目标相互间可能存在一定的冲突，也有可能无法进行数学量化。因此建立部分目标具有模糊性或定性刻画的多目标选址模型并对其进行研究是连续选址重要研究方向之一。同时，选址模型中一般都带有参数。这些参数对数学模型模拟实际选址问题的准确度有着相当大的影响，因此研究参数对模型及决策结果的影响也是连续选址的重要研究内容。

(2)方法与技术。连续设施选址模型为连续优化问题，所以在求解这类模型时线性与非线性规划发挥着重要作用。

精确算法与(元)启发式方法。当连续选址模型的规模较小时，可以考虑设计小规模问题的精确算法。但对于整合模型或者拓展模型而言其规模非常大，求解就会复杂。考虑到数学模型总是实际问题某种程度上的近似，故很难界定该模型的最优解是否即为实际问题的最优设施位置。因此对于大规模选址问题设计快速的(元)启发式方法求得其近似最优解有时比求得精确解更重要。将精确算法和(元)启发式方法相结合设计混合算法也是一个比较有效的思路：利用(元)启发式方法求得选址模型的近似解，再利用其作为精确算法的初始点求得选址模型的最优解。

优化技术的应用与发展。连续设施选址的研究涉及到大量优化技术，比如不确定优化、多目标优化、变分不等式等。另一方面，随着大数据时代的来临设施选址中会产生了大量的数据，故数据分析与处理技术也必不可少。这些技术在连续选址中的应用将极大地推动该领域的蓬勃发展。将已有的优化技术以及不断发展的新技术应用于连续选址的研究也将是这一领域的重要发展方向。

(3)应用。设施选址研究的最终目的是要落地，即能够真正解决实际选址问题，因此连续设施选址的应用研究也是非常重要的。

工业与管理角度。实际的选址问题都有其自身的特点，这就要求我们在进行设施选址应用研究时能够真正地从工业与管理的角度出发建立适合于实际问题的整合模型、拓展模型或新模型。这是连续设施选址应用研究的第一步，显然也是应用研究中的难点。

拓展应用范围。将连续选址的模型、理论和算法与相关领域(如供应链、城市规划等)的实际问题相结合开展多学科交叉的应用研究将是一项有意义的工作。此外，某些领域表面上与设施选址并无联系，但实际上设施选址的理论和方法也可用于这些领域解决其中的实际问题。将设施选址的研究成果应用到这些领域从而拓展其应用范围也是设施选址应用研究的工作之一。