消防队选址模型的建立与分析
本文就给定的城市交通图，对城市消防站三类选址问题进行了探讨，并分别建立了相应模型，较好的解决了消防队选址问题。对解决目前各个城市消防站增建选址问题有一定指导意义。
模型Ⅰ：提出了一个完整的消防队选址评估模型。通过对不同影响因素的分析，利用加权方式平衡了防火单位差别和道路差别。根据选址问题的特点和要求，在时间最短的基础上，构造了火灾损失最小的数学模型。把Floy-Warshall算法引入到该模型的求解中，顺利解决了求防火单位最短距离问题。通过计算机编程，求得了模型的最优解，验证了模型的正确性。实例求解表明，该模型可以有效、快速地求得消防队选址问题的全局最优解。
模型Ⅱ：在对模型Ⅰ求得的结果充分分析的基础上，将模型进行了合理的简化。顺利解决了消防队的数目扩大到两个时变量过多模型求解困难的问题。
模型Ⅲ：综合模型Ⅰ与模型Ⅱ，通过分阶段选址，提出了改进的模型，顺利解决了新增消防站选址问题。
关键词：消防站选址 最短路Floy-Warshall算法
（一）问题重述
1.1 基本情况
专职消防队是指在城市新区、经济开发区、工业集中区及经济较为发达的中心乡镇,根据《中华人民共和国消防法》，按照质量建队的要求,建立的承担区域性火灾扑救任务的市办、县办专职的消防队。消防队的任务是在发生火灾时及时赶到火灾现场，扑救火灾，抢救人的生命和重要物资。因此消防站的选址一定要科学合理，在火灾发生时及时尽快赶到火灾现场，减小损失。
1.2 问题的由来
总体来说全国大部分城市，消防站布点少，保护面积过大，如规划前广州市消防站所服务的最小责任区达11.8平方公里，最大责任区面积达700平方公里。从2001年的统计资料看，全国266个地级以上城市应有公安消防站2655个，实有1548个，欠账41.7%。不少城市已建的消防站责任区保护面积过大，难以满足消防车5min到达责任区边缘的要求，有些地区，甚至连一个消防站都没有。因此，在资源有限的条件下，消防队的选址显得尤为重要。另外，在一座城市中，有重点防火单位，一级防火单位，一般防火单位之分。道路也有主干道和一般街道之分。所以消防队的选址不能简单的定在城市中心，而应当根据各单位分布，道路交通状况，综合考虑选址地点，必要时应当增加消防队的数目，保证在火灾发生时消防队的及时到达。
1.3 问题的要求
有一座城市，需要建立消防队，城市地图如下，其中实线为主干道，虚线为一般街道，标A的地方为重点防火单位所在地。标B的地方为一级防火单位。其他地方为一般防火单位，均匀分布在主干道和一般街道两旁。图中数字为相应
路线长度，单位为公里。
（1）请你为消防队选一个合适的建队地址。 （2）若要同时建两个消防队，地址该如何选？
（3）若第二个消防队在前面已建好一个后再建，该如何选择地址？（可以类似自画图，考虑复杂程度，本图街道画得较少）
A1 2 1.5 A3 A4 1 A5 2 0.3 B1 B2 0.8 1.2 B3 1.7 2.0 B4 3 1.5 0.7 0.7 B5 A2 B6 0.5 0.9 A6 1 0.2 B7 A7 0.3 0.8 2 1.8 AB1.4 0.5 A1.2 1.2 B8 A9 B9 0.8 0.8 0.4 0.3 A8 0.3 B1 1.5 0.8 0.7 0.7 2 AA1.4 B0.7 A1.2 A
（二）基本假设
为简化模型，便于量化与计算，现作假设如下：
1.不考虑消防队的反应时间，假设接到火情的瞬间，消防队即出发救火。
2. 不考虑路况，转弯，各路段加减速情况，假设消防车一直匀速运动。因此行车时间的衡量可简化为距离的衡量。主干路与一般街道的区别用路长的加权表示。
（三）符号设定
用于标定具体位置 。当1?,ij15?i,j——城市地图中的各防火单位，
代表防火单位Ai,Aj；当16?i,j?27时，i,j代表防火单位Bi?15,Bj?15。
R时，i,j——城市地图防火单位邻接矩阵。R?i,j?表示点i,j之间道路实际距离，
若无直连道路，赋值为inf，代表无穷大。
W——赋权矩阵。当i?j?k时，W?i,j?表示防火单位k的重要度加权；当
i?j且i,j有直连道路时，W?i,j?表示此道路加权值；当i?j且i,j无直连道路
时，W?i,j?赋值inf。
AW,A?i,j?表示防火单位i,j之——加权后的道路邻接矩阵。定义A?R?间加权后道路距离，若无直连道路，赋值为inf，代表无穷大
D——最短距离矩阵，D?i,j?表示i,j间最短距离。
——火灾损失。
n——防火单位总个数。
Bs(k)——防火单位k距离消防队的最短距离。
M?i,j?，N?i,j?——火灾损失指标函数。
（四）模型的建立与问题解决
4.1．问题的初步分析
通常选址问题只考虑到距离因素的影响，而消防队选址则还需要考虑到目标的重要性和时间因素。消防目标分布较为分散、地域跨度大，这对消防队位置的确定产生了较大的影响。其实影响消防站选址的因素很多,例如交通条件、自然地理条件、道路状况、地价、城市功能分区要求等。显然，其中一些因素只能由人进行主观判断，而有些因素则可以利用计算机进行分析。事实上，要使火灾损失达到最小，最重要的是消防队接到火警后应能够尽快到达火灾现场。因此，在以往的研究中，一般都将消防车辆的行车时间作为评判消防站选址优劣的原则。本文则在此基础上，结合各单位防火级别的不同，火灾时间与损失的关系，建立了一个更为合理的评估模型体系。
在确立了以行车距离为基础作为消防站选址原则后，如何计算行车距离就成了关键问题。对于一般防火单位，均匀分布在道路两旁，最明显的计算方法是积分法。设消防站位于?x0,y0?处，火灾发生点为?x,y?，s?x,yx0,y0?表示从消防站到火灾现场的最短距离，为了体现不同单位防火级别的不同，例如易
燃易爆物品工厂，仓库与一般的住宅区火灾危险性不同。用W?x,y?表示火灾现场?x,y?处的火灾重要性权重，对一般地区可取W?x,y?为1，对重要地区
可取W?x,y?为大于1的实数,则位于?x0,y0?处的消防站至该区内所有假设火灾发生点的总行车距离为
S???W?x,y?s?x,yi?1linx0,y0?dxdy
其中li为各路段。上述积分法理论上简单，但在实际应用中却并不实用。这是因为积分表达式中的W?x,y?和s?x,yx0,y0?并不是简单的连续函数，且这种对整个责任区段进行积分的过程也不容易编程实现。对于本题而言，一般防火单位均匀分布在主干道和一般街道两旁，因此只要能够有效到达重点防火单位和一级防火单位（也即图中各节点），就也能有效到达一般防火单位。故将模型合理简化为考虑有限个防火单位的选址问题。
4.2模型Ⅰ：单个消防队选址模型 4.2.1模型初步分析
根据题目所提供的城市图，提取数据，给出道路邻接矩阵R（具体数据见附录一）。其中R?i,j?表示防火单位i,j之间道路实际距离，若无直连道路，赋值为，代表无穷大
为便于量化求解，将题目中的重点防火单位，一级防火单位，主干路，一般街道赋权处理。防火单位的处理以一级防火单位为基准，权重为1，重点防火单位赋权?，??1可以适度照顾重点防火单位；道路的处理以一般道路为基准，权重为1，主干路赋权v，v?1可体现主干路的行车速度优势，由此得到赋权矩
inf阵W（具体数据见附录二）。当i?j?k时，W?i,j?表示防火单位k的重要度加权；当i?j且i,j有直连道路时，W?i,j?表示此道路加权值；当i?j且i,j无直连道路时，W?i,j?赋值inf。
定义加权后的道路邻接矩阵
A?R?W
A?i,j?表示防火单位i,j之间加权后道路距离，若无直连道路，赋值为inf，
代表无穷大。
定义最短距离矩阵D，其中D?i,j?表示道路加权后i,j间最短距离。显然，要求出D并不容易，逐条计算的方法繁复且不具有通用性，借助计算机求解是可行的方案。在图论中有许多求节点间最短距离的算法，在这里我们采用Floy-Warshall算法编程求解。
Floy-Warshall算法是基于动态规划的一种求有向图G??V,E?顶点间最短路径的解决方案。它的运行时间为??V3?，并且允许权值为负的边存在，但我们假设不存在权值为负的边。该算法利用最短路径结构的一个特征，即考虑最短路径上的中间顶点，其中简单路径p??v1,v2,?,vl?上的中间顶点是除v1，vl之外p上的任何一个顶点，即任何属于集合?v2,?,vl?1?的顶点。[2]具体算法分析见参考文献[2]。
本文在Matlab环境下采用Floy-Warshall算法编程，圆满实现了矩阵D的求解（程序代码见附录三，程序文件为floyd.m）
4.2.2模型的建立与求解 不妨假设消防队建在道路?i,j?之间的某个点上(i?j)。设它距离i点x?i,j?，则显然距离j点A(i,j)?x?i,j?。假设k为一个防火单位，则它距离消防队的最短距离为
s(k)?min?D?i,k??x?i,j?,D?j,k??A?i,j??x?i,j??
一般而言，火灾发生后，火势以失火点为中心，以均匀速度向四周呈圆形蔓延，所以蔓延的半径r与时间t成正比。故火灾损失B与t2成正比，在速度v一定的情况下，s与t成正比，故损失B与s2成正比。结合防火防火单位的重要度加权，建立火灾损失指标函数如下:
?n?2M?i,j??min??W?k,k?s(k)?
?k?1?
根据指标函数依次对图中的道路进行分析，可以得到一个有限点的集合。量化火灾损失
Bmin?min?M?i,j??