消防站选址问题(附代码)

城市消防站点选址问题（附代码）第二组组员：郑舟杜洋洋陈建彬张强沈露陈宇银摘要随着国家现代化进程的不断推进，必须要有一个与之相适应的现代化城市应急系统和消防布局规划．选址问题是应急系统中重要的长期决策之一，选址的好坏直接影响到服务方式、质量以及服务成本等，从而影响到城市应急能力的有效发挥和资源的合理配置．本文主要研究城市消防选址的决策问题，包括单目标选址模型和多目标选址模型。其中问题一，三，四属于单目标选址问题，问题二属于多目标选址问题。首先我们运用网络图的最短路径算法理论，给出了基于最短路径的选址问题的算法(Floyd算法)，计算出任意两点的最小路径。问题一：单一消防站选址问题，我们借用P中心模型，求离消防站的点的最大距离的最小值。先假定应急服务设施点都选在网络图的顶点处，所求的中心点是139点，离消防站的最远距离为10296.1米。然后考虑了消防站和火灾现场在道路上的的情况，求出了整个网络的一般绝对中心点A(7354.915，4096.364)，离消防站的最远距离为10271.18米.问题二：多消防站选址问题，我们采用了多目标决策模型，既考虑了离消防站最远距离的最小化，又考虑了消防站离需求点的总加权最小，还考虑了超额覆盖需求区域的总权重最大。然后用参数规划的目标约束法，把多目标转化成单目标，求出消防站的位置。为了简化问题，仅考虑消防站和火灾现场在端点的情况。本题中，假设离消防站的最大距离为5000米，超额覆盖区域的总权重赋值为6，求出消防站的位置分别为点24，98，194，211，253.该模型可以根据不同城市的具体情况赋权值，求出适合不同城市的最佳消防点，易于推广。问题三：共同时间约束下的消防站数量最少问题，我们首先应用位置集合覆盖模型，结合本题的约束条件（10分钟）算出所需消防站最少个数为2个，其次，建立P中值模型，得出所求点为点24和143。问题四：不同时间约束下的消防站最少问题，通过集合覆盖模型，结合本题约束条件（一般位置5分钟，重要位置3分钟），算出所需消防站最少个数为5个，其次建立P中值模型，得出所求点为点45，点75，点211，点224，点228.问题五：分析消防车的速度对到达时间的影响，当速度改变时，考虑到经济效益以及最优化结果，则消防站点的个数相应改变，所以时间随速度以及站点个数的影响。根据以上分析可以得到对于实际问题得出最优的消防站的选址，解决经济效益和满足实际的救火需求。关键词：最优选址问题P中心模型P中值模型多目标决策模型1问题重述在城市中消防站的选址对于及时的消灭火警有着特别重要的意义。考虑某城市内一区域，为简化问题，假定所有火警现场均在下图的道路上。该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332）（见下图红点部位，蓝色部分为水域）。要解决如下问题：1.如果该城市只建一个消防站，最佳的地点应该位于什么位置，该消防站到达城市道路上的点的最远距离是多少？2.如果该城市建五个消防站，最佳的地点应该位于什么位置。3.如果消防车的行驶速度60km/h，要建几个消防站才能使得该城市道路上任何一点发生火警之后，消防车能在10分钟之内到达。4.如果消防车的行驶速度60km/h，要建几个消防站才能使得该城市道路上任何一点发生火警之后，消防车能在5分钟之内到达，同时要求到达重点部位的时间不多于3分钟。5.分析消防车的行驶速度对消防车到达火警现场的时间的影响。2问题分析2.1问题一分析在城市中建立一个消防站点，要求出此消防站点的最佳位置以及该点到到达城市道路上的点的最远距离。交通条件、自然地理条件、道路状况等因素都会影响消防站点的选址。为了简化问题，本题我们只考虑行车距离因素的影响。消防站和火灾现场的地址可以是城市道路上的任何位置，而不仅仅是道路端点。要使火灾损失达到最小，最重要的是消防队接到火警后能够尽快到达火灾现场，这就要求消防站点到城市中任何火灾现场的“最远距离最小”。2.2问题二分析在多个消防站点选址问题中，宜采用多目标方法，并充分体现公共服务设施的公平性和效率性。首先要求应急求援设施覆盖所有需求趋于，在考虑具体目标时一是从快速反应或公平性考虑要求消防站服务需求点的最大距离为最小；二是从超额覆盖和备用设施考虑，要求消防站覆盖需求点的总权重最大；三是从消防站的易接近性和使用效率出发，要求消防站服务需求点的总加权距离最小。2.3问题三分析第三问需要求出在相应的时间限制下，为了能使中位选址问题达到最优需要在该城市建立的消防站点个数。根据消防车的行驶速度60km/h以及反应时间限制10分钟，得出消防站点与相应区域内的点的最大距离应小于d=60*10/60km=10km,运用中位点问题模型，采用参数规划的约束法，可以很好的解决该问题。2.4问题四分析第四问在第三问的基础上，进一步将反应时间限制为5分钟，同时增加对重点部位反应时间的限制3分钟，得出消防站距离相应区域内的普通部位和重点部位的最远距离分别为5km和3km。在问题三模型的基础上，增加以及改变某些约束条件，便可让问题得到解决。3模型假设和符号说明3.1模型假设（1）相邻两个交叉路口之间的道路近似认为是直线，把城市地图抽象成由点和线组成的无向网络赋权图；（2）假设消防车在到达火灾点的途中没有障碍，即不考虑路况和其他突发事件的影响，消防车按照其行驶速度匀速行驶直至到达火灾点；（3）不考虑灾情蔓延速度，即火灾点不会转移和增加（4）不考虑消防队的反应时间，假设接到火情的瞬间，消防队即出发救火3.2符号说明),(jiD最短距离矩阵ijd点Vi到点Vj的最短距离I消防站点的集合J火灾现场的集合iIijJj4模型的建立与求解4.1问题一：单个消防站点选址问题首先，用Floyd算法求出任意两个结点之间的最短路径；Floyd算法的基本思想如下：把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=0。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。如果消防站点和火灾现场的地点仅仅可以发生在网络图的节点上，则根据“最远距离最小”的选址原则，我们很容易就可以得到在途中第139点设置消防站最合适，10296.1mmL。但是实际情况中，更多的消防站点是建设在城市道路上。此模型中运用的符号说明：mL消防站点到最远距离最小is消防站责任区内ijb（0-1）变量，1ijb则表示在ije中建设消防站，否则反之ijz如果消防站点Vj覆盖点Vi，则1ijz，否则0ijz建立如下优化模型：minmLZ..tsiipqpqpiiaxbds10000)(3071(1-1))1(10000)(3071iipqpqpqqiiaxdbds(1-2)ijjimdssL2(1-3)ijijijbdx(1-4)以最远距离最小作为目标函数。约束条件（1-1），（1-2）表示约束条件（1-3）表示约束条件（1-4）表示用Lingo求解得到：j=139,147。（即消防站应建在139,147交叉路口）05000100001500001000200030004000500060007000800090001234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063074.2问题二：多个消防站点选址问题此模型中运用的符号说明：i第Vi点的权重，重点部位权值为2，其他点权值为1iu表示点Vi被超额覆盖的次数，即总覆盖次数-1,iu为整数jy（0-1）变量，1jy则表示在Vj中建设消防站，否则反之ijz（0-1）变量，如果消防站点Vj覆盖点Vi，则1ijz，否则0ijzijs消防站点到图上的最大距离根据上述选址特点，本文提供了一个针对该问题的多目标决策模型。消防站选址的多目标决策模型表述为:minijsZ1(1)max30712iiiuZ(2)..ts53071jjy(3)30711jiijuz(4)0jijyz(5)3071jijijijiszd(6)模型说明如下：约束条件(4)和(6)式保证设置的消防站数目为p；约束条件（5）式保证设置的应急救援设施数目不低于需求区域i要求的最少设施数qi,超出的数目（iJjijqz）即为需求区域i超覆盖的次数ui；目标函数（1）式和约束条件（7）式使设置的应急救援设施服务需求区域的加权最大距离（平均意义上）L为最小（即p-中心模型），体现公平性；如果约束条件（7）式改为,szdijijJjIi,(9)则目标函数（1）式和约束条件（9）式保证设置的应急救援设施服务需求区域的最大距离L为最小，体现对应急救援设施快速反应的要求；目标函数（2）式和约束条件（5）式使超额覆盖最大化，其主要目的是使权重越大的需求区域有更多的应急救援设施为其服务；目标函数（3）式和约束条件（5）式使设置的应急救援设施服务需求点的加权总距离为最小（即p-中值模型），体现效率性。上述模型为3个目标的多目标决策模型，多目标准则函数为min[v1,v2,v3].本文采用参数规划的目标约束法把多目标转化成单目标，来求解上述选址决策模型。保留决策问题中的一个目标，其余两个目标被作为约束，通常保留目标v3，把目标v1和v2约束化，根据城市的具体情况，使v1和v2分别约束于a和b.模型求解：对于本题，给离消防站的最大距离的最小值赋值5000m，给消防站覆盖需求点的总权重赋值为6，写出目标函数和约束条件如下：minIiJjijijizdZ..tsijijijzds(2-1)30711jiijuz(2-2)05000ijijzs(2-3)30716iiiu(2-4)0jijyz(2-5)模型说明：约束（2-1）（2-3）表示在要建立五个消防站点约束（2-2）保证每个