基于改进NSGA-II算法的多级服务设施备用覆盖选址决策模型

宋 艳， 滕辰妹， 姜金贵

(哈尔滨工程大学 经济管理学院,黑龙江 哈尔滨 150001)

0 引言

近年来跨区域突发事件成为普遍现象，跨区域地域间的突发事件处置日益受到重视。跨区域突发事件具有典型的区域性，跨越了多个行政区，超越了市界、省界，如2006年“桑美”台风造成浙江、福建等东南沿海地区重大人员伤亡和经济损失， 2008 年南方雨雪冰冻灾害使得湖南湖北等数省交通、电力、供水系统大幅受灾，等诸如此类跨区域问题由来已久，至今也没有得到很好地解决。

2015年9月民政部、国家发改委等九个部门联合印发《关于加强自然灾害救助物资储备体系建设的指导意见》，首次提出了构建“中央-省-市-县-乡”纵向衔接、横线支撑的五级救灾物资储备体系，由此，服务设施的空间选址布局一定程度上得到更为广泛的重视。跨区域突发事件通常在覆盖范围与行政区域有错位与重合，需要合理科学的选址布局才可有效应对。选址布局影响需求点与设施点的服务关系，是服务质量的重要决定性因素。选址问题在设施服务能力与效率的应用中起决定性作用，自上世纪以来深受广大学者的关注。

1 问题描述

传统的常规选址决策模型有研究最为广泛的覆盖模型及常见的 P-中值模型、P-中心模型[1]；其中经典的覆盖问题包括：识别覆盖所有需求点服务设施的集合覆盖问题(Location Set Covering Problem. LSCP)[2]；满足设施覆盖需求点的效益最大的最大覆盖问题 (Maximum Covering Location Problem.MCLP)[3]；以及由集合覆盖问题扩展演化而来的备用覆盖问题[4](BACOP1，BACOP2)，广义最大覆盖问题(General Maximum Covering Problem,GMCLP)[5]，渐进覆盖问题[6]，多层级服务选址问题[7](Hierarchical Service Location Problem, HSLP)，以及多目标选址问题等。覆盖模型通常应用于公共设施与应急设施的选址，认为在设施点的服务半径内需求点受设施点覆盖；而多级服务覆盖模型映射了生活中应急设施服务水平的层级关系及流向属性，是满足人们对服务差异化需求程度的决策模型。与许多其它选址问题相似，解决高服务效率的多级服务覆盖模型逐渐成为受学者们推崇的研究领域。

Daskin指出最大覆盖选址问题为NP困难问题[8]，需要有效的智能算法解决此类问题；根据最大覆盖选址问题的不同目标可分为总成本最低和覆盖总需求最大两类模型。本文在考虑设施繁忙(被占用)的状况下设计改进的NSGA-II算法，建立并求解多层级服务设施的备用覆盖选址模型，旨在设计计算机时间内的有效算法来解决各层级设施空闲与繁忙状态下的选址问题，达到各目标最优的目的。

文章第二部分综述了与主要建构模型相关的多层级选址问题和备用覆盖问题以及NSGA-II算法，第三部分定义变量并构建模型，第四部分设计染色体编码方式以改进NSGA-II算法，第五部分测试、验证模型及算法的有效性，第六部分总结展望。

2 文献回顾

2.1 多级服务设施选址问题

应急服务设施多数致力于单级服务，而最为常见的多级服务为医疗保障系统，深受Dokmeci[9]， Church[10]，Butler[11]，Boffey[12]等学者们青睐，Eitan[13]等对现有设施的重新分配模型进行概述总结，根据公共服务设施提供的服务水平层级关系，将公共服务设施分为嵌套型和非嵌套型[14]。如果高级别设施的服务功能包含低级别服务设施的功能，其称为嵌套型设施，若不同级别的设施仅提供自身等级的服务，则该类设施为非嵌套型设施。生活中嵌套型服务属性更为广泛，Banerji and Fisher[15], Calvo and Marks[16], Dökmeci[17], Narula and Ogbu[18], Schult[19]等研究者建立不同限定条件嵌套型服务设施的模型。

Narula[20]考虑了两种不同的服务设施流向模式，单级流向意味着低级服务可流向任何高级服务，相反多级流向服务可在任意级别间流动。Serra等[21]将空间配置划分为连贯型与非连贯型配置，连贯型配置指接受低等级设施的需求者同样也要接受相同设施的高级服务，非连贯性配置对此不作要求。Moore等[7]提出带容量限制的多层级服务覆盖选址模型，目标为求设施的最大化各级服务覆盖人口。Sahin[22], Farahani等[23]将多级服务系统进行多种应用。

2.2 备用覆盖选址问题

在最大覆盖模型基础上，Hogan, ReVelle[4]基于设施繁忙与空闲的状态建立SCLP下的BACOP1与MCLP下的BACOP2模型，以期提供第一层覆盖缺失时的备用覆盖服务。Daskin, Hogan, ReVelle[24]后续比较了备用覆盖思想的多种覆盖模型。Berman, Krass[25]建立了拥堵系统中的最大覆盖复杂模型。ARAZ等[26]将BACOP2扩展补充考虑非覆盖总距离的最小化。Erdemir等[27]引入备用覆盖思想研究医疗设施的联合选址问题。肖俊华等[28]通过遗传算法对建立的“备用覆盖”和“渐进覆盖”思想的多级覆盖选址模型求解。葛春景等[29]基于BACOP2构建不同服务水平下的多重覆盖模型(MQCLP)。由于多级服务设施选址问题的规模维度高，一部分启发式算法作为研究问题的方法得到发展。VahidHajipour等[30]改进NSGA-II算法解决多目标备用覆盖下的设施分配问题。国内学者[31,32]综合成本费用和覆盖效率尝试利用NSGA-II算法讨论多目标决策选址模型的求解策略。

2.3 经典NSGA-II算法

NSGA-II算法[33]在非支配排序遗传算法(NSGA算法)的基础上引入精英策略，是解决多目标优化问题的一个比较新颖的智能算法，国外学者将其大量应用于科学研究和工程实践[34～37]，并通过设计染色体基因组DNA编码取得了优越的成效[38～43]。而国内对于NSGA-II算法的在应急选址研究应用比较有限[44～46]，部分学者针对多目标进化算法的解分布与收敛速度设计了改进算法，如：谢承旺等提出带差分局部搜索的改进型NSGA-II算法，改善了结群的分布特性[47]；肖怀硕等采用一种基于局部差分方法改进非支配排序遗传算法，提升全局寻优能力[48]；罗辞勇等采用循环拥挤排序策略改进算法，使得到的解具有更好的多样性[49]；李琳等通过采用配水系数进行染色体编码及归一化处理论证了优化方法的可行性[50]；这些改进的NSGA-Ⅱ算法比起标准NSGA-Ⅱ算法具有更好的收敛性和多样性。

现有的设施选址布局模型中，一方面多以设施点的单源服务与单级服务水平为假设，另一方面未对备用覆盖模型中不同层级设施的覆盖效率加以限制区分，降低了设施点的服务利用性，同时也忽略了不同层级设施间的不同服务质量，不能有效满足人们对服务的差异化需求。本文以“备用覆盖”、“多级覆盖”思想为基础，建立多级流向，非连贯，嵌套型的多级备用覆盖选址决策模型，通过结合单点交叉变异遗传操作设计染色体的编码方式以提升NSGA-II算法在运行时间和搜索范围方面的效能，并通过模拟仿真证实模型的有效性。

3 模型构建

3.1 概念界定及基本假设

在确定参与事故响应的不同等级救援力量下，根据突发事故点距设施储备点距离考虑覆盖情况，任意需求点存在由不同层级的多个设施点提供不同层级水平服务，或由高层级设施提供不同层级水平服务的可能性。依据各层级设施点的有效半径覆盖面积是否重叠 (布局形式)，储备点的位置关系分为独立和重叠两种关系；如图1所示，根据设施点坐标是否同属一个位置、覆盖半径是否相同的条件，重叠关系分为完全重叠关系和非完全重叠关系(中心点重叠关系和部分重叠关系)，覆盖面积完全不重叠为独立关系。

图1 位置关系图

模型有关参数定义如下：

i：需求点索引，1≤i≤I;j：应急设施点索引，1≤j≤J;p,h：设施点级别索引，1≤p,h≤H;ai：需求点i的人口数;Sh：h级应急设施的覆盖能力(覆盖半径);dijh：需求点i到h级设施点j的直线距离;Nih{j|dijh≤Sh}：有能力覆盖需求点i的h级设施点的集合;Np：p级设施点的个数。

变量：

xjh：0-1变量，建立h级设施点j时变量为1，否则为0;yih：0-1变量，需求点i受h级设施点至少一次覆盖时变量为1，否则为0;yi：0-1变量，需求点i受设施点各h级覆盖至少一次时变量为1，否则为0;uih：0-1变量，需求点i受h级设施点至少二次覆盖时变量为1，否则为0。

考虑模型复杂程度，假设以直线距离作为设施点与需求点间的距离，设施的服务能力与容量无限制。

3.2 建立模型

多层级服务下备用覆盖物资储备库的多目标选址决策模型可以表述如下:

yih-ui≥0,∀i,h

yih-yi≥0,∀i,h

xjh,yih,yi,uih∈{0,1},∀i,h

以上建立的多目标模型为嵌套型服务设施的选址决策模型(如三级设施点提供其独特服务外可提供一级与二级设施所提供的服务；二级设施点提供其特有的二级服务及一级设施服务。)因此目标函数根据设施层级有不定个数，共h+1个。目标函数式一表示布局的设施储备点应使得总覆盖需求最大，仅当需求点满足所有级别服务覆盖时才认为此需求点受覆盖；目标函数式h+1致力于h级服务的超额覆盖，使设施点满足h级服务超额覆盖的最大化，区别于目标函数式一，是多层级设施分别对设施的各层级服务进行的超额覆盖最大化。

约束一限定了各h级设施点的个数；约束二表明建造对需求点i有覆盖能力的嵌套型p施xjp时，由于嵌套型高级别设施的服务功能包含低级别服务设施的功能，所以，需求点i的h级覆盖需求来自于嵌套型p级设施提供的h级服务(p大于等于h，j为对i有h级服务覆盖能力的级嵌套型p设施xjp)；约束三表明需求点i受大于等于嵌套型h级设施并满足覆盖要求的p级设施的h级的超额覆盖，决定了需求点i的h级需求覆盖距离内的h级设施的数量；约束四体现变量yi与yih间的关系，对于需求点当且仅当所有级别服务可达时才满足受覆盖的需求；约束五确保需求i点满足受h级备用覆盖发生在第一次覆盖后的强制性条件；约束六保障变量xjh,yih,yi,uih为0-1整数决策变量。

针对区域的高备用覆盖需求，可以以同样方式扩展建立多层级设施三次覆盖(两次超额覆盖)模型，增加新0-1变量wih，变量为1表示需求点i受h级设施点至少三次覆盖，反之变量取0。多层级设施三次覆盖模型如下：

yih-yi≥0,∀i,h

yih-ui≥0,∀i,h

uih-wih≥0,∀i,h

xjh,yih,ui,wih∈{0,1},∀i,h

4 NSGA-II算法改进设计

4.1 NSGA-II方法步骤

为了更好的解决多层级服务下备用覆盖物资储备库的多目标选址决策问题，我们在标准NSGA-II算法上进行改进，设计新式染色体编码方式，基于此与现有NSGA-II算法的结果比较分析。算法设计中的改进主要体现在三方面，首先，提出一种分段的染色体编码方式以提高运算效率；其次，以此为基础在第一代遗传操作中引入精英策略，使得最佳初始染色体个体不会丢失，扩大了标准NSGA-II算法染色体的采样空间；最后，在进化过程中，使当前种群中拥挤度比较算子大的个体参与遗传操作运算，并用它来替换本代群体中经过交叉变异遗传操作后所产生的拥挤度比较算子小的个体，一定程度上加大了种群的多样性。改进的NSGA-II算法主要操作步骤流程如下：

图2 NSGA-II算操作流程图

1)产生初始种群。设定群体规模N，随机产生初始群体P0。

2)非支配排序。对种群进行分级，先找到种群中所有支配解保存在当前集合F1中，命名为第一层非支配解，遍历当前集合F1中的个体i支配的每个个体j，若j仅受i支配则将j保存在F2中，命名为第二层非支配解，并以F2为当前集合重复上述操作直至所有染色体被分级。

3)拥挤度计算。基于每个目标函数值对种群进行排序。

4)拥挤度比较算子。利用2)，3)步骤的非支配排序值nr和拥挤度nd属性对各染色体进行优劣比较：认为nrindj时个体优于j个体。

5)选择。通过二进制锦标赛法从Pt选择个体。即每次选择两个个体比较等级，取等级级数小的个体，或者对于同等级个体取拥挤度大的个体。

6)交叉变异操作。采用异于SBX交叉算子的单点交叉变异方式进行交叉和变异操作，产生种群Qt。

7)合并父子带种群。通过合并Pt和Qt产生出组合种群Rt=Pt∪Qt。对Rt进行非支配排序，并通过排挤和精英保留策略选出N个个体，组成新一代种群Pt+1。跳转到步骤5)开始循环，至满足结束条件。

4.2 NSGA-II算法染色体分段符号编码方式

图3 染色体分段符号编码方式

下文通过对BSX交叉算子和单点交叉变异两种不同的交叉变异操作方法进行仿真结果对比分析，以期得到染色体分段符号编码方式下的NSGA-II算法改进。

5 算例仿真

5.1 测试问题及参数设置

根据以上模型，假设某一区域有50个跨区域突发事件潜在点并可供选择储备设施点，经各级政府等部门规划，确定建立二级救灾物资储备体系(为方便直观比较两种方法), 规划5处为待建储备设施点为需求点提供各层级水平服务，其中一级储备点 3 个、二级储备点2个，有效覆盖半径分别为80、200单位；如图4中“+”符号代表各备选设施点的布局，根据仿真结果确定设施点。

1.6GHz Inter Core i5处理器，4GB 1600MHz内存的OS X10.10.5系统下，以MATLAB_R2014b编程实现改进的NSGA-II算法，参数设置种群规模M=100，最大进化代数GEN=100，依次取GEN=100进化代数下两种策略的结果，将得到的部分代表性多目标Pareto解集做目标函数值三维图与收敛分析图，验证模型与算法的有效性。

5.2 结果分析

表1 不同编码方式与模型的分析对比

如表1所示，不考虑设施被占用的情况下，设种群个数足够大，为避免偶然性取十组仿真时间的平均值使结论具有普遍意义。两种染色体编码方式下的受覆盖总人口数均为821.3，分段符号编码方式下所占用时间仅为二进制编码方式下的45.8%，表示出染色体的分段符号编码方式相对二进制编码方式在计算机处理时间上有绝对优势，证明了其在计算机时间内的有效性。

考虑设施被占用的情况时，多层级服务选址模型(HSLP)与所建构的多层级备用覆盖模型(BACOP3)相比较，HSLP不能体现超额覆盖人次， 而BACOP3在满足HSLP的同时又设立各层级需求的超额覆盖，由此，这一过程增强了设施点繁忙状态下的可实用性并证明了BACOP3的优越性。对此基于染色体的分段符号编码方式的运算性能，运行主程序模拟仿真，进行两组策略下的BSX交叉算子与单点交叉变异操作的结果分析比较如表2与图5。

表2 两组策略下Pareto非劣解集对比

根据染色体分段符号编码方式的两种交叉变异操作方法下的非劣解集，每个点代表了一个选址决策方案下的三个目标函数值，“*”代表BSX交叉算子法下的Pareto非劣解集，“▽”表示选址决策模型中单点交叉变异的Pareto非劣解集；以“点划线、实线、虚线”分别代表三个目标函数Obj1、Obj2、Obj3的收敛效果如图5。

两种方法分别得到相同组数Pareto非劣解集。GEN1和GEN2的进化过程显示出单点交叉变异遗传操作下得到的目标1(Obj1)方向的Pareto非劣解集面高于BSX交叉算子操作下的Pareto解集面，同时收敛速度效果也相对优于经典BSX交叉算子操作。通过对所得非劣解集的对比分析得知以下结论：两种方法得到的Pareto非劣解数量相同，分布均比较均匀，从目标函数值和运行时间方面看，分段的染色体编码方式在NSGA-II算法中解决多目标选址决策问题具有一定的优势，与NSGA-II算法BSX交叉算子下得到的非劣解相比，程序运行耗时少，收敛速度与效果相对较优。因此，改进的NSGA-II算法是决策者在处理多级服务设施备用覆盖选址问题时的优势算法，可以有效的解决多级服务设施备用覆盖选址决策问题。

各级地方政府在应急资源储备设施选址过程中，根据是否在同一地点建设多个服务设施点制定部署要求。策略一：不同服务层级设施点选建在同一位置，需要整合现有资源，建立涵盖于中心点重叠并可提供相应备用覆盖的综合性应急资源储备点，以MaxObj3为例得到图5的选址方案，避免了救援物资的重复建设。策略二：空间布局选址过程中，规定为保证备用覆盖效率建立专业化应急救援力量，即各设施点的选建条件为非中心点重叠关系位置范围，此时选址决策布局方案以MaxObj3为例见图5。

6 结论与展望

文章根据多级服务设施问题与备用覆盖选址问题建立了多级服务备用覆盖选址决策模型。在NSGA-II算法基础上，比较了BSX交叉算子操作与分段染色体编码的单点交叉变异两种不同遗传操作的结果，通过多目标Pareto最优解集面与收敛曲线分析，得到了改进的NSGA-II算法与多级服务备用覆盖选址决策模型具有有效性的结论。

受突发事件严重程度和响应级别等方面影响，在模型应急服务层级的预测把握上存在一定的局限性。本文存在以下几点不足：第一，在突发事件发生前不可切实预知事故的严重程度以及真实需求。第二，建模的前提假设条件一定程度上增加了多级服务设施备用覆盖模型的局限性。未来的改善研究可以通过考虑各层级设施主体间的协作关系与权重关系设置参数以加强模型解释度，并应用计量分析工具解决选址布局决策优化问题。以上内容将在今后学习中进一步补充完善。