多设施公平选址方法及其系统

摘要

本发明涉及一种多设施公平选址方法，该方法包括步骤：计算各需求点至设施点的最短距离，构建距离矩阵；根据所述距离矩阵，计算每一个可选设施点至各需求点的加权平均距离；构建各设施点与需求点的加权距离方差的矩阵；根据选取加权距离方差最小的设施点的选址原则，构建公平选址目标函数；求解所述目标函数，完成多设施公平选址。本发明的方法及其系统简化了多设施选址公平问题的求解难度，应采用蚁群算法选取，更贴近实际值，适用于各等级层次上的公共服务设施选址问题的解决。

说明书

技术领域

本发明涉及公共服务设施选址技术领域，尤其涉及一种多设施公平选址方法及其系统。

背景技术

通常某地区发生重大突发事件后，主要由当地政府启动应急预案，成立现场指挥部，统一指挥调度突发事件的应急处置工作，包括紧急调动各方面力量和资源、组成专家组以提供应对和处置突发事件的决策服务、适时发布紧急命令以调动相关力量进行增援等。由于政府各部门间缺乏应急应变方面的协调机制，公共部门缺乏预防突发事件的意识，致使现有的应急资源配置和应急设施的选址存在不合理之处。目前国内外的设施选址方法的研究主要侧重于平面上的单设施选址问题和离散网络上的多设施选址研究，仅依靠建立非线性目标函数，通过flord等方法，求取基尼系数最小或加权距离方差最小时的结果，flord算法具体为从代表两个顶点的距离的权矩阵开始，每次插入一个顶点，比较任意两点间的已知最短路径和插入顶点作为中间顶点时可能产生的路径距离，然后取较小值以得到新的距离权矩阵。这些研究侧重于算法设计，不符合实际应用的要求：首先现实中往往要面临多设施选址问题；其次，应考虑自然、社会条件的限制；最后，计算结果可能偏离目标值。

我国是世界上受自然灾害影响最为严重的国家之一，特殊的地理环境决定了我国的自然灾害具有种类多、发生频度高、灾害集中、损失严重等特点。21世纪以来，我国现代化建设进入新的阶段，新情况、新问题层出不穷，由于公共安全基础薄弱，自然灾害以及人为引起的各种重大事故灾难、重大公共卫生事件和社会安全事件经常发生。仅2008年，我国就遭受了雪灾、手足口病、地震3起大规模突发事件的袭击，造成直接经济损失11752亿元。这些重大突发事件既严重威胁了人类的生命安全，又大大危害了我国的经济发展和社会安定。

自1998年国家建立了国家级应急物资储备制度以来，经过十几年的发展，已在10个城市设立了国家级应急物资储备库。我国国家级应急储备物资代储单位有：天津、辽宁、黑龙江、安徽、河南、湖北、湖南、广西、四川、陕西等10省(区、市)民政厅(局)。国家级应急物资定点储备在天津、沈阳、哈尔滨、合肥、郑州、武汉、长沙、成都、南宁、西安10个城市。同时，部分省、市、县也通过各种方式建立了本级应急物资储备库。但总体上看，目前各级应急物资储备库普遍存在仓库面积小、建设标准低、基本装备严重不足的问题，不能很好地满足目前的救灾工作需要，更无法适应新时期党和国家对备灾、救灾工作提出的新要求。为完善应急物资储备体系，必须新建、改建和扩建一批符合标准的应急物资储备库，《国家综合减灾“十一五”规划》和《国家自然灾害救助应急预案》对此都作了明确规定，并已开始启动。据中新网2009年5月11日报道，全国国家级的应急物资储备库将由10个增加到24个。住房城乡建设部、发展改革委批准发布的《救灾物资储备库建设标准》(建标121-2009)，已于2009年10月1日起施行。

发明内容

(一)要解决的技术问题

本发明要解决的技术问题是：简化多设施选址问题的求解难度，提供一种适用于各等级层次上的公共服务多设施公平选址方法及其系统。

(二)技术方案

为实现上述目的，本发明提供一种多设施公平选址方法，该方法包括步骤：

S1.计算各需求点至设施点的最短距离，构建距离矩阵；

S2.根据所述距离矩阵，计算每一个可选设施点至各需求点的加权平均距离；

S3.构建各设施点与需求点的加权距离方差的矩阵；

S4.根据选取加权距离方差最小的设施点的选址原则，构建公平选址目标函数；

S5.求解所述目标函数，完成多设施公平选址。

其中，步骤S1中的距离为欧氏距离、行车距离、行车时间、或网络距离。

其中，步骤S2进一步包括：

S2.1获取各需求点的人口数量a_i；

S2.2求得每一个可选设施点至各需求点的加权平均距离：

${\bar{d}}_i=\frac{\underset{i=1}{\overset{m}{\Sigma }}{a}_i{d}_{\mathrm{ij}}}{\underset{i=1}{\overset{m}{\Sigma }}{a}_i}$

其中，d_ij为各需求点至设施点的最短距离，m为需求点的个数。

其中，步骤S3进一步包括：

S3.1计算各需求点与设施点两两之间的加权距离a_id_ij；

S3.2用所述加权距离a_id_ij减去所述加权平均距离得到每一个需求点至设施点的离差；

S3.3对每一个所述离差进行平方，即

S3.4根据步骤S3.3所得的离差的平方，构建设施点与各需求点的加权距离方差的矩阵。

其中，步骤S4进一步包括步骤：

S4.1确定决策变量X_ij及Y_ij，若需求点i被设施点j覆盖，则X_ij取1，否则取零，若可选择的设施点j被选择进行设施建设，则Y_ij取1，否则取0；

S4.2根据选取加权距离方差最小的设施点的选址原则，建立所述目标函数：

$\min z=\frac{\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}{(a_i{d}_{\mathrm{ij}}-{\bar{d}}_j)}^2{X}_{\mathrm{ij}}}{\underset{i=1}{\overset{m}{\Sigma }}{a}_i}$

其中，X_ij≤Y_j，n为设施点的个数，p为选择的设施点的个数。

其中，步骤S5中求解所述目标函数的方法为蚁群算法。

本发明还提供了一种多设施公平选址系统，该系统包括：距离矩阵构建模块，用于计算需求点至各设施点的最短距离，构建距离矩阵；加权平均距离计算模块，用于根据所述距离矩阵构建模块构建的距离矩阵，计算每一个可选设施点至各需求点的加权平均距离；加权距离方差矩阵计算模块，用于构建各设施点与需求点的加权距离方差的矩阵；目标函数构建模块，用于根据选取加权距离方差最小的设施点的选址原则，构建公平选址目标函数；求解模块，用于求解所述目标函数，完成多设施公平选址。

(三)有益效果

本发明的方法及其系统简化了多设施选址公平问题的求解难度，应采用蚁群算法选取，更贴近实际值，适用于各等级层次上的公共服务设施选址问题的解决。

附图说明

图1为依照本发明一种实施方式的多设施公平选址方法流程图。

具体实施方式

本发明提出的多设施公平选址方法，结合附图和实施例详细说明如下。

本发明的多设施公平选址方法是以国家和地区各级应急物资储备库为依托，分析重大突发事件下区域对设施的需求和各层级应急物资储备库的覆盖范围，计算各点间的距离，选定设施点。该选址方法包括需求点、设施点和覆盖半径的设定。其中：需求点是区域中需要应急物资和服务的元素，可以代表人、社区或村镇；设施点是各层级应急物资储备库的布局，本发明中将它们抽象为“点”元素；覆盖半径是指设施点j至所有需求点i的权重平均距离，其设定受需求点个数、需求点人口、设施点与需求点之间的实际距离的影响，其中，m为需求点的个数，n为设施点的个数。如图1所示，依照本发明一种实施方式的多设施公平选址方法包括步骤：

S1.计算或者调查得到各需求点至设施点的最短距离d_ij，构建距离矩阵；

S2.根据所得的距离矩阵，计算每一个可选设施点至各需求点的加权平均距离；

S3.构建各设施点与需求点的加权距离方差的矩阵；

S4.根据选取加权距离方差最小的设施点的选址原则，构建公平选址目标函数；

S5.求解目标函数，完成多设施公平选址。

其中，步骤S1进一步包括：

S1.1确定服务设施点与服务需求点的距离测定标准，这里的距离是欧氏距离，也可以是行车距离、行车时间，或者网络距离等，这些距离在联系地区实际时，较容易调查得到；

S1.2计算或者调查得到各需求点至各设施点的最短距离d_ij；

S1.3构建服务设施点与服务需求点的距离矩阵。

步骤S2进一步包括：

S2.1获取各需求点每一特定时间点上的人口数量a_i；

S2.2求得每一个可选设施点至各需求点的加权平均距离：

${\bar{d}}_i=\frac{\underset{i=1}{\overset{m}{\Sigma }}{a}_i{d}_{\mathrm{ij}}}{\underset{i=1}{\overset{m}{\Sigma }}{a}_i}$

其中，m为需求点的个数。

步骤S3进一步包括：

S3.1计算各需求点与设施点两两之间的加权距离a_id_ij；

S3.2用加权距离a_id_ij减去加权平均距离得到每一个需求点至设施点的离差；

S3.3对每一个离差进行平方，即

S3.4根据步骤S3.3所得的离差的平方，构建设施点与各需求点的加权距离方差的矩阵。

步骤S4进一步包括步骤：

S4.1确定决策变量X_ij及Y_ij，X_ij为0-1变量，若需求点i被设施点j覆盖，则X_ij取1，否则取零，Y_ij为也为0-1变脸，若可选择的设施点j被选择进行设施建设，则Y_ij取1，否则取0；

S4.2根据选取加权距离方差最小的设施点的选址原则，即：加权距离方差最小的多设施公平选址问题，等价于确定p个设施点，使之服务于需求点，并使各个需求点至设施点的加权距离方差最小，建立目标函数：

$\min z=\frac{\underset{j=1}{\overset{n}{\Sigma }}\underset{i=1}{\overset{m}{\Sigma }}{(a_i{d}_{\mathrm{ij}}-{\bar{d}}_j)}^2{X}_{\mathrm{ij}}}{\underset{i=1}{\overset{m}{\Sigma }}{a}_i}$

其中，n为设施点的个数，之后附加必要的约束条件，其基本步骤为：

(1)使得选定的是十点覆盖需求点，有X_ij≤Y_j，

(2)强化设施点的服务效率，保证每一个需求点最多可有一个设施点提供服务，消除各设施点间的重复覆盖问题，即：

$\underset{j=1}{\overset{n}{\Sigma }}{X}_{\mathrm{ij}}\le 1,\forall i;$

(3)指定选择的设施点数为p，即

$\underset{j=1}{\overset{n}{\Sigma }}{Y}_j=p;$

(4)限制决策变量X及Y，X_ij＝0，1，Y_ij＝0，1。

步骤S5中求解所述目标函数的方法为蚁群算法，求解包括步骤：

S5.1nc←0(nc指算法的迭代步数或搜索次数)，各参数初始化；

S5.2设置每个蚂蚁对应各变量的初始组合，对每个蚂蚁计算对应变量组合的最小值，计算变量组合的差异，计算转移概率是否进行组合交换，若交换，则将组合i用j替代，增加j各变量的信息素；

S5.3计算各蚂蚁的目标函数值，记录当前最好解；

S5.4按更新方程修改轨迹强度，更新方程为：

${\tau }_i\left(\mathrm{next}\right)=(1-\rho ){\tau }_i\left(\mathrm{old}\right)+\underset{k=1}{\overset{m}{\Sigma }}{\tau }_i^k;$

S5.5置$▿{\tau }_{\mathrm{ij}}\leftarrow 0;\mathrm{nc}\leftarrow \mathrm{nc}+1;$

S5.6若nc小于预定迭代次数且无退化行为，则转至步骤S5.2；

S5.7求出当前最好解。

依照本发明一种实施方式的多设施公平选址系统包括：距离矩阵构建模块，用于计算需求点至各设施点的最短距离，构建距离矩阵；加权平均距离计算模块，用于根据所述距离矩阵构建模块构建的距离矩阵，计算每一个可选设施点至各需求点的加权平均距离；加权距离方差矩阵计算模块，用于构建各设施点与需求点的加权距离方差的矩阵；目标函数构建模块，用于根据选取加权距离方差最小的设施点的选址原则，构建公平选址目标函数；求解模块，用于求解所述目标函数，完成多设施公平选址。

以中国国家级应急物资贮备设施选址问题为例，实施过程考虑《中华人民共和国国家突发公共事件总体应急预案》、《国家突发事件应对法》的相关要求。《中华人民共和国国家突发公共事件总体应急预案》把各类突发公共事件按照其性质、严重程度、可控性和影响范围等因素，一般分为四级：Ⅰ级(特别重大)、Ⅱ级(重大)、Ⅲ级(较大)和Ⅳ级(一般)。

本发明的方法主要适用于应对Ⅰ级(特别重大)、Ⅱ级(重大)突发事件情况下的设施选址问题，也即当突发事件发生后，在中央政府指导下，省级政府(或者省级政府间联合)负责，需要调用国家级应急物资储备资源的情形。由于各省级政府所在地的巨大的经济、文化、技术以及资源调度能力，因此，不失一般性，以我国各省级政府所在地代表本发明方法模型中的各设施点与需求点。

考虑我国大陆范围内将选择24省级政府单位建立国家级应急物资储备库，以应对Ⅰ级(特别重大)、Ⅱ级(重大)突发事件下的情况，假设各设施点(应急物资储备库)能够独立满足自己覆盖半径内的需求点的救助需求，不需其它设施点的协助。上述条件下，确定我国国家级应急资源储备库选址公平准则为加权距离方差最小的准则，依照本发明方法所建目标函数完全能够满足我国国家级应急资源储备库选址问题的要求。我国各省级政府之间距离用欧氏距离表示，数据主要可根据我要地图网网站的测距功能测得。如图1所示，依照本发明一种实施方式的多设施公平选址方法主要包括步骤：

S1.测得我国大陆31个省级政府单位两两之间的距离，即需求点至设施点的最短距离，构建距离矩阵；

S2.根据所得距离矩阵，计算每一个可选设施点至各需求点的加权平均距离，基本步骤如下：

S2.1调查得到我国大陆每一省级政府单位每一特定时间点上的人口数量a_i；

S2.2求得可选设施点(有可能被选择建设国家级应急物资储备库的省级政府单位)至各需求点的加权平均距离：

${\bar{d}}_i=\frac{\underset{i=1}{\overset{m}{\Sigma }}{a}_i{d}_{\mathrm{ij}}}{\underset{i=1}{\overset{m}{\Sigma }}{a}_i}$

S3.构建各设施点与需求点的加权距离方差的矩阵，基本步骤如下：

S3.1计算各省级政府单位(即各设施点与需求点)两两之间的加权距离a_id_ij；

S3.2用各需求点至设施点之间的加权距离a_id_ij减去每一个可选设施点至各需求点的加权平均距离得到每一需求点至设施点的离差；S3.3对每一个需求点至设施点的离差进行平方，即

S3.4根据步骤S3.3所得的离差平方，构建各设施点与需求点的加权距离方差的矩阵。

S4.分析得到：在步骤S1-3工作的基础上，加权距离方差最小的多设施选址公平问题，等价于确定多个设施点，使之服务于需求点，并使各个需求点至设施点的加权距离方差最小，从而建立我国国家级应急物资储备库公平选址问题的目标函数；

S5.附加上述必要的约束条件，完成我国国家级应急物资储备库多设施公平选址优化设计；

S6.利用Borland Delphi 7.0编写蚁群算法程序，在PC机windows xp环境下运行，完成多设施公平选址问题的求解计算。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下，还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明的范畴，本发明的专利保护范围应由权利要求限定。