Research on the optimal escape path algorithm in mine water bursting disaster

Abstract

To find the optimal escape path in mine water bursting disaster, present researches have proposed the Dijkstra iterative algorithm. The optimal escape route should be chosen according to the extent of the disaster development and its impact scope. However, the traditional algorithm does not have a real-time analysis on the water flow and the escaping process, thus its solution is not or even far from optimal. Based on the traditional algorithm, this paper puts forward an algorithm with real-time analysis of escaping and water bursting processes. It analyzes water bursting range in real time according to the time of passing through each roadway on a path, and then finds an optimal escape path which is most secure and least time-consuming through comparison. The experiments show that the algorithmis able to find the optimal escape path more effectively compared with other algorithms.

Keywords

Water bursting disasters Dijkstra algorithm shortest path optimal escape path

1. Introduction

The accidents of mine water bursting are sudden, destructive and secondary. The complexity of the underground roadway environment brings difficulties to rescuers to know the overall situation of water bursting in a short time and master the inundated range and the risks that the people in the mine suffer. Therefore, it is hard to take effective measures to evacuate people in best escaping time, which can be fatally damaging [1].

The shortest path problem aims to find the best path with respect to some cost measure between two distinct nodes in a graph [2]. The shortest path refers to a path where the sum of the weights on each edge is the smallest of the paths along the vertex and reaching the other vertex along the edge of the graph. The shortest path problem is solved by the following algorithms: Dijkstra algorithm, Bellman-Ford algorithm, Floyd algorithm and SPFA algorithm. In addition, there is also the famous heuristic search algorithm A*. In 1959, computer scholars in Holland proposed Dijkstra algorithm, whose advantage is that it can get the optimal solution of the shortest path. However, to find the best disaster avoidance path of mine roadways means the consideration of not only the shortest spacial distance but also other factors such as difficulty of passage, escaping time, etc. [3]. Li et al. [4] and Wang et al. [5] believed that to set the best escaping path to which type of shortest path mainly depends on the degree of the disaster development and the impact scope in underground roadway. Wang and Wu [6] optimized the algorithm based on the original Dijkstra algorithm in aspects of search efficiency and search range.

The main documents contributing to this paper include:

1) 1)
Sifaleras [7] presented a wide range of problems concerning minimum cost network flows, and also discussed state-of-the-art algorithmic and recent advances in the solution to the MCNFP. Although the classic linear MCNFP could be efficiently solved in strongly polynomial time by algorithms that exploited the network structure of the problem, there were several other intractable generalizations (e.g., time-varying MCNFP). Therefore, further research effort was required.
2)
In Marinakis et al.’s research [8], the following variant of the Shortest Path problem is solved. Given a graph G of which each arc is associated with two positive weights, cost and delay, we consider the problem of selecting a set of $k$ arc-disjoint paths from a node $s$ to another node $t$ such that the total cost of these paths is minimum and that the total delay of these paths is not greater than a specified bound. This problem is called the constrained shortest arc-disjoint path problem (CSDP).
3)
Hu [9] said that in urban area, the delay due to the traffic lights should be taken into consideration when searching for the optimal path. So this paper presents an algorithm to find the real-time shortest path in urban area with traffic lights. It uses a heuristic evaluation function which contains information on issues to sort the nodes of Open list, so that the search was guided to the direction with high possibility to produce the optimal solution to find the target.
4)
Roth [10] wanted to compute all shortest paths from a set of starts to a set of targets. If we use the one-to-one planning in a loop, we consider each path as an independent computation. The drawback: we cannot take benefit of similarities between planning steps. In this paper he described the efficient many-to-many path planning that is based on A*. It significantly reduced the number of visited crossings due to computation similarities.
5)
Yuan and Wang [11] considered more practical factors, A multi-objective path selection model is presented to minimize the total travel time along a path and to minimize the path complexity.
6)
Zhang et al. [12] talked about the path selection in emergency logistics management. He thought the travel speed will change that with the extension of the disaster, a novel bio-inspired method is proposed to solve this problem.

These studies had been more or less applied in solving the optimal escape route of mine water bursting disaster, but for the water flooding process, there is no real-time analysis, thus the solution is not or far from optimal. In this paper, in the condition of no globally optimal solution, the path decomposition analysis is carried out. According to the time of passing through each roadway, the water bursting range in this time can be calculated. Then through comparison, the escape path that does not pass through the water bursting range can be found. If there is no such path, the traffic ability of submerged roadways will be assessed to solve the optimal path.
2. Calculation of the shortest path

2.1 Equivalent length of roadway

The difficulty of roadway passing is mainly affected by nclination angle of the roadway, the accumulation of obstacles, the height of the roadway and so on. The equivalent length of roadway is the product of different factors’ quantization result and the actual length of the roadway.

The influence coefficients of different factors need to be determined in advance to calculate roadway equivalent length [13], these factors mainly include: roadway inclination, roadway height, obstruction in roadway, transportation facilities and water bursting situation. Set the coefficients of influence factors as: $\beta_{1},\beta_{2},\ldots,\beta_{n}$ . The calculation is shown in Eq. (1):

$\beta_{i}=[T_{i}-t]/t$ (1)

where, $\beta_{i}$ : the influence coefficient of a certain influence factor of a roadway; $T_{i}$ : the time that people pass through the roadway when the influencing factor exist; $t$ : The time that people pass through the roadway when the influencing factor does not exist.

After calculating the influence coefficient of each influencing factor in the current roadway, the formula of the equivalent length of the single roadway is shown in the Eq. (2):

$L=l\times\left({\frac{V_{s}}{V_{n}}}\right)=l\times({1+\beta_{1}+\beta_{2}+% \ldots+\beta_{n}})$ (2)

where, $L$ : the equivalent length of a roadway, m; $l$ : the actual length of a roadway, m; $V_{s}$ : the actual speed of passing through the roadway, m/s; $V_{n}$ : the highest average speed of passing through the roadway, m/s.

2.2 Roadway traffic ability and weight

According to the above analysis, there are many factors influencing the traffic ability of roadway. Due to the difficulty of quantifying all the influence factors in reality, the people forward speed in roadway is adopted to indirectly measure the traffic ability of roadway [14].

The calculation of optimal escape route needs the roadway traffic ability weight as parameter. The height of the water level in the roadway and the average height of the Chinese 1.70 meters are used to design the traffic ability weigh of roadway, as shown in Table 1.

Table 1
Roadway traffic ability weight

Walking posture	Traffic ability	Walking environment (water level $x$ )	Traffic ability
Crawl	4	Water level of the knee ( $x<$ 55 cm)	2
Stoop	2	Water level of the waist (55 cm $<x<$ 101 cm)	4
Walk	1	Water level of the chest (101 cm $<x<$ 131 cm)	5
Trot	0.5	Familiar darkness	2
Run	0.25	Unfamiliar darkness	4

This paper applies the graph theory to define the mine roadway network as $G=(V,E)$ , where $V$ represents the set of nodes in the roadway network; and $E$ is the correlation between nodes. If any of the two nodes $V_{i}$ and $V_{j}$ in the graph are adjacent to each other, then $W_{ij}$ represents the corresponding traffic ability weight of the roadway. If the two nodes are not adjacent, they can’t form a roadway, then the weight $W_{ij}$ between the two nodes is presented by $\infty$ . When the adjacency matrix column $i=j$ , set $W_{ij}=$ 0, mathematically, as shown in Eq. (3):

$W_{ij}=\begin{cases}0&({i=j})\\ \text{weight of the edge}({i,j})&({i,j\in E,i\neq j})\\ \infty&(V_{i},V_{j}\text{ are not adjacent})\\ \end{cases}$ (3)

Figure 1.

Flow chat of water spreading downward.

For optimal escape route analysis, the road traffic ability weight is the most important factor, and it is comprehensive evaluation of the parameters such as the equivalent length of roadway and the weight of traffic efficiency.

Mathematical Model of Roadway Traffic Ability Weight is shown in Eq. (4):

$W_{ij}=L\times w_{ij}\times\frac{1}{P}$ (4)

where, $W_{ij}$ : roadway Traffic Ability Weight; $L$ : the equivalent length of the roadway between nodes $i$ and $j$ ; $w_{ij}$ : according to the water level in the roadway, the traffic ability weight between nodes $i$ and $j$ can be obtained. Let the weight of most efficient traffic to be 0, and when the weight is $\infty$ , namely, when $W_{ij}=$ $\infty$ , the roadway is impassable; $P$ : the inclination angle of the roadway between nodes $i$ and $j$ , the smaller the angle, the easier to pass; otherwise, the more difficult.

2.3 Dijkstra shortest path algorithm

The Dijkstra algorithm is a classical algorithm to solve the shortest path problem in network graph analysis. The algorithm solves the shortest path according the increasing order of the path length using greedy algorithm strategy. The algorithm is widely used for its high robustness and simple program [15]. Therefore this paper employs this algorithm solve the shortest path.

3. Calculation of spreading range of water bursting

In the mine roadway, the direction of the water flow is weighted digraph. Suppose $G=(M,Z,N,$ $t(p,t))$ is a weighted directed graph, where $M$ is the adjacency matrix containing the weights between all the nodes in the roadway; $Z$ is the set of elevation information of all the nodes; $N$ is the set of the nodes that are not submerged adjacent to the current node, and the water flow direction is decided by the elevation of adjacency nodes of each node in this set; $t(p,t)$ is the set of water flow paths, where $p$ is pervaded path, namely the key points water flow passes successively, and $t$ is the time of the water spreading.

3.1 Calculation of downward water spreading path

Due to the gravity, water preferentially flows into the roadway of lower elevation. Finally it reaches the global or local lowest point. At this time the downward water spreading process is over, then the water level will rise. See Fig. 1.

From the downward water spreading algorithm, the spreading sequence of the key nodes on the flow path is obtained. The influencing factors of gravity in actual water flowing process will ensure that water flows to the point with lowest potential energy.

Figure 2.

Flow chat of water spreading upward.

3.2 Calculation of upward water level rise

The start point of water level rise algorithm is the end point of downward water spreading algorithm, namely the local or global lowest point in the roadway, which is to say, from this point, water level starts to rise to the points with higher potential energy. The termination of water rising process is confirmed by the balance between the total amount of gushed water and the amount of water in roadways. See Fig. 2.

In the mine roadway network, the water level value H0 of a key node is the roadway water capacity of all key points, namely, the amount of burst water in mine when the water level of all the key points rises, divided by the cross-section area of water in roadway in depth direction, and the calculated length is the water level value H0.

3.3 Calculation of water spreading speed and time

3.3.1 Downward water spreading speed and time

Calculate water flow along horizontal roadway according to the constant flow and open channel flow. And according to other relevant factors, the speed of downward water flow is calculated considering the XieCai formula in hydrodynamics, as shown in Eq. (5)

$v=\sqrt{\frac{8g}{\lambda}}\sqrt{R\frac{h_{f}}{l}}=C\sqrt{RJ}$ (5)

where, $g$ : gravitational acceleration; $\lambda$ : roadway resistance coefficient; $h_{f}$ : head loss in the roadway; $R$ : water transfer capacity of roadway (hydraulic radius); $C$ : coefficient of XieCai, generally $\mathrm{C=}R^{\frac{1}{6}}/n$ , $n$ is roughness coefficient; $J$ : Hydraulic gradient in roadway.

When the water flow down along the vertical roadway, it can be deemed as the free falling of water. Gravity acceleration is the key influencing factor, so the water spreading speed can be calculated by the energy conversion formula, as shown in Eq. (6)

$mgh=\frac{1}{2}mv^{2}\Leftrightarrow gh=\frac{1}{2}v^{2}\Leftrightarrow v=% \sqrt{2gh}$ (6)

where, $m$ : burst water unit mass; $h$ : height of vertical roadway.

When water flows downward along inclined roadway, if the angle of inclination is less than 45 ${}^{\circ}$ , add the inclined angle of the inclined roadway to the speed calculation formula of water flow along horizontal roadway. If the angle of inclination is more than 45 ${}^{\circ}$ , add the inclined angle of the inclined roadway to the speed calculation formula of water flow along vertical roadway.

The time that water spreads to an arbitrary position in the downward spreading path is calculated by summing the ratios of the length of each roadway on the current path and its speed of spreading. As shown in Eq. (7)

$t=l_{1}/v_{1}+l_{2}/v_{2}+\ldots+l_{i}/v_{i}$ (7)

where, $l_{i}$ : length of roadway $i$ ; $v_{i}$ : flow rate of roadway $i$ .

Figure 3.

Flow chart of optimal escape path algorithm.

3.3.2 Water level rising time

The condition for the stop of water level rising is that the current roadway water level is equal to the water level at water bursting point, so if the water level at bursting point is always higher than the current roadway level, the water level will go on rising until the water fills the entire roadway. Based on this, according to the amount of burst water in unit time and the capacity of roadway, the time for water to fill entire roadway, namely the water level rising time, can be calculated [16], as shown in Eq. (8)

$t=\frac{V}{Q-Q_{1}}$ (8)

where, $V$ : water capacity of roadway; $Q$ : Water inrush per unit time, formula as shown in Eq. (5); $Q_{1}$ : Unit drainage capacity; $t$ : The time that water spreads to an arbitrary point on the rising path.

4. Solution of the optimal escape path

Because the water spreading is real-time and dynamic, the wight shortest path or the time shortest path obtained using the shortest path algorithm is not certainly the optimal path, and it is not consistent with the actual situation of underground personnel escape. Based on the shortest path algorithm, this paper proposes a method to solve the optimal path. The idea is to obtain the shortest path using the Dijkstra algorithm, and then calculate the range of the water flow, and compare the shortest path and the range of the water flow, the path that does not pass through the flooding range is the optimal path, if there is no optimal path, it is necessary to analyze the shortest path decomposition to find the optimal path that does not pass through the flooded range. If it is not found, it means that people must go through the water spread range in the process of escape, at this time, it is necessary to recalculate the traffic ability of the roadways in the path. With the precondition of traffic ability, the path using the shortest time is the optimal path.

Step 1 Step 1
Calculate the weight $L$ of each roadway according to Eq. (4), initialize the weight matrix $W$ of the nodes, give the escape starting point st and escape ending point $e$ . The set $Y$ of the time of downward water spreading and the time of water level rising for each section of the roadway is known from Section 2.3;
Step 2
Use the Dijkstra algorithm to get the shortest path path from st to $e$ , save each obtained path to the set $F$ and then determine whether the sum of the weights of the path is infinite, if so, go to Step 5; if not, go to Step 3;
Step 3
Calculate the time $T$ of the person passing the path, path, based on the time information of the set $Y$ , the range of the water flooding in the time $T$ is obtained by the solution of the downward water spreading and water level rising paths in the 2.3 Section, deposit spreading path into set WP;
Step 4
Determine whether the edges of the path overlap the edges of wp, if no, it means that the people can escape to the security node and without passing through the flooding path, and the path is the optimal escape path, program ends; if yes, set the weight of the repeated edges to infinity in the weight matrix $W$ , and a new weight matrix is obtained, and then return to Step 2;
Step 5
Repeatedly take each path in $F$ path, determine whether the path is null, if no empty, calculate the set $T^{\prime}$ of the time of people passing through each roadway of path path, go to Step 6; if yes, go to Step 8;
Step 6
Loop to get each roadway $p$ in path path and the time $t$ of people escaping from escape start point to $p$ , determine whether p is null, if yes, path is the optimal escape path, program ends; if no, go to Step 7;
Step 7
Calculate the water spreading range wp ${}^{\prime}$ in time $t$ based on the time information of the set $Y$ , determine whether $p$ belongs to wp ${}^{\prime}$ , if yes, go to Step 5, if no, go to Step 6;
Step 8
Add the water level influencing factors, and then recalculate the traffic ability of submerged roadways on each path in $F$ , if the path is not passable, it means that there is no optimal escape path, program ends; If it is passable, recalculate the time of people passing through each path, and the path which requires the shortedt time is the optimal escape path, program ends.
Step 9
Repeat Steps 2 $\sim$ 8 until the end of the program, the returned path is the optimal escape path.

The optimal escape path algorithm obtained by improving the shortest path algorithm is more suitable for the actual situation of personnel escape when mine water bursting occurs, its optimal escape path is safer.
5. Case analysis

According to the information table of a mine roadway in the literature [17], the data such as cross-sectional area, length, inclination angle and water capacity of each roadway are obtained.

Table 2
Information table of mine roadway

Roadway	Starting	End	Start node	End node	Section	Length	Angle	Capacity of
branch	node	node	coordinates	coordinates	area /m ${}^{2}$	/m	/ ${}^{\circ}$	water /m ${}^{3}$
e ${}_{1}$	V ${}_{1}$	V ${}_{2}$	(0, 0, 0)	(50, 0, 0)	18	50	0	900
e ${}_{2}$	V ${}_{2}$	V ${}_{3}$	(50, 0, 0)	(50, 90, 52)	18	104	30	1872
e ${}_{3}$	V ${}_{3}$	V ${}_{4}$	(50, 90, 52)	(80, 90, 52)	14	30	0	420
e ${}_{4}$	V ${}_{4}$	V ${}_{5}$	(80, 90, 52)	(220, 90, 52)	14	140	0	1960
e ${}_{5}$	V ${}_{4}$	V ${}_{6}$	(80, 90, 52)	(80, 149, 86)	18	68	30	1224
e ${}_{6}$	V ${}_{6}$	V ${}_{7}$	(80, 149, 86)	(220, 149, 86)	12	140	0	1680
e ${}_{7}$	V ${}_{6}$	V ${}_{8}$	(80, 149, 86)	(0, 149, 86)	12	80	0	960
e ${}_{8}$	V ${}_{1}$	V ${}_{8}$	(0, 0, 0)	(0, 149, 86)	18	172	30	3096
e ${}_{9}$	V ${}_{3}$	V ${}_{16}$	(50, 0, 0)	(50, 360, 208)	18	312	30	5616
e ${}_{10}$	V ${}_{16}$	V ${}_{9}$	(50, 360, 208)	( $-$ 20, 360, 208)	14	70	0	980
e ${}_{11}$	V ${}_{9}$	V ${}_{10}$	( $-$ 20, 360, 208)	( $-$ 40, 390, 225)	18	40	30	720
e ${}_{12}$	V ${}_{10}$	V ${}_{11}$	( $-$ 40, 390, 225)	( $-$ 230, 390, 225)	14	190	0	2660
e ${}_{13}$	V ${}_{10}$	V ${}_{14}$	( $-$ 40, 390, 225)	( $-$ 20, 390, 225)	14	20	0	280
e ${}_{14}$	V ${}_{14}$	V ${}_{15}$	( $-$ 20, 390, 225)	(0, 415, 240)	14	30	30	420
e ${}_{15}$	V ${}_{8}$	V ${}_{15}$	(0, 149, 86)	(0, 415, 240)	18	308	30	5544
e ${}_{16}$	V ${}_{16}$	V ${}_{17}$	(50, 360, 208)	(50, 407, 235)	18	54	30	972
e ${}_{17}$	V ${}_{17}$	V ${}_{21}$	(50, 407, 235)	(50, 520, 300)	18	130	30	2340
e ${}_{18}$	V ${}_{17}$	V ${}_{18}$	(50, 407, 235)	(280, 407, 235)	14	230	0	3220
e ${}_{19}$	V ${}_{18}$	V ${}_{19}$	(280, 407, 235)	(180, 454, 262)	24	114	30	2736
e ${}_{20}$	V ${}_{19}$	V ${}_{20}$	(180, 454, 262)	(0, 454, 262)	12	180	0	2160
e ${}_{21}$	V ${}_{11}$	V ${}_{12}$	( $-$ 230, 390, 225)	( $-$ 230, 407, 252)	14	34	30	476
e ${}_{22}$	V ${}_{12}$	V ${}_{13}$	( $-$ 230, 407, 252)	( $-$ 230, 436, 252)	24	54	0	1296
e ${}_{23}$	V ${}_{15}$	V ${}_{13}$	(0, 415, 240)	( $-$ 230, 436, 252)	18	24	30	432
e ${}_{24}$	V ${}_{13}$	V ${}_{20}$	( $-$ 230, 436, 252)	(0, 454, 262)	18	230	30	4140

Table 3

Passable weights of each roadway

Roadway	Starting node	End node	Weights /m	Roadway	Starting node	End node	Weights /m
branch				branch
e ${}_{1}$	V ${}_{1}$	V ${}_{2}$	50	e ${}_{13}$	V ${}_{10}$	V ${}_{14}$	20
e ${}_{2}$	V ${}_{2}$	V ${}_{3}$	197.6	e ${}_{14}$	V ${}_{14}$	V ${}_{15}$	57
e ${}_{3}$	V ${}_{3}$	V ${}_{4}$	30	e ${}_{15}$	V ${}_{8}$	V ${}_{15}$	585.2
e ${}_{4}$	V ${}_{4}$	V ${}_{5}$	140	e ${}_{16}$	V ${}_{16}$	V ${}_{17}$	102.6
e ${}_{5}$	V ${}_{4}$	V ${}_{6}$	129.2	e ${}_{17}$	V ${}_{17}$	V ${}_{21}$	247
e ${}_{6}$	V ${}_{6}$	V ${}_{7}$	140	e ${}_{18}$	V ${}_{17}$	V ${}_{18}$	230
e ${}_{7}$	V ${}_{6}$	V ${}_{8}$	80	e ${}_{19}$	V ${}_{18}$	V ${}_{19}$	216.6
e ${}_{8}$	V ${}_{1}$	V ${}_{8}$	326.8	e ${}_{20}$	V ${}_{19}$	V ${}_{20}$	180
e ${}_{9}$	V ${}_{3}$	V ${}_{16}$	592.8	e ${}_{21}$	V ${}_{11}$	V ${}_{12}$	64.6
e ${}_{10}$	V ${}_{16}$	V ${}_{9}$	70	e ${}_{22}$	V ${}_{12}$	V ${}_{13}$	54
e ${}_{11}$	V ${}_{9}$	V ${}_{10}$	76	e ${}_{23}$	V ${}_{15}$	V ${}_{13}$	45.6
e ${}_{12}$	V ${}_{10}$	V ${}_{11}$	190	e ${}_{24}$	V ${}_{13}$	V ${}_{20}$	437

Figure 4.

Mine roadway network generated by Matlab.

Table 4

The time required for the personnel passing through each roadway

Roadway branch	Starting node	End node	Time /s	Roadway branch	Starting node	End node	Time /s
e ${}_{1}$	V ${}_{1}$	V ${}_{2}$	38.5	e ${}_{13}$	V ${}_{10}$	V ${}_{14}$	15.4
e ${}_{2}$	V ${}_{2}$	V ${}_{3}$	152	e ${}_{14}$	V ${}_{14}$	V ${}_{15}$	43.8
e ${}_{3}$	V ${}_{3}$	V ${}_{4}$	23.1	e ${}_{15}$	V ${}_{8}$	V ${}_{15}$	450.2
e ${}_{4}$	V ${}_{4}$	V ${}_{5}$	107.7	e ${}_{16}$	V ${}_{16}$	V ${}_{17}$	78.9
e ${}_{5}$	V ${}_{4}$	V ${}_{6}$	99.4	e ${}_{17}$	V ${}_{17}$	V ${}_{21}$	190
e ${}_{6}$	V ${}_{6}$	V ${}_{7}$	107.7	e ${}_{18}$	V ${}_{17}$	V ${}_{18}$	176.9
e ${}_{7}$	V ${}_{6}$	V ${}_{8}$	61.5	e ${}_{19}$	V ${}_{18}$	V ${}_{19}$	166.6
e ${}_{8}$	V ${}_{1}$	V ${}_{8}$	251.4	e ${}_{20}$	V ${}_{19}$	V ${}_{20}$	138.5
e ${}_{9}$	V ${}_{3}$	V ${}_{16}$	456	e ${}_{21}$	V ${}_{11}$	V ${}_{12}$	49.7
e ${}_{10}$	V ${}_{16}$	V ${}_{9}$	53.8	e ${}_{22}$	V ${}_{12}$	V ${}_{13}$	41.5
e ${}_{11}$	V ${}_{9}$	V ${}_{10}$	58.5	e ${}_{23}$	V ${}_{15}$	V ${}_{13}$	35.1
e ${}_{12}$	V ${}_{10}$	V ${}_{11}$	146.2	e ${}_{24}$	V ${}_{13}$	V ${}_{20}$	336.2

Table 5

Spreading time of node to node in driftway

Roadway branch	Node	Node	Downward water spreading time /s	Water level rising time /s
e ${}_{1}$	V ${}_{1}$	V ${}_{2}$	68.5	153.6
e ${}_{3}$	V ${}_{3}$	V ${}_{4}$	41.1	71.7
e ${}_{4}$	V ${}_{4}$	V ${}_{5}$	191.8	334.5
e ${}_{6}$	V ${}_{6}$	V ${}_{7}$	191.8	286.7
e ${}_{7}$	V ${}_{6}$	V ${}_{8}$	109.6	163.8
e ${}_{10}$	V ${}_{16}$	V ${}_{9}$	95.9	167.2
e ${}_{12}$	V ${}_{10}$	V ${}_{11}$	260.3	453.9
e ${}_{13}$	V ${}_{10}$	V ${}_{14}$	27.4	47.8
e ${}_{18}$	V ${}_{17}$	V ${}_{18}$	315.1	549.5
e ${}_{20}$	V ${}_{19}$	V ${}_{20}$	246.6	368.6
e ${}_{22}$	V ${}_{12}$	V ${}_{13}$	74	221.2

According to the coordinates of roadway nodes in Table 2, the mine roadway network is generated by Matlab, as shown in Fig. 4. The weight of the line segment is the actual length between the nodes.

5.1 Calculate the traffic ability weights of roadway and the time for passing through the roadway

The traffic ability weight of each roadway are calculated by the Eqs (1), (2) and (4), as shown in Table 3.

According to the traffic ability weight of the roadway shown in Table 5, the time required for passing through each roadway is calculated according to the free walking speed of 1.3 m/s, as shown in Table 4.

5.2 Calculate the water spreading range, speed and time

Assume that node $V_{3}$ is the water bursting point, all the node paths of water bursting can be obtained through the analysis of the spreading path algorithm in Sections 2.1 and 2.2, as shown in Fig. 5.

Through the water level sensor placed in the mine roadway, it can be known that the time of water flowing to node $V_{6}$ is 10 min. Considering the solved water spreading path, after checking the water capacity information of the roadway in Table 2, the burst water amount when water flows to node $V_{6}$ can be calculated:

$Q=\frac{1872{\rm∼{}m}^{3}+420{\rm∼{}m}^{3}+1224{\rm∼{}m}^{3}}{600{\rm∼{}s}}=5.% 86{\rm∼{}m}^{3}/{\rm∼{}s}$

According to the amount of burst water in unit time 5.86 m ${}^{3}$ /s, and the roadway water capacity information in Table 2, using the Eq. (5) in Section 2.3 to calculate the flooding velocity, where $n$ is 0.02. Assuming water depth $h=$ 0.2 m, according to the formula $R=\frac{bh}{b+2h}$ ( $b$ is width of the bottom of the roadway) the hydraulic radius $R$ can be calculated; according to the formula $C=\frac{1}{n}R^{\frac{1}{6}}$ , $C$ can be calculated, in the lane $J=i$ ( $i$ is bottom slope of the open channel), let it to be 1/500, then the average flow velocity $v_{w}=$ 0.73 m/s. In the 30 ${}^{\circ}$ inclined roadway $i=\sin(30^{\circ})=0.5$ , then the average flow velocity $v_{d}=$ 7.4 m/s. Combine Eqs (7) and (8) the time of water spreading time from a node to the next node on the water spreading path can be calculated, as shown in Tables 5 and 6.

Table 6
Spreading time of node to node in oblique lane

Starting node	End node	Downward water spreading time /s	Starting node	End node	Water level rising time /s
V ${}_{3}$	V ${}_{2}$	14.1	V ${}_{2}$	V ${}_{3}$	319.5
V ${}_{6}$	V ${}_{4}$	9.2	V ${}_{4}$	V ${}_{6}$	208.9
V ${}_{8}$	V ${}_{1}$	23.2	V ${}_{1}$	V ${}_{8}$	528.3
V ${}_{16}$	V ${}_{3}$	42.2	V ${}_{3}$	V ${}_{16}$	958.4
V ${}_{10}$	V ${}_{9}$	5.4	V ${}_{9}$	V ${}_{10}$	122.9
V ${}_{15}$	V ${}_{14}$	4.1	V ${}_{14}$	V ${}_{15}$	71.7
V ${}_{15}$	V ${}_{8}$	41.6	V ${}_{8}$	V ${}_{15}$	946.1
V ${}_{17}$	V ${}_{16}$	7.3	V ${}_{16}$	V ${}_{17}$	165.9
V ${}_{21}$	V ${}_{17}$	17.6	V ${}_{17}$	V ${}_{21}$	399.3
V ${}_{19}$	V ${}_{18}$	15.4	V ${}_{18}$	V ${}_{19}$	466.9
V ${}_{12}$	V ${}_{11}$	4.6	V ${}_{11}$	V ${}_{12}$	81.2
V ${}_{13}$	V ${}_{15}$	3.2	V ${}_{15}$	V ${}_{13}$	73.7
V ${}_{20}$	V ${}_{13}$	31.1	V ${}_{13}$	V ${}_{20}$	706.5

Figure 5.

Nodes path of water bursting.

Figure 6.

The shortest escape path in the roadway network.

5.3 Calculate the shortest escape path and the time

Using Matlab to calculate the shortest escape path on the roadway according to Dijkstra algorithm, $V_{1}$ is the starting point of the escaping, and $V_{19}$ is the end point of escaping. According to the roadway traffic ability weights in Table 3, the shortest escape path $V_{1}\to V_{2}\to V_{3}\to V_{16}\to V_{17}\to V_{18}\to V_{19}$ can be obtained, as shown in Fig. 6. According to the time required for people passing through the roadway in Table 4, the time for passing through the escape path is 1069 s.

5.4 Get the optimal escape path

5.4.1 Calculate the spread of water in the escape time

According to the time of 1069 s that people in mine need to pass through the shortest escape path, considering the solved water spreading range and the relevant time, the water spreading path in 1069 s can be obtained as shown in Fig. 7.

Figure 7.

Water spreading path at time 1069 s.

5.4.2 Analysis of water spreading path and escape path

By comparison between the shortest escape path and the water spreading path, it can be known that the overlapped roadways are e1, e2, e9, then mark their traffic ability weights as infinity, and recalculate the shortest escape path and the escape time, result shows that the path is $V_{1}\to V_{8}\to V_{15}\to V_{13}\to V_{20}\to V_{19}$ , and the escape time is 1211 s. Then calculate the range of water within 1211 s, and compare it with the escape path to get the overlapping roadway e8, whose traffic ability weight is marked as infinity. Next, recalculate the shortest escape path. The shortest escape path cannot be obtained, then decompose and analyze all the shortest escape paths.

5.4.3 Analysis of escape path decomposition

1) 1)
Path $V_{1}\to V_{2}\to V_{3}\to V_{16}\to V_{17}\to V_{18}\to V_{19}$

Table 4 shows that the time for escaping from $V_{1}$ to $V_{2}$ is $t_{1}=$ 38.5 s. In the period of time $t_{1}$ , it can be known through calculating the water spreading range that at 14.1 s, the water has flowed down from $V_{3}$ to $V_{2}$ , and then rises from $V_{2}$ to $V_{1}$ in the horizontal roadway e1. At this time the escaping people are still in roadway e1, thus great potential risks exists in this escape path.
2)
Path $V_{1}\to V_{8}\to V_{15}\to V_{13}\to V_{20}\to V_{19}$

From Table 4 it can be seen that the time for the people to escape from $V_{1}$ to $V_{8}$ is $t_{2}=$ 251.4 s. In the period of time $t_{2}$ , through calculating the water spreading range it can be known that at 14.1 s, water has flowed down from $V_{3}$ to $V_{2}$ ; at time 167.6 s, water has filled roadway e1, then it starts to rise from $V_{2}$ to $V_{3}$ and from $V_{1}$ to $V_{8}$ at the same time. As 528.3 s is needed for water to rise from $V_{1}$ to $V_{8}$ and fill the roadway, the people in mine have fled to e15 roadway.

From Tables 4–3, the time for people to escape from $V_{8}$ to $V_{15}$ is $t_{3}=$ 450.2 s. At the time point $t_{2}+t_{3}=$ 701.6 s, water is rising in roadways e3 and e4. At this time the water level is the elevation of node $V_{3}$ , which won’t threaten the safety of escaping people.

Table 4 shows that the time for people to escape from $V_{15}$ to $V_{13}$ is $t_{4}=$ 35.1 s. At the time point $t_{2}+t_{3}+t_{4}=$ 736.7 s, water is rising in roadways e3 and e4. At this time the water level is the elevation of node $V_{3}$ , which won’t threaten the safety of escaping people.

Figure 8.
At the time 1211.4 s the roadway real-time situation map.

Table 4 shows that the time people to escape from $V_{13}$ to $V_{20}$ is $t_{5}=$ 336.2 s. At the time point $t_{2}+t_{3}+t_{4}+t_{5}=$ 1072.9 s, water is rising roadways e5 and e8. At this time the water level is the elevation of node $V_{6}$ , which won’t threaten the safety of escaping people.

Figure 9.
The shortest escape route in the roadway network.

Figure 10.
Water spreading path at time of 855.7 s.

Table 4 demonstrates that the time for people to escape from $V_{20}$ to $V_{19}$ is $t_{6}=$ 138.5 s. At the time point $t_{2}+t_{3}+t_{4}+t_{5}+t_{6}=$ 1211.4 s, the escaping people have fled to the safety point $V_{19}$ . At this time water is rising in roadways e6 and e7, and the water level is the elevation of node $V_{8}$ , which won’t threaten the safety of escaping people.

Through analysis, it can be known that although the shortest escape route $V_{1}\to V_{2}\to V_{3}\to V_{16}\to V_{17}\to V_{18}\to V_{19}$ is the global shortest path, the escaping people will meet the water flow during the escaping process, which is a dangerous factor. The shortest escape path in second calculation is needs longer time, butt in the escape process people don’t need to go through the submerged roadway, thus the path is safer. The path obtained at this time is the optimal escape path. The real-time situation on the roadway in the process of escape is shown in Fig. 8.
5.5 Case II

Set node $V_{18}$ to be water bursting point, $V_{5}$ to be escape starting point, and $V_{21}$ to be safety point.

5.5.1 Calculate the shortest escape path and time

According to the Dijkstra algorithm, the shortest escape path in the roadway is calculated using Matlab, and according to the roadway traffic ability weights Table 3, the shortest escape path is: $V_{5}\to V_{4}\to V_{3}\to V_{16}\to V_{17}\to V_{21}$ , as shown in Fig. 9. According to the time needed to pass through the roadway in Table 4, the time for people to pass through the escape path is 855.7 s.

Table 7
The height of the waterway in the roadway corresponds to the speed of the person

Walking environment (water level $x$ )	Walking speed (m/s)
Water level of the knee ( $x<$ 55 cm)	0.7
Water level of the waist (55 cm $<x<$ 101 cm)	0.3
Water level of the chest ( $x>$ 101 cm)	0

5.5.2 Obtain the optimal escape path

Step 3 Step 1
Calculate the range of water in the escape time

According to the time of 855.7 s for the people in mine to pass through the shortest escape path, considering the solved water spreading range and water spreading time, it can be concluded that in 855.7 s, the water spreading path is as Fig. 10 shows.
Step 2
Analysis of water spreading path and escape path

Compare the shortest escape path with the water spreading path to get the overlapping roadways e1, e2, e9 and e16, then mark their traffic ability weights as infinity, and recalculate the shortest escape path and the escape time to get the result that the path is: $V_{5}\to V_{4}\to V_{6}\to V_{8}\to V_{15}\to V_{13}\to V_{20}\to V_{19}\to V_% {18}\to V_{17}\to V_{21}$ , and the escape time is 1762.1 s. Then calculate the water spreading range in 1762.1 s again and compare it with the escape route to obtain the overlapping roadways e4, e5 and e18. Mark their traffic ability weights as infinity, and recalculate the shortest escape path, The shortest escape path can not be obtained, so decompose and analyses all the shortest escape paths.
Step 3
Analysis of escape path decomposition

1) 1)
Path $V_{5}\to V_{4}\to V_{3}\to V_{16}\to V_{17}\to V_{21}$

Figure 11.
The real time situation of roadway at time 1314.2 s.

From Table 4, the time for people to escape from $V_{5}$ to $V_{16}$ is $t_{1}=$ 586.8 s. In the period of time $t_{1}$ , it can be known through water spreading range calculation that water has flowed down from $V_{16}$ to $V_{3}$ at the time point 364.6 s, at this time the escaping people are still in roadway e9, thus this path is potentially dangerous.
2)
Path $V_{5}\to V_{4}\to V_{6}\to V_{8}\to V_{15}\to V_{13}\to V_{20}\to V_{19}\to V_% {18}\to V_{17}\to V_{21}$

From Table 4, the time needed to escape from $V_{5}$ to $V_{17}$ is $t_{2}=$ 1572.1 s. By calculating water spreading range, it’s known that in the period of time $t_{2}$ , water flows through roadway e18, thus the path is potentially dangerous. Next recalculation of path traffic ability weight is needed to get the least time-consuming path.

Step 4
Accessibility analysis of escape route

Because the roadways of the two paths which overlaps the water spreading path are not filled with water, both paths are passable. Assuming that the water level in inclined roadway and that in horizontal roadway are lower than 55 cm, referring to Table 7 it can be known that people’s moving speed through water is 0.7 m/s. For the path $V_{5}\to V_{4}\to V_{3}\to V_{16}\to V_{17}\to V_{21}$ , recalculate the escape time and get $T=(107.7+23.1+\frac{592.8}{0.7}+\frac{102.6}{0.7}+190)\text{ s}=1314.2\text{∼{% }s}$ , for the path $V_{5}\to V_{4}\to V_{6}\to V_{8}\to V_{15}\to V_{13}\to V_{20}\to V_{19}\to V_% {18}\to V_{17}\to V_{21}$ , r recalculate the escape time and get $T^{\prime}=(107.7+99.4+61.5+450.2+35.1+336.2+138.5+166.6+\frac{230}{0.7}+190)% \text{∼{}s}=1913.8\text{∼{}s}$ , Time $T$ is shorter, so the path $V_{5}\to V_{4}\to V_{3}\to V_{16}\to V_{17}\to V_{21}$ is the optimal escape path. The real-time situation of the roadway in the escape process is shown in Fig. 11.

6. Summary

This paper gave the calculation of roadway weights for first, which lays the foundation for solving the shortest escape route for evacuation in mine. Then, downward water spreading path and water level rising path were solved, in addition, water spreading speed and time were calculated, which laid a foundation for solving the optimal escape rout. finally, the optimal escape route was solved.

The shortest path of the first solution in Case 1 is not the optimal path because on this path the escaping people will pass through flooded roadway. The relative shortest path of the second solution is the optimal path. Although the path weight is relatively large, the safety of the escaping people is ensured. In Case 2, the people in mine must pass through the path flooded by water. In this case, it is necessary to judge the traffic ability of the roadway with water flow and recalculate the time that people passing through each path in accordance with people moving speed through water. Finally the path which need the shortest time is the optimal path.

According to the actual situation of coal mine, the optimal path generated by the algorithm can minimize the injuries and death caused by water bursting, and make the rescue in mine water bursting disaster more successful.

Footnotes

Acknowledgments

This work is financially supported by Yulin City Science and Technology Project No. Cxy12-2-07 and Natural Science Foundation of Shaanxi Provincial under Grant No. 2016JM6031.

References

Zhang

, Research on Three-dimensional Visual Emergency Emergency Rescue Information System for Mine Water Bursting, Central South University, 2012.

Fábio

Maria

T.L.

and JoséL

, The shortest path problem on networks with fuzzy parameters, Fuzzy Sets and Systems 158(14) (2007), 1561–1570.

, Study on the Best Disaster Relief Path in Mine Catastrophe Period, Shanxi: Taiyuan University of Technology, 2013.

Cao

Peng

and Lin

, Determination of the best escape route, Journal of Liaoning Technical University (Natural Science Edition) 1 (1999), 27–29.

Wang

and Cui

, Study on the accessibility and selection of the best disaster relief and evacuation route in mine fire, Journal of Coal Science 1 (1994), 58–64.

Wang

and Wu

, Improvement of Dijkstra algorithm for optimal disaster avoidance route in mine emergency rescue, Industrial Automation 5 (2008), 13–15.

Sifaleras

, Minimum cost network flows: Problems, algorithms, and software, Yugoslav Journal of Operations Research 23(1) (2013), 3–17.

Marinakis

Migdalas

and Sifaleras

, Hybrid particle swarm optimization – variable neighborhood search algorithm for constrained shortest path problems, European Journal of Operational Research 261(3) (2017), 819–834.

, The real-time shortest path algorithm with a consideration of traffic light, Journal of Intelligent & Fuzzy Systems 31 (2016), 2403–2410.

10.

Roth

, Efficient manyhtohmany path planning and the Traveling Salesman Problem on road networks, International Journal of Knowledge-Based and Intelligent Engineering Systems 20 (2016), 135–148.

11.

Yuan

and Wang

, Path selection model and algorithm for emergency logistics management, Computers & Industrial Engineering 56(3) (2009), 1081–1094.

12.

Zhang

Wei

and Deng

, Route selection for emergency logistics management: A bio-inspired algorithm, Safety Science 54 (2013), 87–91.

13.

Chen

and Kong

, Study on the optimal path of mine fire disaster avoidance and disaster relief, Industrial Safety and Environmental Protection 11 (2010), 40–42.

14.

Cheng

Zhang

and Li

, Study on the application of optimal path of K in mine water hazards, Metal Mine 1 (2014), 137–140.

15.

, Optimization of Dijkstra algorithm in shortest path analysis of GIS, Computer and Digital Engineering 12 (2006), 53–56.

16.

Zheng

Hou

and Zhou

, Three-Dimensional Dynamic Simulation Model of Underground Mine Water Bursting Process, Journal of University of Science and Technology Beijing 2 (2013), 140–147.

17.

and Liu

, Application of mine water bursting path search algorithm, Science and Technology of Safety Production in China 11 (2015), 35–40.

Research on the optimal escape path algorithm in mine water bursting disaster

Abstract

Keywords

1. Introduction

2.1 Equivalent length of roadway

Table 1 Roadway traffic ability weight

3. Calculation of spreading range of water bursting

3.1 Calculation of downward water spreading path

3.3 Calculation of water spreading speed and time

3.3.1 Downward water spreading speed and time

Table 2 Information table of mine roadway

5.2 Calculate the water spreading range, speed and time

Table 6 Spreading time of node to node in oblique lane

5.4 Get the optimal escape path

5.4.1 Calculate the spread of water in the escape time

5.4.3 Analysis of escape path decomposition

5.5.1 Calculate the shortest escape path and time

Table 7 The height of the waterway in the roadway corresponds to the speed of the person

Footnotes

Acknowledgments

References

Table 1
Roadway traffic ability weight

Table 2
Information table of mine roadway

Table 6
Spreading time of node to node in oblique lane

Table 7
The height of the waterway in the roadway corresponds to the speed of the person