# Escape-Route Planning of Underground Coal Mine Based on Improved Ant Algorithm

Authors: Guangwei Yan; Dandan Feng
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

When a mine disaster occurs, to lessen disaster losses and improve survival chances of the trapped miners, good escape routes need to be found and used. Based on the improved ant algorithm, we proposed a new escape-route planning method of underground mines. At first, six factors which influence escape difficulty are evaluated and a weight calculation model is built to form a weighted graph of the underground tunnels. Then an improved ant algorithm is designed and used to find good escape routes. We proposed a tunnel network zoning method to improve the searching efficiency of the ant algorithm. We use max-min ant system method to optimize the meeting strategy of ants and improve the performance of the ant algorithm. In addition, when a small part of the mine tunnel network changes, the system may fix the optimal routes and avoid starting a new processing procedure. Experiments show that the proposed method can find good escape routes efficiently and can be used in the escape-route planning of large and medium underground coal mines.


---

## Body

## 1. Introduction

In mining, water, fire, gas, and other natural disasters often occur. The disasters have a heavy effect to mines’ safety production. Statistics show the coal mine industry has the most serious casualty accidents in China [1]. From 1991 to 2001, 86000 people died in coal mine accident, accounts for 85% of deaths in the mining industry. According to statistics in 2006–2008, in high-risk industries of China, the proportion of coal mine accidents and deaths equal 21.3% and 28.5%, respectively, top the list of industrial and mining business enterprises [2].When mine disaster occurs, it is very important to find good escape routes. Escape routes planning can be realized based on computers, sensor networks, and relevant data. This problem had been studied at home and abroad, literature [3–7] use the Dijkstra algorithm or its improved algorithm to solve the problem. These algorithms are different in time complexity, space complexity, and so forth. The Dijkstra algorithm has three shortages. First, large amounts of calculation are required when number of network nodes and edges reaches several hundred, because these algorithms usually need to traverse all vertices of the network. Second, the Dijkstra algorithm only obtains the best route and in fact the second-best route is needed sometimes. Third, the Dijkstra algorithm is static, if mine states change, it needs to be recalculated.Put forward by Italian scholar Dorigo et al., the ant algorithm [8] is a new heuristic evolutionary algorithm. Biological ant colony can produce a chemical substance called pheromone for communication and coordination of ants. Pheromone can form positive feedback and make individual ants gradually gathered in the shortest route between the food source and the nest. The algorithm has advantages of strong robustness, distributed computing, positive feedback mechanism and it is easy to combine with other algorithms. When solving the shortest route in large-scale network, it has excellent feasibility and adaptability.In this paper, factors which influence passing difficulty in tunnels are led into. Based on these factors and the actual lengths of the tunnels, equivalent lengths of the tunnels are calculated and acted as weights of the underground tunnel graph. This graph acts as the input of the improved ant algorithm.In this paper, an important improvement to the ant algorithm is introducing tunnel zoning. Underground mine networks include many faces and main tunnels. This paper divides all mine zones into two types: the backbone-zoneS0 and the nonbackbone-zone Sn(n=1,2,3…). The backbone-zone S0 is the main searching area, containing backbone tunnels and the safety point. The nonbackbone-zone Sn containing several zones, each face is a nonbackbone-zone. They connect to the main road (See Figure 2). By zoning the weighted graph of tunnels, the ants’ behaviors can be affected and the searching efficiency can be improved.The experimental results in this paper show the improved algorithm are suitable for escape routes planning of large and medium sized mines.


## 2. System Framework

To calculate the optimal escape routes in underground mines, tunnels’ status and data should be provided. And these can be obtained by sensor network in tunnels. In different mine disasters, factors that influence men passing difficulty of the tunnel are various and complex. Based on methods proposed by literature [9, 10], these factors are generalized for six classes including tunnel type, wind speed, tunnel slope, particle concentrations, crowded degree, and special factors related with mine disaster. Firstly, these factors are converted to tunnel equivalent length according to the formula (1). Secondly, a graph denoted by G(V,E) is built based on the tunnel network topology and the normalized tunnel equivalent lengths which act as the graph weights. Thirdly, a group of underground workers is set as node V0 and a safety point or exit point is set as Ve in G. Finally, improved ant algorithm is used to plan the optimal route and several alternative routes between the terminals (V0,Ve) in G. The system implementation framework is shown in Figure 1.Figure 1
System Framework.Figure 2
The network topology of the mine.


## 3. Calculation of Tunnel Weights

### 3.1. Calculation of Tunnel Equivalent Length

Status of underground tunnels are various and complex. Factors influencing passing difficulty of tunnels are generalized for six classes including tunnel type, wind speed, tunnel slope, particle concentrations, crowded degree, and special factors related to mine disasters. These factors influence people’s escape speed and they can increase or decrease the escape speedv. The influences of these factors to the escape speed v are transformed to the tunnels’ equivalent length. The smaller the value of the speed v is, the longer the tunnel equivalent length is and vice versa. Formula (1) gives the calculation method of the tunnel equivalent lengths. And these equivalent lengths are as weights of the graph G after normalizing:
(1)li=(kti·kwi·kgi·kvi·kmi·kdi)lri.In (1), lri indicates the actual length of the tunnel i and li is the equivalent length of the tunnel i;kti,kwi,kgi,kvi,kmi,kdi are tunnel type influence coefficient, tunnel wind speed influence coefficient, tunnel slope influence coefficient, tunnel particle concentrations influence coefficient, tunnel crowded degree influence coefficient, special factors related to mine disasters influence coefficient of the tunnel i, respectively. Below we explain the relationship of these coefficients and the escape speed v.We denote the people’s normal walking speed byv0. Under the influence of the tunnel type coefficient, the people escape speed v equals to v0/kti. These six coefficients are independent, and under their common influence, the escape speed v equals to v0/(kti·kwi·kgi·kvi·kmi·kdi). Through formula (1), we can know the escape time t (which equals to lri/v) also equals to li/v0. Below we will explain in detail how these coefficients are calculated and how they influence the escape speed v separately.


#### 3.1.1. Tunnel Type Influence Coefficient

Underground tunnels can generally be divided into working surface, transport tape lane, contact lane, rail lane, shaft, air leakage branch, and ventilation borehole, in which the air leakage branch and the ventilation borehole are forbidden for people to pass. Tunnel type may influence the people’s escape speed. For example, in the rail lane, the passing speed is equal to the speed of transportation tool. Formula (2) gives the calculating method of the tunnel type influence coefficient.
(2)kti={v0vvehicle,tunneliistheraillanetype,+∞,tunneliistheairleakagebranchortheventilationboreholetype,1,othertunneltype.The parametervvehicle represents the speed of the transformation tool. People’s moving speed equals to the speed of the vehicle when people are in the vehicle. When the value of vvehicle is greater than the value of v0, the value of kti is smaller than 1. And this indicates the equivalent length of the tunnel i will decrease according to the formula (1) and the people will spend less time to pass through the tunnel.


#### 3.1.2. Wind Speed Influence Coefficient

The mine networks is a thorough ventilation system itself. Generally in the total return lanes the wind speed is big. The wind speed may influence people’s escape speed.It influence degree is in direct ratio with the actual roadway length. We assume the human’s walking power is constant and denote it byP0, and only taking stable states into account, we can derive the formula under against wind situation as follows:
(3)P0=Fv0=(F+Fw)v,
where F is the power of the humanand v0 is the normal human walking speed without any outside influence. And Fw is the power of wind and v is the human’s speed after affected by wind.Assume the person is a cuboid object, andFw can be derived from the Bernoulli’s equation [11]:
(4)Fw=cdρSvw22.The parametercd is a resistance coefficient, experience shows that it is related to the Reynolds number; ρ is the density of the gas; S is the touching surface area between the human body and the wind; vw is the wind speed in the current roadway.This paper concludes (5) from (3) and (4):
(5)v=2v0P02P0+cdρSv0vw2.The wind speed influence coefficient under against wind situation is shown as(6)kwi=lilri=v0v=2P0+cdρSv0vw22P0.Similarly, the coefficient under following wind situation is shown as follows:(7)kwi=2P0-cdρSv0vw22P0.Formula (7) has a limitation: when the wind speed is too big, this formula is not applicable.


#### 3.1.3. Tunnel Slope Influence Coefficient

Tunnel gradient influences the peoples’ walking speed. The greater the slope is, the greater the resistance is. With the same analysis method as Section3.1.2, we get the formula as follows under climbing situation:
(8)P0=Fv0=mgvsinθi+Fvcosθi,
where m is the standard human mass, g is the gravity acceleration, θi is the current tunnel’s angle of slope. The tunnel upslope influence coefficient can be represented as follows:
(9)kgi=v0v=mgv0sinθiP0+cosθi.When workers pass down slope tunnels, we assume their speed will still bev0 (i.e., kgi=1).The parameter values in Sections3.1.2 and 3.1.3 are shown in Table 1.Table 1
Parameters’ values.
Parameter name
Value
ρ
1.2 (kg/m3)
S
0.7225 (m2)
c
d
0.8
P
0
200 (w)
m
80 (kg)
v
0
5 (m/s)


#### 3.1.4. Tunnel Particle Concentrations Influence Coefficient

Tunnel particle concentrations mainly include tunnel visibility, the height between the gas critical layer and the floor. They have important effects on the walking speed of people who are escaping [12]. This coefficient is denoted by kvi, and its calculation method is
(10)kvi=(1+αh+Lr).In (10), αh is the effecting coefficient of the height of gas layer and its empirical value is shown in Table 2 [12]; Lr is the affecting coefficient of visibility; its empirical value is shown in Table 3.Table 2
Value of parameterαh.
Height of gas layer (m)
Coefficientαh
Height of gas layer (m)
Coefficientαh
>6
0
1.6–1.8
2
4–6
0.1
1.4–1.6
5
2–4
0.5
1–1.4
10
1.8–2
1
<1
100Table 3
Value of parameterLr.
Visibility distance (m)
CoefficientLr
>20
1
10–20
1.25
5–10
2.95
3–5
6.25
<3
12.5


#### 3.1.5. Tunnel Crowded Degree

The denseness of the crowd affects the walking speed to some extent. Thompson proposed a speed calculation method which utilized the crowd denseness factor in Simulex model [13]. This method can be expressed as a coefficient calculation formula as follows:
(11)kmi={1sin{90°×((d-b)/(td-b))},b<d<td,1,d≥td.In (11), d represents the body interval between people, here the body interval means the distance from one person’s body center to another person’s body center (we assume the people have the same height); td represents the upper limit of the moving constraint interval; b represents the size of the body in horizontal direction.


#### 3.1.6. Special Factors Related to Mine Disaster Influence Coefficient

In order to create a simple and unified mathematical model for various tunnel disasters, we consider special factors related to mine disaster, which refers to the extreme cases of different tunnel disasters, denoted bykdi. Its value is in {1,+∞}, and 1 indicates that this tunnel is normal and there is not exist mine disaster’s influence, and +∞ means this tunnel cannot be passed. There are a lot of factors which can cause the tunnel cannot be passed, for example:(1)
there is serious landslide in the tunnel and people cannot go through it.(2)
There exists high temperature (or large amount of smoke, toxic gas) in the tunnel, people cannot bear it.(3)
There is flood in the tunnel and the water height is more than people’s bear limitation.


### 3.2. The Normalization of Tunnel Weights

According to the above calculation model, the tunnel equivalent length’s range is(0,+∞], in which +∞ indicates that the tunnel cannot be got through. For the convenience of data processing, the data is mapped to range (0,1]. The linear mapping is used as follows:
(12)wi=0.1+(li-min(l))(max(l)-min(l))*(0.9-0.1).In whichmin(l) refers to the minimum equivalent length of all tunnels’, max(l) is the maximum equivalent length of all tunnels’ (except for the length value +∞). This function means the closer to 0 the values after mapping is, and the easier to pass through it. When the value is 1, it means the tunnel cannot be passed.Based on calculated weights and the tunnel topology graphG(V,E), the following improved ant algorithm can do a good route planning processing.


## 3.1. Calculation of Tunnel Equivalent Length

Status of underground tunnels are various and complex. Factors influencing passing difficulty of tunnels are generalized for six classes including tunnel type, wind speed, tunnel slope, particle concentrations, crowded degree, and special factors related to mine disasters. These factors influence people’s escape speed and they can increase or decrease the escape speedv. The influences of these factors to the escape speed v are transformed to the tunnels’ equivalent length. The smaller the value of the speed v is, the longer the tunnel equivalent length is and vice versa. Formula (1) gives the calculation method of the tunnel equivalent lengths. And these equivalent lengths are as weights of the graph G after normalizing:
(1)li=(kti·kwi·kgi·kvi·kmi·kdi)lri.In (1), lri indicates the actual length of the tunnel i and li is the equivalent length of the tunnel i;kti,kwi,kgi,kvi,kmi,kdi are tunnel type influence coefficient, tunnel wind speed influence coefficient, tunnel slope influence coefficient, tunnel particle concentrations influence coefficient, tunnel crowded degree influence coefficient, special factors related to mine disasters influence coefficient of the tunnel i, respectively. Below we explain the relationship of these coefficients and the escape speed v.We denote the people’s normal walking speed byv0. Under the influence of the tunnel type coefficient, the people escape speed v equals to v0/kti. These six coefficients are independent, and under their common influence, the escape speed v equals to v0/(kti·kwi·kgi·kvi·kmi·kdi). Through formula (1), we can know the escape time t (which equals to lri/v) also equals to li/v0. Below we will explain in detail how these coefficients are calculated and how they influence the escape speed v separately.


### 3.1.1. Tunnel Type Influence Coefficient

Underground tunnels can generally be divided into working surface, transport tape lane, contact lane, rail lane, shaft, air leakage branch, and ventilation borehole, in which the air leakage branch and the ventilation borehole are forbidden for people to pass. Tunnel type may influence the people’s escape speed. For example, in the rail lane, the passing speed is equal to the speed of transportation tool. Formula (2) gives the calculating method of the tunnel type influence coefficient.
(2)kti={v0vvehicle,tunneliistheraillanetype,+∞,tunneliistheairleakagebranchortheventilationboreholetype,1,othertunneltype.The parametervvehicle represents the speed of the transformation tool. People’s moving speed equals to the speed of the vehicle when people are in the vehicle. When the value of vvehicle is greater than the value of v0, the value of kti is smaller than 1. And this indicates the equivalent length of the tunnel i will decrease according to the formula (1) and the people will spend less time to pass through the tunnel.


### 3.1.2. Wind Speed Influence Coefficient

The mine networks is a thorough ventilation system itself. Generally in the total return lanes the wind speed is big. The wind speed may influence people’s escape speed.It influence degree is in direct ratio with the actual roadway length. We assume the human’s walking power is constant and denote it byP0, and only taking stable states into account, we can derive the formula under against wind situation as follows:
(3)P0=Fv0=(F+Fw)v,
where F is the power of the humanand v0 is the normal human walking speed without any outside influence. And Fw is the power of wind and v is the human’s speed after affected by wind.Assume the person is a cuboid object, andFw can be derived from the Bernoulli’s equation [11]:
(4)Fw=cdρSvw22.The parametercd is a resistance coefficient, experience shows that it is related to the Reynolds number; ρ is the density of the gas; S is the touching surface area between the human body and the wind; vw is the wind speed in the current roadway.This paper concludes (5) from (3) and (4):
(5)v=2v0P02P0+cdρSv0vw2.The wind speed influence coefficient under against wind situation is shown as(6)kwi=lilri=v0v=2P0+cdρSv0vw22P0.Similarly, the coefficient under following wind situation is shown as follows:(7)kwi=2P0-cdρSv0vw22P0.Formula (7) has a limitation: when the wind speed is too big, this formula is not applicable.


### 3.1.3. Tunnel Slope Influence Coefficient

Tunnel gradient influences the peoples’ walking speed. The greater the slope is, the greater the resistance is. With the same analysis method as Section3.1.2, we get the formula as follows under climbing situation:
(8)P0=Fv0=mgvsinθi+Fvcosθi,
where m is the standard human mass, g is the gravity acceleration, θi is the current tunnel’s angle of slope. The tunnel upslope influence coefficient can be represented as follows:
(9)kgi=v0v=mgv0sinθiP0+cosθi.When workers pass down slope tunnels, we assume their speed will still bev0 (i.e., kgi=1).The parameter values in Sections3.1.2 and 3.1.3 are shown in Table 1.Table 1
Parameters’ values.
Parameter name
Value
ρ
1.2 (kg/m3)
S
0.7225 (m2)
c
d
0.8
P
0
200 (w)
m
80 (kg)
v
0
5 (m/s)


### 3.1.4. Tunnel Particle Concentrations Influence Coefficient

Tunnel particle concentrations mainly include tunnel visibility, the height between the gas critical layer and the floor. They have important effects on the walking speed of people who are escaping [12]. This coefficient is denoted by kvi, and its calculation method is
(10)kvi=(1+αh+Lr).In (10), αh is the effecting coefficient of the height of gas layer and its empirical value is shown in Table 2 [12]; Lr is the affecting coefficient of visibility; its empirical value is shown in Table 3.Table 2
Value of parameterαh.
Height of gas layer (m)
Coefficientαh
Height of gas layer (m)
Coefficientαh
>6
0
1.6–1.8
2
4–6
0.1
1.4–1.6
5
2–4
0.5
1–1.4
10
1.8–2
1
<1
100Table 3
Value of parameterLr.
Visibility distance (m)
CoefficientLr
>20
1
10–20
1.25
5–10
2.95
3–5
6.25
<3
12.5


### 3.1.5. Tunnel Crowded Degree

The denseness of the crowd affects the walking speed to some extent. Thompson proposed a speed calculation method which utilized the crowd denseness factor in Simulex model [13]. This method can be expressed as a coefficient calculation formula as follows:
(11)kmi={1sin{90°×((d-b)/(td-b))},b<d<td,1,d≥td.In (11), d represents the body interval between people, here the body interval means the distance from one person’s body center to another person’s body center (we assume the people have the same height); td represents the upper limit of the moving constraint interval; b represents the size of the body in horizontal direction.


### 3.1.6. Special Factors Related to Mine Disaster Influence Coefficient

In order to create a simple and unified mathematical model for various tunnel disasters, we consider special factors related to mine disaster, which refers to the extreme cases of different tunnel disasters, denoted bykdi. Its value is in {1,+∞}, and 1 indicates that this tunnel is normal and there is not exist mine disaster’s influence, and +∞ means this tunnel cannot be passed. There are a lot of factors which can cause the tunnel cannot be passed, for example:(1)
there is serious landslide in the tunnel and people cannot go through it.(2)
There exists high temperature (or large amount of smoke, toxic gas) in the tunnel, people cannot bear it.(3)
There is flood in the tunnel and the water height is more than people’s bear limitation.


## 3.1.1. Tunnel Type Influence Coefficient

Underground tunnels can generally be divided into working surface, transport tape lane, contact lane, rail lane, shaft, air leakage branch, and ventilation borehole, in which the air leakage branch and the ventilation borehole are forbidden for people to pass. Tunnel type may influence the people’s escape speed. For example, in the rail lane, the passing speed is equal to the speed of transportation tool. Formula (2) gives the calculating method of the tunnel type influence coefficient.
(2)kti={v0vvehicle,tunneliistheraillanetype,+∞,tunneliistheairleakagebranchortheventilationboreholetype,1,othertunneltype.The parametervvehicle represents the speed of the transformation tool. People’s moving speed equals to the speed of the vehicle when people are in the vehicle. When the value of vvehicle is greater than the value of v0, the value of kti is smaller than 1. And this indicates the equivalent length of the tunnel i will decrease according to the formula (1) and the people will spend less time to pass through the tunnel.


## 3.1.2. Wind Speed Influence Coefficient

The mine networks is a thorough ventilation system itself. Generally in the total return lanes the wind speed is big. The wind speed may influence people’s escape speed.It influence degree is in direct ratio with the actual roadway length. We assume the human’s walking power is constant and denote it byP0, and only taking stable states into account, we can derive the formula under against wind situation as follows:
(3)P0=Fv0=(F+Fw)v,
where F is the power of the humanand v0 is the normal human walking speed without any outside influence. And Fw is the power of wind and v is the human’s speed after affected by wind.Assume the person is a cuboid object, andFw can be derived from the Bernoulli’s equation [11]:
(4)Fw=cdρSvw22.The parametercd is a resistance coefficient, experience shows that it is related to the Reynolds number; ρ is the density of the gas; S is the touching surface area between the human body and the wind; vw is the wind speed in the current roadway.This paper concludes (5) from (3) and (4):
(5)v=2v0P02P0+cdρSv0vw2.The wind speed influence coefficient under against wind situation is shown as(6)kwi=lilri=v0v=2P0+cdρSv0vw22P0.Similarly, the coefficient under following wind situation is shown as follows:(7)kwi=2P0-cdρSv0vw22P0.Formula (7) has a limitation: when the wind speed is too big, this formula is not applicable.


## 3.1.3. Tunnel Slope Influence Coefficient

Tunnel gradient influences the peoples’ walking speed. The greater the slope is, the greater the resistance is. With the same analysis method as Section3.1.2, we get the formula as follows under climbing situation:
(8)P0=Fv0=mgvsinθi+Fvcosθi,
where m is the standard human mass, g is the gravity acceleration, θi is the current tunnel’s angle of slope. The tunnel upslope influence coefficient can be represented as follows:
(9)kgi=v0v=mgv0sinθiP0+cosθi.When workers pass down slope tunnels, we assume their speed will still bev0 (i.e., kgi=1).The parameter values in Sections3.1.2 and 3.1.3 are shown in Table 1.Table 1
Parameters’ values.
Parameter name
Value
ρ
1.2 (kg/m3)
S
0.7225 (m2)
c
d
0.8
P
0
200 (w)
m
80 (kg)
v
0
5 (m/s)


## 3.1.4. Tunnel Particle Concentrations Influence Coefficient

Tunnel particle concentrations mainly include tunnel visibility, the height between the gas critical layer and the floor. They have important effects on the walking speed of people who are escaping [12]. This coefficient is denoted by kvi, and its calculation method is
(10)kvi=(1+αh+Lr).In (10), αh is the effecting coefficient of the height of gas layer and its empirical value is shown in Table 2 [12]; Lr is the affecting coefficient of visibility; its empirical value is shown in Table 3.Table 2
Value of parameterαh.
Height of gas layer (m)
Coefficientαh
Height of gas layer (m)
Coefficientαh
>6
0
1.6–1.8
2
4–6
0.1
1.4–1.6
5
2–4
0.5
1–1.4
10
1.8–2
1
<1
100Table 3
Value of parameterLr.
Visibility distance (m)
CoefficientLr
>20
1
10–20
1.25
5–10
2.95
3–5
6.25
<3
12.5


## 3.1.5. Tunnel Crowded Degree

The denseness of the crowd affects the walking speed to some extent. Thompson proposed a speed calculation method which utilized the crowd denseness factor in Simulex model [13]. This method can be expressed as a coefficient calculation formula as follows:
(11)kmi={1sin{90°×((d-b)/(td-b))},b<d<td,1,d≥td.In (11), d represents the body interval between people, here the body interval means the distance from one person’s body center to another person’s body center (we assume the people have the same height); td represents the upper limit of the moving constraint interval; b represents the size of the body in horizontal direction.


## 3.1.6. Special Factors Related to Mine Disaster Influence Coefficient

In order to create a simple and unified mathematical model for various tunnel disasters, we consider special factors related to mine disaster, which refers to the extreme cases of different tunnel disasters, denoted bykdi. Its value is in {1,+∞}, and 1 indicates that this tunnel is normal and there is not exist mine disaster’s influence, and +∞ means this tunnel cannot be passed. There are a lot of factors which can cause the tunnel cannot be passed, for example:(1)
there is serious landslide in the tunnel and people cannot go through it.(2)
There exists high temperature (or large amount of smoke, toxic gas) in the tunnel, people cannot bear it.(3)
There is flood in the tunnel and the water height is more than people’s bear limitation.


## 3.2. The Normalization of Tunnel Weights

According to the above calculation model, the tunnel equivalent length’s range is(0,+∞], in which +∞ indicates that the tunnel cannot be got through. For the convenience of data processing, the data is mapped to range (0,1]. The linear mapping is used as follows:
(12)wi=0.1+(li-min(l))(max(l)-min(l))*(0.9-0.1).In whichmin(l) refers to the minimum equivalent length of all tunnels’, max(l) is the maximum equivalent length of all tunnels’ (except for the length value +∞). This function means the closer to 0 the values after mapping is, and the easier to pass through it. When the value is 1, it means the tunnel cannot be passed.Based on calculated weights and the tunnel topology graphG(V,E), the following improved ant algorithm can do a good route planning processing.


## 4. Searching the Optimal Escape Routes with Improved Ant Algorithm

This paper presents an improved ant algorithm which can quickly and effectively find the best route and several sub optimal routes fromVo (the trapped personnel position) to Ve (the safety point) in the tunnel network. There are two improvements to the ant algorithm: firstly, tunnel zoning characteristics are used to influence the ants’ behaviors and improve the searching efficiency of ants; secondly, the strategy of meeting of ants and the ant death rules are modified to improve the ant algorithm’s performance.


### 4.1. Calculation Steps of the Improved Ant Algorithm

Basic steps of the improved ant algorithm are as follows.Step 1.
Based on the above tunnel weights calculation model, weighted graphG is built. The trapped personnel position is denoted by Vo and the exit point (safety point) is denoted by Ve in graph G. The zoning attribute information is loaded.Step 2.
Initializes the ant algorithm’s parameters includingα, β, iter, Cmax, the pheromone trail matrix and the ant routes record table, and so forth; assigns the zoning number to each node according to the zoning attribute information acquired; arranges the ants’ position with the distribution requirements of Section 4.2.Step 3.
In the graphG, every ant is constructed an accessible node set in accordance with the moving rules in Section 4.2, and the tunnel zoning may influence the ants’ accessible node set. The ant selects the next node by formula (14), and puts the selected node into its route record. After every live ant has selected a node, the system will judge whether the ant is dead or not (based on the rules described in Section 4.3). The procedure is repeated until all ants are dead and by this manner an iteration step is finished. The whole ant algorithm calculating procedure requires Cmax times iteration.Step 4.
Updates the pheromone trail matrix and the parameterα, β in accordance with the update rules in Section 4.4. Records the optimal route and L alternative routes in this iteration, and denotes it by OPij (i is the number of current iteration; j=0,1,2,…,L; j=0 indicates the optimal route). According to the information of the current underground tunnels, weighted graph G′ is reconstructed. The change rate of ΔG is calculated according to the formula (19). If ΔG is less than a small constant δ, it changes optimal routes of all executed iterations if these routes contain changed tunnels. If ΔG is greater than δ, a new ant algorithm is restarted (go to Step 1).Step 5.
Initializes ant routes recording table; fixes and controls pheromone trail matrix by the MMAS method; updates parameteriter as (iter+1). If current iter’s value is less than Cmax, go to Step 2.Step 6.
From the records of the iterations’ routesOPij (i=1,2,…, Cmax, j=0,1,2,…,L), select the optimal route and L suboptimal routes for the current underground trapped workers.


### 4.2. Ants’ Distribution and Moving Rules

TheVo and Ve nodes of the graph G are set m ants separately. For the ant k, its current node i’s accessible nodes set is built as
(13)allowik=Ai-Bk-(1-p)Ck,p={0,1}.In (13), if the node i is in the backbone zone S0 or expected zone Se, p’s value is 1, else p’s value is 0. The set Ai is {nodes ∣the  node  which  connected  with  node  i}, and the set Bk is {nodes ∣the  node  that  the  ant  k  has  passed}, and the set Ck is {nodes ∣the  node  which  does  not  belong  to  zone  S0  and  zone  Se}. Through the use of the set Ck, unnecessary detour can be avoided and the searching efficiency can be improved.In accordance with the probability value calculated through (14), the ant k selects the next node in allowik. Formula (14) is described as follows:
(14)pijk={τijαwijβ∑s∈allowikτisαwisβ,j∈allowik,0,else.In (14), α,  β are factors of importance of the pheromone trail and the heuristic function respectively. And τij,  wij are pheromone trail concentration and weights respectively from the node i to the node j. The heuristic function is defined as weights between the current nodes.


### 4.3. The Rules of Meeting and Death of Ants

Every ant has attributes of a start node and an expected node. There are two improvements in meeting and death strategy showed in rule (2) and (4).These rules are as follows.(1)
If there is no way for the ant, the ant dies and is marked with no available route status.(2)
When two ants meet, if the expecting point of one ant and the start point of the other ant intersect, the ant having short route gives its route to another, and then the latter dies and is marked with an available route status. The former moves on.(3)
If the ant reaches the expected point, the ant dies and is marked with an available route status.(4)
Sets a physical power parameter to the trapped workers groupi and denotes it as PFi which will reduce gradually. The PFi parameters are assigned to ants. The ant will die when PFi of the ant is reduced to zero no matter what status the ant is in and then it is marked with no available route status.


### 4.4. Update of Pheromone Trail and Main Parameters

When one iteration processing is completed, the pheromone matrix and the parameterα and β need to be updated. To prevent premature problem, the MMAS method [10] is used in the pheromone updating procedure. After an iteration processing, only the pheromone of this iteration optimal route is updated, according to (15) and (16). In addition, in order to improve the convergence of the later iteration and the early intelligence, factors α and β are dynamically changed at a fixed length between two iterations. At the later stage, α acts as the major factor; at the early stage, β acts as the major factor. See (17) and (18):
(15)τij(t+1)=(1-ρ)τij(t)+Δτij(t),(16)Δτij={Q∑w,arc(i,j)inoptimalroute,0,arc(i,j)notinoptimalroute,(17)α(t+1)=α(t)+Δα,Δα=(αmax-αmin)cmax,(18)β(t+1)=β(t)-Δβ,Δβ=(βmax-βmin)cmax.Formula (15) gives the pheromone relationship between the iteration (t+1) and the iteration t, and ρ is the volatile factor of the pheromone, and Δτij is the incremental pheromone.Formula (16) is built based on MMAS strategy, only if the arc(i,j) is in the optimal route of the iteration, the pheromone of the arc(i,j) is updated. ∑w is the length of the current optimal route.In (17), αmax is the maximum ofα, and αmin is the minimum of α, cmax is the total iteration number. The meaning of formula (18) is similar to the meaning of formula (17).


### 4.5. Condition of the Algorithm Stopping

When one iteration calculation is completed, according to current information, underground tunnel diagramG′ is reconstructed, and the diagram’s change rate can be represented as
(19)ΔG(t)=|G′(t)-G|G.In (19), |G′(t)-G| indicates the changing number of arcs between G′ of iteration t and the original G, and G indicates the total number of arcs of the original diagram.WhenΔG is less than the small value δ, weights of the related arcs in the optimal routes of executed iterations are updated. Under this situation, the optimal length of executed iterations changes, but the order of passed node does not change. When ΔG is more than δ, current calculation is stopped and a new algorithm calculation is restarted.


## 4.1. Calculation Steps of the Improved Ant Algorithm

Basic steps of the improved ant algorithm are as follows.Step 1.
Based on the above tunnel weights calculation model, weighted graphG is built. The trapped personnel position is denoted by Vo and the exit point (safety point) is denoted by Ve in graph G. The zoning attribute information is loaded.Step 2.
Initializes the ant algorithm’s parameters includingα, β, iter, Cmax, the pheromone trail matrix and the ant routes record table, and so forth; assigns the zoning number to each node according to the zoning attribute information acquired; arranges the ants’ position with the distribution requirements of Section 4.2.Step 3.
In the graphG, every ant is constructed an accessible node set in accordance with the moving rules in Section 4.2, and the tunnel zoning may influence the ants’ accessible node set. The ant selects the next node by formula (14), and puts the selected node into its route record. After every live ant has selected a node, the system will judge whether the ant is dead or not (based on the rules described in Section 4.3). The procedure is repeated until all ants are dead and by this manner an iteration step is finished. The whole ant algorithm calculating procedure requires Cmax times iteration.Step 4.
Updates the pheromone trail matrix and the parameterα, β in accordance with the update rules in Section 4.4. Records the optimal route and L alternative routes in this iteration, and denotes it by OPij (i is the number of current iteration; j=0,1,2,…,L; j=0 indicates the optimal route). According to the information of the current underground tunnels, weighted graph G′ is reconstructed. The change rate of ΔG is calculated according to the formula (19). If ΔG is less than a small constant δ, it changes optimal routes of all executed iterations if these routes contain changed tunnels. If ΔG is greater than δ, a new ant algorithm is restarted (go to Step 1).Step 5.
Initializes ant routes recording table; fixes and controls pheromone trail matrix by the MMAS method; updates parameteriter as (iter+1). If current iter’s value is less than Cmax, go to Step 2.Step 6.
From the records of the iterations’ routesOPij (i=1,2,…, Cmax, j=0,1,2,…,L), select the optimal route and L suboptimal routes for the current underground trapped workers.


## 4.2. Ants’ Distribution and Moving Rules

TheVo and Ve nodes of the graph G are set m ants separately. For the ant k, its current node i’s accessible nodes set is built as
(13)allowik=Ai-Bk-(1-p)Ck,p={0,1}.In (13), if the node i is in the backbone zone S0 or expected zone Se, p’s value is 1, else p’s value is 0. The set Ai is {nodes ∣the  node  which  connected  with  node  i}, and the set Bk is {nodes ∣the  node  that  the  ant  k  has  passed}, and the set Ck is {nodes ∣the  node  which  does  not  belong  to  zone  S0  and  zone  Se}. Through the use of the set Ck, unnecessary detour can be avoided and the searching efficiency can be improved.In accordance with the probability value calculated through (14), the ant k selects the next node in allowik. Formula (14) is described as follows:
(14)pijk={τijαwijβ∑s∈allowikτisαwisβ,j∈allowik,0,else.In (14), α,  β are factors of importance of the pheromone trail and the heuristic function respectively. And τij,  wij are pheromone trail concentration and weights respectively from the node i to the node j. The heuristic function is defined as weights between the current nodes.


## 4.3. The Rules of Meeting and Death of Ants

Every ant has attributes of a start node and an expected node. There are two improvements in meeting and death strategy showed in rule (2) and (4).These rules are as follows.(1)
If there is no way for the ant, the ant dies and is marked with no available route status.(2)
When two ants meet, if the expecting point of one ant and the start point of the other ant intersect, the ant having short route gives its route to another, and then the latter dies and is marked with an available route status. The former moves on.(3)
If the ant reaches the expected point, the ant dies and is marked with an available route status.(4)
Sets a physical power parameter to the trapped workers groupi and denotes it as PFi which will reduce gradually. The PFi parameters are assigned to ants. The ant will die when PFi of the ant is reduced to zero no matter what status the ant is in and then it is marked with no available route status.


## 4.4. Update of Pheromone Trail and Main Parameters

When one iteration processing is completed, the pheromone matrix and the parameterα and β need to be updated. To prevent premature problem, the MMAS method [10] is used in the pheromone updating procedure. After an iteration processing, only the pheromone of this iteration optimal route is updated, according to (15) and (16). In addition, in order to improve the convergence of the later iteration and the early intelligence, factors α and β are dynamically changed at a fixed length between two iterations. At the later stage, α acts as the major factor; at the early stage, β acts as the major factor. See (17) and (18):
(15)τij(t+1)=(1-ρ)τij(t)+Δτij(t),(16)Δτij={Q∑w,arc(i,j)inoptimalroute,0,arc(i,j)notinoptimalroute,(17)α(t+1)=α(t)+Δα,Δα=(αmax-αmin)cmax,(18)β(t+1)=β(t)-Δβ,Δβ=(βmax-βmin)cmax.Formula (15) gives the pheromone relationship between the iteration (t+1) and the iteration t, and ρ is the volatile factor of the pheromone, and Δτij is the incremental pheromone.Formula (16) is built based on MMAS strategy, only if the arc(i,j) is in the optimal route of the iteration, the pheromone of the arc(i,j) is updated. ∑w is the length of the current optimal route.In (17), αmax is the maximum ofα, and αmin is the minimum of α, cmax is the total iteration number. The meaning of formula (18) is similar to the meaning of formula (17).


## 4.5. Condition of the Algorithm Stopping

When one iteration calculation is completed, according to current information, underground tunnel diagramG′ is reconstructed, and the diagram’s change rate can be represented as
(19)ΔG(t)=|G′(t)-G|G.In (19), |G′(t)-G| indicates the changing number of arcs between G′ of iteration t and the original G, and G indicates the total number of arcs of the original diagram.WhenΔG is less than the small value δ, weights of the related arcs in the optimal routes of executed iterations are updated. Under this situation, the optimal length of executed iterations changes, but the order of passed node does not change. When ΔG is more than δ, current calculation is stopped and a new algorithm calculation is restarted.


## 5. Implementation of the Algorithm and the Experimental Results

### 5.1. Parameter Setting

Differentα, β, ρ parameter values have different influence to the stability and convergence of the ant algorithm. Based on literature [14] and relative experiments, to an underground tunnel network which has 210 tunnels and 147 nodes, these parameters’ values are set in Table 4.Table 4
Parameters value of the ant algorithm.
Parameters
Value
α
1-2
β
2-1
ρ
0.3
Q (in formula (16))
1
C
max
150
m (the number of ants)
16
L (the number of alternative routes)
2


### 5.2. Experiment Data

The underground tunnel data come from a large sized coal mine in China. Partial data are showed in Table5.Table 5
Partial data and weights of underground tunnel network.
Start point
End point
Tunnel type influenckti
Wind speed (m/s)
Angle of slope (°)
Special factors influencekdi
The lowest height of smoke layer (m)
Visibility distance (m)
Body interval (m)
Length (m)
31
30
∞
0
0
1
6
20
1
40
30
32
1
10.3
10
1
6
20
0.8
35
32
33
1
5.6
0
1
6
20
0.8
242
35
12
0.5
9.4
0
1
5
20
0.8
80
12
37
1
10.3
10
∞
5
20
0.8
281
…
…
…
…
…
…
…
…
…
…In Table5, some simulated factors (such as slope, tunnel particle concentrations influence, tunnel crowded degree and special factors influence) are created based on original data. The network topology of the mine and its zoning result is shown in Figure 2.The Matlab tool is used to realize the data processing and the ant algorithm. The node 83 is set asVo and the node 1 is set as Ve. The iteration curve of the ant algorithm is shown in Figure 3.Figure 3
Iteration curve of the ant algorithm.In Figure3, the x-axis represents the number of iterations, and the ordinate represents the minimum cost of the current iteration. The cost is the sum of arc weights in the optimal route of the current iteration. From the chart we can see the algorithm has better convergence ability: after three convergences the global optimal route is found in 100 iterations about.The algorithm procedure loads related parameters and experimental data firstly and then does calculation. Five calculation results are shown in Table6. The experimental data is showed in Table 7.Table 6
Five running results of the ant algorithm.
NO.
Computing time (s)
The optimal route
The first alternative route
The second alternative route
1
3.935
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.47337
2
3.443
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.47337
cost: 0.49651
3
3.365
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.49651
4
3.337
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 78, 72, 71, 70, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.58666
5
3.935
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 62, 61, 58, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.51041
Average
3.603
Average cost: 0.42799
Average cost: 0.462034
Average cost: 0.512692Table 7
Experimental data.
Start point
End point
Tunnel type influencekti
Wind speed (m/s)
Angle of slope (°)
Special factors influencekdi
The lowest height of smoke layer (m)
Visibility distance (m)
Body interval (m)
Length (m)
31
30
∞
0
0
1
6
20
1
40
30
32
1
10.3
10
1
6
20
0.8
35
32
33
1
5.6
0
1
6
20
0.8
242
35
12
0.5
9.4
0
1
5
20
0.8
80
12
37
1
10.3
10
∞
5
20
0.8
281
37
38
1
10.4
0
1
5
20
0.8
135
38
40
1
10.4
0
1
5
20
0.8
43
40
42
0.5
10.2
0
1
5
20
0.8
28
45
46
1
0
0
1
5
20
0.8
136.4
46
40
1
0.3
−20
1
5
20
1
70.6
46
38
1
0.3
−20
1
6
20
1
27.6
42
129
1
6.4
0
1
6
20
1
194
50
51
0.5
10.9
0
1
6
20
1
40
52
51
1
0
0
∞
6
20
1
56
51
53
1
10.9
0
1
6
20
1
120
50
52
1
0
0
1
6
20
1
40
1
45
0.5
3.3
10
1
6
20
1
670
45
55
0.5
2.5
0
1
6
20
1
67
56
37
0.5
0.6
0
1
3
20
1
40
56
55
0.5
4.9
0
1
3
20
1
131.5
55
57
0.5
0.1
0
1
3
20
1
50
57
58
0.5
10.9
0
1
3
20
1
100
59
58
0.5
0.6
0
1
3
20
1
100
58
60
0.5
4.9
15
1
3
20
1
580
61
59
0.5
0
0
1
3
20
1
45
36
61
0.5
10.5
0
1
3
20
1
517
61
62
1
10.6
0
1
6
20
1
28
62
63
1
0.2
0
1
6
20
1
40
63
57
1
10.4
0
1
6
20
1
85
65
59
1
0.6
0
1
6
20
1
26
126
65
1
0
0
1
6
20
1
20
66
65
1
0.4
−15
1
6
20
1
40
67
66
1
0.5
0
1
6
20
1
72
62
67
1
10
0
1
6
20
1
27
67
237
1
10.8
0
1
6
20
1
348
69
68
0.5
1.9
0
1
6
20
1
20
71
70
0.5
0
0
1
6
15
1
15
72
70
0.5
1.6
0
∞
6
20
0.7
30
74
63
0.5
11
0
1
3
20
0.7
375
69
75
0.5
0
0
1
3
20
0.7
20
76
74
0.5
10.4
20
1
3
20
0.7
50
75
76
0.5
10.4
0
1
3
20
0.7
22
77
76
0.5
0
20
1
3
20
0.7
40
78
77
0.5
2.8
0
1
3
20
0.7
25
129
78
1
6.4
0
1
3
20
0.7
223
52
79
1
0
0
1
3
20
0.7
460
125
92
1
0
0
1
3
20
0.7
35
80
93
1
0
20
1
6
20
0.7
90
82
84
0.5
2.7
0
1
6
20
0.7
40
83
81
0.5
2.6
0
1
6
20
1.5
240
84
83
0.5
2.7
0
1
6
20
1.5
630
128
56
0.5
5.6
0
1
6
20
1.5
300
87
86
0.5
4.3
0
1
5
20
1.5
25
88
87
0.5
3
0
1
5
20
1.5
20
33
88
0.5
2.1
0
1
5
20
1.5
47
33
89
1
3.4
0
1
5
20
1.5
27
89
90
1
2.5
0
1
5
20
1.5
20
90
86
1
1.6
0
1
5
20
1.5
45
90
87
1
0
0
1
5
20
1.5
20
89
88
1
1.3
0
1
5
20
1.5
20
31
91
1
4
−20
1
5
20
1.5
286
81
93
1
2.6
0
1
6
20
1.5
640
93
94
1
2.7
0
1
6
20
1.5
35
53
80
1
10.9
0
1
6
20
1.5
90
80
82
1
10.9
0
1
6
20
1.5
204
77
99
1
4.7
0
1
6
20
1.5
254
80
77
1
2
0
1
6
20
1.5
40
82
96
0.5
9.1
0
1
6
20
1.5
61
96
97
1
8.5
15
1
6
20
1.5
40
97
98
1
0
0
1
6
20
1.5
196
99
98
1
3.5
0
1
6
20
1.2
80
96
99
1
0.6
15
1
3
20
1.2
40
99
110
1
1.9
0
∞
3
20
1.2
29.2
98
101
1
3.4
15
1
3
20
1.2
40
101
102
1
0.1
0
1
3
20
1.2
265.2
103
241
0.5
3.1
0
1
3
20
1.2
163.3
104
103
1
5.3
−20
1
3
20
1.2
21.2
105
104
0.5
3.7
0
1
3
20
1.2
110
106
105
0.5
10.8
0
1
3
20
1.2
40
106
107
1
0.1
0
1
3
20
1.2
75
98
107
1
0.1
−15
1
3
20
1.2
50
102
107
1
10.1
0
1
6
20
1.2
85
107
108
1
10.1
0
1
6
20
1.2
218.2
109
108
0.5
8.1
0
1
6
20
1.2
50
110
106
0.5
10.8
0
1
6
20
1.2
70
68
110
1
10.2
0
1
6
20
1.2
243
110
100
1
1.1
10
1
6
5
1.2
5
71
112
0.5
1.7
0
1
6
20
1.2
128
72
71
0.5
2.4
0
1
6
14
1.2
14
112
68
0.5
0.8
0
1
6
11
1.2
11
237
113
1
4.3
0
1
5
20
0.8
65.1
113
141
1
2
10
1
5
20
0.8
248
1
131
1
0.1
−15
1
5
20
0.8
50
60
115
1
10.3
0
1
5
20
0.8
50
105
241
1
8.1
0
1
5
20
0.8
130
35
91
1
9.5
10
1
5
20
0.8
40
91
138
0.5
10.4
0
1
5
20
0.8
40
108
75
0.5
10.7
20
1
5
20
0.8
95
78
72
0.5
3
0
1
5
7.6
0.8
7.6
81
94
1
0
0
1
5
20
0.8
690
94
125
1
2.7
0
1
5
20
0.8
61.2
53
125
1
0
0
1
5
20
0.8
57
125
74
1
2.7
−20
1
5
20
0.8
530
127
126
0.5
0
0
1
5
20
0.8
40
66
127
0.5
0
20
1
5
15
0.8
15
86
128
0.5
5.9
0
1
6
20
0.8
24.7
50
129
1
0
0
1
6
20
0.8
40
70
69
1
1.8
20
1
6
20
0.8
65
131
60
1
0
0
1
6
20
0.8
20
1
115
0.5
10.4
−15
1
6
20
0.8
25
32
34
0.5
10
0
1
6
20
0.8
100
136
34
0.5
0
0
1
6
20
0.8
46.1
136
137
1
10.1
0
1
6
20
0.8
210
137
35
1
11
0
1
6
20
0.8
41.4
138
36
1
10.4
0
1
6
20
0.8
39
112
139
1
0
0
1
6
20
0.8
26
100
109
1
4.3
0
1
6
20
0.8
40
142
145
0.5
0
0
1
6
20
0.8
52.2
144
145
0.5
0
0
1
6
20
0.8
71
143
144
0.5
0
0
1
6
20
0.8
71
141
143
0.5
0.4
0
∞
6
20
0.8
71
148
140
1
1.4
0
1
6
20
0.8
52.2
147
148
1
0
−10
1
6
20
0.6
71
146
147
1
0
−10
1
5
20
0.6
71
139
146
1
0.4
0
1
5
20
0.6
71
143
146
1
0
0
1
5
20
0.6
25
144
147
1
0
0
1
5
20
0.6
25
145
148
1
0
0
1
5
20
0.6
25
149
150
0.5
4.4
0
1
5
20
0.6
265.2
141
151
0.5
2.2
20
1
5
20
0.6
150
152
153
0.5
2.3
20
1
5
20
0.6
165
153
154
0.5
2.3
0
1
5
20
0.6
160
154
149
1
4.3
0
1
5
20
0.6
20
113
155
1
2.1
0
1
6
10
0.6
10
155
156
1
2.1
0
1
6
20
0.6
159.6
156
157
1
2.1
10
1
6
20
0.6
165.8
157
158
1
2
0
1
6
20
0.6
155.1
158
154
1
1.8
0
1
6
20
0.6
25.5
157
153
1
0
0
1
6
20
0.6
26.9
156
152
1
0
0
1
6
20
0.6
26.6
155
151
1
0
0
1
6
20
0.6
27.9
140
109
1
3.7
0
1
6
20
1
25.7
142
140
1
2.6
0
1
6
20
1
25.2
97
159
1
8.6
−10
1
6
20
1
240
159
160
1
4.1
−10
1
6
20
1
44
159
162
1
4.7
0
1
6
20
1
47
162
163
1
2.6
0
1
6
14.4
1
14.4
163
164
1
0
0
1
3
19
1
19
162
164
1
1.7
0
1
3
20
1
33.4
163
165
1
2.2
0
1
3
20
1
61.8
164
165
1
2.4
0
∞
3
20
1
51.2
165
104
1
4.6
20
1
3
20
1
92.3
104
166
1
3
20
1
3
20
1
120
166
167
1
2.7
0
1
3
20
1
157.9
167
168
1
2.2
0
1
3
20
1
225.9
168
169
1
2.2
0
1
3
20
1
201.4
169
170
0.5
2.2
0
1
3
20
1
212.5
170
171
0.5
2.2
0
1
3
20
1
202.8
171
172
0.5
2.2
10
1
3
20
1
175.5
172
173
0.5
2.2
10
1
3
20
1
197.5
173
174
0.5
2.2
0
1
3
20
1
216.8
174
175
1
2.2
0
1
3
20
1
203.9
175
176
1
2.4
0
1
3
20
1
51.9
176
177
1
0
0
∞
3
20
1
24.2
177
178
1
0
0
1
6
20
1
23.5
179
178
1
2.4
0
1
6
20
1
24.3
179
176
1
0
0
1
6
20
1
23.5
176
180
1
1.4
20
1
6
20
1
266.2
180
181
1
1.4
0
1
6
20
1
1285.6
182
100
1
3
0
1
6
20
1
9.2
183
182
1
1.9
0
1
6
20
1
24.9
184
183
1
2.6
0
1
6
20
1
151.2
185
184
1
1.3
0
1
6
20
1
203.5
181
185
1
1.4
0
1
6
20
1
207.6
186
142
1
3.1
0
1
6
20
1
132.7
187
186
1
4.4
0
∞
6
20
1
203.6
188
187
1
4.4
0
1
6
20
1
209
150
188
1
4.4
0
1
6
20
1
112.9
181
188
1
0
−15
1
6
20
1
29.2
187
185
1
0
0
1
6
20
1
30.3
186
184
1
1.8
0
1
6
20
1
30.3
101
160
1
1.2
0
1
6
20
1
240
103
190
1
2.1
10
1
6
20
1
25
167
190
1
0
10
1
6
20
1
29.3
190
191
0.5
2.7
0
1
5
20
1
215.6
191
168
0.5
0
0
1
5
20
1
35.8
191
192
0.5
2.6
0
1
5
20
1
211.5
169
192
0.5
0
0
1
5
20
1
29.2
192
193
1
2.7
0
∞
5
20
1
216.4
170
193
1
0
0
1
5
20
1
27.1
193
194
1
2.6
0
1
5
20
1
200
171
194
1
0
0
1
5
20
1
28.4
194
195
1
2.7
0
1
5
20
1
174.2
195
172
1
0
0
1
5
20
1
29.1
195
196
1
2.7
0
1
6
20
1
195
196
173
1
0
0
1
6
20
1
30.6
196
197
1
2.7
0
1
6
20
1
219.3
174
197
1
0
0
1
6
20
1
29.2
197
198
1
2.7
−10
1
6
20
1
197.3
198
175
1
0
−10
1
6
20
1
33.1
198
179
1
2.4
0
1
6
20
1.4
74.6
237
68
0.5
8.5
0
1
6
20
1.4
72
183
238
0.5
0
0
1
6
20
1.4
77
166
239
0.5
0.4
0
∞
6
20
1.4
101.5
239
238
0.5
0
0
1
6
20
1.4
86.1
239
240
0.5
0
0
1
6
20
1.4
112.9
238
240
1
0
0
1
6
20
1.4
25.1
240
182
1
0.8
0
1
6
20
1.4
77
237
74
1
0
20
1
6
20
1.4
40
241
102
1
0.1
0
1
6
20
1.4
40In Table6, what in small brackets is the sequence of passed nodes. To observe the calculated routes intuitively, the first running result is marked in Figure 2. The red line indicates the optimal route, and the green line is the first alternative route and the blue line is the second alternative route.In fact, through the manual calculation we know the shortest cost between node 83 and node 1 is 0.42799 and the route is(83,84,82,80,77,76,74,63,57,55,45,1). From results in Table 6 we can see the best route is found steadily, meanwhile, two alternative routes are found but not stable.


## 5.1. Parameter Setting

Differentα, β, ρ parameter values have different influence to the stability and convergence of the ant algorithm. Based on literature [14] and relative experiments, to an underground tunnel network which has 210 tunnels and 147 nodes, these parameters’ values are set in Table 4.Table 4
Parameters value of the ant algorithm.
Parameters
Value
α
1-2
β
2-1
ρ
0.3
Q (in formula (16))
1
C
max
150
m (the number of ants)
16
L (the number of alternative routes)
2


## 5.2. Experiment Data

The underground tunnel data come from a large sized coal mine in China. Partial data are showed in Table5.Table 5
Partial data and weights of underground tunnel network.
Start point
End point
Tunnel type influenckti
Wind speed (m/s)
Angle of slope (°)
Special factors influencekdi
The lowest height of smoke layer (m)
Visibility distance (m)
Body interval (m)
Length (m)
31
30
∞
0
0
1
6
20
1
40
30
32
1
10.3
10
1
6
20
0.8
35
32
33
1
5.6
0
1
6
20
0.8
242
35
12
0.5
9.4
0
1
5
20
0.8
80
12
37
1
10.3
10
∞
5
20
0.8
281
…
…
…
…
…
…
…
…
…
…In Table5, some simulated factors (such as slope, tunnel particle concentrations influence, tunnel crowded degree and special factors influence) are created based on original data. The network topology of the mine and its zoning result is shown in Figure 2.The Matlab tool is used to realize the data processing and the ant algorithm. The node 83 is set asVo and the node 1 is set as Ve. The iteration curve of the ant algorithm is shown in Figure 3.Figure 3
Iteration curve of the ant algorithm.In Figure3, the x-axis represents the number of iterations, and the ordinate represents the minimum cost of the current iteration. The cost is the sum of arc weights in the optimal route of the current iteration. From the chart we can see the algorithm has better convergence ability: after three convergences the global optimal route is found in 100 iterations about.The algorithm procedure loads related parameters and experimental data firstly and then does calculation. Five calculation results are shown in Table6. The experimental data is showed in Table 7.Table 6
Five running results of the ant algorithm.
NO.
Computing time (s)
The optimal route
The first alternative route
The second alternative route
1
3.935
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.47337
2
3.443
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.47337
cost: 0.49651
3
3.365
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 96, 99, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.49651
4
3.337
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 78, 72, 71, 70, 69, 68, 237, 74, 63, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.58666
5
3.935
(83, 84, 82, 80, 77, 76, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 57, 55, 45, 1)
(83, 84, 82, 80, 77, 76, 75, 69, 68, 237, 74, 63, 62, 61, 58, 57, 55, 45, 1)
cost: 0.42799
cost: 0.45920
cost: 0.51041
Average
3.603
Average cost: 0.42799
Average cost: 0.462034
Average cost: 0.512692Table 7
Experimental data.
Start point
End point
Tunnel type influencekti
Wind speed (m/s)
Angle of slope (°)
Special factors influencekdi
The lowest height of smoke layer (m)
Visibility distance (m)
Body interval (m)
Length (m)
31
30
∞
0
0
1
6
20
1
40
30
32
1
10.3
10
1
6
20
0.8
35
32
33
1
5.6
0
1
6
20
0.8
242
35
12
0.5
9.4
0
1
5
20
0.8
80
12
37
1
10.3
10
∞
5
20
0.8
281
37
38
1
10.4
0
1
5
20
0.8
135
38
40
1
10.4
0
1
5
20
0.8
43
40
42
0.5
10.2
0
1
5
20
0.8
28
45
46
1
0
0
1
5
20
0.8
136.4
46
40
1
0.3
−20
1
5
20
1
70.6
46
38
1
0.3
−20
1
6
20
1
27.6
42
129
1
6.4
0
1
6
20
1
194
50
51
0.5
10.9
0
1
6
20
1
40
52
51
1
0
0
∞
6
20
1
56
51
53
1
10.9
0
1
6
20
1
120
50
52
1
0
0
1
6
20
1
40
1
45
0.5
3.3
10
1
6
20
1
670
45
55
0.5
2.5
0
1
6
20
1
67
56
37
0.5
0.6
0
1
3
20
1
40
56
55
0.5
4.9
0
1
3
20
1
131.5
55
57
0.5
0.1
0
1
3
20
1
50
57
58
0.5
10.9
0
1
3
20
1
100
59
58
0.5
0.6
0
1
3
20
1
100
58
60
0.5
4.9
15
1
3
20
1
580
61
59
0.5
0
0
1
3
20
1
45
36
61
0.5
10.5
0
1
3
20
1
517
61
62
1
10.6
0
1
6
20
1
28
62
63
1
0.2
0
1
6
20
1
40
63
57
1
10.4
0
1
6
20
1
85
65
59
1
0.6
0
1
6
20
1
26
126
65
1
0
0
1
6
20
1
20
66
65
1
0.4
−15
1
6
20
1
40
67
66
1
0.5
0
1
6
20
1
72
62
67
1
10
0
1
6
20
1
27
67
237
1
10.8
0
1
6
20
1
348
69
68
0.5
1.9
0
1
6
20
1
20
71
70
0.5
0
0
1
6
15
1
15
72
70
0.5
1.6
0
∞
6
20
0.7
30
74
63
0.5
11
0
1
3
20
0.7
375
69
75
0.5
0
0
1
3
20
0.7
20
76
74
0.5
10.4
20
1
3
20
0.7
50
75
76
0.5
10.4
0
1
3
20
0.7
22
77
76
0.5
0
20
1
3
20
0.7
40
78
77
0.5
2.8
0
1
3
20
0.7
25
129
78
1
6.4
0
1
3
20
0.7
223
52
79
1
0
0
1
3
20
0.7
460
125
92
1
0
0
1
3
20
0.7
35
80
93
1
0
20
1
6
20
0.7
90
82
84
0.5
2.7
0
1
6
20
0.7
40
83
81
0.5
2.6
0
1
6
20
1.5
240
84
83
0.5
2.7
0
1
6
20
1.5
630
128
56
0.5
5.6
0
1
6
20
1.5
300
87
86
0.5
4.3
0
1
5
20
1.5
25
88
87
0.5
3
0
1
5
20
1.5
20
33
88
0.5
2.1
0
1
5
20
1.5
47
33
89
1
3.4
0
1
5
20
1.5
27
89
90
1
2.5
0
1
5
20
1.5
20
90
86
1
1.6
0
1
5
20
1.5
45
90
87
1
0
0
1
5
20
1.5
20
89
88
1
1.3
0
1
5
20
1.5
20
31
91
1
4
−20
1
5
20
1.5
286
81
93
1
2.6
0
1
6
20
1.5
640
93
94
1
2.7
0
1
6
20
1.5
35
53
80
1
10.9
0
1
6
20
1.5
90
80
82
1
10.9
0
1
6
20
1.5
204
77
99
1
4.7
0
1
6
20
1.5
254
80
77
1
2
0
1
6
20
1.5
40
82
96
0.5
9.1
0
1
6
20
1.5
61
96
97
1
8.5
15
1
6
20
1.5
40
97
98
1
0
0
1
6
20
1.5
196
99
98
1
3.5
0
1
6
20
1.2
80
96
99
1
0.6
15
1
3
20
1.2
40
99
110
1
1.9
0
∞
3
20
1.2
29.2
98
101
1
3.4
15
1
3
20
1.2
40
101
102
1
0.1
0
1
3
20
1.2
265.2
103
241
0.5
3.1
0
1
3
20
1.2
163.3
104
103
1
5.3
−20
1
3
20
1.2
21.2
105
104
0.5
3.7
0
1
3
20
1.2
110
106
105
0.5
10.8
0
1
3
20
1.2
40
106
107
1
0.1
0
1
3
20
1.2
75
98
107
1
0.1
−15
1
3
20
1.2
50
102
107
1
10.1
0
1
6
20
1.2
85
107
108
1
10.1
0
1
6
20
1.2
218.2
109
108
0.5
8.1
0
1
6
20
1.2
50
110
106
0.5
10.8
0
1
6
20
1.2
70
68
110
1
10.2
0
1
6
20
1.2
243
110
100
1
1.1
10
1
6
5
1.2
5
71
112
0.5
1.7
0
1
6
20
1.2
128
72
71
0.5
2.4
0
1
6
14
1.2
14
112
68
0.5
0.8
0
1
6
11
1.2
11
237
113
1
4.3
0
1
5
20
0.8
65.1
113
141
1
2
10
1
5
20
0.8
248
1
131
1
0.1
−15
1
5
20
0.8
50
60
115
1
10.3
0
1
5
20
0.8
50
105
241
1
8.1
0
1
5
20
0.8
130
35
91
1
9.5
10
1
5
20
0.8
40
91
138
0.5
10.4
0
1
5
20
0.8
40
108
75
0.5
10.7
20
1
5
20
0.8
95
78
72
0.5
3
0
1
5
7.6
0.8
7.6
81
94
1
0
0
1
5
20
0.8
690
94
125
1
2.7
0
1
5
20
0.8
61.2
53
125
1
0
0
1
5
20
0.8
57
125
74
1
2.7
−20
1
5
20
0.8
530
127
126
0.5
0
0
1
5
20
0.8
40
66
127
0.5
0
20
1
5
15
0.8
15
86
128
0.5
5.9
0
1
6
20
0.8
24.7
50
129
1
0
0
1
6
20
0.8
40
70
69
1
1.8
20
1
6
20
0.8
65
131
60
1
0
0
1
6
20
0.8
20
1
115
0.5
10.4
−15
1
6
20
0.8
25
32
34
0.5
10
0
1
6
20
0.8
100
136
34
0.5
0
0
1
6
20
0.8
46.1
136
137
1
10.1
0
1
6
20
0.8
210
137
35
1
11
0
1
6
20
0.8
41.4
138
36
1
10.4
0
1
6
20
0.8
39
112
139
1
0
0
1
6
20
0.8
26
100
109
1
4.3
0
1
6
20
0.8
40
142
145
0.5
0
0
1
6
20
0.8
52.2
144
145
0.5
0
0
1
6
20
0.8
71
143
144
0.5
0
0
1
6
20
0.8
71
141
143
0.5
0.4
0
∞
6
20
0.8
71
148
140
1
1.4
0
1
6
20
0.8
52.2
147
148
1
0
−10
1
6
20
0.6
71
146
147
1
0
−10
1
5
20
0.6
71
139
146
1
0.4
0
1
5
20
0.6
71
143
146
1
0
0
1
5
20
0.6
25
144
147
1
0
0
1
5
20
0.6
25
145
148
1
0
0
1
5
20
0.6
25
149
150
0.5
4.4
0
1
5
20
0.6
265.2
141
151
0.5
2.2
20
1
5
20
0.6
150
152
153
0.5
2.3
20
1
5
20
0.6
165
153
154
0.5
2.3
0
1
5
20
0.6
160
154
149
1
4.3
0
1
5
20
0.6
20
113
155
1
2.1
0
1
6
10
0.6
10
155
156
1
2.1
0
1
6
20
0.6
159.6
156
157
1
2.1
10
1
6
20
0.6
165.8
157
158
1
2
0
1
6
20
0.6
155.1
158
154
1
1.8
0
1
6
20
0.6
25.5
157
153
1
0
0
1
6
20
0.6
26.9
156
152
1
0
0
1
6
20
0.6
26.6
155
151
1
0
0
1
6
20
0.6
27.9
140
109
1
3.7
0
1
6
20
1
25.7
142
140
1
2.6
0
1
6
20
1
25.2
97
159
1
8.6
−10
1
6
20
1
240
159
160
1
4.1
−10
1
6
20
1
44
159
162
1
4.7
0
1
6
20
1
47
162
163
1
2.6
0
1
6
14.4
1
14.4
163
164
1
0
0
1
3
19
1
19
162
164
1
1.7
0
1
3
20
1
33.4
163
165
1
2.2
0
1
3
20
1
61.8
164
165
1
2.4
0
∞
3
20
1
51.2
165
104
1
4.6
20
1
3
20
1
92.3
104
166
1
3
20
1
3
20
1
120
166
167
1
2.7
0
1
3
20
1
157.9
167
168
1
2.2
0
1
3
20
1
225.9
168
169
1
2.2
0
1
3
20
1
201.4
169
170
0.5
2.2
0
1
3
20
1
212.5
170
171
0.5
2.2
0
1
3
20
1
202.8
171
172
0.5
2.2
10
1
3
20
1
175.5
172
173
0.5
2.2
10
1
3
20
1
197.5
173
174
0.5
2.2
0
1
3
20
1
216.8
174
175
1
2.2
0
1
3
20
1
203.9
175
176
1
2.4
0
1
3
20
1
51.9
176
177
1
0
0
∞
3
20
1
24.2
177
178
1
0
0
1
6
20
1
23.5
179
178
1
2.4
0
1
6
20
1
24.3
179
176
1
0
0
1
6
20
1
23.5
176
180
1
1.4
20
1
6
20
1
266.2
180
181
1
1.4
0
1
6
20
1
1285.6
182
100
1
3
0
1
6
20
1
9.2
183
182
1
1.9
0
1
6
20
1
24.9
184
183
1
2.6
0
1
6
20
1
151.2
185
184
1
1.3
0
1
6
20
1
203.5
181
185
1
1.4
0
1
6
20
1
207.6
186
142
1
3.1
0
1
6
20
1
132.7
187
186
1
4.4
0
∞
6
20
1
203.6
188
187
1
4.4
0
1
6
20
1
209
150
188
1
4.4
0
1
6
20
1
112.9
181
188
1
0
−15
1
6
20
1
29.2
187
185
1
0
0
1
6
20
1
30.3
186
184
1
1.8
0
1
6
20
1
30.3
101
160
1
1.2
0
1
6
20
1
240
103
190
1
2.1
10
1
6
20
1
25
167
190
1
0
10
1
6
20
1
29.3
190
191
0.5
2.7
0
1
5
20
1
215.6
191
168
0.5
0
0
1
5
20
1
35.8
191
192
0.5
2.6
0
1
5
20
1
211.5
169
192
0.5
0
0
1
5
20
1
29.2
192
193
1
2.7
0
∞
5
20
1
216.4
170
193
1
0
0
1
5
20
1
27.1
193
194
1
2.6
0
1
5
20
1
200
171
194
1
0
0
1
5
20
1
28.4
194
195
1
2.7
0
1
5
20
1
174.2
195
172
1
0
0
1
5
20
1
29.1
195
196
1
2.7
0
1
6
20
1
195
196
173
1
0
0
1
6
20
1
30.6
196
197
1
2.7
0
1
6
20
1
219.3
174
197
1
0
0
1
6
20
1
29.2
197
198
1
2.7
−10
1
6
20
1
197.3
198
175
1
0
−10
1
6
20
1
33.1
198
179
1
2.4
0
1
6
20
1.4
74.6
237
68
0.5
8.5
0
1
6
20
1.4
72
183
238
0.5
0
0
1
6
20
1.4
77
166
239
0.5
0.4
0
∞
6
20
1.4
101.5
239
238
0.5
0
0
1
6
20
1.4
86.1
239
240
0.5
0
0
1
6
20
1.4
112.9
238
240
1
0
0
1
6
20
1.4
25.1
240
182
1
0.8
0
1
6
20
1.4
77
237
74
1
0
20
1
6
20
1.4
40
241
102
1
0.1
0
1
6
20
1.4
40In Table6, what in small brackets is the sequence of passed nodes. To observe the calculated routes intuitively, the first running result is marked in Figure 2. The red line indicates the optimal route, and the green line is the first alternative route and the blue line is the second alternative route.In fact, through the manual calculation we know the shortest cost between node 83 and node 1 is 0.42799 and the route is(83,84,82,80,77,76,74,63,57,55,45,1). From results in Table 6 we can see the best route is found steadily, meanwhile, two alternative routes are found but not stable.


## 6. Conclusion

An improved ant algorithm is proposed in this paper to solve the escape routes planning problem of underground coal mines. A simple unified tunnel weights calculation model is designed, which considers various impact factors. By the tunnel zoning method, searching efficiency of the ant algorithm has been improved effectively. The MMAS method is used to optimize the meeting strategy to improve the performance of the ant algorithm. In the algorithm’s processing procedure, when small part of mine networks changes, the system may fix the optimal routes and avoid starting a new processing procedure. The algorithm was achieved in the Matlab platform and the best route was worked out steadily. The algorithm obtained good results when treating the data of a large coal mine of China. The proposed algorithm can be used in underground mine disaster rescue.



---

*Source: 687969-2013-02-28.xml*