# Multi-Objective Real-Time Planning of Evacuation Routes for Underground Mine Fires
## 4 Mathematical Models and Algorithms for Emergency Escape Routes
### Labeling Algorithm Based on Dynamic Programming  
A general algorithm for solving constrained shortest circuits is the labeling algorithm based on dynamic programming [34]. The algorithm degenerates into [PERSON]'s algorithm when there is only one type of weight on the edges of the network and only one objective function for the shortest path model. The labels in this algorithm refer to the data structure that stores the paths as well as the distances of the paths and the traveling time in the smoke stream. The algorithm starts from the starting point and gradually searches for feasible paths and records them in the labels. The same node will generate different labels when it is reached through different paths. The REFs are used to generate and determine whether the labels are legal and construct the solution set space of feasible paths; the dominance function is used to determine the dominant relationship between the labels on the same node. If a label is dominated, it means that the path represented by the label is not the shortest path or cannot constitute the shortest path to the end point. Then, in order to speed up the solution, the label should be discarded. A reasonable dominance function is the key to accelerating the algorithm solution. Label data structure:  
struct Label(  
Vector\(\cdot\)int\(\cdot\)Path,\(//\)Path  
int Equal_Distance;// Equivalent length  
int Time_in_smoke;// Time spent walking in the smoke  
int Time_escape_smoke_area;//Time to leave the smoke area  
Resource Expansion Function(REFs): The Resource Expansion Function specifies the change in each resource (path length, cost, etc.) from the start point to the end point on each edge. It provides a lower bound on the resource value at the end point based on the start point to resource value. For any resource \(r\), the resource consumption at the node \(i\) is \(T_{i}\), and the weight of that resource on the edge \(<i,j>\) is \(t_{ij}\); hence, the resource consumption at the node is \(j\)  
\[{f_{ij}^{r}(T_{i})={T_{i}^{r}+{t_{ij}}^{r}}} \tag{6}\]  
where \(f_{ij}^{r}(T_{i})\) is the resource consumption of resource \(r\) based on the resource consumption at node \(i\) expanded along edges \(<i,j>\). Dominance function: The two attributes of the path equivalent length and the travel time in the smoke flow in this problem are represented by the vector \(<W,T>\). Since the two resource attributes in this problem are non-negative, the resource expansion function is non-decreasing. Therefore, for labels \(\text{L}_{1}=<W_{1},T_{1}>\) and labels \(\text{L}_{2}=<W_{2},\text{T}_{2}>\), if \(W_{1}\leq W_{2}\) and \(\text{T}_{1}\leq T_{2}\), then label \(\text{L}_{1}\) is dominated by label \(\text{L}_{2}\). All non-dominated labels on a node form a Pareto optimal set [35]. A constrained shortest path example based on two resources is shown in Figure 2. Starting from the starting point S, there are two labels, s-2-1 and s-1 at node 1, and the resource vectors are (1,2) and (2,1), respectively, and there is no dominance relationship; at node 2, there are two labels, s-1-2 and s-2, and the resource vectors are (2,5,2) and (0.5,1), respectively, and the former is dominated by the latter. Therefore, the path s-1-2 is abandoned and no longer expanded. Finally, at node t, there are three labels, s-2-t, s-2-1-t, and s-1-t, and the resource vectors are (3,3), (4,2), and (5,1), respectively, and there is no dominant relationship between them. Therefore, all three paths are Pareto optimal solutions. The algorithm flow of the constrained shortest path model emergency route planning problem is shown in Figure 3.  
The specific steps are as follows. Step 1: Firstly, read the roadway and mine ventilation network information to construct the escape and emergency escape information network \(G\); obtain the personnel position \(s\) as well as the escape target \(d\); define the set of unprocessed labels as \(U=\{(s)\}\), containing only one path; and define the set of labels that have been processed as \(P=\{\}\), which is initialized to be the empty set.