近年来,全球各类自然灾害等非常规突发事件的发生频率和影响范围不断增加,给受灾地区的经济和人民群众的生命财产安全造成了巨大损失。中国是世界上遭受自然灾害最为严重的国家之一,每年因灾造成的经济损失都在1 000亿元以上,占国民经济生产总值的3%~5%,常年受灾人口达2亿人次。据民政部《2015年全国自然灾害基本情况》显示,2015年,各类自然灾害共造成全国18 620.3万人次受灾,819人死亡,148人失踪,644.4万人次紧急转移安置,181.7万人次需紧急生活救助;24.8万间房屋倒塌,250.5万间房屋受到不同程度的损坏;农作物受灾面积21 769.8千公顷,其中绝收2 232.7千公顷;直接经济损失2 704.1亿元。[1]城镇作为中国行政组织结构中最重要的基础组成部分,承载了中国绝大部分人口,是当前中国推动城镇化建设和经济发展的主战场。然而,随着人口的不断积聚,城镇规模的不断扩大,地震、泥石流及洪涝等自然灾害对经济建设和人民生命财产损失造成的影响也日益增大,因此,如何构建与中国当前实际情况相符的应急物资储备与救援体系已成为政府和学者们日益关注的焦点问题之一。
应急物资储备库作为一类重要的应急公共服务设施是政府提供应急物资和开展应急救援工作的重要载体,在灾前进行物资储备、灾中进行应急物资分配和灾后重建等过程中都发挥着无可取代的基础性作用,是国家减少灾害损失,保证灾区经济、社会生产活动和灾民日常生活尽快恢复正常的重要公共基础设施。应急设施选址自1972年Berlin在其博士论文中首次系统提出后[2],越来越多的学者开始该问题研究,如Larson构建了hypercube模型及其扩展模型[3]。Drezner对比分析了p-中值模型、p-中位模型、最大覆盖模型等5种选址模型在研究地震应急避难场所选址问题时的优缺点。[4]当前,在应急设施选址模型研究中,覆盖模型发展最为迅速,学者们从不同角度出发,结合各类应急设施选址特点,发展出了一系列扩展模型。
首先,针对需求点与设施点间距离小于某一距离时则认为被完全覆盖,反之则不被覆盖的假设:Berman等提出了基于逐渐覆盖思想的最大覆盖模型及其求解方法[5];Drezner等通过构建逐渐覆盖模型用于解决存在消费者满意度差异的选址问题[6];张宗祥等从客户满意和服务质量水平的角度出发,以逐渐覆盖思想和最大覆盖模型为基础,构建了基于服务质量水平的随机逐渐覆盖模型,并设计了求解该模型的拉格朗日算法[7];陈义友等基于逐渐覆盖理论,并结合自提点选址的特点,构建了基于逐渐覆盖的自提点选址模型[8];马云峰等从消费者的角度提出了基于时间满意的最大覆盖模型及扩展模型[9];陆相林等针对覆盖半径内需求满意差异问题,提出了覆盖半径内需求满意度递减的最大覆盖设施选址模型[10]1000—1008;范建华构建了基于阶梯型衰退效用函数的竞争选址问题[11]。
其次,针对一个需求点只能由一个设施点提供服务的假设:Hogan和ReVelle在研究应急服务网络选址问题时,构建了考虑备用覆盖的最大覆盖模型[12];Araz等以最大覆盖和备用覆盖思想为基础,以覆盖人口最大化和总旅行距离最小化为目标,研究了应急服务车辆定位问题[13];万波和万敏以首次覆盖人口最大化、备用覆盖人口最大化和非覆盖范围内总的旅行成本最小化为目标,构建了相应的3目标应急设施选址模型[14];Daskin和Stern在研究应急医疗服务车辆选址问题时,针对传统集合覆盖模型在计算和实践中的局限性,提出了多重覆盖的集覆盖模型[15];葛春景等针对重大突发事件发生后多个应急需求点同时需求和多次需求的特点,提出了应急设施多重覆盖选址模型[16];王文峰等以最大覆盖选址模型和部分覆盖思想为基础,构建出应急设施多级覆盖选址模型[17]144—148;肖俊华和侯云先考虑设施选址的公平性、效率性及成本等因素,结合多级覆盖和覆盖衰减思想,提出应急设施选址多级覆盖选址模型,并采用遗传算法进行求解[18-20]。
文献梳理发现,目前对应急公共设施选址问题的研究已取得众多成果,但仍存在一些不足:①主要通过设施点与需求点间距离(或通行时间)确定需求满意度,忽视了两者间的道路状况,然而在实际应急救援中,道路状况往往是保障应急救援效果的决定因素。②一般从覆盖半径或满意度的角度出发确定设施点位置及服务范围,从供需的角度出发考虑问题较少,因此,难以客观反映应急救援活动的真实情况。因在许多情况下,由于受到道路、救灾人员数量等客观条件的制约,导致应急设施点对应急需求点的应急服务能力有限且小于应急需求点的需求,当灾害发生后,只有持续保障足够的应急服务,才能最大限度地降低灾害造成的损失。③在应急设施选址问题研究中,静态模型研究较多,动态模型研究较少。然而,应急救援活动本身是一个动态变化过程,随着应急救援工作的开展,灾区的道路状况、应急物资储备库对应急需求点的物资供应能力及应急需求点的应急物资需求量等均处于动态变化过程中,因此,应急设施的布局优化亦是一个动态规划过程。
基于以上分析,文章研究了应急物资储备库动态多重覆盖模型。该模型首先在构建满意度函数过程中,通过引入道路风险系数反映应急物资储备库与应急需求点间的道路状况,提高函数科学性和适用性;之后,从供需和时间维度两个角度出发,结合最大覆盖选址模型和“多重覆盖”思想,建立应急物资储备库动态多重覆盖模型,该模型的决策目标是使总需求满意度最大和总配送距离最短。
二、模型的建立 (一) 问题描述文章所研究的问题是,如何科学地确定各阶段城镇应急物资储备库的开放位置及服务范围,以期在灾害发生后及时有效地为受灾地区提供应急物资保障,达到最大限度降低灾害损失。此类设施具有使用率较低,建设运营成本大等特点,但在应急救援中起着关键作用。因此,在满足一定需求的情况下,建设一定数量的应急物资储备库具有重要的现实意义。
灾害发生时,若应急物资储备库所在地受到破坏,则应急物资储备库直接向该地提供应急物资;若该应急物资储备库服务范围内其他地区遭到破坏,则从该应急物资储备库调配应急物资发往受灾地区。因受交通状况、救援人员数量等因素制约,导致单个应急物资储备库发往受灾地区的应急物资数量有限,且往往低于应急需求点的需求量。此外,随着应急救援工作的不断深入,受灾地区道路状况将不断改善,应急物资储备库的物资供应能力将逐渐增强,应急需求点对应急物资的需求量将在一定程度上有所降低,因此,文章从供需和时间维度2个角度出发研究此类问题。为建立数学模型描述以上问题,文章做如下假设:
假设1.应急物资储备库和应急需求点在选址区域内离散分布,且任意应急物资储备库和应急需求点间的距离为欧式距离。
假设2.应急物资储备库布局优化可划分为多个阶段,每个阶段应急物资储备库开放数量已知。
假设3.任意应急物资储备库的容量无限,但应急物资储备库对应急需求点的物资供应能力有限,且各阶段不同。
假设4.随着灾区状况逐渐好转,选址区域内应急物资储备库的物资供应能力逐渐增强,应急需求点的物资需求量逐渐下降,因此,应急物资储备库开放数量随之减少,且后阶段选择开放的应急物资储备库只能从前一阶段中选取。
假设5.每个应急物资储备库可为多个应急需求点提供服务。
假设6.每个应急需求点需要一个或多个应急物资储备库为其提供服务。
(二) 满意度衰减函数在传统的覆盖模型中,一般认为同一设施点的覆盖半径内需求点的满意程度是相同的,然而在实际的应急救援活动中,应急物资储备库和应急需求点间的距离和道路状况对最终的救援效果往往具有决定性作用,因此,文章借鉴陆相林等提出的覆盖半径内需求满意度递减思想[10]1000—1008和王文峰等提出的反映时效性评价函数构建方法[17]144—148,并引入道路风险系数概念,构建如下满意度衰减函数:
(1) |
其中:ρijs为s阶段应急物资储备库j与应急需求点i之间的道路风险系数,且ρijs为s阶段应急物资储备库j与应急需求点i间救援通道隐患点数与整个选址区域内救援通道隐患点总数间的比值,且ρijs∈[0, 1];β为应急物资储备库对应急需求点提供服务的敏感系数,且β∈[0, 1];max(dij)为任意应急需求点与应急物资储备库间的最大距离。
(三) 基于满意度衰减函数的动态多重覆盖模型令I={I1, I2, …, Im} 和J ={J1, J2, …, Jn}分别为应急需求点和候选应急物资储备库的集合;s为应急救援活动开展阶段(s=1, 2, …, q);ps为s阶段需开放的应急物资储备库数量;Qis为s阶段应急需求点i的需求量;dij为应急需求点i与候选应急物资储备库j间距离;uijs为s阶段候选应急物资储备库j对应急需求点i的物资供应量;f ijs为s阶段候选急物资储备库j对应急需求点i的满意度水平;xijs为0, 1变量,当xijs为1时,表示s阶段应急需求点i被应急物资储备库j覆盖,否则为0;yjs为0, 1变量,当yjs为1时,表示候选应急物资储备库在s阶段被选中,否则为0。
(2) |
(3) |
S·T·
(4) |
(5) |
(6) |
(7) |
目标函数(2)是使应急需求点被多个应急物资储备库覆盖的总需求满意度最大;目标函数(3)是使应急需求点被多个物资储备库覆盖的总距离最短;约束条件(4)为在s阶段只有当候选应急物资储备处j被选定时,应急需求点i才能被覆盖;约束条件(5)为在s阶段必须保证具有足够物资供应量的应急物资储备库覆盖应急需求点;约束条件(6)为在s阶段需建设的应急物资储备库数量;约束条件(7)保证xijs和yjs均为二元整数决策变量。
三、模型转化与算法选择 (一) 模型转化多目标规划指研究多于一个的目标函数在给定区域上的最优化问题,且常常这些目标之间具有冲突关系。[21]目前,已发展出多种较为成熟的方法用于求解多目标规划,如Pareto最优性分析、目标规划方法、模糊多目标规划方法及参数规划方法等。
加权法和约束法是参数规划法中常用的两种方法,其核心是通过将多目标模型转化为单目标线性规划模型后进行求解。其中,加权法通过对每个目标Zk赋予一个权系数λk的方式,将多目标准则函数转化为单目标准则函数,当
令λ1和λ2分别为目标函数Z1和Z2的权系数,且λ1+λ2=1,则上节所建模型可转换为如下形式:
(8) |
S·T·:(4)~(7)
(二) 算法选择[23]最大覆盖模型已被学者们证明为NP-Hard问题[24],因此,文章所构建的应急物资储备库动态多重覆盖模型作为最大覆盖模型的扩展模型,亦是NP-Hard问题,针对此类问题,目前学者们普遍选用启发式算法求得满意解。文章选用免疫优化算法对模型进行求解。
免疫优化算法是一种以免疫学理论为基础,模仿生物系统区分外部有害抗原,从而维持有机体稳定的智能启发式算法。针对遗传算法在求解问题时交叉和变异算子相对稳定,灵活度较低,且忽视问题的特征信息对求解问题时的辅助作用等方面不足,学者们通过将免疫概念及理论与遗传算法结合,构建得到免疫优化算法。该算法力图在保留遗传算法原有优良特性的前提下,利用免疫系统的多样性产生和维持机制来保持群体多样性的特点,达到克服求解多峰函数过程中难处理的“早熟”问题,最终求得全局最优解。
1.抗体编码和抗体群的产生
文章选用简单直观的实数编码方式,每个选址方案形成一个长度为p的抗体(p为区域物流中心的个数),每个抗体代表一组被选为应急物资储备库的序列。由于免疫优化算法需要从一个初始抗体群开始计算,因此,文章通过随机的方式产生一个群体规模为M的初始抗体群。为了提高算法的收敛速度,因而在每次迭代过程中选出N个最优抗体存入记忆库,并在下一代计算中取出与子代抗体组合成新的抗体群进行下一步迭代运算。
2.抗体亲和度评价函数
抗体群中的抗体亲和度评价函数由目标函数式(8)计算得到。具体计算过程如下:
第一步:选择一个应急需求点,将各候选应急物资储备库对该应急需求点的物资供应能力进行降序排序(若出现供应能力相同,则满意度大的在前)。
第二步:判断前k(k=1, 2, …, ps)个基因位代表的应急物资储备库对该应急需求点的物资供应能力之和与该应急需求点的应急物资需求量Qis间的大小关系,若大于等于,求出其对应位置的λ1Z1-λ2Z2值,否则,取0。
第三步:重复步骤1~步骤2,遍历所有应急物资需求点后求和,即为该抗体亲和度评价函数值。
3.免疫操作
该部分内容与遗传算法的主要步骤一致,包括选择、交叉和变异。
(1) 选择,文章选用常用的轮盘赌法进行选择操作。
(2) 交叉,采用单点交叉法进行交叉操作。
(3) 变异,选择常用的随机选择变异位进行变异操作。
4.终止条件
记录下每次迭代过程中抗体亲和度值最大的抗体,直到达到算法设定的最大迭代次数。当算法终止时,抗体亲和度值最大的抗体所代表的选址方案,即为该问题的满意解。
5.免疫优化算法具体步骤
根据以上分析,具体步骤如下。
第一步:初始化参数,定义免疫优化算法的抗体群规模、记忆库规模、最大遗传代数、交叉概率、变异概率等。
第二步:产生初始抗体群。如果记忆库为非空,则初始抗体群从记忆库中选取,否则,从可行解空间中随机生成。
第三步:解的多样性评价。首先,分别计算抗体和抗原间的亲和力、抗体和抗体之间的相似程度及抗体浓度;然后在以目标函数作为适应度函数,计算抗体的亲和力,并进一步得到各抗体的期望繁殖概率。
第四步:免疫操作。此部分与遗传算法相似,主要包括选择、交叉和变异操作。
第五步:判断是否满足结束条件,如果是转到第三步,否则结束,输出结果。
四、实例分析某区域有15个应急需求点,随着应急救援工作的不断深入,当地政府计划分2个阶段从中选择开放若干数量的应急物资储备库以应对突发事件的发生,目标是以最小的总配送距离最大化满足应急需求点的总需求满意度。各应急需求点的位置为[0, 100]区间随机产生的15组随机整数。第1阶段,应急需求点的应急物资需求量在[20,50]间随机产生,应急物资储备库对应急需求点的物资供应能力在[5, 15]间随机产生;根据假设4,第2阶段应急需求点的应急物资需求量Qis在前一阶段的基础上按比例减少,应急物资储备库对应急需求点的物资供应能力uijs在前一阶段的基础上按比例增加,变动幅度均在[0.1, 0.3]间随机产生,具体情况如表 1和表 2所示。
为了分析说明应急物资储备库动态多重覆盖模型的特点及有效性,文章设p1=6,p2=4;道路风险系数ρijs在[0, 1]间随机产生,敏感系数β=2,且第1阶段和第2阶段相同;模型中,目标函数Z的权系数λ1、λ2分别为0.6和0.4。
基于算例的输入参数,利用应急物资储备库动态多重覆盖模型,来确定该例中应急物资储备库在第1阶段和第2阶段的布局及服务范围。用matlabR2013b软件按照上述改进的免疫优化算法编程求解此模型,其中种群规模为50,记忆库容量为10,迭代次数为200,交叉概率为0.5,变异概率为0.4,多样性评价参数为0.95。求解结果如表 3、表 4和表 5所示。
由表 3和表 4可知,当假定第1阶段开放应急物资储备库数量为6个时,需求点1, 3, 5, 6, 8和10被选为应急物资储备库开放点,总需求满意度为365.17,总距离为1 418.04。此时,应急物资储备库1为应急需求点1和11服务,提供的应急物资量分别为33和14;应急物资储备库3为应急需求点3, 4, 7, 9, 13, 14和15服务,提供的应急物资量分别为47, 13, 15, 15, 13, 14和13;应急物资储备库5为应急需求点4, 5, 7, 11, 12, 13, 14和15服务,提供的应急物资量分别为14, 28, 11, 10, 11, 15, 9和12;应急物资储备库6为应急需求点2, 4, 6, 7, 11, 12和14服务,提供的应急物资量分别为14, 12, 37, 14, 13, 15和12;应急物资储备库8为应急需求点4, 8, 9和15服务,提供的应急物资量分别为11, 50, 15和13;应急物资储备库10为应急需求点2, 10, 13, 14和15服务,提供的应急物资量分别为12, 47, 13, 11和10。
由表 3和表 5可知,当假定第2阶段开放应急物资储备库数量为4时,第1阶段中的应急物资储备库3, 6, 8和10被选中,总需求满意度为303.23,总距离为1 351.47。此时,应急物资储备库3为应急需求点3, 4, 7, 9, 11, 13, 14和15,提供的应急物资量分别为38, 15, 19, 18, 10, 15, 16和14;应急物资储备库6为应急需求点2, 6, 7, 11, 12和14服务,提供的应急物资量分别为16, 33, 16, 16, 18和14;应急物资储备库8为应急需求点1, 4, 5, 8, 9, 11和15服务,提供的应急物资量分别为15, 14, 16, 45, 19, 9和14;应急物资储备库10为应急需求点1, 2, 4,5, 10, 12, 13, 14和15服务,提供的应急物资量分别为17, 13, 13, 12, 36,12, 16, 13和12。
五、结论由于道路交通状况对应急救援效果具有重要影响,文章在构建满意度衰减函数时,引入了道路风险系数这一概念,这将有利于更加准确的反映应急设施点和应急需求点间的需求满意度。此外,根据城镇突发事件应急的特点,文章从供需和时间维度两个角度出发,构建了城镇应急物资储备库动态多重覆盖模型,本模型以总应急需求满意度最大和总距离最小为目标。通过运用线性加权法将原双目标模型转变为单目标模型后,编写免疫优化算法进行求解。通过对随机生成的算例进行计算,说明了模型及算法的有效性。
城镇应急物资储备库动态多重覆盖模型能够在一定程度上反映城镇应急物资储备库布局特点,但是,在研究过程中仍有许多因素未考虑,如应急物资储备库的容量限制问题,增加应急物资储备库容量限制将会大大增加模型的求解难度,但却可以更加准确的贴合实际,这是笔者下一步研究的重点。
[1] |
中华人民共和国民政部.2015年全国自然灾害基本情况[EB/OL].(2016-01-11).http://news.hexun.com/2016-01-11/181727845.html.
|
[2] |
BERLIN G N.Facility location and vehicle allocation for provision of an emergency service[D]. Baltimore: Johns Hopkins University, 1972.
|
[3] |
LARSON R C. A hypercube queuing model for facility location and redistricting in urban emergency services[J]. Computers & Operations Research, 1974(1): 67-95. |
[4] |
DREZNER T. Location of casualty collection points[J]. Environment and Planning C:Government and Policy, 2004, 22(6): 899-912. DOI:10.1068/c13r |
[5] |
BERMAN O, DREZNERB Z, KRASS D. Generalized coverage:New developments in covering location models in covering location models[J]. Computers and Operations Research, 2010(37): 1675-1687. |
[6] |
DREZNER Z, WESOLOWSKY G O, DREZNER T. The gradual covering problem[J]. Naval Research Logistics, 2004, 51(6): 841-855. DOI:10.1002/(ISSN)1520-6750 |
[7] |
张宗祥, 杨超, 陈中武. 基于服务质量水平的随机之间覆盖模型与算法[J]. 工业工程与管理, 2012, 17(5): 35-45. DOI:10.3969/j.issn.1007-5429.2012.05.007 |
[8] |
陈义友, 陈以衡. 基于逐渐覆盖的自提点模型与算法研究[J]. 计算机应用研究, 2015, 33. |
[9] |
马云峰, 杨超, 张敏, 等. 基于时间满意的最大覆盖选址问题[J]. 中国管理科学, 2006, 14(2): 45-51. DOI:10.3321/j.issn:1003-207X.2006.02.008 |
[10] |
陆相林, 侯云先, 林文, 等. 基于选址理论的小城镇应急物资储备库优化配置:以北京房山区为例[J]. 地理研究, 2011, 30(6): 1000-1008. |
[11] |
范建华. 基于阶梯型衰退效用函数的竞争选址问题[J]. 管理学报, 2009, 6(12): 1638-1642. DOI:10.3969/j.issn.1672-884X.2009.12.013 |
[12] |
HOGAN K, REVELLE C. Concepts and applications of backup coverage[J]. Management Science, 1986, 32(11): 1434-1444. DOI:10.1287/mnsc.32.11.1434 |
[13] |
ARAZ C, SELIM H, OZKARAHAN I. A fuzzy multi-objective covering-based vehicle location model for emergency services[J]. Computers & Operations Research, 2007, 34(3): 705-726. |
[14] |
万波, 万敏. 基于备用覆盖的应急服务设施选址问题研究[J]. 武汉理工大学学报(信息与管理工程版), 2015, 37(6): 730-734. DOI:10.3963/j.issn.2095-3852.2015.06.015 |
[15] |
DASKIN M S, STERN E H. A hierarchical objective set covering model for emergency medical service vehicle deployment[J]. Transportation Science, 1981(15): 137-152. |
[16] |
葛春景, 王霞, 关贤军. 重大突发事件应急设施多重覆盖选址模型及算法[J]. 运筹与管理, 2011, 20(5): 50-56. DOI:10.3969/j.issn.1007-3221.2011.05.009 |
[17] |
王文峰, 郭波, 刘新亮. 多级覆盖设施选址问题建模及其求解方法研究[J]. 中国管理科学, 2007(15): 144-148. |
[18] |
肖俊华, 侯云先. 应急物资储备库多级覆盖选址模型的构建[J]. 统计与决策, 2012(23): 45-48. |
[19] |
肖俊华, 侯云先. 考虑多级覆盖衰减的双目标应急设施选址模型及算法[J]. 软科学, 2013, 26(12): 127-131. |
[20] |
肖俊华, 侯云先. 区域救灾物资储备库布局优化的实证研究:以北京市昌平区为例[J]. 经济地理, 2013, 33(2): 135-140. |
[21] |
韩庆兰. 物流设施规划的多目标优化模型[J]. 控制与决策, 2006, 21(8): 957-960. DOI:10.3321/j.issn:1001-0920.2006.08.026 |
[22] |
陈志宗, 尤建新. 重大突发事件应急救援设施选址的多目标决策模型[J]. 管理科学, 2006, 19(4): 10-14. |
[23] |
史峰, 王辉, 郁磊, 等. MATLAB智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2010: 118-129.
|
[24] |
KARIV O, HAKIMI S L. An algorithmic approach to network location problems[J]. SIAM Journal on Applied Mathematics, 1979, 37(3): 513-560. DOI:10.1137/0137040 |