消防站选址问题附代码

1、城市消防站点选址问题（附代码）第二组组员：郑舟 杜洋洋陈建彬张强沈露陈宇银摘要随着国家现代化进程的不断推进，必须要有一个与之相适应的现代化城市应 急系统和消防布局规划.选址问题是应急系统中重要的长期决策之一，选址的好坏直接影响到服务方式、质量以及服务成本等，从而影响到城市应急能力的有效 发挥和资源的合理配置.本文主要研究城市消防选址的决策问题， 包括单目标选址模型和多目标选址 模型。其中问题一，三，四届于单目标选址问题，问题二届于多目标选址问题。 首先我们运用网络图的最短路径算法理论,给出了基于最短路径的选址问题的算法（Floyd算法），计算出任意两点的最小路径。问题一：单一消防站选址问题，我

2、们借用P中心模型，求离消防站的点的最 大距离的最小值。先假定应急服务设施点都选在网络图的顶点处，所求的中心点是139点，离消防站的最远距离为10296.1米。然后考虑了消防站和火灾现场在 道路上的的情况，求出了整个网络的一般绝对中心点 A（7354.915, 4096.364）,离 消防站的最远距离为10271.18米.问题二：多消防站选址问题，我们采用了多目标决策模型，既考虑了离消防 站最远距离的最小化，乂考虑了消防站离需求点的总加权最小， 还考虑了超额覆 盖需求区域的总权重最大。然后用参数规划的目标约束法，把多目标转化成单目 标，求出消防站的位置。为了简化问题，仅考虑消防站和火灾现场在端点

3、的情况。 本题中，假设离消防站的最大距离为 5000米，超额覆盖区域的总权重赋值为 6, 求出消防站的位置分别为点24, 98, 194, 211, 253.该模型可以根据不同城市的 具体情况赋权值，求出适合不同城市的最佳消防点，易于推广。问题三：共同时间约束下的消防站数量最少问题， 我们首先应用位置集合覆 盖模型，结合本题的约束条件（10分钟）算出所需消防站最少个数为 2个，其 次，建立P中值模型，得出所求点为点24和143。问题四：不同时间约束下的消防站最少问题， 通过集合覆盖模型，结合本题 约束条件（一般位置5分钟，重要位置3分钟），算出所需消防站最少个数为 5 个，其次建立P中值模型，

4、得出所求点为点45,点75,点211,点224,点228.问题五：分析消防车的速度对到达时间的影响， 当速度改变时，考虑到经济 效益以及最优化结果，则消防站点的个数相应改变，所以时间随速度以及站点个 数的影响。根据以上分析可以得到对于实际问题得出最优的消防站的选址，解决经济 效益和满足实际的救火需求。关键词：最优选址问题 P中心模型 P中值模型 多目标决策模型1问题重述在城市中消防站的选址对于及时的消灭火警有着特别重要的意义。考虑某城市内一区域，为简化问题，假定所有火警现场均在下图的道路上。该区域内三个重点部位的坐标分别为：(5112, 4806), (9126, 4266) ,( 7434

5、, 1332)(见下图红点部位，蓝色部分为水域)。要解决如下问题：1. 如果该城市只建一个消防站，最佳的地点应该位于什么位置，该消防站 到达城市道路上的点的最远距离是多少？2. 如果该城市建五个消防站，最佳的地点应该位于什么位置。3. 如果消防车的行驶速度60km/h,要建几个消防站才能使得该城市道路上 任何一点发生火警之后，消防车能在 10分钟之内到达。4. 如果消防车的行驶速度60km/h,要建几个消防站才能使得该城市道路上 任何一点发生火警之后，消防车能在5分钟之内到达，同时要求到达重点部位的 时间不多于3分钟。5. 分析消防车的行驶速度对消防车到达火警现场的时间的影响。2问题分析2.1

6、问题一分析在城市中建立一个消防站点，要求出此消防站点的最佳位置以及该点到到达 城市道路上的点的最远距离。交通条件、自然地理条件、道路状况等因素都会影响消防站点的选址。为了简化问题，本题我们只考虑行车距离因素的影响。消防站和火灾现场的地址可以是城市道路上的任何位置,而不仅仅是道路端点。要使火灾损失达到最小，最重要的是消防队接到火警后能够尽快到达火灾现 场，这就要求消防站点到城市中任何火灾现场的“最远距离最小”。2.2问题二分析在多个消防站点选址问题中，宜采用多目标方法，并充分体现公共服务设施 的公平性和效率性。首先要求应急求援设施覆盖所有需求趋于，在考虑具体目标时一是从快速反应或公平性考虑要求消

7、防站服务需求点的最大距离为最小；二是从超额覆盖和备用设施考虑,要求消防站覆盖需求点的总权重最大； 三是从消防 站的易接近性和使用效率出发，要求消防站服务需求点的总加权距离最小。2.3问题三分析第三问需要求出在相应的时间限制下，为了能使中位选址问题达到最优需要 在该城市建立的消防站点个数。根据消防车的行驶速度60km/h以及反应时间限制10分钟，得出消防站点与相应区域内的点的最大距离应小于 d=60*10/60km=10km,运用中位点问题模型，采用参数规划的约束法，可以很好 的解决该问题。2.4问题四分析第四问在第三问的基础上，进一步将反应时间限制为5分钟，同时增加对重 点部位反应时间的限制3

8、分钟，得出消防站距离相应区域内的普通部位和重点部 位的最远距离分另U为5km和3km。在问题三模型的基础上，增加以及改变某些约束条件，便可让问题得到解决。3模型假设和符号说明3.1模型假设(1) 相邻两个交义路口之间的道路近似认为是直线，把城市地图抽象成由 点和线组成的无向网络赋权图；(2) 假设消防车在到达火灾点的途中没有障碍，即不考虑路况和其他突发 事件的影响，消防车按照其行驶速度匀速行驶直至到达火灾点；(3) 不考虑灾情蔓延速度，即火灾点不会转移和增加(4) 不考虑消防队的反应时间，假设接到火情的瞬间，消防队即出发救火3.2符号说明D(i, j)最短距离矩阵dij点Vi到点Vj的最短距离

9、I消防站点的集合J火灾现场的集合ii w Ijj w J4模型的建立与求解4.1问题一：单个消防站点选址问题首先，用Floyd算法求出任意两个结点之间的最短路径；Floyd算法的基本思想如下：把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，贝U Gi,j=d, d表示 该路的长度；否则Gi,j=0。定义一个矩阵D用来记录所插入点的信息，Di,j表 示从Vi到Vj需要经过的点，初始化Di,j=j。把各个顶点插入图中，比较插点后 的距离与原来的距离，Gi,j = min( Gi,j, Gi,k+Gk,j),如果Gi,j的值变小，M Di,j=k。在G中包含有两点之间最短道路的信息，而在D中则包

10、含了最短通路径的信息。如果消防站点和火灾现场的地点仅仅可以发生在网络图的节点上，贝U根据“最远距离最小”的选址原则，我们很容易就可以得到在途中第139点设置消防站最合适，Lm =10296.1m 。但是实际情况中，更多的消防站点是建设在城市道路上。此模型中运用的符号说明：Lm消防站点到最远距离最小Si消防站责任区内bij（0-1）变量，b =1则表示在ej中建设消防站，否则反之zij如果消防站点Vj覆盖点Vi,则Zj =1 ,否则Zj =0建立如下优化模型:min Z = Lm307s.t.Si w (d pi bpq Xpq) 10000 ai(1-1)i 土 307SiZ (dqibpq

11、+d pq Xpq ) 1 0 0 0(1 _ai )(1-2)i z12Lm SiSj dij(1-3)Xij < d ij bij(1-4)以最远距离最小作为目标函数。约束条件（1-1）, （1-2）表示约束条件（1-3）表示约束条件（1-4）表小用Ling。求解得到：j=139, 147。（即消防站应建在139, 147交义路口）9000800070006000500040003000200010000解 33261。384346627389826766719294 995 102 11110911312830 131157 58 167159193211I255260270275

12、'I282892979 1210 7 .11 144 518 131516-178346婀2007 |117.1156016iSO24.21i42415650 51 5247 t 44 K 5|61632251 25388 84 焰586，81三779116123124 739138 1 44心污1 M 7316692 97233243443449 ksR44644S48c£43443?442250 258 -2514 2：254276 2812912985000141痛8170370 26 -2282422340241 26550261盥!羸德77叩80归2 冒寿62T29

13、2 2930942552236235237257：292 293近4 30002 召03 9041295 -296£05 七0630710000150004.2问题二：多个消防站点选址问题 此模型中运用的符号说明：仍i第Vi点的权重，重点部位权值为2,其他点权值为1Ui表示点Vi被超额覆盖的次数，即总覆盖次数-1,山为整数V(0-1)变量，yj =1则表示在Vj中建设消防站，否则反之zij(0-1)变量，如果消防站点Vj覆盖点Vi，则Zj =1 ,否则z“ =0Sij消防站点到图上的最大距离根据上述选址特点，本文提供了一个针对该问题的多目标决策模型。消防站选址的多目标决策模型表述为：

14、min Z1 =$目(1)307max Z2 = ,心山s.t.L=5j呸307' Zij -Ui _1j AZij - Yj _0(5)307'，idj，fj =1模型说明如下：约束条件（4）和（6）式保证设置的消防站数目为 p；约束条件（5）式保证设置的应急救援设施数目不低丁需求区域i要求的最少设施数qi，超出的数目（播zj Q'）即为需求区域i超覆盖的次数Ui；目标函数（1）式和约束条件（7）式使设置的应急救援设施服务需求区域的 加权最大距离（平均意义上）L为最小（即p-中心模型），体现公平性；如果约束条件（7）式改为d ij zij - s - 一 i 三 I

15、, j 三 J则目标函数（1）式和约束条件（9）式保证设置的应急救援设施服务需求区 域的最大距离L为最小，体现对应急救援设施快速反应的要求；目标函数（2）式和约束条件（5）式使超额覆盖最大化，其主要目的是使权 重越大的需求区域有更多的应急救援设施为其服务；目标函数（3）式和约束条件（5）式使设置的应急救援设施服务需求点的加 权总距离为最小（即p-中值模型），体现效率性。上述模型为3个目标的多目标决策模型，多目标准则函数为minvi,v2,v3.本文采用参数规划的目标约束法把多目标转化成单目标， 来求解上述选址决 策模型。保留决策问题中的一个目标，其余两个目标被作为约束，通常保留目标 V3,把目

16、标V1和V2约束化，根据城市的具体情况，使 V1和V2分别约束丁 a和 b.模型求解：对丁本题，给离消防站的最大距离的最小值赋值 5000m,给消防站覆盖需求 点的总权重赋值为6,写出目标函数和约束条件如下：min 2：_ :'idj Zjs.t. sj -d zj（2-1）307x Zij -Ui -1（2-2）j =1Sj -5 0 0 0ij < 0（2-3）3 0 7'_6（2-4）i白Zij -Yj _0（2-5）模型说明：约束（2-1） （2-3）表示在要建立五个消防站点约束（2-2）保证每个点至少被一个消防站所覆盖约束（2-3）给消防站点设置最小距离约束（2

17、-4）保证每个重点部位至少被两个消防站覆盖目标函数Zi和约束（2-4）使消防站点到火灾现场的加权最大距离最小用Lingo求解得到：j=24, 98, 194, 211, 253。（即消防站应建在 24, 98, 194, 211, 253交又路口）4.3 I可题二：在已知消防车运行速度的前提下，我们将时间约束转换成最远距离约束，即 最远行车距离为10000m。此时我们并不知道要在最远行车距离为10000m的前提下，需要建设多少个消防站点才能覆盖全部点。我们以最小消防站点个数为约束条件，建立优化模型：min z Yji 1s"、07z,=1j =1Zij - Yj 0djjZjj &l

18、t; 10000用Lingo软件编程求出在反应时间限制下，在该城市建立的最少消防站为 2。目标为使距离总和最小，所以得到的模型为：min ZTgjZjji ± j T3 0 7 s.t. ' Yj =2(3-1)j 土dijZij -10000(3-2)Zij -Yj H(3-3)307 ' Zij =1(3-4 )j =i 模型说明：约束（3-1）表小在图上建立两个消防站点约束（3-2）表示Vj消防站到服务点Vi的最远距离为10000m约束（3-3）在Vj点建立消防站后它才能覆盖该区域内的点约束（3-4）使p中心问题得到最优，城市内每个点仅且仅被一个消防站覆用Lin

19、g。求解得到：j=84,143。（即消防站应建在84和143交义路口）9000800070006000500040003000200010000942<1432 #32607302731 :112eJ822 29-4口23J66一二6271157158 167 淄193211I255275297260270I28289117J9185516016838204244.48伊424151 .524792 94 995102 11110911312830 131犯§2 ,13或笋涵照2276291298|一5000£69 J268如氐281288平

20、92 i2930If300 物2，3037728024170272,295296-305 306307237257236235251 25351617225 -2282421161"29930410000150004.4问题四：首先，把各个部位对时间的约束转化为最远距离约束，即消防站点到其责任 区内普通火灾现场的最远距离为 5000m,到三个重点部位火灾的时间约束，仍然 转化为最远距离约束。根据第四问中对普通部位反应时间 5分钟及重点部位3分钟的限制，编制算 法得到的最少消防站个数为5yii W I , yi为（0 -1）变量，Vi =1表示在Vi点建立消防站，Yi= 0，否d0点V

21、i到点Vj的最短距离z ziJZj为（0-1）变量，Zj =1表示消防站点Vj服务于点Vimin z =£ yi3 0 7S.t. 、' zij =1 j AZij -yj £0瞄§ £ 5 0 0 0d 103 j Z103 j 3000d123 j Z123 j 一 3000d 277 j Z277 j - 3000求解的模型：min zL、Zij i ± j 3 0 7s.t. w yj =5 j w dijZij < 5 0 0 0 dijZij - 3 0 0 0 Zj -yj -0 3 0 7 .二 Zij -1 j

22、=1同样用ling。求解得出：j=45, 75, 211, 224, 228 （即消防站应建在第45, 75, 211, 224, 228交又路口）。90008000700060009_.12107_.111432 332630虻F?7?1'4 #650 妄1.634 518 131516174241 .52-47 44 ,48.5000400030002000100067 663749294 攒 8982 9009111 109芾112830 13191-83 18884物107,167 攻193211255275297260270282897典6116 心M14T 一静37魁2 .

23、13324291梁215嬲硼蹦83一 臀催>24矗447263瓠 2682!132 23423,294825.2456人29W2276 281291 <2984L4J51 169668.184!5_192238l0.241 ,2422魅6,261SS72l77 案2 M：H300 郃02 3032722802137170228296307236235237251 253257I I;49456163785 86 81f'1299304._30500500010000150004.5问题五：根据查阅的资料得到，消防车的速度最小值达到30km/h,最大速度值可达到110km/h

24、，如森林消防车的速度一般为30km/h,机场消防车的速度为 80110km/h，针对本题第五问，我们设置城市消防车的速度v占如而仆，以此为最低值考虑消防车到达火警现场的时间t的影响。由物理学公式有：消防车行驶的距离s=vt，根据国家标准城市消防规划 规划，消防车从出发到火警现场的时间不超过5分钟，对丁某一城市，消防站的辖区面积一定，即可知消防车达到某一现场距离s是确定的，即得到v与t成反比例关系，进而考虑影响速度的因素：1:道路状况其中城市道路的弯折度为主要影响因素，记其为h,查阅资料，h计算公式：、若改0寸上匚广辖区内任一点到消防站该两点的最小实际距离道路的弯折度=该两点的直线距离对丁确定的

25、辖区内，设可能发生火灾部位的个数为n,辖区内任一点到消防站的最小实际距离为Si(i =1,2,，n)，直线距离为li(i =1,2,., n)；Si hi = (i =1,2,., n)lin'、' hih = (i =1,2,., n) 则该辖区平均道路的弯折度n, h为道路的弯折度最终比较量。h越大，道路越弯折，平均速度v越小，s 一定时，消防车到达火警现场的时间越大。2:交通拥堵情况，天气情况，驾驶员驾车技术等等都会对会通过速度来影 响消防车到达火警现场的时间。5模型的分析本论文针对五个问题，建立了四个模型。第一问的模型考虑了图上的所有点，而不仅仅是图上的顶点，对应现实问

26、题， 相当于考虑了城市街道上的所有住户，而不仅仅是以往问题中的路口上的住户， 这样得到的中心点更具有现实意义。第二问所建立的多目标规划模型，考虑突发事件应急救援设施的选址决策目 标时，宜采用多目标方法，并充分体现公共服务设施的公平性和效率性。比一般的单目标规划模型更加具有灵活性和综合性。第三问、第四问建立的都是根据消防站点责任区内最大行车距离建立的中位 点选址模型，但是此模型要求知道图中最少需要建立的消防站点数目，故先建立了一个以最少站点数位约束目标函数的优化模型，求出需要的最少消防站点数。这两个模型算法简洁，结果稳定，具有一定可推广性。6模型的评价优点：1.模型本身不存在近似误差，计算误差由

27、 Ling。软件和计算机精度决 定。2. 适用范围广，该模型适用于诸如医院急救站、巡逻警点等类似公共设施的 规划建设，只需将参数或约束条件做相应修改即可。3. 该模型易于推广普及，仅需一幅城市地图和相应的坐标信息，便可解决 一类中位选址问题。4. 算法简单易懂，得到的结果稳定性好缺点：1. 假设理想化，没有考虑到诸多因素如水源的影响，实际问题可能更加复杂 化。2. 只考虑了将消防站建立在交义路口的情况，忽略了消防站可建立在路边 的情形，所以得到的模型可能不是最优的模型。7参考文献11王正东，数学软件与数学实验，北京：科学出版社，2004年【2】 邓佩，苏翔，时间约束下的运输网络最短路径研究，

28、机电产品开发与创新， 第19卷第一期：18-20, 2006年【3】 韩伟一，王铮，Dijkstra算法的一个改进，运筹与管理，第十三卷第6期: 6-10, 2004 年【4】 李德宜，李明，数学建模，北京：科学出版社， 2009年【5】 谢金星，薛毅，优化建模与LINDO/LINGO软件，北京：活华大学出版社,2005 年附录：第一问代码(lingo)model:sets:point/1.307/:s,a;links(point,point):d;connect(point,point)/1,2 1,35 2,5 2,21 3,6 3,4 3,13 4,5 4,15 5,16 6,8 6,1

29、8 7,10 7,117,278,11 8,22 9,12 9,14 10,1210,30 11,20 12,2613,18 13,23 14,32 14,33 15,16 15,2516,1717,24 18,29 19,20 19,2820,34 21,24 21,3721,45 22,28 22,29 22,50 23,25 23,2923,4224,25 24,49 25,44 26,3026,33 27,30 27,3127,57 28,34 29,51 30,60 31,34 31,5332,3332,36 33,38 34,54 35,4036,38 36,43 37,3938,

30、46 39,40 39,77 40,79 41,42 41,4742,5243,46 43,67 44,47 44,4844,84 45,49 45,8146,62 47,52 48,49 48,61 49,63 50,5150,5651,52 51,83 52,88 53,5553,57 54,55 54,5654,87 55,64 56,91 57,58 57,68 58,5958,6559,60 59,65 60,62 60,6960,82 61,63 61,7862,66 64,72 65,69 65,70 66,67 66,7167,9268,70 69,74 69,93 70,75

31、71,73 72,75 73,8974,76 75,90 76,98 77,79 77,81 78,8478.85 79,237 80,93 80,96 80,100 81,86 82,89 82,93 83,88 83,91 83,108 84,88 84,11685.86 85,122 86,137 87,90 87,91 87,106 88,115 89,95 90,98 90,99 91,107 92,94 92,11193,100 94,97 94,109 95,97 95,102 96,98 96,104 97,102 98,101 99,101 99,105 100,132101

32、,103 101,110102,113103,104 103,112 104,124105,106106,107106,118 106,120107,108 107,114108,117109,111 109,113 110,112110,118111,128112,121 113,131114,117 114,140115,116115,117 115,138 116,123117,139118,119118,125 118,134119,121 119,127120,126121,129 122,123 123,141124,129124,135125,127 125,143126.146

33、 127,133128,130128,157 129,133 130,131130,158131,132131,167 132,135132,160 133,142134,144136,137 136,148 138,139138,141139,147139,149 140,145140.146 140,152141,148141,215 142,143 143,144143,156144,146144,153 145,147145,150 146,152147,154149,151 149,154 149,169150,152150,154151,166 152,155153,163 153

34、,201154,171155,171 156,162 156,183157,158157,193158,167 159,160159,174 160,161160,178161,162 162,179 163,164164,172165,169165,173 166,173167,211 168,170168,192169,192 169,194 171,185171,172172,184174,180 174,186175,179 175,182175,188176,177 176,180 176,187177,178177,199178,181 178,191179.189 181,182

35、181,190182,200 183,196 184,214185,194186,187186,198 187,195188.189 189,205190,191190,204 191,208 193,211193,255194,210194,213 194,214194,238 195,198195,199196,206 196,209 197,203197,215198,211198,218 199,208200,204 200,209200,219201,206 201,207 202,207202,214202,216203,210 203,220204,208 205,209205,

36、254206,243 207,222 208,212209,221210,225211,260 212,234213,223 214,216215,226215,228 216,222 216,224217,218217,232218,231 219,221219,233 220,226 220,227 221,229 222,230 223,224 224,239 224,244 225,227 226,242228,251 229,233 230,250 231,232 231,259 232,234 232,246 233,234 233,248 234,247235,236 235,2

37、37 236,251 237,257 238,240 238,244 238,265 239,252 240,241 240,266241,242 241,261 242,272 243,249 243,263 244,268 245,246 245,256 246,247 247,248247,258 249,250 250,252 250,264 251,253 251,305 252,269 253,257 253,295 254,258255,260 255,275 256,258 256,259 257,296 258,276 260,270 261,266 261,280 262,

38、263262,267 264,271 265,266 265,277 267,281 268,269 268,279 269,273 270,287 271,284272.304 273,274 274,278 275,297 276,281 276,291 277,279 277,280 277,285 278,279278,290 279,286 280,299 282,283 282,284 282,288 283,293 285,286 285,294 286,290287,289 288,292 289,291 290,294 290,302 291,292 291,298 292,

39、300 293,301 294,303295,296 295,306 296,307 297,298 298,300 299,303 299,304 300,301 301,302 302,303304.305 305,306 306,307/:b,x;endsetsdata:桌面 D1.xlsx','distance');enddatamin=dis;for(point(i):s(i)>sum(connect(p,q):d(p,i)*b(p,q)+x(p,q)-100000*a(i);for(point(i):s(i)>sum(connect(p,q):d(q,i)*b(p,q)+d(p,q)*b(p,q)-x(p,q)-100000*(1-a(i);for(connect(i,j):x(i,j)<d(i,j)*b(i,j);for(connect(i,j):2*dis>s(i)+s(j)+d(i,j);for(point:bin(a);for(connect:bin(b);sum(connect(i,j):b(i,j)=1;end第二问代码：model:sets:point/1.307/:w,u,y;lin