基于min-plus代数可达的城市消防站点配置评估及优化

高晓梅 杜庆治 孙磊 龙华 邵玉斌

引用本文:
Citation:

基于min-plus代数可达的城市消防站点配置评估及优化

    作者简介: 高晓梅(1994−),女,云南人,硕士生,主要研究方向为数据挖掘,大数据处理,网络优化. E-mail:1148455642@qq.com;
    通讯作者: 杜庆治, 57960748@qq.com
  • 中图分类号: TU998.1

Evaluation and optimization of urban fire station configuration based on min-plus algebra accessibility

    Corresponding author: DU Qing-zhi, 57960748@qq.com ;
  • CLC number: TU998.1

  • 摘要: 城市消防站点配置是城市消防规划中的重点问题,城市消防站点从出动到着火辖区的时间是影响消防救援的重要因素. 在火灾发生时,为了使消防队能在“3 min”内到达起火点,提出一种基于min-plus代数域上可达的消防站点配置评估及优化的方法. 该方法首先将消防网络抽象为一个网络拓扑图,通过改进的Dijkstra算法计算网络最优路径,评估消防网络的“3 min”可达性. 然后新增微型消防站优化消防站点配置,将消防站点增添问题转化为一个0-1整形规划问题,并求得“3 min”可达条件下的最优解. 实验结果表明,优化后的消防站配置提升了消防站到需求点的可达能力,增加了城市消防站点配置在时间上的合理性,对城市消防规划具有一定的应用价值和决策指导意义.
  • 图 1  某地区区域消防网络布局图

    Figure 1.  Regional fire network layout map

    图 2  原消防网络的拓扑抽象图

    Figure 2.  Topological abstraction of the original fire network

    图 3  新增微型消防站后的消防网络

    Figure 3.  Add a fire network after the mini fire station

    图 4  “3 min到场”优化新增消防站点数

    Figure 4.  "3 min on arrival" to optimize the number of new fire stations

    图 5  “3 min到场”消防站点性能评估

    Figure 5.  "3 min on arrival" fire station performance evaluation

    表 1  模型输入的参数列表

    Table 1.  List of parameters entered by the model

    消防站拓扑结构状态向量站点设置向量
    ${v_1}$$A = L * w$${{x} }(0) = {[ 0,\infty ,....,\infty ] _{1 \times 7} }$${c} = {[ 0,1,...,1] _{1 \times 7} }$
    下载: 导出CSV

    表 2  原消防网络的供应需求最优路径

    Table 2.  The optimal path of supply demand for the original fire network

    ${V_{\rm b}}$${V_{\rm e}}$最优路径耗时/min最优路径
    ${v_1}$${v_2}$2${v_1} \to {v_2}$
    ${v_3}$4${v_1} \to {v_4} \to {v_3}$
    ${v_4}$3${v_1} \to {v_4}$
    ${v_5}$6${v_1} \to {v_4} \to {v_5}$
    ${v_6}$5${v_1} \to {v_4} \to {v_6}$
    ${v_7}$8${v_1} \to {v_4} \to {v_7}$
    下载: 导出CSV

    表 3  GO, GS, Gn网络性能比较

    Table 3.  Network performance comparison of GO, GS, Gn

    消防网络
    性能评价指标
    ${G_{\rm O}}$${G_{\rm S} }$${G_{\rm n}}$
    ${l_{ {\rm {time} } } }/{\rm {min}}$4.666 72.250 01.750 0
    ${E_{\rm g}}$0.166 70.192 10.255 9
    ${E_{\rm l}}$0.059 50.321 40.391 8
    下载: 导出CSV

    表 4  与文献[8]的网络特征比较

    Table 4.  Compared with the network characteristics of literature [8]

    消防网络特征本文算法文献[8]的算法
    平均到达时间/min2.356 32.302 8
    新增消防站数49
    网络传输效率0.428 20.497 9
    下载: 导出CSV
  • [1] 白华, 吴越. 城市老城区消防站布局优化研究[J]. 中国安全科学学报, 2010, 20(8): 81-87. DOI:  10.3969/j.issn.1003-3033.2010.08.013. Bai H, Wu Y. Study on the distribution optimization of urban fire stations in old city[J]. China Safety Science Journal, 2010, 20(8): 81-87.
    [2] 陈驰, 任爱珠. 消防站布局优化的计算机方法[J]. 清华大学学报:自然科学版, 2003, 43(10): 1 390-1 393. Chen C, Ren A Z. Optimization of fire station locations using computer[J]. Journal Tsinghua University :Sci & Tech, 2003, 43(10): 1 390-1 393.
    [3] 邓轶, 李爱勤, 窦炜. 城市消防站布局规划模型的对比分析[J]. 地球信息科学学报, 2008, 10(2): 242-246. DOI:  10.3969/j.issn.1560-8999.2008.02.020. Deng Y, Li A Q, DOU W. A comparative analysis of the models in urban fire station layout planning[J]. GEO-Information Science, 2008, 10(2): 242-246.
    [4] 祝明明, 罗静, 余文昌, 等. 城市POI火灾风险评估与消防设施布局优化研究—以武汉市主城区为例[J]. 地域研究与开发, 2018, 182(4): 88-93. Zhu M M, Luo J, Yu W C, et al. Urban fire risk evaluation and location optimization of fire station based on the POI: A case study of main urban region in Wuhan[J]. Areal Research and Development, 2018, 182(4): 88-93.
    [5] 徐倩, 贺兴时. 基于AHP与集合覆盖模型的新增消防站选址问题[J]. 信息与电脑:理论版, 2019(13): 26-28. Xu Q, He X S. New fire station location problem based on AHP and set coverage model[J]. China Computer & Communication:Musical Theory, 2019(13): 26-28.
    [6] 俞艳, 郭庆胜, 何建华, 等. 顾及地理网络特征的城市消防站布局渐进优化[J]. 武汉大学学报:信息科学版, 2005, 30(4): 333-336. Yu Y, Guo Q S, He J H, et al. Gradual optimization of urban fire station location based on geographical network attribute[J]. Geomatics and Information Science of Wuhan University, 2005, 30(4): 333-336.
    [7] 詹庆明, 庞前聪, 周玉红, 等. 基于时空分配组合的消防设施服务范围计算方法探讨[J]. 武汉大学学报: 信息科学版, 2008, 33(4): 353-357. Zhan Q M, Pang Q C, Zhou Y H, et al. Computing service areas of fire protection facilities based on the space-time allocation model in GIS[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 353-357.
    [8] 刘莉, 陈晨. 一种GIS与集合覆盖法的消防区优化布局[J]. 测绘科学, 2018, 43(9): 50-55. Liu L, Chen C. A GIS and set covering method for division of responsibility area of fire stations and layout optimization[J]. Science of Surveying and Mapping, 2018, 43(9): 50-55.
    [9] Wei L, Li H L, Liu Q, et al. Study and implementation of fire sites planning based on GIS and AHP[J]. Procedia Engineering, 2011(11): 486-495.
    [10] Dong X M, Li Y, Pan Y L, et al. Study on urban fire station planning based on fire risk assessment and GIS technology[J]. Procedia Engineering, 2018(211): 124-130.
    [11] Francois B, Guy C, Geert J O, et al. Synchronization and linearity: An algebra for discrete event systems[M]. New York, NY, USA: Wiley, 1992:101-104.
    [12] Tao Y G, Liu G P, Mu X W. Max– plus matrix method and cycle time assignability and feedback stabilizability for min– max– plus systems[J]. Mathematics of Control, Signals, and Systems (MCSS), 2013, 25(2): 197-229. DOI:  10.1007/s00498-012-0098-7.
    [13] Wang L, Li C Y, Chen Z Q, et al. Connectivity- based accessibility for public bicycle sharing systems[J]. IEEE Transactions on Automation Science and Engineering, 2018, 15(4): 1 521-1 532.
    [14] Myšková H, Plavka J. Reachability of eigenspaces for interval matrices in max-min algebra[J]. Linear Algebra and its Applications, 2019, 578: 314-333. DOI:  10.1016/j.laa.2019.05.018.
    [15] Latora V, Marchiori M. Efficient behavior of small-world networks[J]. Physical Review Letters, 2001, 87(19): 198701. DOI:  10.1103/PhysRevLett.87.198701.
    [16] Xiao X M, Jia L M, Wang Y H, et al. Topological characteristics of metro networks based on transfer constraint[J]. Physica A: Statistical Mechanics and its Applications, 2019, 532: 121 811. DOI:  10.1016/j.physa.2019.121811.
  • [1] 马锐 . BL代数特征性质. 云南大学学报(自然科学版), 2003, 25(6): 487-489.
    [2] 刘翠梅李彦敏傅景礼 . 非保守动力系统的Lie对称性代数. 云南大学学报(自然科学版), 2008, 30(4): 371-375,380.
    [3] 杨宗文 . 代数正规类的上根. 云南大学学报(自然科学版), 2006, 28(1): 8-11.
    [4] 张轶陈华喜 . 分裂的正则双Hom-Poisson代数结构. 云南大学学报(自然科学版), 2019, 41(3): 435-441. doi: 10.7540/j.ynu.20180147
    [5] 伏文清李生刚 . L-子坡代数范畴及其性质. 云南大学学报(自然科学版), 2013, 35(2): 129-136. doi: 10.7540/j.ynu.20120236
    [6] 杨宗文 . 一般代数正规类中的δ-根类. 云南大学学报(自然科学版), 2005, 27(5): 380-382.
    [7] 张芳娟师东河王立红 . 因子von Neumann代数上的非线性保多重新积. 云南大学学报(自然科学版), 2017, 39(5): 733-738. doi: 10.7540/j.ynu.20170113
    [8] 岳昆王贵松刘惟一 . 一种用于Web服务合成过程建模的不确定性事件代数方法. 云南大学学报(自然科学版), 2008, 30(5): 448-453,459.
    [9] 李克丽张坤梁颖杨军 . 一种基于RO分组的高安全性可配置RO-PUF研究与设计. 云南大学学报(自然科学版), 2020, 42(2): 228-234. doi: 10.7540/j.ynu.20190464
    [10] 蒋玲熊良林树金龙 . 二阶凸优化不等式及加性时变时滞系统的稳定性研究. 云南大学学报(自然科学版), 2019, 41(3): 425-434. doi: 10.7540/j.ynu.20170801
    [11] 王亚丽陈天江普小云 . 消逝场增益耦合微型球腔的光散射理论研究. 云南大学学报(自然科学版), 2005, 27(6): 504-508.
    [12] 高瑞华孙青仪马剑锋江吉波宋洪盛 . 龙口自动站与人工站观测气温的对比分析. 云南大学学报(自然科学版), 2012, 34(3): 303-307.
    [13] 段云俊柴素盈余珂王颢樾李婕张振秀王卫国 . 云南探空站报文质量分析. 云南大学学报(自然科学版), 2015, 37(S1): 67-. doi: 10.7540/j.ynu.20140554
    [14] 王艳霞丁琨周汝良 . 基于地形、水热指标的陆地生物多样性富集度评估——以云南为例. 云南大学学报(自然科学版), 2017, 39(3): 481-493. doi: 10.7540/j.ynu.20160333
    [15] 吴志勇何军刘衍民 . 广义张量特征值的包含域. 云南大学学报(自然科学版), 2017, 39(4): 529-533. doi: 10.7540/j.ynu.20160614
    [16] 赵东风令狐昌兵何永恒丁洪伟王赞扬赵一帆 . 边境地区无线电台站频率冲突分析与对策研究. 云南大学学报(自然科学版), 2009, 31(1): 21-26 .
    [17] 成兆金张国峰于怀征路正文 . 山东省农业气象自动站土壤分布状况研究. 云南大学学报(自然科学版), 2013, 35(S1): 219-225. doi: 10.7540/j.ynu.20130280
    [18] 龚彩仙成佳丽王颢樾张振秀谢晓华 . 新型自动气象站数据维护和保障措施研究. 云南大学学报(自然科学版), 2014, 36(S1): 117-121. doi: 10.7540/j.ynu.20140227
    [19] 李燕楊凤琼马永林 . 自动气象站蒸发量观测疑误数据诊断分析处理. 云南大学学报(自然科学版), 2015, 37(S1): 63-. doi: 10.7540/j.ynu.20150204
    [20] 朱荣欢苏有锦 . 云南区域数字地震台网台站场地响应研究. 云南大学学报(自然科学版), 2007, 29(4): 364-370.
  • 加载中
图(5)表(4)
计量
  • 文章访问数:  437
  • HTML全文浏览量:  530
  • PDF下载量:  37
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-10-21
  • 录用日期:  2019-11-30
  • 网络出版日期:  2019-12-16
  • 刊出日期:  2020-03-01

基于min-plus代数可达的城市消防站点配置评估及优化

    作者简介:高晓梅(1994−),女,云南人,硕士生,主要研究方向为数据挖掘,大数据处理,网络优化. E-mail:1148455642@qq.com
    通讯作者: 杜庆治, 57960748@qq.com
  • 1. 昆明理工大学 信息工程与自动化学院,云南 昆明 650500
  • 2. 云南省计算机技术应用重点实验室,云南 昆明 650500

摘要: 城市消防站点配置是城市消防规划中的重点问题,城市消防站点从出动到着火辖区的时间是影响消防救援的重要因素. 在火灾发生时,为了使消防队能在“3 min”内到达起火点,提出一种基于min-plus代数域上可达的消防站点配置评估及优化的方法. 该方法首先将消防网络抽象为一个网络拓扑图,通过改进的Dijkstra算法计算网络最优路径,评估消防网络的“3 min”可达性. 然后新增微型消防站优化消防站点配置,将消防站点增添问题转化为一个0-1整形规划问题,并求得“3 min”可达条件下的最优解. 实验结果表明,优化后的消防站配置提升了消防站到需求点的可达能力,增加了城市消防站点配置在时间上的合理性,对城市消防规划具有一定的应用价值和决策指导意义.

English Abstract

  • 随着城市的发展,生活中的起火源越来越多,致使火灾事故发生的概率逐年增长. 城市消防规划中消防站的选址和消防站责任区的划分是传统消防站建设中的主要问题,为了使所有消防供应点都能被有效的利用,所有需求点都能得到安全保障,火灾事故点能尽快的获得救援,需要在现有大型消防站的基础上合理地增添微型消防站.

    传统的消防站配置评估优化主要是基于该地区的火灾风险和防护等级[1]或是考虑消防站分布的覆盖面[2-4],配置的随意性较大,评价指标缺乏科学性. 通过本地火灾风险防护等级评估消防配置具有局限性和针对性. 同样,若只是简单的考虑消防站分布的责任区覆盖,不考虑交通的实际运载能力,消防队的实际救援时间就无法准确把控,消防站的建立便很难达到防火救灾的标准. 常见的基于覆盖的配置评估模型主要有区位集合覆盖模型(LSCP)、最大覆盖模型(MCLP)、P-中心模型(P-center Problem)等,这些方法各有其优缺点,经常配合使用. 然而传统的消防站点配置评估方法受实际情况的约束很大,并且通常以距离最短、设施数目最小为目标建立模型,忽略了消防救援时间的重要性,为此有研究者提出了基于AHP与集合覆盖模型的新增消防配置方法[5],考虑了消防站点到需求点的响应时间,但响应时间会随实际情况而变化,所以该方法的实际适用性较差. 为了解决传统消防站点选址的随意性和站点覆盖范围过大等缺点,俞艳等[6]提出了基于城市地理网络特征的消防站点配置评估标准,同时考虑了消防站责任区覆盖和城市地理网络特征,从而在交通可达的前提下评估消防站点配置的优劣. 詹庆明等[7]则通过时空分配组合对消防站点的布局进行选址优化,提出了基于多个独立指标的消防站点配置方法,使得消防设施的配置更符合实际情况. 考虑多个独立指标使得消防区域覆盖计算更加精确,但是算法过于复杂,覆盖人口率的计算结果受人口密集度的制约. 近年来,无论是国内还是国外,学者们仍以消防站的区域覆盖为主要研究方向,提出了基于GIS(地理信息系统)消防站布局研究的大量方法,以解决传统方法中的缺陷[4-10]. 为了简化消防站的配置优化问题,在考虑已有消防设施和消防救援时间下,本文从可达角度出发提出了一种基于min-plus代数域可达的消防站点增添配置方法. min-plus代数域又叫最小加代数域,最早是由Charles Leake[11]提出,2013年已被Tao等[12]用于系统优化,2018年Wang等[13]首次提出基于min-plus代数域上的可达性并将其应用于公交及共享自行车系统配置优化问题中,取得了较好的成果. 2019年国外学者H.Myšková[14]对基于max-min plus代数域上的可达性做了进一步的理论研究,证明了方法的正确性和可行性.

    本文以“3 min”可达为目标,通过供应点和需求点之间的可达性来评估优化消防站点的配置问题,使得消防站点的配置方式更加科学和合理. 并考虑在现有城市基础上进行微型消防站点的优化增补,提高了消防站整体的救援能力.

    • 定义1 连通图:设一个无向赋权图 $G = (V,E,w)$,其中 $V = \{ {v_1},{v_2},\cdots,{v_N}\} $ 表示图的节点集,由点集 $V$ 中的节点关联的边集为 $E = \{ {e_1},{e_2},\cdots,{e_M}\} \subseteq V \times V,$$\forall {e_i} \in E,$$\exists v,u \in V,$ $s.t$${e_i} = vu$$(i = 1,2,\cdots,i,\cdots,M)$$w = \{ {w_1},{w_2},\cdots,{w_M}\} $ 表示对应边的权重值. 当图 $G$ 中任意两节点间均存在至少一条路时,我们称其为连通图,这条性质称为无向图的连通性.

      定义2 min-plus代数域(即最小加代数域)[11]:满足以下两种运算和两个条件的代数域我们称之为min-plus代数域 $\phi $

      两种运算:

      (1)加法 $ \oplus $$\forall a,b \in \phi ,$$a \oplus b \triangleq \min \{ a,b\} $.

      (2)乘法 $ \otimes $$\forall a,b \in \phi ,$$a \otimes b \triangleq a + b$.

      两个条件:

      (3)$\phi $ 中所有元素取自实数集 $R$,且含有一零元 $\varepsilon $,对 $\forall a \in \phi $,满足 $a \oplus \varepsilon \triangleq a$$a \otimes \varepsilon \triangleq \varepsilon $.

      (4)对 $\phi $ 中所有元素,加法 $ \oplus $、乘法 $ \otimes $ 均满足交换律和结合律.

      注意:当域 $\phi $ 中的元素为矩阵时,有下面混合运算,

      $C \triangleq A \otimes B,$

      展开可写成,

      $ \begin{split} &\forall A = {({A_{ij}})_{m \times n}},\;B = {({B_{ij}})_{n \times q}},\;C = {({C_{ij}})_{m \times q}}.\\ &{C_{ij}} = \displaystyle\sum\limits_{k = 1}^n {_ \oplus ({A_{ik}} \otimes {B_{kj}}),} \;\forall i = 1,\cdots,m,j = 1,\cdots,q.\\[-20pt] \end{split} $

      其中我们定义

      $\sum\limits_{i = 1}^Q {_ \oplus {a_i} \triangleq {a_1}} \oplus\cdots \oplus {a_Q}(\forall {a_i} \in R,i = 1,\cdots,Q), $

      ${A^{ \otimes q}} \triangleq \underbrace {A \otimes A \otimes \cdots \otimes A}_q,$

      $A$ 为矩阵,$q$ 为非负整数. 当 $q = 0$ 时,${A^{ \otimes 0}}$ 为零矩阵(也称 $\varepsilon \text{-} $ 矩阵).

      Wang等[13]首次提出基于min-plus代数域上的可达性,他将可达性描述为一个局部网络中的节点之间的连通性,其中局部网络定义为定义3中的 $k$-邻域. 本文在王磊的基础上对可达性做了全新的定义,将可达性定义为两节点间存在规定时间内的路径,即定义4“$k$ min”可达.

      定义3 最小加代数域上的 $k$-邻域[13]:设 $G = $$(V,E,w)$ 为一连通无向赋权图,其中 $V = \{ {v_1},{v_2},\cdots, $${v_N}\} $ 表示节点集,$E = \{ {e_1},{e_2},\cdots,{e_M}\} $ 表示边集,$w = $$\{ {w_1},{w_2},\cdots,{w_M}\} $ 表示边上的权重(可以是距离、时间、消耗量等). 从 $V$ 中任取一点 ${v_i}$,对 $k \in {N^*}$,如果 $w({v_i},{v_j}) < = k$,则称 ${v_j}$${v_i}$$k$-邻域点,${v_i}$ 的所有 $k$-邻域点组成的集合记为 $o({v_i},k)$,称为节点 ${v_i}$$k$-邻域,简写为 ${o_i}(k)$${v_j} \in o({v_i},k)$).

      定义4 “k min”可达:设一连通无向赋权图G= (Vb, Ve, E, w)和一常数$k \in {N^*} $,其中$V_{\rm b} $表示图G的起点集,$V_{\rm e} $表示G的终点集,节点集$V=(V_{\rm b},V_{\rm e}) $. 对任意两点$v_i \in V_{\rm b}$$v_j \in V_{\rm e} $,记 $w({v_i},{v_j})$ 为节点 ${v_i}$ 与节点 ${v_j}$ 间路的最少时间消耗. 若 $w({v_i},{v_j})\leqslant k$,则称 ${v_i}$${v_j}$ 是“$k$ min”可达的(反之也成立). 由于节点 ${v_i}$$k$-邻域 ${o_i}(k)$ 中的任意一点 ${v_j}$ 到节点 ${v_i}$ 是“$k$ min”可达的,则称 ${o_i}(k)$ 是“$k$ min”可达的. 如果$\forall {v_{j_1}} \in V_{\rm e} $$\exists V_{i_1} \in V_{\rm b}$使得$v_{j_1}\in o_{i_1}(k)$,则称连通无向赋权图G是“k min”可达的,即无向赋权图G满足min-plus代数域上的“k min”可达. 当k=3时,称无向赋权图G是“3 min”可达的.

    • 在对拓扑网络进行可达性分析时,首先需要计算起始点到终点的最优路径,常用的求解拓扑网络中节点间最优路径的方法是Dijkstra算法,传统的Dijkstra算法可以求解从顶点到其余各点的最优路径,用于解决赋权无向图的最优路径问题. Dijkstra算法不仅可以找出从点 $s$ 到点 $e$ 的一条最优路径,运行一次Dijkstra算法就可以找到从点 $s$ 到图中任意一点的最优路径. 但是,这样每寻找一次两点间的最优路径至少需要做 ${N^2}$$N$ 为拓扑网络中的节点数)次代数运算,当 $N$ 较大时,算法的执行效率将变得很慢. 为了加快算法执行效率,本文利用最小加代数域上的两种运算,对传统Dijkstra算法进行改进,可以明显提高算法实现的效率.

      定义5 图的拓扑结构和邻接矩阵:设一无向赋权图 $G = (V,E,w)$$L = ({l_{ij}}) \in \{ 0,1\} $ 为其拓扑结构矩阵,其中 ${l_{ij}} = 1$ 表示节点 ${v_i}$ 和节点 ${v_j}$ 之间存在一条直接相连的边,${l_{ij}} = 0$ 表示这两个节点间不存在直接相连的边. 令 $A = ({a_{ij}}) = L * w$ 表示节点间的相邻关系(边)称为图 $G$ 的邻接矩阵.

      改进Dijkstra算法基本思想如下:

      $G = (V,E,w),w \geqslant 0$ 是一个连通无向赋权图,$N$ 为此无向赋权图的节点数,$w$ 为其权重矩阵. 令 $L = {({l_{ij}})_{N \times N}}$ 为图 $G$ 的拓扑结构矩阵,则有邻接矩阵 $A = {({a_{ij}})_{N \times N}} = L * w$. 使用改进Dijkstra算法求解起始点 ${v_1} \in V$ 到节点集 $V$ 中其余各点的最优路径.

      第1步,确定起点 $s = {v_1}$,源点集 $S{\rm{ = \{ }}s\} $ 以及目标点集 $En = V - S,$$t$ 为从起点到达其余节点所前进的次数(也称为当前状态时刻),计算各个节点当前时刻 $t = 0$ 的状态变量 ${x_i}(0)$$(i = 1,2,\cdots,N)$ 并将其储存在状态向量 ${{x}}(t = 0) = {[ 0,\infty ,\cdots,\infty ] _{1 \times N}},$ 中. 其中 ${x_1}(0) = 0$ 表示以 ${v_1}$ 为起点,${x_i}(0) = \infty (i = 2, $$3,\cdots,N)$ 表示当前状态下从起点 ${v_1}$ 出发,还未到达其他任何一个节点.

      第2步,计算起点 ${v_1}$ 相邻点的权值,并更新各节点的状态变量 ${{x}}(t = 1) = {[0,\infty ,\cdots,\mathop 2\limits_{{x_i}(1)} ,\cdots,\infty ]_{1 \times N}},$ 其中节点 $v_i$ 为点 ${v_1}$ 的相邻点. 由此我们得到min-plus代数域上的状态向量的状态方程(5)

      ${{x}}(t) = [{x_1}(t),{x_2}(t),\cdots,{x_N}(t)], $

      $\begin{split} {x_i}(t) = &{A_{i * }} \otimes {\bf{x}}(t - 1)= \\ &\displaystyle\sum\limits_{j = 1}^N {_ \oplus ({A_{ij}} \otimes {x_j}(t - 1)),}\\ i =& 1,2,\cdots,N,t = 1,2,\cdots , \end{split} $

      其中 ${A_{ij}}$ 为邻接矩阵 $A$$i$ 行第 $j$ 列的元素,${A_{i * }}$ 为邻接矩阵 $A$ 的第 $i$ 行.

      第3步,从目标集 $En$ 中选取状态变量最小的节点放入源点集 $S$ 中,并将此节点作为新的起始节点,计算其相邻节点的权值,并更新各个节点的状态变量. 此时,如果 $En = \varnothing $ 则继续第4步,否则跳到第3步.

      第4步,得到最终状态向量 ${{x}}({t_{\rm d}}) = [ {x_1}({t_{\rm d}}), $${x_2}({t_{\rm d}}),\cdots,{x_N}({t_{\rm d}})] $,其中状态向量的每一个元素

      $\begin{split} {x_i}({t_{\rm d}}) =& {A_{i * }} \otimes {\bf{x}}({t_d} - 1) =\\ & {A_{i * }} \otimes {A_{i * }} \otimes {{x}}({t_d} - 2)= \\ & \cdots= A_{i * }^{ \otimes (N - 1)} \otimes {{x}}(0), \\ i =& 1,2,\cdots,N,t = 1,2,\cdots{t_{\rm d}}. \end{split} $

      则有

      ${{x}}({t_{\rm d}}) = {A^{ \otimes (N - 1)}} \otimes {{x}}(0),$

      ${t_{\rm d}}$ 为最终状态时刻,${A^{ \otimes (N - 1)}}$ 称为判别矩阵. 最终状态向量表示从起点 ${v_1}$ 到其余各点的最优路径的长度,从而也就得到了从起点 ${v_1}$ 到其余各点的最优路径.

    • 我国的城市消防站布局,根据《中华人民共和国消防法》(2016年修订版)、《城市消防规划规范》(2015年)中消防规划要求,城市规划区内普通消防站的布局一般应以接到报警消息后5 min内消防队可以到达着火辖区边缘为原则. 记消防站接到报警消息到消防队到达着火辖区边缘所花费的时间为 $T$,则有

      $T{\rm{ = }}{T_1} + {T_2} + {T_3},$

      其中 ${T_1} \leqslant {\rm{1}}$ min表示119指挥中心接警并寻找距离火源最近消防站发出出警命令所需时间. ${T_{\rm{2}}} \leqslant $1 min表示消防队接到出警命令后出动准备花费的时间. ${T_{\rm{3}}} \leqslant 3$ min表示消防队从消防站出发到达着火辖区边缘在交通上花费的时间. 本文将消防站点的配置问题抽象为一个网络拓扑优化问题,所以只考虑消防队已经出动后在交通上所花费的时间 ${T_3}$. 以 ${T_3}$ 作为消防网络配置问题的优化指标,于是原问题就变成了“3 min”可达条件下的拓扑网络优化问题.

      假设:①所有微型消防站的服务力度相同,即相同时间内到达相同地点的灭火能力相同;②所有需求点没有重要程度之分;③所有道路均是双向可行驶的;④消防队在接到报警命令时能够立即出动,即不考虑接警和出动准备时花费的时间;⑤本文所有涉及时间的数据单位均为分钟,消防站到需求点耗时不足1 min时按1 min计算.

    • 图1所示为一个城市的消防系统部分布局图,其中包含了消防站(图1中红色的点)、抽象的需求点(图1中黄色的点)以及城市街道. 由于发生火灾时从消防站出发到各个可能的着火点秉着就近分配的原则,城市消防系统可以分成一个个独立的子系统,每个子系统都有一个对应的消防站控制,这样的网络结构类似一个分布式的网络拓扑结构,其拓扑结构可以用一个矩阵 $L$ 表示:

      图  1  某地区区域消防网络布局图

      Figure 1.  Regional fire network layout map

      $\begin{array}{l} L = {({l_{ij}})_{N \times N}} = \left( {\begin{array}{*{20}{c}} {{0_{}}}&{{1_{}}}&{{1_{}}}&{{1_{}}}&{{\varepsilon _{}}}&{{\varepsilon _{}}}&{{\varepsilon _{}}}\\ {{1_{}}}&{{0_{}}}&{{\varepsilon _{}}}&{{1_{}}}&{{1_{}}}&{{\varepsilon _{}}}&{{\varepsilon _{}}}\\ {{1_{}}}&{{\varepsilon _{}}}&{{0_{}}}&{{1_{}}}&{{\varepsilon _{}}}&{{1_{}}}&{{\varepsilon _{}}}\\ {{1_{}}}&{{1_{}}}&{{1_{}}}&{{0_{}}}&{{1_{}}}&{{1_{}}}&{1{}_{}}\\ {{\varepsilon _{}}}&{{1_{}}}&{{\varepsilon _{}}}&{{1_{}}}&{{0_{}}}&{{\varepsilon _{}}}&{{1_{}}}\\ {{\varepsilon _{}}}&{{\varepsilon _{}}}&{{1_{}}}&{{1_{}}}&{{\varepsilon _{}}}&{{0_{}}}&{{1_{}}}\\ {{\varepsilon _{}}}&{{\varepsilon _{}}}&{{\varepsilon _{}}}&{{1_{}}}&{{1_{}}}&{{1_{}}}&{{0_{}}} \end{array}} \right), \end{array} $

      $ i = 1,2,\cdots,N,j = 1,2,\cdots,N,N = 7. $

      其中矩阵 $L$ 的行和列 ${v_1},{v_2},{v_3},{v_4},{v_5},{v_6},{v_7}$ 分别对应图中的消防站和7个需求点(也称为被服务点),注意由于需求点1附近存在消防站,故认为节点 ${v_1}$ 既是消防站也是需求点,此时认为消防站1和需求点1之间必然满足3 min可达性. ${l_{ij}} = 1$ 表示节点 ${v_i}$${v_j}$ 之间有直接相连的道路,${l_{ii}} = 0$ 表示自身节点的关系,${l_{ij}} = \varepsilon $(令 $\varepsilon = \infty $)表示节点 ${v_i}$${v_j}$ 之间没有直接相连的道路(但可以间接相连,即可以通过先到达某个节点后再到达该节点). $V = \{ {v_1},{v_2},{v_3}, $${v_4},{v_5},{v_6},{v_7}\} $ 称为网络的节点集,令源点集 ${V_{\rm b}} = \{ {v_1}\} $ 表示消防站站点集,终点集 ${V_{\rm e}} = \{ {v_1},{v_2},{v_3},{v_4},{v_5}, $${v_6},{v_7}\} $ 表示消防需求点集,则有 $V = \{ {V_{\rm b}},{V_{\rm e}}\} $. 边集 $E = \{ {e_1},{e_2},\cdots,{e_{12}}\} $$({e_1} = {v_1}{v_2},$ ${e_2} = {v_1}{v_3},\cdots)$ 表示节点与节点之间直接相连的道路,消防队通过每条边的最少时间消耗我们称之为边的权值,用一个向量 $w = \{ {w_1},{w_2},\cdots,{w_{12}}\} $ 表示,于是这个复杂的网络系统就被抽象为数学上的一个连通无向赋权图 $G = (V,E,w)$(其中 $V = \{ {V_{\rm b}},{V_{\rm e}}\} $)(如图2所示). 注意由于消防网络中的消防站是建立在需求点之上的所以图 $G$ 中的所有节点 $V$ 均是需求点,消防站点包含于节点集 $V$ 中.

      图  2  原消防网络的拓扑抽象图

      Figure 2.  Topological abstraction of the original fire network

      图2所示消防网络拓扑结构的状态向量为 ${{x}}(t) = [ {x_1}(t),{x_2}(t),\cdots,{x_7}(t)] $,其表示在 $t$ 时刻下以消防站 ${v_1}$ 为起点到达所有需求点花费的最少时间. 当 $t = 0$ 时,${{x}}(0) =[ 0,\varepsilon ,\varepsilon ,\varepsilon ,\varepsilon ,\varepsilon ,\varepsilon ] $ 表示从消防站 ${v_1}$ 到达需求点 ${v_1}$ 所消耗的最少时间为0,消防站 ${v_1}$ 到达其他需求点所消耗的最少时间为 $\varepsilon = \infty $,当前时刻下,只有节点 ${v_1}$ 是“3 min”可达的. 当 $t \geqslant 2$ 时,${{x}}(t) = [0,2,4,3,6,5,8] $ 表示以消防站 ${v_1}$ 为起 为起点到达其余各需求点的最少时间消耗. 此时状态向量$\leqslant 3 $的需求点 >${v_1},{v_2},{v_4}$ 就满足了“3 min”可达,也即剩余需求点不满足“3 min”可达. 在状态向量表示下,消防网络的可达性判断就等价于判断状态向量是否满足给定限制条件.

      在对消防网络进行可达性分析时,需要计算网络节点间的最少时间消耗,此时等价于求无向赋权图 $G$$w$ (时间权重)下的最优路径长度,也称为最优路径耗时.本文通过第2节中改进的Dijkstra算法求解.

    • 本文通过将区域抽象为一个网络结构图,分析消防站点到需求点间是否满足“3 min”可达,其中消防站到需求点的最少时间消耗通过计算两点间的最优路径长度获得,每一个需求点只要存在一个“3 min”可达的消防站点则称其满足当前网络结构下的“3 min”可达. “3 min”可达的意义旨在消防队接到出动指令后3 min内(包括3 min)可以到达着火点辖区边缘. 结合可达性定义4以及文献[13]中可达性的充要条件,我们得到“$k$ min”可达的充要条件.

      定理1. “$k$ min”可达的充要条件:图G的子图$G_i=(v_i,V_i,E_i,w^i)(v_i \in V_b )$ 是“$k$ min”可达的当且仅当 $A_i^{ \otimes ({n_i} - 1)}$ 中的所有元素均$\leqslant k$,其中 ${n_i}$ 为子图 $G_i$ 对应的节点数.

      由“$k$ min”可达的充要条件以及公式(8)中的判别矩阵,我们构造“3 min”可达的二进制判别矩阵如下

      $\begin{split} &{{\tilde A}^{ < N > }} = \left( {\begin{array}{*{20}{c}} {{{\tilde A}^{ < {n_1} > }}}\\ \vdots \\ {{{\tilde A}^{ < {n_i} > }}}\\ \vdots \\ {{{\tilde A}^{ < {n_m} > }}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{{(\tilde A_{gh}^{ < {n_1} > })}_{{n_1} \times {n_1}}}}\\ \vdots \\ {{{(\tilde A_{gh}^{ < {n_i} > })}_{{n_i} \times {n_i}}}}\\ \vdots \\ {{{(\tilde A_{gh}^{ < {n_m} > })}_{{n_m} \times {n_m}}}} \end{array}} \right),\\ &(\tilde A_{gh}^{ < {n_i} > } \in \{ 0,1\} ,i = 1,2,\cdots,m;\\ &{A_i}^{ \otimes ({n_i} - 1)}(g,h) \leqslant {\rm{3}} \to \tilde A_{gh}^{ < {n_i} > }{\rm{ = 1}};\\ &{A_i}^{ \otimes ({n_i} - 1)}(g,h) > {\rm{3}} \to \tilde A_{gh}^{ < {n_i} > }{\rm{ = 0;}}) \end{split}$

      其中,${A_i}$ 为消防站 $i$ 对应子网络的邻接矩阵,${n_i}$ 为消防站 $i$ 对应子网络中的节点个数,$m$ 为消防网络中子网的个数(即消防站个数). 通过公式(11)我们可以将每个消防供应点对应的满足“3 min”可达的需求点求解出来,放入消防站点的 $k$-邻域中 $(k = 3)$,如果得到所有消防站的 $k$-邻域后,仍然存在孤立的需求点,则认为当前的消防站网络不满足“3 min”可达.

    • 城市消防系统是一个分布式结构的网络系统,这个网络是由一个个以消防站为中心的子网络组合而成,在这样的拓扑网络结构中每一个子网络的防灾问题都由其唯一的消防站控制,因此合理的建设微型消防站使其能保证城市消防防灾的“3 min”可达是本文要解决的消防站点配置优化问题.

      ${c} = [ v{'_{{i_1}}},v{'_{{i_2}}},\cdots,v{'_{{i_h}}},\cdots, v{'_{{i_N}}}] (v{'_{{i_h}}} \in \{ 0,1\} )$ 为微型消防站的站点设置向量,如果节点 ${v_{i_h}}$ 附近设立微型消防站则 $v{'_{i_h}} = 1$,否则 $v{'_{i_h}} = 0$. 我们根据公式(11)定义的二进制判别矩阵 ${\tilde A^{ < {n_i} > }} = [\tilde A_{gh}^{ < {n_i} > }] \in {R^{{n_i} \times {n_i}}}$$i=1,2,\cdots,m $,对应每一个矩阵 $A_i^{ \otimes ({n_i} - 1)},i = 1,2,\cdots,m$,如果 $A_i^{ \otimes ({n_i} - 1)}(g,h) \leqslant 3$$\tilde A_{gh}^{ < {n_i} > } = 1$,如果 $A_i^{ \otimes ({n_i} - 1)}(g,h) > 3$$\tilde A_{gh}^{ < {n_i} > } = 0$,这样“3 min”可达的充要条件就等价于矩阵 ${\tilde A^{ < {n_i} > }}$ 不含有0元素,也即

      $\sum\limits_{h = 1}^{{n_i}} {\tilde A_{gh}^{ < {n_i} > }} v{'_{{i_h}}} \geqslant 1,g = 1,2,\cdots,{n_i}.$

      于是在满足可达性条件下,建立优化消防站点配置的线性规划问题:

      $\begin{array}{l} \begin{array}{*{20}{c}} {\min }&{\displaystyle\sum\limits_{j = 1}^N {{c_{{j}}}} } \end{array} \\ \begin{array}{*{20}{c}} {{\rm s}.{\rm t}}\!\!\!&\!\!\!{\displaystyle\sum\limits_{h = 1}^{{n_i}}\! {\tilde A_{gh}^{ < {n_i} > }\!{c_{{{{i_h}}}}}\! \geqslant 1,} }\!\!\!&\!\!\!{g = 1,2,\cdots,{n_i}} , \end{array}\!\!i = 1,2,\cdots,m, \\ \begin{array}{*{20}{c}} {{c_{{j}}} \in \{ 0,1\} ,}&\forall \end{array}j = 1,2,\cdots,N. \\[-15pt] \end{array} $

      算法1:消防站点配置优化模型求解

      输入:拓扑结构矩阵 $L$,时间权重矩阵 $w$,常量 $k = 3$,消防网络的节点数 $N$,消防站数 ${N_{\rm f}}$

      输出:二进制向量 ${c} = [ v{'_{i_1}},v{'_{i_2}},\cdots,v{'_{i_h}},\cdots,v{'_{i_N}}] $

      $(v{'_{i_h}} \in \{ 0,1\} )$$v{'_{i_h}} = 1$ 表示当前位置附近应建立微型消防站.

      步骤1 初始化状态向量 $x(t)$${c} = [ 1,1,\cdots,1] $,确定已有的消防站节点集 ${V_{\rm b}} =\{{v_{{j_1}}},\cdots,{v_{{j_h}}},\cdots, v_{j_{N_{\rm f}}}\} \in V$.

      步骤2 使用改进Dijkstra算法计算以 ${V_{\rm b}} = $$\{ {v_{{j_1}}},\cdots,{v_{{j_h}}},\cdots, v_{j_{N_{\rm f}}}\}$ 中的节点为起点到网络中所有需求点的最优路径 ${p_{{{\rm e}_i}}} = \{ {v_{{j_i}}},\cdots,{v_{\rm e}}\} ,$ 其中 $i = 1,$$2,\cdots,N_{\rm f},{v_{\rm e}} \in {V_{\rm e}} = V - {V_{\rm b}}$,称Ve为消防节点的剩余集,ve为剩余集Ve中的元素. 记 ${P_{{j_i}}} = {({p_{{{\rm e}_{ij}}}})_{j = 1,\cdots,N - N_{\rm f}}}$ 表示已知消防站 ${v_{{j_i}}}$ 到所有需求节点的最优路径矩阵,

      $\begin{split} &{P_{{j_i}}} = {({p_{{{\rm e}_{ij}}}})_{j = 1,\cdots,N - N_{\rm f}}} = \left( {\begin{array}{*{20}{c}} {{v_{{j_i}}}}& \cdots &{{v_{{{\rm e}_1}}}} \\ \vdots & \ddots & \vdots \\ {{v_{{j_i}}}}& \cdots &{{v_{{{\rm e}_j}}}} \\ \vdots & \ddots & \vdots \\ {{v_{{j_i}}}}& \cdots &{{v_{{{\rm e}_{N-N_{\rm f}}}}}} \end{array}} \right), \\ &{v_{{{\rm e}_j}}} \in {V_{\rm e}} = V - {V_{\rm b}}, \\ \end{split} $

      计算最优路径矩阵 ${P_{{j_i}}}$ 对应的最优路径长度 $L{'_{{j_i}}} = $$ [ {l_{{{\rm e}_1}}},{l_{{{\rm e}_2}}},\cdots,{l_{{{\rm e}_{N - N_{\rm f}}}}}],$ 其中 ${l_{{{\rm e}_j}}}$ 表示以 ${v_{{j_i}}}$ 为起点 ${v_{{{\rm e}_j}}}$ 为终点的最优路径长度.

      步骤3 以消防站为中心确定满足可达性的 $k$-邻域,分别记为 ${o_{{j_i}}}(k),\forall {v_{{j_i}}} \in {V_{\rm b}}$,除去消防站 $k$-邻域包含的节点,剩下的节点放入剩余集 ${V_{{\rm e}1}}$,以消防站为起点它们不满足可达性,需要新建微型消防站.

      步骤4 分别对每个消防站点的 $k$-邻域求二进制判别矩阵(11).

      步骤5 求解公式(13)描述的0-1整型规划问题,并返回向量 $c$.

    • 图2描述的拓扑网络进行消防站点配置评估优化,如图2所示无向赋权图 $G{\rm{ = }}(V,$$ E,w)$ 中的 ${v_1}$ 为消防站,其余各点均是需求点,图2中边上的数值表示边连接的两节点间的最少时间消耗. 表1是实验需要输入的数据,考虑到 ${v_1}$ 已经有消防站,所以不需要在 ${v_1}$ 处建立微型消防站.

      消防站拓扑结构状态向量站点设置向量
      ${v_1}$$A = L * w$${{x} }(0) = {[ 0,\infty ,....,\infty ] _{1 \times 7} }$${c} = {[ 0,1,...,1] _{1 \times 7} }$

      表 1  模型输入的参数列表

      Table 1.  List of parameters entered by the model

      图2知权重矩阵 $w$ 为:

      $ \begin{array}{*{20}{c}} \end{array}w = \left( {\begin{array}{*{20}{c}} {{{\rm{0}}_{}}}&{{{\rm{2}}_{}}}&{{{\rm{6}}_{}}}&{{{\rm{3}}_{}}}&{{{\rm{1}}_{}}}&{{{\rm{4}}_{}}}&{{{\rm{7}}_{}}} \\ {{{\rm{2}}_{}}}&{{{\rm{0}}_{}}}&{{{\rm{5}}_{}}}&{{{\rm{7}}_{}}}&{{{\rm{6}}_{}}}&{{{\rm{7}}_{}}}&{{{\rm{8}}_{}}} \\ {{{\rm{6}}_{}}}&{{{\rm{5}}_{}}}&{{{\rm{0}}_{}}}&{{{\rm{1}}_{}}}&{{{\rm{3}}_{}}}&{{{\rm{4}}_{}}}&{{{\rm{2}}_{}}} \\ {{{\rm{3}}_{}}}&{{{\rm{7}}_{}}}&{{{\rm{1}}_{}}}&{{{\rm{0}}_{}}}&{{{\rm{3}}_{}}}&{{{\rm{2}}_{}}}&{{{\rm{5}}_{}}} \\ {{{\rm{1}}_{}}}&{{{\rm{6}}_{}}}&{{{\rm{3}}_{}}}&{{{\rm{3}}_{}}}&{{{\rm{0}}_{}}}&{{{\rm{8}}_{}}}&{{{\rm{2}}_{}}} \\ {{{\rm{4}}_{}}}&{{{\rm{7}}_{}}}&{{{\rm{4}}_{}}}&{{{\rm{2}}_{}}}&{{{\rm{8}}_{}}}&{{{\rm{0}}_{}}}&{{{\rm{9}}_{}}} \\ {{{\rm{7}}_{}}}&{{{\rm{8}}_{}}}&{{{\rm{2}}_{}}}&{{{\rm{5}}_{}}}&{{{\rm{2}}_{}}}&{{{\rm{9}}_{}}}&{{{\rm{0}}_{}}} \end{array}} \right). $

      则邻接矩阵 $A = L * w$

      $A = \left( {\begin{array}{*{20}{c}} 0&2&6&3&\varepsilon &\varepsilon &\varepsilon \\ 2&0&\varepsilon &7&6&\varepsilon &\varepsilon \\ 6&\varepsilon &0&1&\varepsilon &4&\varepsilon \\ 3&7&1&0&3&2&5 \\ \varepsilon &6&\varepsilon&3&0&\varepsilon &2 \\ \varepsilon &\varepsilon &4&2&\varepsilon &0&9 \\ \varepsilon &\varepsilon &\varepsilon &5&2&9&0 \end{array}} \right).$

      已知 ${v_1}$ 为原消防站,通过Matlab编程,首先计算出 ${v_1}$ 到所有需求点的最优路径和最优路径耗时见表2.

      ${V_{\rm b}}$${V_{\rm e}}$最优路径耗时/min最优路径
      ${v_1}$${v_2}$2${v_1} \to {v_2}$
      ${v_3}$4${v_1} \to {v_4} \to {v_3}$
      ${v_4}$3${v_1} \to {v_4}$
      ${v_5}$6${v_1} \to {v_4} \to {v_5}$
      ${v_6}$5${v_1} \to {v_4} \to {v_6}$
      ${v_7}$8${v_1} \to {v_4} \to {v_7}$

      表 2  原消防网络的供应需求最优路径

      Table 2.  The optimal path of supply demand for the original fire network

      表2中可知,“3 min”可达的需求点只有 ${v_1},{v_2},{v_4}$,此时我们需要对消防网络进行优化,根据已建立的0-1整形规划求得需要新增的最小消防站点数为2,位置在需求点 ${v_4}$${v_7}$ 的附近如图3所示. 此时的消防网络再次验证满足了“3 min”内的可达性且总的消防救援时间最小,说明在花费资源建设两个微型消防站后图2所示的城市消防网络整体性能有所提升.

      图  3  新增微型消防站后的消防网络

      Figure 3.  Add a fire network after the mini fire station

      使用文献[6]中的方法优化图2所示的消防网络,通过Matlab编程实现,计算得新增消防站点的数量也为2. 和本文算法的结果比较可知,本文方法优化后的消防网络新增的站点数量满足消防全覆盖的最小值.

    • (1) 消防网络的平均最少时间消耗:${l_{\rm{time}}} = \dfrac{{\displaystyle\sum\limits_i^{{N_{\rm f}}} {{d_{{t_i}}}} }}{{N - {N_{\rm f}}}}$, $N$ 为消防网络中需求点的个数(即节点数),${N_{\rm f}}$ 为消防网络中消防站点的个数,${d_{{t_i}}} = \displaystyle\sum\limits_j^{{N_{\rm e}}} {{d_j}} $ 指网络中消防站 $i$ 和对应需求点 $j$ 间的最少时间消耗之和,${d_j}$ 为消防站 $i$ 和对应需求点 $j$ 间的最少时间消耗,其中 ${d_j}$ 的单位为min,${N_{\rm e}}$ 指当前消防站对应的需求点个数. 消防网络的平均最少时间消耗常指消防网络中所有消防站对需求点之间的平均最少时间消耗,常用于表征消防网络的整体性能,时间消耗越少网络性能越好.

      (2) 消防网络传输效率:${E_{\rm g}} = \dfrac{{\displaystyle\sum\limits_{i = 1}^{{N_{\rm f}}} {\displaystyle\sum\limits_{j = 1,j\text{≠}i}^N {{{\rm e}_{ij}}} } }}{{{N_{\rm f}}(N - 1)}}$. 其中 $N$ 为消防网络中需求点的个数(即节点数),${N_{\rm f}}$ 为消防网络中消防站点的个数,${{\rm e}_{ij}} = \dfrac{1}{{d{}_{t(ij)}}}(i\text{≠}j)$ 为消防站 $i$ 和服务点 $j$ 之间的传输效率,${d_{t(ij)}}$ 为两节点间的最少时间消耗. 因为 $1 \leqslant {d_{t(ij)}} \leqslant {d_{\max }}$$0 \leqslant {{\rm e}_{ij}} \leqslant 1$,则有 $0 \leqslant {E_{\rm g}} \leqslant 1$. 消防网络传输效率越高,说明相同时间内的可到达的节点数就越多.

      (3) 网络的局部传输效率 ${E_{\rm l}} = \dfrac{{\displaystyle\sum\limits_{i = 1}^N {{E_{{\rm g}(i)}}} }}{N}$,其中 $N$ 为网络中的节点数,${E_{{\rm g}(i)}}$ 为消防站点 $i$ 及其“3 min”可达的需求点所组成的子网的传输效率. 网络局部传输效率反应网络的局部性能,其高低直接影响了网络的局部容错能力. 由于 $0 \leqslant {E_{{\rm g}(i)}} \leqslant 1$,则有 $0 \leqslant {E_{\rm l}} \leqslant 1$,局部网络传输效率越高,局部容错性越强.

    • 表3是原消防网络 ${G_{\rm O}}$图2)和优化后的消防网络 ${G_{\rm n}}$图3)以及文献[6]中优化后消防网络 ${G_{\rm S}}$ 的平均最少时间消耗ltime、网络传输效率Eg以及局部网络传输效率$E_1(0\leqslant E_g \leqslant 1, 0\leqslant E_1\leqslant 1)$.

      消防网络
      性能评价指标
      ${G_{\rm O}}$${G_{\rm S} }$${G_{\rm n}}$
      ${l_{ {\rm {time} } } }/{\rm {min}}$4.666 72.250 01.750 0
      ${E_{\rm g}}$0.166 70.192 10.255 9
      ${E_{\rm l}}$0.059 50.321 40.391 8

      表 3  GO, GS, Gn网络性能比较

      Table 3.  Network performance comparison of GO, GS, Gn

      表3中可以明显看出新增微型消防站后整个消防网络的平均最少时间消耗减少、网络传输效率和网络局部传输效率均有提高,说明新的消防网络较原网络性能更好,局部容错性也比较高. 相对于文献[6]中的算法优化的结果,本文的结果在3个性能指标上都有提高,平均最少时间消耗的减少说明了本文算法得到的新增消防站点数量和位置保证了最少时间消耗下的站点配置是相对更优的. 为了进一步证明算法的有效性,本文使用100组包含20个网络节点,3个原始消防站点的仿真数据进行验证得到新增消防站点数(图4)和3个网络特征比较图(见图5

      图  4  “3 min到场”优化新增消防站点数

      Figure 4.  "3 min on arrival" to optimize the number of new fire stations

      图  5  “3 min到场”消防站点性能评估

      Figure 5.  "3 min on arrival" fire station performance evaluation

      图4中可以看出本文算法优化的消防网络新增消防站点数在大部分仿真结果处都比文献[6]中的新增站点数少,部分新增消防站点数为0,说明在本文的可达性评价标准下原消防网络不需要新增消防站点. 总的来说本文算法求出的新增站点数在保证“3 min”可达的前提下比文献[6]中的结果更好.

      图5(a)中可以看出原始的消防网络在平均最少时间消耗上比新增微型消防站后的新消防网络多了约2 min,而文献[6]优化后消防网络的平均最少时间消耗较本文的稍高. 新消防网络的平均最少时间消耗小于3 min,说明优化后的消防网络保证了消防站到每个需求点都是“3 min”可达的. 图5中的网络传输效率(b)和局部网络传输效率(c)显示,新增微型消防站后消防网络的整体传输效率和局部容错性都有明显的提升. 这在理论上也很容易证明,在新增微型消防站后原消防系统“3 min”可达的覆盖面已经达到了100%,整体网络传输效率都得到提高,而且就算有个别消防站暂时失去功能,也能通过就近消防站得到及时的补充救援.

      对比文献[8]中的算法,见表4.

      消防网络特征本文算法文献[8]的算法
      平均到达时间/min2.356 32.302 8
      新增消防站数49
      网络传输效率0.428 20.497 9

      表 4  与文献[8]的网络特征比较

      Table 4.  Compared with the network characteristics of literature [8]

      表4中知,本文算法的平均到达时间与文献[8]中算法的平均到达时间相差不大,网络传输效率相对于文献[8]的结果稍差,但是新增消防站的站点个数减少了一半,说明本文的算法能较好地节省建造成本.

      类似文献[6]和文献[8]中基于GIS系统配置优化消防站布局的论文很多[4-10],这些论文均在特定条件下取得了较好的结果. 本文通过min-plus代数域上的运算改进了Dijkstra算法,使得算法执行速度更快,并基于min-plus代数域构造了“3 min”可达的判别矩阵,解决了总救援时间和新增消防站点数最小的消防布局问题,所得新增消防站点数较传统方法更少,平均消耗时间最少,网络传输效率和局部网络传输效率均较优.

    • 通过本文提出的基于min-plus代数域上的可达性,利用改进Dijkstra算法求解网络的最优路径,从而评估消防站点能否“3 min”到达,对于无法“3 min”到达的需求点新增微型消防站优化消防站点配置.根据本文优化方法配置相应的微型消防站后,消防网络的平均最少时间消耗有明显的减少,消防网络的整体传输效率和局部传输效率也有明显的提高,说明优化后新消防网络的整体性能和容错性都有所提高,对消防站的合理配置有一定的指导意义.

参考文献 (16)

目录

    /

    返回文章
    返回