队城市应急系统优化选址的模型及其算法(共40页)

1、精选优质文档-倾情为你奉上城市应急系统优化选址的模型及其算法队伍编号：046队员： 王天成 代川 李黎摘要本文针对城市应急系统选址问题，结合2中位点理论模型、图论的相关理论和优化方法，在不同的约束条件下，建立了城市应急系统优化选址模型，并且给出了多种条件下最优方案的求解算法。主要工作如下:问题一：我们通过年度、月、以及每个街区等不同的维度来找出事件发生的规律性，挖掘出其发生的规律性如下：每年中每个街区发生应急事件次数主要集中在1、11、12月份；1-8号街区在10年中发生应急事件次数的波动较小；用50个街区00年到09年平均的应急事件次数，通过系统.聚类，发现50个街区可以聚类分成5类。分析过

2、程中，我们发现过去十年的应急事件发生总数原始数据呈现S形，因此我们建立了灰色Verhulst预测模型，对不确定性的应急事件对2010年的预测，为问题二的数据来源做准备。问题二：我们通过建立笛卡尔直角坐标系给各个街区、街道、街角定位，将总响应时间转化为权距离，并结合图论，使用了一种独立的最短路算法，求得每个需求点和应急服务地点在坐标系内的最短距离。通过matlab编程求出的结果为第16号和44号应急服务供给点，最终服务店定位在8、9、13、14号街区的街角处，另一个定位在31、32、36、37号街区的街角处。问题三：对于问题三，我们采取的策略跟问题二基本一致，我们首先假设两个障碍区中道路可以通过

3、，用问题二的算法，求解得到了一组备选点分别与第8号备选点（即已确定的1、2、6、7号街区之间的街角处）的组合方案，然后考虑L型和长条形的障碍区域的影响，对这些组合的总响应时间进行调整。最后通过matlab计算的方式确定了另外一个点的位置在45号应急设备点，即第32、33、37、38号街区之间的街角处。问题四：问题四跟问题二的问题不同点在于问题二不考虑障碍的影响，而问题四考虑了障碍的影响，但是我们发现，障碍的影响范围是有限的，只对部分的应急设施点产生障碍，因此，我们在问题二和三结合的基础上，求得了与问题二相同的答案，即在第16号和44号应急设施点，原因是由于最佳的两个组合点没有受到障碍区域的影响

4、。 问题五：对于问题五，我们首先证明了无向图的顶点是最优应急设施供给点的备择点，并且优于至少不劣于相应边的内点。然后顺利的把应急设施的备选点转化到了顶点（也就是街角处）。然后，计算出所有应急设施供应点的组合到所有街区的最短权距离即总响应时间。通过matlab编程实现求解过程，最终的应急设施的选择点在16、45号应急设施备选点，16号选址点在8、9、13、14号街区的中心街角处，45号选址点在32、33、37、38号街区中心街角处。 关键字 灰色verhulst预测 受限制选址优化 优化算法 2-中位问题 应急系统选址问题第一部分 问题重述 对社会各种突发事件进行处理的应急系统中，应急服务设施的

5、选址涉及经济、技术、社会、安全等多方面因素。因此在应急服务设施的选址上，如何建立一个满足约束条件的优化模型，成为实际问题的重中之重。 从本文的要求来看，主要是讨论在不同的约束条件下，多个服务点选址的问题。题目中给出了50个街区，及其相互之间的道路图，而且在城市中间设定了两个障碍区域，并且应急车辆驶过一条垂直向的街区平均要花20秒，而通过一条水平向的街区平均要花30秒。附录中给出了过去10年间每个街区每月发生应急事件的次数，因此，为了提高该城市突发事件的处理能力而且，在考虑未来10年的应急事件发生的基础上，欲建立两个应急服务设施，考察应急服务设施的选址，要分别对如下问题进行探讨：1、分析各街区应

6、急事件发生的规律；2、假定应急需求集中在每个街道的中心，而应急设施位于街角处，并假设两个障碍区域中道路可以通过。为使总的响应时间最少，确定这两个应急设施的位置。3、假定应急需求集中在每个街道的中心，而应急设施位于街角处，并假设两个障碍区域中道路不能通过。若一个应急设施的位置已经确定位于1、2、6、7的街角处。为使总的响应时间最少，确定另一个应急设施的位置。4、第3问中若两个应急设施的位置均未确定，试确定这两个应急设施的位置。5、若第4问中，将假定改为：假定需求是沿包围每个街区的街道上均匀分布的，而应急设施可位于街道的任何地方。问题又如何求解？第二部分 基本假设 1. 题目中附录所给的数据真实可

7、靠 2. 假设每个街区的中心存在一个点，作为临时需求中转点，便于求出需求点与应急供给点的最短距离； 3. 假设每个街区的中心点到街区周围的街道中需求点的距离，垂直向的距离为10，水平向的的距离为15。 4. 应急设施点设定的原则只考虑其未来发生的次数，不考虑应急事件的严重程度。 5. 在应急车辆进行救助的过程中，不存在道路拥堵的情况。 6. 对于障碍区，不能通过障碍区内部的的街道，但是可以通过障碍区外围的街道。第三部分 符号说明符号含义表示原始数据列表示的紧邻均值数列均方差比值，用于检验verhulst预测模型的精确度0-1变量，表示第j个点是否被选为应急设施点0-1变量，表示第j号应急设施点

8、是否服务于第i个街区无向网络全图表示第i个街区的编号，应急服务供给点的编号，表示第i个街区中心点的坐标表示第j个应急设施供给点的坐标第i个街区的需求权重，它是未来10年平均每年发生应急事件的次数表示第j个服务点到第i个街区的距离总系统响应时间A是最短路矩阵，B是最小值矩阵，W是权重矩阵受障碍影响的应急服务点的集合表示由于障碍区域而导致的响应时间的增加量受障碍区域影响，街区最短距离路径变化的集合第四部分 问题分析 本问题涉及到的是关于城市应急系统的选址问题，面对城市中突发事件的的应急处理，对应急服务设施进行选址优化。由于垂直向街道和水平向的街道花费的时间不一样，因此，为了使得总的响应时间最少，如

9、何选择应急服务设施的位置。4.1 基本思路题目中给出了过去十年中每个街区每个月发生应急事件的次数，但是由于突发时间的发生是具有不确定性的，因此就加大了从这些数据中挖掘出规律性的难度；找到了每个街区每月或者每年发生应急事件的次数后，由于题目中要求是在考虑未来10年应急事件发生的基础上来建立服务站，所以要对未来10年的数据进行准确的预测，方法和工具的选择也是难点；预测出了未来的数据后，就把这个数据的平均值作为每个街区的需求权重，这对确定应急设施的位置有重大的约束作用；后面的问题是如何在考虑L型和长条形状的障碍区域的基础上，分别选址。服务点选址的原则有：每个服务店都要覆盖到一部分需求点；使得总的响应

10、时间最少；服务点只能位于街角处；基于上面的难点与重点原则，我们运用灰色系统理论里面的Verhulst模型对2010年的数据进行预测，并且将结果作为每个街区的需求权；在后面的四个问题中，由于确定了是建设2个应急服务设施。只是限制的条件不同，因此我们利用建立坐标系的方法简化了问题。4.2 具体分析 对于问题一：先通过excel、spss进行数据统计观察，然后从三个维度进行考察过去十年每个街区之间发生应急事件的规律性。然后通过两种不同的角度的聚类找出了50个街区中，具有某些相似特征的街区。在统计的过程中，我们发现2000到2009之间每个街区之间发生应急事件的综合呈现S型增长，于是就用到了灰色ver

11、hulst理论对2010年的数据进行预测。 对于问题二、三、四，我们发现其基本的模型是一致的，只是在求解算法上的细节差异，对于问题二，我们先求出每个应急设施服务备选点与街区需求之间的一个最短距离矩阵，然后得到最小距离矩阵，通过与权值矩阵的成绩，得到了使得总响应时间最短的两个设施点的组合，即为最优。但是对于问题三来说，由于其中一个点是确定的，在第8号设施点，因此我们只是需要在剩下的65个点中一一与8号设施点作为组合，然后把每种组合按照总响应时间的顺序排名。最后做受障碍区影响的组合的调整，我们发现，最优的组合并没有收到障碍区的影响。对于问题四，也是先假设没有障碍区，然后对受障碍区影响的某些点进行总

12、距离的调整，最后找出最优解。 对于问题五，我们首先利用定理证明了在顶点是最优应急设施供给点的备择点，并且优于至少不劣于相应边的内点。然后就把设施点转化到了原来问题二、三四中的街角处。最后通过计算机模拟的按照均匀分布的特征在每个街区周围进行需求点的模拟，最终通过一种搜索式的算法得到最优解。第五部分 模型建立与求解5.1 问题一的模型及其求解5.1.1 模型准备对于问题一，从过去10年的数据中找出规律，我们主要从4个维度进行考察，五个维度分别是：50个街区在不同年份应急事件发生的次数频率；不同年份的不同月份，应急事件发生的次数统计；应急事件发生的频率在过去10年之间的变化趋势；对不同的街区进行聚类

13、分析，考察各个街区发生应急事件的规律；对每个街区未来的应急事件进行预测。5.1.2 数据挖掘与规律探索 （一）50个街区在不同年份应急事件发生的稳定性 我们对该地所有的50个街区在过去10年发生应急事件次数上，进行了统计，统计的结果如下： 从上图可知，1-8号街区在十年间发生应急时间的频率比较低，而且波动幅度比较小，说明该地比较稳定，除此之外，8号街区，14号街区，19号，41号47号等在不同的年份波动幅度比较大。 （二）过去10年不同月份应急事件发生的频率统计 通过数据观察，我们还发现在不同的年份几乎应急事件的高发频度总是出现在1,11,12月三个月份。具体的统计分析图如下： 由统计分析图可

14、以看到，每年的1月，11月，12月发生应急事件的频率高于其他月份，而且在10年间一直保持几乎相同的态势。 （三）过去十年应急事件发生总数的变化趋势 通过对过去10年每年发生应急事件次数的加总统计，我们发现所有地区加总起来，随着时间增加，应急事件发生的频率也在逐步升高。 从图中，可以看到，过去10年发生应急时间的趋势呈现出一个向上的S型，因此，这满足了灰色verhulst预测模型的要求。 （四）对50个街区应急事件发生次数的聚类分析 （1）聚类模型建立而对街区进行分类的主要衡量指标是每个街区每年发生应急次数的距离分析，这里的距离，我们选择的是欧氏距离平方，其介绍如下： 欧氏距离平方是每个老师打分

15、变量值之差的平方和，在上面的公式中，k是样本的数量，是表示第一个样本在第i个变量上的取值，是表示第二个样本在第i个变量上的取值。 最终得到欧氏距离的距离矩阵： （2）聚类分析的结果 我们把所有的50个街区每年发生次数通过聚类发现，一共可以分成五类，聚类的结果如下： 街区编号聚类结果说明第一类1 、2、3、4、5、6、7、9、10、11、13、16、20、24、25、36、37、39、40、44、45、48、49、50这一类街区发生应急事件在不同的年份中发生的次数少，均在（300,700）之间波动第二类8、14、15、19、21、22、23、26、27、28、31、32、33、这一类街区内部发生

16、应急时间的绝对次数很高，并且稳定性较弱第三类29、30、34、35这一类街区年度的变化趋势不明显，但是其绝对次数也较低第四类41、42、46、47这一类街区内部发生应急时间的绝对次数很高，并且稳定性较强第五类12、17、18、38、43障碍区域 此外我们还对10年的总次数进行了聚类，聚类的结果如下： 街区编号聚类结果说明第一类1217183843障碍区第二类30343529低第三类1339444452925349611750375204010481361624较低第四类2221262328313233中第五类158191427较高第六类47464142高 由此可见，上述中每一类都有各自的特点。

17、因此这也是该街区发生应急事件的规律性。5.1.3 灰色Verhulst预测模型 （一）模型准备我们要对一个不确定性的应急时间发生的次数进行预测，而且是以时间序列预测，因此，我们先对2000年-2009年的应急事件发生次数进行曲线估计。估计如图：该图显示：2000年-2009年的应急事件发生次数呈S型分布，因此使用于用灰色verhulst预测模型对之后的10年进行预测。（2） 模型建立 设为原始序列，为的一次累加生成序列，即为：， 并且 为的紧邻均值生成序列，其满足：， 因此，我们称为灰色verhulst预测模型，其中，a，b均为参数，又有： 为灰色verhulst预测模型的白化方程，t为时间。

18、 灰色verhulst预测模型具有如下定理： NO.1 设灰色verhulst预测模型如上所述，若为参考数列，且则参数列的最小二乘法估计满足： NO.2 设灰色verhulst预测模型如上所述，则白化方程的解（时间相应函数）为： 灰色verhulst预测模型的时间响应序列为： 取为，则上式变为： 其中，累减还原式为： 上述就是灰色verhulst预测模型的模型部分，但是在模型部分后，还有一部分是对模型精确度的检验部分，在灰色模型部分一共有四种检验精确度的方法，我们选取了均方差比合格模型对灰色verhulst预测的精确度检验。对于均方差合格模型，设原始序列为：与其对应的灰色预测的序列为： 因此残

19、差序列为： 则的均值，方差分别是：的均值、方差分别是： 均方差比值，对于给定的，当时即均方差比合格。5.1.4 预测模型求解 对于上面的模型，我们通过matlab编程进行求解，最后还对预测的结果进行了均方差比值的合格精度检验。Matlab源代码见附录一 灰色verhulst预测模型采取的算法步骤如下： 第一步：设初始值i=1,从输入矩阵A中逐步提取出第i行每个街区10年内发生的次数作为初始原始数据列； 第二步：对初始数据列做一次累加生成，变成，转入第三步； 第三步：对累加生成的数列生成一个紧邻均值数列，转入第四步； 第四步：生成B矩阵，为n-1行2列，保持紧邻均值数列，生成一个Y矩阵，用于保存

20、原始序列； 第五步：对参数列中的参数a和b，通过最小二乘，进行求解，转入第六步； 第六步：把参数带入verhulst模型中，并且载入输入的预测的时间长度，保持预测值，并且i=i+1进入第七步; 第七步：判断i是否大于66，如果否，那么返回第一步；如果是，则进入第八步； 第八步：记录每个i产生的预测值，输出预测值 第九步：对预测的结果做精确性评价，计算均方差比值和模拟的精确度； 第十步：返回预测值，以及均方差值和精确度值，算法结束。5.1.5 模型结果评述对于该模型的返回结果，由于我们考虑到下文中需要的是每个街区的应急事件的发生次数，而为应急服务点的选址提供依据，因此我们返回的结果是预测的10年

21、的发生次数，作为选址的依据，返回的结果是：街区编号10年发生应急次数街区编号10年发生应急次数街区编号10年发生应急次数街区编号10年发生应急次数1690.714950.1342271676.940447.17552495.983115977.5281076.7411260.63516.625916562.200629160.6764421178.14494.270217030137.8134305368.705180311200.444497.52746443.5236191012.632921.845411.11967516.058720536.5343331150.84613208922

22、.753821880.234140.6163471253.19410.857222880.235123.886148552.816610525.3876231030.536546.767949458.212911608.725124571.375237513.685550718.612025404.773838013403.860226954.239390.5654而对上述预测结果的检验结果如下：编号精确 度均方差比值编号精确 度均方差比值编号精确 度均方差比值编号精确 度均方差比值10.90.39 140.90.61 2710.18 400.80.57 20.90.46 1510.26 28

23、10.33 410.80.61 30.90.55 160.70.57 290.70.57 420.80.45 40.80.63 1700.00 300.60.63 4300.00 510.36 1800.00 3110.29 440.90.57 60.90.47 190.90.63 320.90.47 450.70.60 70.90.56 200.80.51 3310.30 460.90.52 80.80.54 2110.30 340.90.34 470.90.57 90.80.53 2210.30 350.80.51 480.60.55 1010.45 2310.20 360.80.60 4

24、90.80.73 110.90.38 240.80.64 370.70.57 5010.33 1200.00 250.90.53 3800.00 130.90.64 260.90.42 3910.18 在预测结果里面我们发现所有的预测结果的精确度都在0.6以上，而且大部分都大于0.8（除障碍区点），均方差比值也大都在0.65以下，说明我们的这个预测模型是合格的，所预测的值是比较可靠的5.2 问题二的模型及其求解 5.2.1 模型准备（一）对题设的理解题目中假定应急需求中心在每个街道的中心，我们的理解是应急需求在每个街区的四个方向的街道的中心，也就是说每个街区都有四个需求点，比如说：对于街区1，

25、不论其街区内部什么地点发生应急事件，只要应急车辆赶到任何一个需求点都可以，只要其响应时间最短即可。另外，对于应急设施的位置问题，有两个决定因素，第一个是应急设施与应急需求点之间的距离，第二个是每个街区的应急需求权重。我们的模型中，将二者的乘积即总应急需求权距离作为模型的目标函数。 （二）定义 对于问题二，我们采用图论模型描述待确定的应急服务设施的地点及其约束条件，我们给出如下的定义： 给定一个无向连续网络,其中，为G的点集，为连接G各点间的弧集，为顶点的权重，是弧长，如果弧连接顶点和那么弧气可以表示成，可以表示成，对于G中的任何两个点代表连接点x和点y的最短路径，因此具有以下性质： 设为网络中

26、的j个待确定的应急服务设施点集，定义如下： 网络中的一个顶点到点集的距离为： 5.2.2 模型建立 （一）建立笛卡尔直角坐标系在这个问题上，我们把50个街区和道路放入直角坐标系中，该坐标系带箭头方向为正方向，在这个坐标体系中，应急供应点，应急事件的需求点，以及每个街区的中心点都能一一对应一个坐标。具体的坐标如下图：15009030601201008060402016018020012014023456781109111266第j个服务供给点 j图例应急服务供给点备选点i第i个街区的中心点应急事件需求点 （二）建立应急服务点与街区中心点之间的对应关系 从上面的直角坐标系可以看到，由于每个街区的长

27、和宽是固定的，每个街区的垂直向的街道的响应时间为20秒，水平向的街道的响应时间为30秒。而且，供给点和需求点都能找到对应的坐标；下面给出二者之间的对应关系： 由于第i个街区的中心点的坐标为，因此： 同理，可以得到第j个应急服务设施的坐标： 建立这样的一一对应的关系，主要是为了能够便于计算66个可能设立应急设施的点与任何一个街区之间的最短距离，下面我们举一个例子，通过应急设施的点的坐标与街区中心的坐标之间的互换。 例如：第28个应急设施供给点的坐标为：；第2个街区中心点的坐标为，又如：第12个应急设施供给点的坐标为，第25个街区中心店的坐标为. （三）最短路矩阵、最小值矩阵、权重矩阵 我们对最短

28、路矩阵定义如下：它是集合了所有可能的应急设施供给点与供给需求点（每个街区）之间的最短距离，用符号表示。 最短路矩阵里面的每一个元素的数值是第j个应急设施供给点到第i个街区需求点的最短距离，其计算公式如下： 如下图所示：下图描绘了第28个应急设施供给点到2号街区的最短距离的计算过程，这里，我们解释为什么要减去15，因为我们前面是以每个街区的中心点与每个应急设施点的距离，我们又发现应急设施供给点到某个街区之间的最短距离与应急设施点到街区中心点的最短距离是等价的,而二者之间正好相差15。15009030601201008060402016018020012014023456781109111266第

29、j个服务供给点 j图例应急服务供给点i第i个街区的中心点应急事件需求点（45,10）（90,80）最小值矩阵：它记录的是对于己经求出的最短路矩阵，当以i，j为组合时，我们取第i行和第j行的元素组成一个250的矩阵，比较同列元素，取最小值，并将另一个值赋为0值，若一列的两个元素相同，同时保留，所得矩阵称为最小值矩阵。用B表示。起初，最小值矩阵如下：然后，取每一列的最小值进行变换： 权重矩阵：权重矩阵是记录每一个街区在未来10年的突发事件发生的频率次数，该矩阵的具体数值，我们通过灰色系统预测方法预测得到，用表示。(4) 约束条件在本问题中，约束条件大致有如下： （1）保证每个需求点有且仅由一个设施

30、点为其服务则需满足：（2） 限制所选的中位数为2个则需满足： （3） 两个0-1变量在上面的分析中，。（4） 模型建立 通过以上的分析，我们可以建立以下的数学模型满足一定条件的优化问题： 或者 约束条件如下： 5.2.3 模型求解 对于该规划问题，由于约束条件太离散，并不能采取一般的规划问题算法求解，这里，我们采取了一种搜索式的算法，并且利用matlab实现求解。具体的matlab程序见附录二 该问题是算法步骤如下： 第一步：首先用计算出任一应急设施点与任一街区需求点之间的最短距离，其实现步骤如下： Step1:对变量i和j赋值，i为1-66之间的数，j为1-50之间的数，用i和j做二重循环，

31、首先对i和j分别赋初始值1和1； Step2:条件判断，对于i和j的不同取值进行判断，若，且，,并且执行计算最短距离的公式如下：，在满足该条件时，跳转到step3; Step3:继续条件判断，若，且，, 同样计算最短距离，若以上条件均不满足，则转入step4; Step4:若以上条件都不满足，则直接执行以最短距离公式的计算；并且将以上结果全部保存在A矩阵中；转入step5; Step5:对循环变量重新赋值，跳转回step1; Step6:执行循环体直到i=66，j=50,保存最短距离矩阵A;. Step7:跳转到第二步；第二步：从第一步中得到的的最短距离矩阵A中求出每两点组合之间的最小值矩阵。

32、执行下面的步骤： Step9:取初始值i和j,分别满足,并且,从最短距离矩阵A中提取第i行和第j行组合成初始最小值矩阵B:，转入Step10; Step10:对初始最小值矩阵进行变换，取两行中最小的数值记录到最小值矩阵中去：，得到最小值矩阵后，转入第三步；第三步：通过最小值矩阵B与权重矩阵W的乘积计算出总的响应时间，转入第四步；第四步：选出使得总响应时间最小的组合作为2-中位，即求得最优解，算法结束。 5.2.4 模型结果评述通过执行附录二中的matlab程序，可以得到为了使得总的系统响应时间最少，这两个应急设施的位置分别位于第16号和44号应急服务供给点，第16号应急服务供给点位于第8、9、

33、13、14号街区之间的街角处；第44号应急服务供给点位于31、32、36、37号街区的街角处。11120第j个服务供给点 903060120j80604020图例23456781109150i第i个街区的中心点可供选择应急服务供给点140120180160应急事件需求点10020066两个服务设施站的服务分界线确定的应急设施的位置交叉服务区域 如上图所示：图中带星型的点即为我们确定的应急服务的点的地址，另外黑色线是两个应急服务站的辐射范围的分界线，图中阴影部分是两个应急服务点的交叉服务店，两个服务店到其的响应时间相等。5.3 问题三的模型及其求解5.3.1 模型准备在问题三里面，由于考虑了障碍

34、的存在，就使得某些可以直达的区域必须绕道通行，这样就增加了从应急服务点到需求点街区之间的响应时间，为了充分的考虑障碍的存在，下面我们给出几个定义及其说明：受障碍影响的应急设施备选点的点集:由于障碍的影响范围有限，只影响到了其中的一部分应急设施备选点，下面给出具体的应急设施点的约束范围： 即是下图中标注的部分为受障碍影响的供给服务集合点集： 由于障碍的存在而导致第j个设施点到某些街区的响应时间增加，那么我们把这些街区放入一个集合中。5.3.2 模型建立 真个模型的步骤跟问题二的步骤基本一致，因此得出的模型也跟问题二有相似之处，整个问题我们把他当成一个规划问题，有如下的约束条件是对应急设施备选点的

35、约束和备选点与需求点之间的关系，以及他们之间的运算规则约束 （一）约束条件（1）保证每个需求点有且仅由一个设施点为其服务 则需满足： 其中， （2）限制所选的中位数为1个，因为已经确立了一个应急设施点的位置，因此只需要确定另一个的位置即可： 则需满足： ，其中：（3） 限制每个需求点只能由已选的设施点服务 则需满足： 由于第八个应急服务点已经确立，因此8必须在j中体现。（二）目标函数 我们的目标函数是需要使得总的响应时间最少，则建立如下的目标函数： 其中 （三）最终模型 综上分析，得到如下的规划模型： 5.3.3 模型求解 对于以上的建立的模型，我们依然采取以下的算法流程，算法实现方式是用ma

36、tlab计算再加上后期的调整实现。 算法流程图如下： 第一步算法：求最短距离矩阵A开始初值 i=1,j=1mod(i,5)0且mod(i,5)0YNmod(i,5)=0且mod(i,5)=0YN计算,计算,计算,计算，i=i+1,j=j+1i<=50,且j<=66Y最短距离矩阵AN 第二步算法：计算最小值矩阵B以及最少响应时间输入A赋初值i=1,j=8j=8?N提取第j行元素与A中的第八行组成一个矩阵Z(2行50列)Y提取Z中每一列中最小元素，保存到新的B中i<=66?Y更新B,得到最小距离矩阵输入权重矩阵W响应时间TN 第三步算法：对响应时间进行排名，并且提取出对应的应急设

37、施点j。 第四步算法：计算考虑障碍物对距离的影响调整设施点的位置。 对于第四步的调整计算部分，我们给出如下的计算规则： 首先从提取的排名的序列中选择在没有障碍的条件假设下，使得总的响应时间最短的应急设施点，进行如下步骤： Step1:首先检查该点是否在受障碍影响的点集S内，如果在点集S内，则执行step2,如果没有在S内，就不做处理；Step2:从街道图中找出存在障碍的情况下，障碍会导致该设施点到某些街区的需求点的路径发生变化，我们把这些街区导入到一个集合中，然后分别手动计算出该设施点到每一个街区的实际最短距离（响应时间），然后又手动计算出第8点到这些受影响的设施点的距离，对比二者的距离。St

38、ep3:找出考虑了障碍影响后导致的响应时间的增加后仍然使得响应时间最少的设施点。则找到了设施点。5.3.4 模型结果的评述 根据上述的算法，得到的最终的结果是第45个应急设施点，即在32、33、37、38号街区中间的街角处。090301208060402060150140120180160100200确定的应急设施的位置 如下图所示： 5.4 问题四的模型及其求解 5.4.1 模型准备 与问题三一样，我们依然引入受障碍影响的应急设施备选点的点击S: 由于障碍的影响范围有限，只影响到了其中的一部分应急设施备选点，下面给出具体的应急设施点的约束范围： 5.4.2 模型建立 与前面的问题二模型一样，

39、问题四的模型没有发生变化，只是需要加入一个检验的过程。 建立的模型如下： 或者 5.4.3 模型求解 对于这个问题，我们的求解算法跟问题三的也类似，题目的求解采用matlab进行编程求解，其具体的算法步骤如下： Step1: 计算出第j个应急设施的备选点到第i个街区之间的距离，并且把结果保存在最短距离矩阵A中，并执行step2。 Step2: 从A中提取任意的两行，然后对每一列的数据进行比较，选择最小值保存到最小值矩阵B中，执行step3。 Step3: 用最小值矩阵B乘以权值矩阵，得到最终的响应时间，逐步寻找出两个组合使得总响应时间最短。并且同时按照总响应时间的大小对选址组合进行排名，并且把

40、这些组合计入一个二维矩阵C中，转入step4; Step4: 对矩阵C中的组合的每个点与受障碍影响的应急服务设施点集S中进行检验，并且检验的顺序从排名高低依次进行。如果矩阵C中的组合点均没有在S中，那么该组合即为最优。如果C中有元素在集合S中，那么进入step5。 Step5:如果C中和S中有相同的元素，比如，第j个应急点，那么考虑到障碍的影响，就提取出第j个应急设施备选点。然后计算出由于障碍的产生而增加的响应时间，加入到总响应时间T中，更新后的时间如果低于排名次之的点，那么该组合就达到了最优，如果不是，则转入step6; Step6:如果更新后的排名高于排名次之的点，那么继续重复执行step

41、5,逐步依次执行，直到找出最优解。5.4.4 模型结果评述通过问题四的matlab程序，得到的结果如下（我们截取部分组合）：组合一组合二组合三组合四组合五16，4450， 2245，16 44 ，2250, 16而受障碍影响的应急选址点集S:集合受障碍影响选址的点S19,20,21,22,23,24,26,27,32,33,38,39,44,45,50,51,55,56,57,58,59,60,62,63可以发现，使得总响应时间最少的组合为（16,44），而这两个点均没有被障碍影响，所以，问题四的最终解跟问题二是一样的，两个应急服务店分别为第16个和第44个，第16个点为8、9、13、14号街

42、区中间的街角处。确定的应急设施的位置 如下图所示：5.5 问题五的模型及其求解5.5.1 模型准备 定义设表示图个G中边上的f一点到所有顶点的最短距离之和，即 在所有边的f 一点中，使得取最小值的那个点，称为图G的绝对中位点，记为，有 对于寻找图G 的绝对中位点，有一个重要定理，这里称之为绝对中位点定理： 定理1 在无向网络选址问题中，至少有一个顶点是绝对中位点。 为了证明定理1，我们先引入凹函数的概念及一个定理： 对于一个函数，如果定义域U 中的任意两点，如果均成立，则称函数为凹函数。 引理1 如果凹函数的定义域为有一维有限连续闭区域，那么在其端点处取得最小值。 不妨设的定义域为，设，定义域

43、内任意一点x 总可以表示为，由凹函数的定义可知：显然引理1 成立。下面简单地对定理1 做一证明。证明: 对于无向图，由上述内容可知,若将f 看作自变量, 则 可以看作是f 的函数,其图像只可能是图1 所示的3 种情况之一： 图一 的图像 可见，在以上3 种情况中函数均是凹函数，由于凹函数的非负线性组合仍是凹函数，故也是凹函数，由引理1 可知在顶点处取得最小值。 得证。 由此可以得出结论：无向图的顶点是绝对中位点的备择点，并且优于至少不劣于相应边的内点。5.5.2 模型建立 由于前面已经证明了当应急设施点位于街道任何一个点的时候，要确定的两个应急设施点的最优点应该位于顶点上，因此，这个问题就大大

44、简化了，原来的问题是供给点与需求点都不固定，现在明确了应急设施点在顶点上。因此，我们采用了模拟取点的方法，取点的规则来处理应急需求沿每个街区的街道上均匀分布的问题，对于每个街区，我们模拟取点的个数为每个街区的需求权数，最终，我们建立了如下的数学模型： 其中，是第i个街区的需求权重，是第1-66应急设施备选点中的任意两个店，表示 的是第i个街区周围均匀分布的p个需求点，5.5.3 模型求解算法对于这个问题的求解，我们采用如下的算法步骤：Step1：输入50个街区在预测年度中的应急需求权数据的数组cishu，给j1、j2赋初值为1；跳入step2；Step2：变量j1=j1+1，如果j1不大于66

45、，跳到step3；否则进入step8；Step3：变量j2=j2+1，如果j2不大于66且j2不等于j1，跳到step4；否则，情况一：如果j2=j1且j1不大于66，重新进入step3.情况二：如果j2大于66且j2不等于j1，跳到step2；Step4：变量i=i+1，如果i不大于50，跳到step4，否则跳到step2；Step5：变量p=p+1，如果p不大于fix(cishu(j)/10)，跳到step5，否则跳到step3；Step6：用均匀分布随机函数unifrnd函数模拟出第i个街区的位置，利用位置坐标计算出j1、j2到第i个街区的距离，分别为j1i和j2i；跳到step6；St

46、ep7：将j1i和j2i中较小的数加到sum（j1，j2）中。跳到step4；Step8：找到sum矩阵中非零的最小值所在的位置（j1，j2），跳入step9；Step9：重复进行以上step1到step8总共100次然后进入step10；Step10：按出现的频数从大到小将100次结果中的组合（j1，j2）排序，这些组合是要寻找的最优应急供应点的备选点。进入step11；Step11：对排序后的（j1，j2）逐个进行检验。检验过程是，计算j1、j2到50个街区的最短距离。跳到step12；Step12：如果j1、j2到50个街区的最短距离等于在无障碍情况下j1、j2到50个街区的最短距离，跳

47、到step13，否则，将这个距离去替换无障碍情况的距离，跳到step11；Step13：找出并输出已经检验过的所有组合（j1，j2）中j1、j2到50个街区的总距离最小的组合；Step14；根据每个组合采取问题三种最后的检验步骤好原则，进行，知道求得最优解，算法结束。5.5.4 模型结果及其评述 通过上面的算法步骤，最后我们得出了最终的应急设施的选择点在16、45号应急设施备选点，16号选址点在8、9、13、14号街区的中心街角处，45号选址点在32、33、37、38号街区中心街角处。 如下图所示：090301208060402060150140120180160100200确定的应急设施的位

48、置 第六部分 模型的评价与改进 可以看到，在问题2、3、4、5中，其实模型的本质是一样的，只是有个别的细微的约束条件不一样，而且在考虑障碍的时候，我们对应急设施备选点的检测缺乏程式化的准则，而且这个步骤也没有在前面的模型中体现出，考虑到受障碍区域影响后结果的调整，因此，我们把前面的模型加入这个过程，主要针对的是第3、4、5个问题，调整过程我们考虑一下几个方面。 （1）考虑了受障碍影响的时候，我们首先引入受障碍影响的应急设施备选点的点集:其中，是第j个应急备选点的横坐标，是第j个应急设施备选点的纵坐标。由于障碍的影响范围有限，只影响到了其中的一部分应急设施备选点，下面给出具体的应急设施点的约束范围： （2）我们给出一个排序集合，这个集合是记录最短路矩阵中的某两个应急设施备选点的组合，该集合的元素为这些所有备选点的组合按照总响应时间排序而得到的，排序集合：其中，指的是最短距离矩阵中的任意两行，并不是指第一行和第二行。R记录了任意的两个应急设施备选组合按照总响应时间进行排序的结果。（3） 当受障碍影响的某个应急设施备选点恰好位于排序集合中，那么这个时候，就需要对排序集合进行调整。调整之