万 波，陈 琴

（江汉大学a.商学院；b.文理学院，武汉 430056）

0 引言

随着社会的进步与生活水平的提高，顾客需求的多样化程度越来越高，需要建立不同层级的设施，以满足顾客的多样化需求。层级设施在服务领域广泛存在，典型的层级设施包括医院、学校以及急救中心等。层级设施选址在规划过程中需要考虑诸多的不确定因素，例如顾客对服务的需求具有不确定性，特别是当前城镇化过程中人口波动所导致的需求波动。此外，选址决策的长期性导致旅行时间、建设成本等相关因素也会随着时间发生变化。因此，研究不确定性需求下的层级设施选址问题具有重要的意义。

处理不确定性问题的方法包括随机规划、模糊规划以及鲁棒优化方法等。随机规划需要事前给出不确定参数的概率分布，这在多数情况下是较困难的，而模糊规划要求事先给出不确定参数的模糊隶属度函数，其具有一定的主观性。鲁棒优化起源于鲁棒控制理论，可以很好地解决由于数据不准确而导致的决策风险，从而得到数据不确定情况下的鲁棒最优解[1]。鲁棒优化包括相对鲁棒优化、绝对鲁棒优化以及偏差鲁棒优化等，相对后悔值模型通过控制各种情景下目标值与最优值的波动来保持最优解的稳定性，是一种典型的相对鲁棒优化模型[2]。

Vincenzo等[3]针对需求、成本等市场因素不确定的情况，以各种情景下相对后悔值的期望值最小化为目标，建立了带容量限制的鲁棒优化模型。胡丹丹和杨超[4]针对截流选址问题中流量的不确定性，建立了鲁棒随机截流选址模型。韦忆立和高咏玲[2]利用相对遗憾值约束来控制实际成本与最优成本的差距，建立了配送中心选址的鲁棒优化模型。何珊珊等[5]引入控制参数对各需求点应急物资的需求进行控制，建立了多目标鲁棒优化模型。高雷阜等[6]针对不确定因素对应急物资储备库选址决策的影响，建立了相应的鲁棒优化模型。以上文献仅对单一层级设施选址问题进行研究，而利用鲁棒优化模型对多层级设施选址问题研究鲜见于文献。Pehlivan等[7]建立了设施与顾客均具有嵌套性的层级设施选址模型，对法国上塞纳省妇产科医院选址进行规划；Teixeira和Antunes[8]提出了带容量限制的层级设施选址模型，对学校选址问题进行了研究；Ratick等[9]建立了最大覆盖层级选址模型，对医疗设施选址问题进行了研究；陈志芬等[10]建立了应急设施层级选址模型，并利用实验进行了模拟。以上文献对层级设施选址研究没有考虑需求的不确定性。本文考虑层级设施选址过程中的需求不确定性因素，建立了基于鲁棒优化的层级设施选址模型，并以武汉市某区的医院为例进行实例分析。

1 问题背景与模型符号

1.1 问题背景

本文的研究对象为多层级的医院类设施选址问题。首先，医院服务系统的顾客需求具有不确定性。由于受城镇化因素的影响，大批农民涌入城市，导致就医需求出现波动；另外，城市内部的流动性较大，也导致就医需求不确定性增加。其次，医院所提供的服务具有层级性与嵌套性。服务设施的层级性是由需求多样性和需求偏好所决定的，即需要建立多级医院，以满足不同层次的需求，这也是国家分级诊疗制度的要求；同时，层级设施根据其服务水平可分为嵌套型与非嵌套型，本文研究的医院是典型的嵌套型设施，即高级别设施除提供该层级特有的服务外，还应覆盖低级别设施所提供的服务。此外，医院选址需要考虑成本与效用的均衡性。一方面，要考虑成本因素，各级医院设置最小与最大容量约束；另一方面，医院需要尽可能发挥资源的利用效率，为全体人民提供医疗服务。

1.2 模型符号

模型有关参数定义如下：

H：表示需求点的需求层次、设施点的服务层级的集合；I：需求点集合，i∈I；

J：设施候选点集合，j∈J；

k：需求点的需求层次和设施点的服务层次，k∈H；t：设施点的服务等级，t∈H；

dij：需求点i到设施候选点j的距离；

uiks：情景s下需求点i第k层的需求量；

bjt：点j所设立t级医院承担的最高级服务的最低需求量（下文称为服务能力最小值）；

Bjtk：点j所设立t级医院提供的第k层服务的最大服务能力（下文称为服务能力最大值）；

wjks：情景s下点j承担的第k层需求量。

同时定义如下的决策变量：

xijks：情景s下如果需求点i第k层需求由点j服务，则xijks=1，否则为0；

yjt：如果点j被选中为t级医院，则yjt=1；否则为0。

2 模型建立

2.1 p-鲁棒优化模型

p-鲁棒优化模型是一种相对后悔值模型。设p为相对后悔值限定系数，p≥0；S为情景集，对于特定的情景s而言，Ps为确定的最小化问题，设Ps的最优目标值为，X为所有情景S下问题Ps的可行解，zs(X)为情景s对应的目标值，当时，称X为问题Ps的p-鲁棒解称为相对后悔值[11]。

p-鲁棒优化模型为：

式中，qs为情景s发生的概率；Ω为可行解空间[12]。

2.2 基于鲁棒优化的层级设施选址模型

本文建立了基于鲁棒优化的层级设施选址（Hierarchical Robust，HR）模型。该模型以实现各情景下的期望需求加权距离最小化为目标，同时考虑各级需求全覆盖、服务水平的嵌套性、不同层级设施的服务能力约束以及需求就近分配等因素[13]。

其中，（1）式为目标函数，表示各种情景下期望需求加权距离最小化；（2）式对情景s下的需求加权距离进行定义；（3）式表示任意情景下各需求点的所有层级的需求均能得到满足；（4）式表示各设施候选点只允许建立唯一等级的设施；（5）式表示服务的嵌套性，即设施为相同层级或者低层级的需求提供服务；（6）式表示各情景下设施承担的各层次的需求量等于由该点服务的所有需求点的对应层次的需求量之和；（7）式表示最小容量约束；（8）式表示最大容量约束；（9）式为鲁棒约束；（10）式表示就近分配；（11）式表示决策变量的取值范围。

3 求解算法

对给定的情景s，若不考虑约束条件（9），则模型HR为确定性分层（Hierarchical Deterministic，HD）优化模型；对给定的情景集S，模型HR为基于情景的分层随机（Hierarchical Scenario，HS）优化模型：

模型HD和模型HS为混合整数线性规划模型，模型HR是在模型HS的基础上加上线性约束（9），因此，模型HR也为混合整数线性规划模型。而混合整数线性规划问题是一个典型的NP困难问题，一般没有多项式时间算法，难以在有效时间内求得最优解。

遗传算法是一种智能的、有效的优化算法，它根据目标适应度函数对每个个体进行评价，按照优胜劣汰的进化规则不断得到新的种群，搜索优化种群中的最优个体，从而求得满意解[14]。由于遗传算法具有自组织、自适应、自学习性以及并行性等特点，且该算法简单易行，本文利用遗传算法求解HR模型，具体算法如下。

步骤1：编码，产生初始种群P0。

染色体使用整数编码，表示不同需求点处待建医院的层级。其中，0表示相应的需求点不建立医院，1、2、3分别表示相应的需求点建立一、二、三级医院，如表1所示。随机产生N条染色体，构成一个初始种群P0。

表1 染色体结构

步骤2：按就近原则进行需求点分配。

（1）将需求点分配给最近的待建设施点；

（2）计算每个设施点分配到的需求量，判断是否满足最大服务能力约束，如果是，则将该需求点分配给该设施点，结束；如果否，则转（3）进行需求点的重新分配；

（3）将未予以分配的需求点分配给次近的待建的设施点，转（2）重新进行检查；若继续不满足，则分配给第三近的待建的设施点，依此类推；若全部设施点均不能满足，则将该需求点分配给就近的待建的设施点，结束。

步骤3：利用亲和度函数进行约束条件控制。

为保证所建立的医院能够正常盈利并提供较好的服务质量，采用罚函数法将约束（7）至约束（9）整合到目标函数中，以δ1,δ2,δ3依次表示约束（7）至约束（9）的惩罚因子，亲和度函数定义为：

若As1＞0,则在情景s下未能满足最小服务能力约束（7）；若As2＞0,表示在情景s下未能满足最大服务能力约束（8）；若As3＞0,表示在情景s下未能满足鲁棒约束（9）。分析可知，满足全部约束条件的解，其目标函数Z值一定等于其亲和度函数值A。

步骤4：求初始种群P0的目标值。

步骤5：交叉和变异，产生子种群Q0，求其目标值和亲和度。

步骤6：采用精英策略产生新的种群R0。

步骤7：判断是否满足结束条件，如果否，转步骤2；否则结束[15]。

4 实例分析

本文以武汉市某区为例，模型相关参数取值如下：设H={k|1,2,3}分别代表三个级别的需求层次与服务层级；t∈H={1,2,3}表示三个层级的医院级别。设该区有50个需求点，即假设所有需求点均为设施候选点，即J=I[16]。不同层级的医院对不同层次需求的服务能力不同，Bjtk为j点所设立t级医院对k级需求的最大服务能力，设0,0;500,1000,0;800,1000,2500}。bjt表示在j点设立t级医院的最低服务需求量，设bjt={bj1,bj2,bj3}={300,700,1700}。uiks为情景s下需求点i第k层需求的需求量，uik1由统计规律得出，为了模拟城镇化过程中需求增长的情况，令uiks=uik(s-1)(1+5%),i∈I,k∈H,s∈S，即按每一需求点对各层次需求增长5%来设置情景。设定种群内染色体数为200，交叉概率为0.7，变异概率为0.0876，惩罚系数{{1000,1000,10}，最大迭代次数count=3000。

4.1 算法分析

4.1.1 遗传算法的收敛性分析

取p=0.2来讨论算法的收敛性。由下页图1可知，遗传算法对于求解该问题具有较好的收敛性，当迭代次数count=1913时目标函数收敛，其值收敛于12776。

4.1.2 遗传算法的有效性分析

HR模型是一个典型的线性优化问题，因此可用LINGO求取最优解。将遗传算法与LINGO所得结果进行比较，结果如下页表2所示。表中结果显示，当p≥0.1时，遗传算法所求得的满意解和LINGO求解得到的精确解的相对偏差Δ＜2%，说明相比LINGO而言，遗传算法具有较高的求解质量。然而，在各种p值情况下，遗传算法的时间效率远高于LINGO。因此，遗传算法求解HR模型具有较高的效率，能够在较短的时间内获得满意解。

图1 遗传算法的迭代次数与目标函数值关系图

表2 遗传算法与LINGO结果比较

4.2 模型的鲁棒性分析

最大相对后悔值是当p值确定时，各种情景下相对后悔值的最大值，最大相对后悔值是度量HR模型的鲁棒性的重要指标，最大相对后悔值越小，模型的鲁棒性越强[2]。令HD、HR的需求加权距离分别为，当p确定时，令模型HR的相对后悔值，则可求出各种情景下的，令，则可求出p值确定情况下的最大相对后悔值。利用遗传算法所求出的各种p值的最大相对后悔值，见表3所示。

表3 不同p值的最大相对后悔值一览表

图2 目标函数值和最大相对后悔值随p值变化的情况

为直观起见，用图2表示目标函数值和最大相对后悔值随p值变化的情况。由图2可知，随着p值的增加，目标函数值呈下降趋势，即期望旅行成本呈下降趋势，而最大相对后悔值呈上升趋势，两者呈背反规律。这说明p值较小时模型的鲁棒性较好，但要为此付出较高的成本代价，决策者需要根据实际情况进行权衡，选择合适的p值，既减少不确定因素对决策的影响，降低决策风险，同时保证总成本在可控制的范围之内。

4.3 不同情景概率对HR求解结果的影响

表4为当p=0.1时，不同情景概率下HR模型求得的目标函数值和医院选址方案。本文选取了4种情况，每一种情况与后一种情况相比而言，q1至q5逐步增大，而q6至q10逐步减少。由表4可知，4种情况下的目标函数值逐渐递增，这是因为各情景下的不同需求点对各层级的需求量逐步递增，前几种情景对应的需求加权距离更小所致。对比4种情况，医院选址方案有较大变化，说明情景概率对选址结果产生重要影响。

表4 不同情景概率下模型HR的求解结果

5 结束语

针对城镇化背景下服务设施的层级性与需求的不确定性特点，本文构建了基于鲁棒优化的层级选址模型，利用遗传算法进行求解，并以武汉市某区的医院选址问题为例进行了案例分析。结果表明，遗传算法具有较好的收敛性和较高的求解效率。p值较小时模型的鲁棒性较好，但要为此付出较高的成本代价，决策者需要根据实际情况进行权衡，选择合适的p值，使模型的鲁棒性能和总成本都在可接受的范围内。同时，当p值确定时，不同的情景概率对设施选址方案具有重要影响。

参考文献：

[1]戴军,关贤军.大规模应急救援资源配送点选址鲁棒优化研究文献综述[J].物流技术,2014,33(1).

[2]韦忆立,高咏玲.含时间约束的配送中心选址和能力规划的鲁棒优化[J].统计与决策,2015,(1).

[3]Vincenzo D R,Hartmann E,Gebhard M,Wollenweber J.Robust Capacitated Facility Location Model for Acquisitions Under Uncertainty[J].Computers&Industrial Engineering,2014,(71).

[4]胡丹丹,杨超.a-鲁棒随机截流选址问题的模型和算法[J].中国管理科学,2008,16(6).

[5]何珊册,朱文海,任晴晴.不确定需求下应急物流系统多目标鲁棒优化模型[J].辽宁工程技术大学学报,2013,32(7).

[6]高雷阜,于冬梅,赵世杰.不确定需求下应急物资储备库选址鲁棒优化模型[J].中国安全科学学报,2015,25(12).

[7]Pehlivan C,Augusto V,Xie X L.Dynamic Capacity Planning and Location of Hierarchical Service Networks Under Service Level Constraints[J].IEEE Transactions on Automation Science and Engineering,2014,11(3).

[8]Teixeira J C,Antunes A P.A Hierarchical Location Model for Public Facility Planning[J].European Journal of Operational Research,2008,185(1).

[9]Ratick S J,Osleeb J P,Hozumi D.Application and Extension of the Moore and ReVelle Hierarchical Maximal Covering Model[J].Socio-Economic Planning Sciences,2009,43(2).

[10]陈志芬,李强,陈晋.城市应急避难场所层次布局研究(Ⅱ)[J].自然灾害学报,2010,19(5).

[11]Snyder L V,Daskin M S.Stochastic P-robust Location Problems[J].IIE Transactions,2006,38(11).

[12]冯春,于彧洋.不确定情景下应急物资储备库选址问题研究[J].工业工程,2014,17(2).

[13]李婷婷,宋瑞.国家层面综合客运枢纽分层布局鲁棒优化模型[J].东南大学学报：自然科学版,2015,45(1).

[14]万波.公共服务设施选址问题研究[D].武汉：华中科技大学博士论文,2012.

[15]Berglund P G,Kwon C.Robust Facility Location Problem for Hazardous Waste Transportation[J].Networks&Spatial Economics,2014,(14).

[16]万波,杨超,黄松,董鹏.基于层级模型的嵌套型公共设施选址问题研究[J].武汉理工大学学报：信息与管理工程版,2012,34(2).