消防队选址规划

1消防队选址规划摘要本文就给定的全县交通图，对消防队三个选址问题进行了探讨，并分别建立了相应模型，较好的解决了消防队选址问题。对解决目前城市消防队增建选址问题有一定指导意义。问题一：题目要求在确定一个消防队在县城的情况下，在17个乡镇中选出一个乡镇设立一只新消防队，首先在Matlab环境下编程实现53个地点中2个相邻地点的连线，如果2个地点相邻则输入距离，不相邻则输入inf,建立53*53的邻接矩阵，采用floyd算法求出任意2个点之间的最短距离，建立以总路程最小为目标的函数，建立优化模型，求解得到17个乡镇的总路程如表一。问题二：问题2与问题1的各地火警等概率发生不同，区分的村、乡镇和县城的火警比及大火、小火发生比例，这也是一个最优化问题，我们需要在最短路程矩阵中2个点对应的值乘上一个对应系数进而计算发生小火，发生大火时的消防队去救火的优化权值，将53个点的优化权值累加后，编写以总优化权值最小为目标的函数，建立优化模型，求解得到17个乡镇的总优化权值如表二。问题三：条件与问题2相同，只是又新增一只消防队，因此在发生大火时，就需要判断3个消防队所在地点那2个离火灾发生地较近，而在问题2中是不需要判断的，问题2、3在发生小火时都需要判断最近的消防队所在地，因此我们将问题一的判断条件重新修改，建立新的目标函数，建立优化模型，求解结果见图4.问题四：问题四只有一个约束条件，要求设立的几个消防队所在地按就近原则能在30分钟内到达火灾发生地，这就可以转化为在全县最少选取几个地点能使得按就近原则在30分钟内到达全县任意地点，我们用静态增加新增消防队数目的方法，在Matlab环境下编程得出最少新增4只消防队的结果，并得到18种方案，结果见表3进行优化后选取一种最优方案，最优方案见图4.关键词：消防站选址优化模型Floyd算法Matlab2一、问题重述最近，某县的火灾事故有增多的趋势，某县已有一个消防队（在县府），最近上级拨款可再新建一个消防队，各个乡镇积极打报告都要求建消防队，建在什么地方好呢？县政府请你帮助作一个规划。1.如果仅一处着火时（各地火警等概率），只就近动用一个消防队即可，你如何规划？2.如果县、乡（镇）府所在地的大火和小火的比例为1：5，村里的比例为1：10，县、乡（镇）和村的火警比为5：5：1，并且大火时需要两个消防队，小火时只需要一个消防队，你又如何进行规划？3.对于问题2，若可新建两个消防队又如何规划？4.若要求接到火警报警后30分钟之内赶到现场，请问最少需增加几个消防队，建在哪几个乡镇？上述问题均假定火警不会同时发生，消防队的主要运载工具为消防车，它的平均时速为60公里。二、问题分析2.1问题一问题一是在各地火警等概率的情况下，如果只有一处着火时，按就近原则将安排的2只消防队中的一只派去救火，而其中一只消防队已经布置在县城里，另一只消防队布置在哪个乡镇里，需要看在哪个乡镇设置这只消防队能使这2只消防队管辖的范围总的时间最短（最短时间可以转化为救火的总路程最短），因此我们采用最优化模型规划模型，用floyd算法求出图中任意两个站点之间的最短距离，用Matlab求得在17个乡镇中的任一个乡镇设置消防队在按就近原则到达53个地点救火的总的最短路程，再经比较之后就可以得出在哪个乡镇设置消防队能让救火队相对迅速地赶去救火。2.2问题二问题二中发生大火时需派出2个消防队，而各地发生火灾的比率也都不一样但仍然是要求我们规划设置好的那个乡镇消防队及县城消防队按就近原则能在最短时间（时间可以转内化为路程）内到达，如发生大火时，则2个消防队需同时出动到达救火地点，因此这仍然是一个最大距离最小化问题，我们引用了最优化模型，在Matlab环境下建立了以距离，火灾发生率为权值的目标函数，再根据题意建立最优模型，最终得出需要增加的消防队位置。2.3问题三问题三在问题二的条件基础上新建2只消防队，意味着如果发生大火时，我们需要动用较近的2只消防队去救火，发生小火时只需要动用最近的一只消防队去救火，因此只需要将问题2建立的目标函数修改一下，就能得出需要增加的消防队位置了。2.4问题四问题四要求规划最少新建几个消防队，能使得在全县任一个地点发生火灾时，消防队能在30分钟内到达火灾发生地。我们选用静态增加新增消防队数目的方法，从新增2个消防队开始依次验证，发现直到新增4个消防队才能达到消防队在30分钟内到达任意地点，在Matlab环境下建立目标函数，求得新增43个消防队的选址方案，并将得到得消防队选址地点保存在矩阵中，得到初步的选址规划方案，将其转化为一个最大距离最小化问题，求解得到一个消防队选址的最优方案。三、基本假设与符号说明3.1基本假设1.假设每个路段道路畅通，可以双向行驶，没有堵车现象；2.假设每辆消防车行驶中速度保持匀速且车速均为60km/h；3.假设消防队都按最短路径到达火灾发生地；4.假设不考虑消防队的反应时间，接到火情的瞬间，消防队即出发救火；5.假设在一个乡镇或县城上最多建一个消防队；3.2符号说明ijA=ijw图中直接连点的距离i=1,2,3...53，j=1,2,3…53；∞否则ijw表示(iV,jV)的权数，即两个地点之间的距离；ijD图的最短路程矩阵i=1,2,3...53，j=1,2,3…53；ijW为问题四的初始地点存储矩阵i=2,3...，j=1,2,3,4；iV为全县53个地点,36~53表示A~R标注的乡镇和县城i=1,2,3...53；四、模型的建立与求解根据题目所给的县城图，提取数据，建立全县城的邻接矩阵ijA（数据输入见附录一），其中ijw表示图中能直接连点的距离，若无直连道路，赋值为inf，代表无穷大。定义最短路程矩阵ijD，其中,Dij表示道路加权后,ij间最短距离。显然，要求出D并不容易，逐条计算的方法繁复且不具有通用性，借助计算机求解是可行的方案。在图论中有许多求节点间最短距离的算法，在这里我们采用Floy算法编程求解。Floy算法是基于动态规划的一种求有向图,GVE顶点间最短路径的解决4方案。它的运行时间为3V，并且允许权值为负的边存在，但我们假设不存在权值为负的边。本文在Matlab环境下采用Floy算法编程，圆满实现了矩阵ijD的求解（程序代码见附录二，程序文件为shortdf.m）4.1问题一4.1.1模型建立假设消防队设置在乡镇A~R中的某个点i(53...36,35i)上，则它与火灾发生点j的最短距离为),(jiD,比较它与县城所在点o的最短距离为),50(jD（如果火灾发生点为i或o点，最短距离为0）)),50(),,(min(jDjiDs将比较得出的53个地点的最短路程累加到s中，记录进矩阵ijx（18...2,1i表示A~R这18个乡镇和县城，1j），得到总的最短路程。4.1.1模型求解对模型的求解借助Matlab的编程，相关代码见附录三，求解结果见下表1845.5A1242.4G1361.9M1909.0B1382.5H1438.5N1815.2C1284.8I1942.9O1541.9D1158.1J1765.3P1273.0E1248.1K1806.0Q1310.7F1212.2L1838.3R表一显然将消防队设置在J镇中能使消防队以最短时间到达各个地点。4.2问题二4.2.1模型建立同问题一不同的是，问题二中火灾区分为大火、小火，大火需要动用2个消防队，而且各地发生火灾的概率也不相同，所以充分考虑影响最短路程的各种条件，对最短路程矩阵中的权值进行修正，求得最优权值。这里我们同样假设消防队设置在乡镇A~R中的某个点i(53...36,35i)上，则它与火灾发生点j的最短距离为),(jiD,在发生小火灾的时候，比较它与县城所在点o的最短距离为),50(jD（如果火灾发生点为i或o点，最短距离为0）5)),50(),,(min(jDjiDs这里的s还需要乘上一个系数，如果36i时，即小火灾发生在村时，其系数为村在总的火警比的比例乘上发生小火的比例，为10/121,若35i时，即小火灾发生在乡镇和县城，其系数为25/66；发生大火灾的时候，2个消防队都需要出动，此时),50(),(jDjiDs，当36i时，其系数为1/121，35i时，其系数为5/66。将求得得最优权值s叠加后，比较之后输出的累加值最小的地点i就是应该设置消防队的乡镇。4.2.2模型求解用Matlab进行编程求解，程序见附录四，求解结果显示如下A448.2242G325.77M341.012B454.8288H370.6211N372.0931C431.2127I345.655O452.4829D376.9346J308.0663P432.7347E325.8931K332.7303Q453.4452F347.3964L319.309R448.389表2将修正后的权值叠加比较后得出在J镇设置消防队是最优的图一4.3问题三4.3.1模型建立问题三在问题二的条件基础上，新增2只消防队，求解的过程和问题二很相像，这里我们假设新增的2只消防队一只设置在乡镇A~R中的某个点i（i=35,36…53）上，另一只设置在乡镇A~R中的某个点j(53...36,35j且ji)，这样在发生小火灾的时候，我们需比较的是三个消防队设置点),(kiD，),(kjD，),50(kD到达火灾发生地的最短路程（如果火灾发生点为i，j或o点，最短距离为0），可以设置一个矩阵)],50(),(),,([kDkjDkiDx利用min函数得出最短路程)min(xs，若是发生大火灾时，这时我们需要比较3个消防队所6在地点那2个离火灾发生地近，按就近原则派出消防队救火，这时的最短路程为)max()(xxsums，再乘上其系数之后，将求得得最优权值s叠加后，比较之后输出的累加值最小的地点i和j就是应该设置消防队的乡镇。4.3.2模型求解用Matlab进行编程求解，程序见附录五，求解结果显示如下图2得出在G镇和M镇应该各设置一只消防队。4.4问题四4.4.1模型建立问题四的要求是在全县的某个地点发生火灾，消防队能在30分钟内到达火灾发生地，至少要新建几个消防队，建在哪几个乡镇，在全县17个乡镇中我们先考虑新增2个消防队，其约束条件为)]),50(),(),,(),(),,(min([nDnmDnzDnyDnxDshort)53...2,1,504,,,(nmzyxmzyx个选址地点且为kmshort30如果不满足这个条件，则再增加一个消防队，一直尝试到新增4个消防队后，初始方案存储矩阵ijW才显示出18个初始方案。4.4.2模型求解用Matlab进行编程求解，程序见附录六，18个初始方案显示如下7图3对应的乡镇如下CGKQDFKQDGKQDHKQEFKQEGKQEHKQEJKQEJMQEJMREJNQEJNRGIMQGIMRGJMQGJMRGKMQGKMR表3任意选择在上面18个方案中的其中一个方案，在方案中的4个乡镇中设置4个消防队都可以满足30分钟内到达全县任一火灾发生点4.4.3消防队选址的优化问题四的初始方案有18个，如何选择这18个方案中的其中一种方案来设置消防队所在地？我们仍然按就近原则来设置消防队所在乡镇，即使得总共5个消8防队按就近原则能在到达全县每一地点上的最短时间总和最短（时间可以转化为路程），具体的代码见附录，求解得出的结果如下：图4即在E镇、F镇、K镇和Q镇设置4只消防队，是最优方案。五、模型的评价与推广1.模型的优点：本文对消防站的选址原则，进行了科学的分析，使得消防站的规划建设不再仅依据经验进行。文中提出的方法又是简易，点与点之间最短路程的确定，既保证了准确性，又避免了繁杂的不必要的大量计算过程，该方法易于推广普及，仅需一幅城市地图，，所述的实例即是利用的二次开发技术实现的。(1)本文所建立的模型均有成熟的理论算法基础，可信度高。(2)本文所建模型均采用Matlab编程求解，通用性好，较好的解决了消防站的选址问题。(3)本文建立的模型不仅可解决消防站选址问