基于最短路径算法的舰船通道逃逸路线研究

1 引 言

舰船逃逸路线是指灾害区域及可能受到威胁区域的舰员撤离到安全地点的路线[1]，它直接关系到遇险舰员的生命安全。由于舰船通道普遍比较狭窄，而且通往露天区域的出口有限，其本身的复杂性以及灾害的蔓延对逃生通道的影响，使得选择合理的逃逸路线往往成为一件比较棘手的工作。而一套良好的救生通道设计方案能大大减少舰员疏散撤离的时间，提高舰员获救的几率。因此，开展舰艇救生通道设计方面的研究不仅是必要的，而且意义重大。本文就如何采用图论原理结合计算机技术，对逃逸路线的选择与规划进行了初步探索研究。

2 现有求解逃逸路线的方法

现有最佳逃逸路线的研究主要集中在对高层建筑通道疏散、矿井井巷逃生和紧急情况(如毒气泄漏等)疏散逃生的研究上，国内一些专家学者主要是针对火灾时的最佳逃逸路线进行研究[2-5]。以上的研究都是以图论的最短路理论为基础而展开的，其基本设计思想是求解安全且具有最短行走时间的路线。不同学者采用不同的路权来描述通道通行的难易程度。舰船通道系统的逃生情况与以上几种情况类似，可以借鉴数学建模的方法指导舰船逃逸路线的研究。

如今有少数学者利用GIS(地理信息系统)技术开发智能逃逸系统进行网络分析，开发出了友好的用户界面，已经应用于实际的救灾工作。

当今舰艇及民船上经常采用的方法主要是利用现有的设备帮助舰员选择救生路线，并采用每隔一段时间的训练、演习、广播等使舰员对救生通道更为熟悉，在事故发生时减少判断错误的发生频率。可见，常用的方法主要是经验的推广，与先进的逃逸系统相比，无疑后者更严谨更具有发展前景[6]。作为研究的起步工作，需要将图论等技术应用到实际的舰船通道逃逸路线规划中来，建立初步的研究模型。

3 舰船逃逸路线的计算方法

3.1 道路权重的确定

求解合理的逃逸线路从实质上讲是求解安全撤退的最短时间。最短距离的撤退路线不等于最短的撤退时间，这是因为通道的通行难易程度不一样。对于舰船通道，需要考虑的影响人员通行速度和路线选择的因素主要有：甲板层高、楼梯的坡度、障碍物的影响、有毒有害气体浓度、高温烟流阻塞通道等。这些影响因素与民用建筑人员逃生的影响要素很相似，而不少学者通常用“当量长度”来综合描述建筑物中的这些影响因素。因此，本文引入“当量长度”的概念来描述舰船通道各路段的综合属性，文献[3]的研究方法将这些影响因素用通行难易程度来表示，使之与通道的实际长度相乘后得到的长度即为“当量长度”。用当量长度表示路权不仅考虑了通道长度和可达性，而且考虑了人员分布密度情况以及通行的难易程度。为便于比较和分析，文章分别用各路段行走时间和“当量长度”来表示路段的通行难易程度。

第i条通道的当量长度可用下式来表示：

(1)

式中,li——第i条通道的当量长度值，m；

ω——烟流体积分数惩罚系数；

c——有害气体体积分数；

ρ——群集密度，ρ=P/(B·lri)，P、B分别为通道人数和宽度；

lri——第i条通道的实际长度；

kt——通道类型的难易系数；

ki——不同区域的危险系数。

选择逃逸路线时，应首先分析各通道在灾变时是否适合人员通行；按照上述方法可以计算出通道的当量长度(即路权)，形成当量长度的邻接矩阵。在此基础上，根据舰船通道形成的网络情况，采用一定的算法选择舰员的合理逃逸路线。

3.2 前N条最短路算法描述

图论中经典的最短路算法主要包括Dijkstra及Floyd算法，但它们只能求取第1最短路径而不能求得第2， …，N最短路径。这不能满足疏散逃逸需要多条备选路径的要求。由于灾变的发展有某些不可预测因素，当第1最短路径行不通时，可选用第2、第3最短路径，故引出求解多条救灾与逃逸路线的前N条最短路问题(也称K最短路问题)。

本文前N条最短路算法的基本思想是:首先采用Floyd算法在原图中求两节点间的最短路径(Floyd算法便于求解任意两点间的最短路)，然后依次删除最短路径上的边，每删除一条边生成一个子图，再在子图中用最短路算法求最短路，依次循环调用最短路算法，可求得前N条最短路径[7]。

算法具体步骤和运行流程图(图1)如下:

1) 首先运用Floyd算法求出从源节点s到t的最短路径r0； 将r0插入备选集Pi；

2) 依次删除最短路径上的边，生成与路径的边相同数目的子图，在各自得到的子图r中调用最短路径算法得到路径集。标记r为已处理。

图1 求解前N条逃逸路线程序流程图

3)P中的路径数已达到或超过N值，转步骤5)。

4) 在路径中寻找未处理的路径，将其标记为当前待处理的路径，转步骤2)。

5) 将路径备选集的多条路径返回，算法结束。

4 选择逃逸路线的方法应用

某舰的局部区段简化路线示意图如图2所示，图中对区段进行了网络化(弯曲路线用直线表示，各路段比例不代表实际情况)，整个网络共有67条分支，42个节点。上下两个平面上纵横交错的直线为各层甲板的主要通道，连接两层甲板的直线表示楼梯。由于某地发生事故或火灾，需要将事故节点所在地人员疏散到安全地点。

4.1 舰船路网邻接矩阵的计算

本文使用邻接矩阵作为路网的存储方式，用一个二维数组C[i][j]表示，由于通道网络为带权图，所以其邻接矩阵表示为:

(2)

上式中，wij表示该路段的权值，本文分别用两种参数来表示：各路段的行走时间和当量长度。参考文献[7]中的一项实测研究结果表明，当人员密度为0.5人/m2<ρ≤1.5人/m2时，人员迁移流动呈自由流动状态，人员平均步速为1.3 m/s；当人员密度为1.5人/m2<ρ≤3人/m2时，人员平均步速为0.7 m/s，人员流动呈现滞留流动状态；在人员密度为1.5人/m2以下时，密度的提高导致速度降低并不明显，但是超过这一密度时，随着密度的提高，速度明显下降。同时表明，楼梯间中的人流速度约为水平人流速度的一半。

考虑建筑通道与舰船通道的区别。假定舰员疏散时，所有通道都是畅通的，门和梯口盖完全打开；假定舰员普遍是训练有素的青壮年人员，舰船狭窄的通道会一定程度上影响舰员的行进速度。参考以上假设和研究，平直通道速度取为1.0 m/s；舰上楼梯比建筑楼梯要陡，取上行通过速度和下行速度的折中值为0.5 m/s；直梯上的通行速度约为0.4 m/s；而对于通道网络的各路段的人员密度情况，假定在各个楼梯附近为滞留状态，在平直通道为微滞留或自由流动状态，在多条交叉路口为微滞留状态，根据如上假设进行路段时间和当量长度的计算。这些参数的取值和假设还需要通过实验来进行进一步验证。

图2 通道网络示意图

4.2 运用N最短路算法求解合理逃逸路线

运用Matlab编程工具实现了N最短路相关算法在舰船路网计算上的运用，利用Matlab 6.5的图形用户界面编制程序的操作界面，直观简洁便于操作。程序启动时，在程序界面输入起点和终点节点号，即可得出计算机处理的3条逃逸路线及相关信息。任意指定几个舰员位置(或遇灾区域)和逃生出口，计算机处理的逃逸路线如下(表1～表3)：

表1 节点39逃逸路线计算表

表2 节点40逃逸路线计算表

表3 当量长度计算逃逸路径表

通过各点间最短路径的计算，可以为舰船逃生出口的路线分派提供依据。计算的结果不仅可以显示各个点(或途经各点)到各个出口的远近，便于选择合理的出口，而且容易看到路径的使用情况。比如39节点到32或33出口的逃逸时间明显比到34出口时间短，即可以引导途经39节点的逃生人员优先选择这两个出口逃生。

如果由于火势蔓延等原因，导致某一条或几条通道路径堵塞，或者环境恶劣舰员无法通过，只需要将该条路段的权值设为∞或者一个很大的正整数，那么计算机在搜寻路径的时候会自动改变可通行性条件，自动避开该条路径。比如正常情况下，从节点40逃逸的出口首选节点33，最短路距为38.5 s，路线为：40→26→42→29→17→18→33。当节点17附近发生较大的火灾时，假定短时间内通道17→18或17→29被烟流严重污染，在实际中不可通行。这时，基于最短路线所计算出的疏散时间是不合理的。将该路段权值设为∞，重新计算可以得出节点40合理的疏散路线为：40→26→42→28→27→ 6→ 5→12→13→18→33，路距66.5 s；40→26→24→22→20→9→10→15→34，路距58.5 s；40→26→42→28→27→ 6→7→4→31， 路距60.5 s。从计算结果可看出，合理可行的疏散路线比最短路线合理。而重新计算的结果显示，此时的逃逸首选出口变为34和31而不是33。这样求解的疏散路线安全性要更高，能合理地指导逃生舰员安全疏散出去。

通过表1、表2和表3的比较，采用路段行驶时间和当量长度来表示路权，得出的路线结果大体一致，说明两种方法的计算都有其合理性，但也存在差异。比如，通过两种计算方法得到的节点40到34的计算结果就不同，这是途经路段的人员密度不同造成的。可见当量长度考虑了路段宽度和人员密度对道路通行的影响，使得不同路段的差别增大。采用当量长度来表示路段的通行难易程度，得出的结果更贴近实际更有实用价值。

5 结论和建议

本文探讨了N-最短路算法在舰船通道逃逸路线研究上的应用。在假定灾害的前提条件下，对灾害时期通道的可通行性、通行的难易度、N最短路算法等进行了深入研究。对影响通道通行难易程度的因素进行分析，引进“当量长度”的概念并建立了相应的计算模型，结合N最短路算法对某舰舱段的疏散路径进行了计算，并进行了分析总结。

尽管对该论题的研究还是初探，但对于舰上指挥员决策和总布置设计具有一定的指导意义，今后尚需进一步研究和解决的问题是：

1) 烟流浓度和人员分布密度是动态变化的，如何求解不同时刻的最佳疏散路线。

2) 利用GIS技术实现通道系统的可视化，能够用图形直观显示结果和路径，使操作人员操作更方便。

3) 将“舰船事故逃逸路线系统”与舰艇损管系统的设计相结合。

[1] 付恩俊，唐安东.井下火灾期间最佳避灾路线的选择[J].煤矿安全，2006，37(10)：32-34.

[2] 李兴东.矿井火灾时期避灾路线的确定及其应用程序[J].煤矿安全，2001，32(12)：20-22．

[3] 谢旭阳，任爱珠，周心权.高层建筑火灾最佳疏散路线的确定[J].自然灾害学报，2003，12(3)：75-80.

[4] XIAO Guo-qing，WEN Li-min， CHEN Bao-zhi. Study on model of dangerous areas in poison gas leakage[C]∥Progress in safety science and technology.Beijing：Chemical Industry Press，2000:302-306.

[5] 陈金国，朱金福.矿山灾变环境下逃逸路径优化算法[J].煤矿安全，2005,36(11):54-56.

[6] 胡晓芳，胡勇，程剑.综合安全评估在舰艇救生通道优化设计中的应用[J].舰船科学技术，2006,28(6):121-124.

[7] 柴登峰，张登荣.前N最短路径问题的算法与应用[J].浙江大学学报(工学版)，2002，36(5)：531-534．