# Dynamic Emergency Vehicle Path Planning and Traffic Evacuation Based on Salp Swarm Algorithm

Authors: X. H. Duan; J. X. Wu; Y. L. Xiong
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

In view of the rescue delay due to traffic congestion in the urban road network, this paper implemented real-time traffic control with congestion index constraints in emergency vehicle dispatching and proposed a two-stage optimization model and algorithm. In the first stage, salp swarm algorithm (SSA) was combined with Dijkstra algorithm, and a novel hybrid algorithm with new updating rules was designed to get the multiple alternative paths. In the second stage, an improved salp swarm algorithm (ISSA) with a population grouping strategy was proposed to obtain the best evacuation schemes and the optimal rescue paths of emergency vehicles. Results of the illustrative examples show that, after evacuation, the average travel time of all alternative paths is reduced by 24.22%, while traffic congestion indexes of the adjacent road sections almost unchanged. The computation time of the hybrid algorithm for obtaining the set number of alternative paths is 56.62% and 50.47% shorter than that of bat algorithm (BA) and SSA. For the solution of the evacuation model, the computation time of the ISSA is 33.51%, 30.15%, and 30.60% shorter than that of particle swarm optimization (PSO), BA, and SSA, and the optimal solution of the ISSA is 25.92%, 10.06%, and 0.97% better than that of PSO, BA, and SSA. That is, we shorten the emergency response time and control the adverse impact of traffic evacuation on background traffic. The improved algorithm has excellent performance. This study provides a new idea and method for emergency rescue of traffic accidents.


---

## Body

## 1. Introduction

Traffic accidents not only are the number one cause of premature death for people, but they are easy to cause and aggravate traffic congestion. Almost 60% of traffic delays are caused by traffic accidents [1]. When the traffic accident lasts more than 30 minutes, Beijing expressway capacity will be generally reduced to 53% [2]. Timely rescue after a traffic accident is the key to reduce losses, and emergency vehicle dispatching is an essential part of accident rescue [3]. This requires managers to obtain relevant information and make decisions to dispatch police vehicles, fire engines, and wreckers to arrive at the accident location in time. It is evident that due to the timeliness of emergency rescue, shortening response time must be a prime target of dispatching decisions. The response time consists of decision time and travel time of emergency vehicles [4], and it usually takes much longer for emergency vehicles to travel to the accident. In an intricate urban road network, the emergency vehicle can usually reach the accident location through multiple paths, and different path planning determines different travel times. Therefore, path planning is the basis of vehicle dispatching, and it is crucial to select the path reasonably with the goal of shortening the travel time.The current dispatching methods of emergency vehicles for urban traffic accidents are essential decision-making in the existing road network environment. However, an urban road network is prone to serious congestion for a long time, because the rush-hour traffic volumes are in great demand, and accidents may seriously hold up traffic. In this situation, it is difficult to guarantee that emergency vehicles can arrive at the accident location before the rescue time limit.In order to avoid delays in rescue caused by traffic congestion, this paper tries to solve the path planning problem in emergency vehicle dispatching with a new method. There are three main contributions of this paper: (1) combining path planning with traffic evacuation, using real-time segmental evacuation strategy to optimize road conditions in order to assist emergency vehicles to reach the accident location in time, and constructing a two-stage model of emergency vehicle path planning and traffic evacuation; (2) adding the congestion index constraint to the traffic evacuation model so as to reduce the impact on the background traffic while shortening the traveling time; (3) applying a new swarm optimization algorithm, the salp swarm algorithm, to the solution of the model, and improving the original algorithm by using grouping and mixed strategies, which can significantly improve both the optimization ability and the computation speed.The paper is structured as follows: Section2 provides an overview of related work; Section 3 describes the problem and constructs a two-stage model; Section 4 introduces the improved salp swarm algorithm for solving the model; Section 5 verifies the performance of the model and algorithm through illustrative examples and finally draws a conclusion.


## 2. Related Work

### 2.1. Modeling

The early work assumed that the travel time was static and known, and emergency vehicle dispatching was reducible to the minimal assignment problem. The Hungarian method applies to a rescue situation, in which the number of emergency vehicles in the area is the same as the number of accidents, and an accident can only be served by one vehicle [5]. The direct costs method is used to solve the dispatching problem with multiaccident and multidepot. The objective is to minimize the direct costs, which depend on the shortest distance from the depot to the accident [6]. He et al. [7] built a variety of combinatorial optimization models to select depots that met the constraints of supply and demand of emergency materials for one disaster. Afterward, multiple disasters, a variety of emergency materials, multiple vehicle types, and other factors were gradually introduced, and the models were more and more complex and close to the actual rescue situation [8–10]. In addition to the time objective, a large number of works aimed to optimize the total costs [11–13], reliability with split delivery [13], demand satisfaction [11, 14, 15], path reliability [12, 14, 15], lifesaving utility [16], fairness and the empty-loading ratio [17], and multiobjective optimization models were established.In practical emergency rescue, the travel time required for emergency vehicles to arrive at the accident changes with the departure time. The shortest path does not necessarily have the shortest travel time. Therefore, it is necessary to get the time shortest path according to the real-time road conditions before dispatching emergency vehicles. Haghani et al. [18] built an ambulance response system based on real-time travel time to dispatch emergency vehicles and guide them away from congested road sections. Katsuma and Yoshida [19] proposed a self-organizing network architecture to collect real-time traffic information based on communication between vehicles, and then routes of emergency vehicles were reconstructed periodically.Using the real-time method, the dynamic path planning and dispatching are resolved into several static problems. Every decision-making turn into local optimization is based on real-time information, and therefore, it may not always be possible to obtain the global optimal solutions. The prediction or estimation methods take into account the changes in parameters in the future. Yuan and Wang [20] defined that the travel speed continuously decreased with time at the time of the disaster and established a shortest time path planning model. Pu et al. [21] used the vertical queuing assumption to estimate the travel time of the rescue path; furthermore, they established an improved opportunity cost model considering the change congestion state of the rescue path. Duan et al. [22] built a time-varying road network with a link weight of predictive travel speed. Based on this network, they constructed a dynamic emergency vehicle path planning and dispatching model. In the study of Liu and Wu [23], the model prediction control method was employed to establish a multiperiod rolling optimal dispatching model. According to the continuously updated information, the dispatching strategy was adjusted in each period. We can regard this work as a combination of real-time and prediction methods.For the dynamic and uncertainty of decision parameters, the determined parameters such as the time and demands were replaced by their probability distribution in some studies. Li et al. [24] built an uncertain programming model for solving the problem of medical supplies dispatching, in which the running time and demands were supposed to be uncertain variables. The work of Wang and Hu [25] was targeted at dealing with the uncertainty of distribution center warehouse explosion and road damage. Under this condition, a multistage bilevel optimization model for material supplies was established. Shen et al. [26] decomposed the emergency vehicle routing problem under large-scale bioterrorism into two stages. In the planning stage, distributions of uncertain demand and travel time were assumed to be known, and routes were generated before any emergency. In the operational stage, the preplanned routing solution was adjusted based on the acquired outcome of the parameters at the time of an emergency. Real-time information was employed to modify the uncertain parameters, so as to improve decision-making performance. In addition, the fuzzy decision method was also used to solve the dynamic and uncertain dispatching problems [27].


### 2.2. Bioinspired Algorithms

Bioinspired algorithms, which simulate biological evolution or group social behavior in nature, have the ability of global optimization and are suitable for parallel processing. This type of algorithm does not depend on gradient information and has shown excellent performance in large-scale complex problems that are difficult to solve by traditional methods [28, 29]. Due to the nonpolynomial complexity of the material dispatching problem, bioinspired algorithms have been widely used in such problems. The applications of bioinspired algorithms in emergency material dispatching, path planning, and emergency traffic evacuation problems related to this study are as follows.Bodaghi et al. [30] used genetic algorithm to solve a multiresource dispatching and routing problem with a large scale of relief centers, demand points, and vehicles. Ye et al. [31] proposed an enhanced particle swarm optimization combining multiagent theory and evolutionary population dynamics to solve the problem of emergency resources dispatching in oil spillage accidents. Wan et al. [32] designed a hybrid ant colony optimization algorithm for solving a multibase dynamic emergency dispatching problem under geological disasters. Zahedi et al. [33] used the NSGA-II algorithm to solve a multiobjective programming model for emergency material distribution and vehicle routing. Wang et al. [34] used an improved multiobjective artificial bee colony algorithm to solve a multidisaster emergency resource dispatching problem during the epidemic. Tang et al. [17] designed a multiobjective particle swarm optimization algorithm based on the evaluation of evolutionary states to solve the multiobjective dispatching problem of emergency supplies for earthquakes.Wang [35] proposed a multipath routing algorithm for wireless sensor networks based on genetic algorithm. In order to overcome the problem that genetic algorithm and ant colony optimization algorithm tend to stagnate due to early-maturing, Liang and Wang [36] combined these two algorithms to form a hybrid algorithm and applied it into marine investigation path planning. Zhao et al. [37] designed an improved fast nondominated sorting genetic algorithm for solving a multiobjective bilevel programming model of logistics system path planning. Liu et al. [38] integrated the neighborhood operator into the discrete bat algorithm and used the improved algorithm to solve the multipoint shortest path planning problem. Wu et al. [39, 40] provided a comprehensive review of population-based metaheuristic algorithms and their applications to motion planning of aircraft and used a clustering improved ant colony optimization algorithm to solve the multipath planning problem for drone operations.Yang et al. [41] used an improved particle swarm optimization algorithm based on sorting selection to solve the problem of traffic induced evacuation in large public places under emergency conditions. Tian et al. [42] redesigned pheromone update rules and ant transfer rules and proposed a capacity-constrained evacuation model based on the improved ant colony optimization algorithm. Jabari et al. [43] proposed a genetic algorithm for solving a phased emergency traffic evacuation model. Ma et al. [44] proposed a temporary traffic control method during emergency rescue and get the optimal control plans based on genetic algorithm.


### 2.3. Analysis of Related Work

In terms of modeling, models that consider dynamic changes in road conditions are clearly more suitable for solving the emergency vehicle path planning and dispatching problem in urban road networks. The existing dynamic models are mainly divided into three categories. The first type is based on real-time road condition information, which usually makes initial decisions based on the information at the current moment and then adjusts the path and dispatching strategies at key moments or key nodes according to the new information obtained constantly. The static model is actually used in each decision stage. The second type is based on predicted road conditions. It first predicts the change of road condition during the decision process based on experience or historical big data and then constructs a dynamic model for decision-making. It can also be combined with the first type of model to adjust the strategy in real time. The third type uses the probability distribution of road condition information to construct stochastic programming models. Also, it can be combined with the first type of model.In fact, the above three methods are based on the estimated values of the actual road conditions. However, when the road conditions are bad, it is difficult for emergency vehicles to reach the designated location within the valid rescue time, even if the shortest path is adopted. Therefore, it is necessary to use traffic evacuation measures to fundamentally improve the road conditions of the road sections through which the emergency vehicles pass. To this end, a new model framework is constructed. First of all, the shortest path model, which is currently commonly used to solve this problem, is extended to multiple paths with the aim of obtaining multiple optimal paths available for emergency vehicles. Then, a dynamic traffic evacuation model based on real-time information is used to make evacuation control for the background traffic on the alternative paths, so as to shorten the traveling time of emergency vehicles. Finally, the one with the shortest travel time after evacuation is selected as the final path.The common algorithms for solving emergency vehicle dispatching and path planning include genetic algorithm, particle swarm optimization algorithm, and ant colony optimization algorithm, as well as their modifications [40]. Salp swarm algorithm, proposed by Mirjalili in 2017, is a new swarm optimization method, which simulates the swarming behavior of salps [45]. In nature, many organisms are distributed in groups, but salps move in chains. The leader in the salp swarm is at the head of the chain, and it only affects the second one that follows it. Similarly, when updating the position, the latter salp is only affected by the former one. This behavior can reduce the influence of leaders gradually, thus ensuring the diversity of the population.The adoption of the self-adapting operator makes the SSA algorithm effectively balance the exploration and development, which increases the chances of obtaining a globally optimal solution. The chain moving and self-adapting mechanisms of the algorithm give it a high degree of exploration and the ability to avoid local optimum. Comparing the SSA algorithm with well-known and new algorithms such as PSO, GSA, BA, FPA, SMS, FA, and GA, the results show that the SSA algorithm outperforms the others in most of the test functions [45]. Due to this advantage of the SSA, it has been used in various fields such as feature selection, training neural networks, scheduling, control of power systems, and renewable energy systems [46–48]. In view of the excellent global optimization ability of the SSA, this paper tries to apply it to solve the path planning and traffic evacuation model.


## 2.1. Modeling

The early work assumed that the travel time was static and known, and emergency vehicle dispatching was reducible to the minimal assignment problem. The Hungarian method applies to a rescue situation, in which the number of emergency vehicles in the area is the same as the number of accidents, and an accident can only be served by one vehicle [5]. The direct costs method is used to solve the dispatching problem with multiaccident and multidepot. The objective is to minimize the direct costs, which depend on the shortest distance from the depot to the accident [6]. He et al. [7] built a variety of combinatorial optimization models to select depots that met the constraints of supply and demand of emergency materials for one disaster. Afterward, multiple disasters, a variety of emergency materials, multiple vehicle types, and other factors were gradually introduced, and the models were more and more complex and close to the actual rescue situation [8–10]. In addition to the time objective, a large number of works aimed to optimize the total costs [11–13], reliability with split delivery [13], demand satisfaction [11, 14, 15], path reliability [12, 14, 15], lifesaving utility [16], fairness and the empty-loading ratio [17], and multiobjective optimization models were established.In practical emergency rescue, the travel time required for emergency vehicles to arrive at the accident changes with the departure time. The shortest path does not necessarily have the shortest travel time. Therefore, it is necessary to get the time shortest path according to the real-time road conditions before dispatching emergency vehicles. Haghani et al. [18] built an ambulance response system based on real-time travel time to dispatch emergency vehicles and guide them away from congested road sections. Katsuma and Yoshida [19] proposed a self-organizing network architecture to collect real-time traffic information based on communication between vehicles, and then routes of emergency vehicles were reconstructed periodically.Using the real-time method, the dynamic path planning and dispatching are resolved into several static problems. Every decision-making turn into local optimization is based on real-time information, and therefore, it may not always be possible to obtain the global optimal solutions. The prediction or estimation methods take into account the changes in parameters in the future. Yuan and Wang [20] defined that the travel speed continuously decreased with time at the time of the disaster and established a shortest time path planning model. Pu et al. [21] used the vertical queuing assumption to estimate the travel time of the rescue path; furthermore, they established an improved opportunity cost model considering the change congestion state of the rescue path. Duan et al. [22] built a time-varying road network with a link weight of predictive travel speed. Based on this network, they constructed a dynamic emergency vehicle path planning and dispatching model. In the study of Liu and Wu [23], the model prediction control method was employed to establish a multiperiod rolling optimal dispatching model. According to the continuously updated information, the dispatching strategy was adjusted in each period. We can regard this work as a combination of real-time and prediction methods.For the dynamic and uncertainty of decision parameters, the determined parameters such as the time and demands were replaced by their probability distribution in some studies. Li et al. [24] built an uncertain programming model for solving the problem of medical supplies dispatching, in which the running time and demands were supposed to be uncertain variables. The work of Wang and Hu [25] was targeted at dealing with the uncertainty of distribution center warehouse explosion and road damage. Under this condition, a multistage bilevel optimization model for material supplies was established. Shen et al. [26] decomposed the emergency vehicle routing problem under large-scale bioterrorism into two stages. In the planning stage, distributions of uncertain demand and travel time were assumed to be known, and routes were generated before any emergency. In the operational stage, the preplanned routing solution was adjusted based on the acquired outcome of the parameters at the time of an emergency. Real-time information was employed to modify the uncertain parameters, so as to improve decision-making performance. In addition, the fuzzy decision method was also used to solve the dynamic and uncertain dispatching problems [27].


## 2.2. Bioinspired Algorithms

Bioinspired algorithms, which simulate biological evolution or group social behavior in nature, have the ability of global optimization and are suitable for parallel processing. This type of algorithm does not depend on gradient information and has shown excellent performance in large-scale complex problems that are difficult to solve by traditional methods [28, 29]. Due to the nonpolynomial complexity of the material dispatching problem, bioinspired algorithms have been widely used in such problems. The applications of bioinspired algorithms in emergency material dispatching, path planning, and emergency traffic evacuation problems related to this study are as follows.Bodaghi et al. [30] used genetic algorithm to solve a multiresource dispatching and routing problem with a large scale of relief centers, demand points, and vehicles. Ye et al. [31] proposed an enhanced particle swarm optimization combining multiagent theory and evolutionary population dynamics to solve the problem of emergency resources dispatching in oil spillage accidents. Wan et al. [32] designed a hybrid ant colony optimization algorithm for solving a multibase dynamic emergency dispatching problem under geological disasters. Zahedi et al. [33] used the NSGA-II algorithm to solve a multiobjective programming model for emergency material distribution and vehicle routing. Wang et al. [34] used an improved multiobjective artificial bee colony algorithm to solve a multidisaster emergency resource dispatching problem during the epidemic. Tang et al. [17] designed a multiobjective particle swarm optimization algorithm based on the evaluation of evolutionary states to solve the multiobjective dispatching problem of emergency supplies for earthquakes.Wang [35] proposed a multipath routing algorithm for wireless sensor networks based on genetic algorithm. In order to overcome the problem that genetic algorithm and ant colony optimization algorithm tend to stagnate due to early-maturing, Liang and Wang [36] combined these two algorithms to form a hybrid algorithm and applied it into marine investigation path planning. Zhao et al. [37] designed an improved fast nondominated sorting genetic algorithm for solving a multiobjective bilevel programming model of logistics system path planning. Liu et al. [38] integrated the neighborhood operator into the discrete bat algorithm and used the improved algorithm to solve the multipoint shortest path planning problem. Wu et al. [39, 40] provided a comprehensive review of population-based metaheuristic algorithms and their applications to motion planning of aircraft and used a clustering improved ant colony optimization algorithm to solve the multipath planning problem for drone operations.Yang et al. [41] used an improved particle swarm optimization algorithm based on sorting selection to solve the problem of traffic induced evacuation in large public places under emergency conditions. Tian et al. [42] redesigned pheromone update rules and ant transfer rules and proposed a capacity-constrained evacuation model based on the improved ant colony optimization algorithm. Jabari et al. [43] proposed a genetic algorithm for solving a phased emergency traffic evacuation model. Ma et al. [44] proposed a temporary traffic control method during emergency rescue and get the optimal control plans based on genetic algorithm.


## 2.3. Analysis of Related Work

In terms of modeling, models that consider dynamic changes in road conditions are clearly more suitable for solving the emergency vehicle path planning and dispatching problem in urban road networks. The existing dynamic models are mainly divided into three categories. The first type is based on real-time road condition information, which usually makes initial decisions based on the information at the current moment and then adjusts the path and dispatching strategies at key moments or key nodes according to the new information obtained constantly. The static model is actually used in each decision stage. The second type is based on predicted road conditions. It first predicts the change of road condition during the decision process based on experience or historical big data and then constructs a dynamic model for decision-making. It can also be combined with the first type of model to adjust the strategy in real time. The third type uses the probability distribution of road condition information to construct stochastic programming models. Also, it can be combined with the first type of model.In fact, the above three methods are based on the estimated values of the actual road conditions. However, when the road conditions are bad, it is difficult for emergency vehicles to reach the designated location within the valid rescue time, even if the shortest path is adopted. Therefore, it is necessary to use traffic evacuation measures to fundamentally improve the road conditions of the road sections through which the emergency vehicles pass. To this end, a new model framework is constructed. First of all, the shortest path model, which is currently commonly used to solve this problem, is extended to multiple paths with the aim of obtaining multiple optimal paths available for emergency vehicles. Then, a dynamic traffic evacuation model based on real-time information is used to make evacuation control for the background traffic on the alternative paths, so as to shorten the traveling time of emergency vehicles. Finally, the one with the shortest travel time after evacuation is selected as the final path.The common algorithms for solving emergency vehicle dispatching and path planning include genetic algorithm, particle swarm optimization algorithm, and ant colony optimization algorithm, as well as their modifications [40]. Salp swarm algorithm, proposed by Mirjalili in 2017, is a new swarm optimization method, which simulates the swarming behavior of salps [45]. In nature, many organisms are distributed in groups, but salps move in chains. The leader in the salp swarm is at the head of the chain, and it only affects the second one that follows it. Similarly, when updating the position, the latter salp is only affected by the former one. This behavior can reduce the influence of leaders gradually, thus ensuring the diversity of the population.The adoption of the self-adapting operator makes the SSA algorithm effectively balance the exploration and development, which increases the chances of obtaining a globally optimal solution. The chain moving and self-adapting mechanisms of the algorithm give it a high degree of exploration and the ability to avoid local optimum. Comparing the SSA algorithm with well-known and new algorithms such as PSO, GSA, BA, FPA, SMS, FA, and GA, the results show that the SSA algorithm outperforms the others in most of the test functions [45]. Due to this advantage of the SSA, it has been used in various fields such as feature selection, training neural networks, scheduling, control of power systems, and renewable energy systems [46–48]. In view of the excellent global optimization ability of the SSA, this paper tries to apply it to solve the path planning and traffic evacuation model.


## 3. Problem Statement and Modeling

According to graph theory, traffic network can be represented as a graph. We suppose that all dispatched emergency vehicles can arrive at the accident locations over a period of timeT. With an interval of τ, T is divided into several periods. The t-th period is defined as the instant t. In addition, a directed time-varying road network model G=N,E,W is built, where N is the node set, and ni∈N is the i-th node. E is the link set, and ei,j=ni,nj is a link (i.e., road section) between ni and nj. W is the link weight set, and wi,j=li,j,vi,jt,mi,jt,ri,jt,Ti,jt is the weight vector of ei,j, in which li,j is the length of ei,j. vi,jt, mi,jt and ri,jt respectively represent the travel speed, traffic load, and traffic demand at the instant t. Ti,jt is the travel time, and it represents the time for the emergency vehicle, leaving at the instant t, traveling from node ni to nj. The k-th emergency vehicle is expressed as ck,k=1,2,…,K, and all of them form a set C. O accidents happened at the instant t0 form a set A, and the o-th accident is ao. The locations of ck and ao are nkc and noa.


### 3.1. Decision-Making Process of Emergency Vehicle Path Planning and Traffic Evacuation

As shown in Figure1, the decision-making process includes two stages: alternative path planning and traffic evacuation.Figure 1
Decision-making process of emergency vehicle path planning and traffic evacuation.


#### 3.1.1. The First Stage: Alternative Path Planning

This stage is targeted at obtaining the firstD shortest paths for each emergency vehicle to each accident location. Traffic evacuation can keep a high speed of emergency vehicles; in this situation, the travel time mainly depends on the length of the path. Accordingly, li,j of ei,j is taken as the link weight, and the first D shortest paths from nkc to noa are calculated. These D paths form an alternative path set Pk,o, and the d-th path is expressed as pk,od.


#### 3.1.2. The Second Stage: Traffic Evacuation

In this stage, some of the traffic volumes on the alternative path are assigned to other road sections over a certain period. We are aiming at shortening hours for the emergency vehicle to pass through the alternative path. At the same time, we try to avoid the adverse impact on traffics. Two types of road sections are defined as follows:


#### 3.1.3. Road Sections of the Alternative Path

The alternative pathpk,od consists of road sections ek,o,d=nik,o,d,njk,o,d∈Ek,o,d, and they are defined as road sections of pk,od. The weight vector of ek,o,d is wek,o,d=lek,o,d,vek,o,dt,mek,o,dt,rek,o,dt,Tek,o,dt, where lek,o,d is the length of ek,o,d. vek,o,dt, mek,o,dt, rek,o,dt and Tek,o,dt are, respectively, the travel speed, traffic load, traffic demand, and travel time at the instant t.


#### 3.1.4. Adjacent Road Sections of the Alternative Path

Other road sections starting from the nodenik,o,d are described as adjacent road sections of ek,o,d. We represent these adjacent road sections as fe,ik,o,d∈Fe,ik,o,d, of which weight vector is wf,e,ik,o,d=lf,e,ik,o,d,vf,e,ik,o,dt,mf,e,ik,o,dt,rf,e,ik,o,dt, where lf,e,ik,o,d is the length of fe,ik,o,d. vf,e,ik,o,dt, mf,e,ik,o,dt, and rf,e,ik,o,dt are, respectively, the travel speed, traffic load, and traffic demand at the instant t.Finally, after getting the after-evacuation travel time of each alternative path, we select the one with the shortest travel time as the optimal path for the emergency vehicle.


### 3.2. Alternative Path Planning Modeling

#### 3.2.1. Decision Vector

The decision vector of the alternative path planning problem is a node sequence from the starting nodenkc to the ending node noa. For example, the node sequence n1c,n2,n4,n1a represents that the vehicle c1 starts from the node n1c, passes through nodes n2 and n4 in sequence, and finally arrives at the node n1a.


#### 3.2.2. Objective Function

We are aiming at minimizing the length of pathpk,o=nkc,…,ni,nj,…,noa from each node nkc,k=1,2,...,K to each node noa,o=1,2,…,O. All the road sections of path pk,o form a set Ek,o, and the length of pk,o equals the total length of all the road sections ei,j=ni,nj∈Ek,o. The objective function of the alternative path planning model is to get the first D paths with the minimum length.(1)min∑ei,j∈Ek,oli,j,∀ck∈C,∀ao∈A.


#### 3.2.3. Constraint Conditions

The emergency vehiclec1 starts from the node n1c, passes through all the nodes of the path pk,o in sequence, and finally arrives at the node n1a. The adjacent nodes ni and nj are connected by the road section ei,j∈E, and all the nodes of the path pk,o are different. The constraint conditions of the model are(2)nkc,…,ni,nj,…,noa∈N,(3)nkc≠⋯≠ni≠nj≠⋯≠noa,(4)ei,j=ni,nj∈E,Equation (2) shows that nkc,…,ni,nj,…,noa are the nodes in the road network.Equation (3) indicates that nodes nkc,…,ni,nj,…,noa are different.Equation (4) indicates that adjacent nodes are connected in turn to form a path.


### 3.3. Traffic Evacuation Modeling

#### 3.3.1. Decision Variables

We suppose that the instant when the emergency vehicleck enters the road section ek,o,d after traffic evacuation is te,ik,o,d. Traffic demands of ek,o,d are distributed to ek,o,d and its adjacent road sections fe,ik,o,d∈Fe,ik,o,d over a period of time tsek,o,d=to,te,ik,o,d. The decision variables of the traffic evacuation problem are two types of inflow rates uek,o,dt and uf,e,ik,o,dt, and they represent inflow rates of ek,o,d and fe,ik,o,d at the instant t∈tsek,o,d individually.


#### 3.3.2. Objective Function

We are targeting minimizing the timeTek,o,dte,ik,o,d for an emergency vehicle ck, entering at the instant te,ik,o,d, traveling through the road section ek,o,d of pk,od∈Pk,o. The objective function of the traffic evacuation model is(5)minTek,o,dte,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d,(6)te,ik,o,d=te−1,ik,o,d+Te−1k,o,dte−1,ik,o,d,nik,o,d≠nkc,to,nik,o,d=nkc.Equation (6) calculates the instant te,ik,o,d when the emergency vehicle ck enters the road section ek,o,d, where te−1,ik,o,d is the instant when the vehicle enters the previous road section of ek,o,d on the path pk,od, and the travel time of this road section is Te−1k,o,dt.


#### 3.3.3. Constraint Conditions

(1) Evacuation Impact Constraint. Traffic congestion is easy to cause drivers to have negative moods. Traffic congestion index (TCI) can indicate drivers’ feelings about changes in road conditions. When speed changes in the range of a certain traffic congestion index, drivers do not feel this change obviously, so we use TCI to measure the impact of evacuation on background traffic. According to the classification standard adopted by the Beijing Municipal Commission of Transport (BMCT), TCI is divided into five levels. Based on real-time data of TCI published on the website of BMCT, the speed range of each level is obtained as shown in Table 1.Table 1
Traffic congestion index.
LevelLower speed (km/h)Upper speed (km/h)147.0580.00238.7047.05330.4038.70423.5530.40518.5523.55For eachfe,ik,o,d, we calculate its average speed avf,e,ik,o,d′ in the period tsek,o,d before traffic evacuation, look up TCI level of avf,e,ik,o,d′ in Table 1, and then get the lower speed dvf,e,ik,o,d of this TCI level. During traffic evacuation, we try to ensure that the average speed avf,e,ik,o,d is not slower than dvf,e,ik,o,d. The evacuation impact constraint of the model is(7)avf,e,ik,o,d≥dvf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.If the constraint condition cannot be satisfied, the lower speed will be reduced by one level, and so on until this constraint condition is satisfied.(2) Evacuation Requirement Constraint. At the instant t, it is to ensure that the total inflow rates distributed to ek,o,d and fe,ik,o,d is greater than the traffic demand of ek,o,d.(8)uek,o,dt+∑fe,ik,o,d∈Fe,ik,o,duf,e,ik,o,dt≥rek,o,dt,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.(3) Flow Conservation Constraints. (9)mek,o,dt+1=mek,o,dt+uek,o,dt−hek,o,dt,where hek,o,dt is the outflow rate of ek,o,d at the instant t.(10)mf,e,ik,o,dt+1=mf,e,ik,o,dt+uf,e,ik,o,dt+rf,e,ik,o,dt−hf,e,ik,o,dt,where hf,e,ik,o,dt is the outflow rate of fe,ik,o,d at the instant t. uf,e,ik,o,dt is the inflow rate evacuated from ek,o,d to fe,ik,o,d at the instant t.Vehicles, enteringek,o,d at the instant t, will drive out at the instant t+Tek,o,dt.(11)uek,o,dt=hek,o,dt+Tek,o,dt.(4) Calculation of the Travel Speed and Travel Time. (12)vek,o,dt=vek,o,d∗×1−mek,o,dtmek,o,d∗.where vek,o,d∗ is maximum travel speed of ek,o,d, and mek,o,d∗ is maximum traffic load of ek,o,d.(13)Tek,o,dt=lek,o,dvek,o,dt,vf,e,ik,o,dt=vf,e,ik,o,d∗×1−mf,e,ik,o,dtmf,e,ik,o,d∗.where vf,e,ik,o,d∗ is maximum travel speed of fe,ik,o,d and mf,e,ik,o,d∗ is maximum traffic load of fe,ik,o,d.(5) Evacuation Direction Constraint. We set that traffic demands of ek,o,d can only be evacuated to the road section of which the included angle with ek,o,d is less than ξ.


## 3.1. Decision-Making Process of Emergency Vehicle Path Planning and Traffic Evacuation

As shown in Figure1, the decision-making process includes two stages: alternative path planning and traffic evacuation.Figure 1
Decision-making process of emergency vehicle path planning and traffic evacuation.


### 3.1.1. The First Stage: Alternative Path Planning

This stage is targeted at obtaining the firstD shortest paths for each emergency vehicle to each accident location. Traffic evacuation can keep a high speed of emergency vehicles; in this situation, the travel time mainly depends on the length of the path. Accordingly, li,j of ei,j is taken as the link weight, and the first D shortest paths from nkc to noa are calculated. These D paths form an alternative path set Pk,o, and the d-th path is expressed as pk,od.


### 3.1.2. The Second Stage: Traffic Evacuation

In this stage, some of the traffic volumes on the alternative path are assigned to other road sections over a certain period. We are aiming at shortening hours for the emergency vehicle to pass through the alternative path. At the same time, we try to avoid the adverse impact on traffics. Two types of road sections are defined as follows:


### 3.1.3. Road Sections of the Alternative Path

The alternative pathpk,od consists of road sections ek,o,d=nik,o,d,njk,o,d∈Ek,o,d, and they are defined as road sections of pk,od. The weight vector of ek,o,d is wek,o,d=lek,o,d,vek,o,dt,mek,o,dt,rek,o,dt,Tek,o,dt, where lek,o,d is the length of ek,o,d. vek,o,dt, mek,o,dt, rek,o,dt and Tek,o,dt are, respectively, the travel speed, traffic load, traffic demand, and travel time at the instant t.


### 3.1.4. Adjacent Road Sections of the Alternative Path

Other road sections starting from the nodenik,o,d are described as adjacent road sections of ek,o,d. We represent these adjacent road sections as fe,ik,o,d∈Fe,ik,o,d, of which weight vector is wf,e,ik,o,d=lf,e,ik,o,d,vf,e,ik,o,dt,mf,e,ik,o,dt,rf,e,ik,o,dt, where lf,e,ik,o,d is the length of fe,ik,o,d. vf,e,ik,o,dt, mf,e,ik,o,dt, and rf,e,ik,o,dt are, respectively, the travel speed, traffic load, and traffic demand at the instant t.Finally, after getting the after-evacuation travel time of each alternative path, we select the one with the shortest travel time as the optimal path for the emergency vehicle.


## 3.1.1. The First Stage: Alternative Path Planning

This stage is targeted at obtaining the firstD shortest paths for each emergency vehicle to each accident location. Traffic evacuation can keep a high speed of emergency vehicles; in this situation, the travel time mainly depends on the length of the path. Accordingly, li,j of ei,j is taken as the link weight, and the first D shortest paths from nkc to noa are calculated. These D paths form an alternative path set Pk,o, and the d-th path is expressed as pk,od.


## 3.1.2. The Second Stage: Traffic Evacuation

In this stage, some of the traffic volumes on the alternative path are assigned to other road sections over a certain period. We are aiming at shortening hours for the emergency vehicle to pass through the alternative path. At the same time, we try to avoid the adverse impact on traffics. Two types of road sections are defined as follows:


## 3.1.3. Road Sections of the Alternative Path

The alternative pathpk,od consists of road sections ek,o,d=nik,o,d,njk,o,d∈Ek,o,d, and they are defined as road sections of pk,od. The weight vector of ek,o,d is wek,o,d=lek,o,d,vek,o,dt,mek,o,dt,rek,o,dt,Tek,o,dt, where lek,o,d is the length of ek,o,d. vek,o,dt, mek,o,dt, rek,o,dt and Tek,o,dt are, respectively, the travel speed, traffic load, traffic demand, and travel time at the instant t.


## 3.1.4. Adjacent Road Sections of the Alternative Path

Other road sections starting from the nodenik,o,d are described as adjacent road sections of ek,o,d. We represent these adjacent road sections as fe,ik,o,d∈Fe,ik,o,d, of which weight vector is wf,e,ik,o,d=lf,e,ik,o,d,vf,e,ik,o,dt,mf,e,ik,o,dt,rf,e,ik,o,dt, where lf,e,ik,o,d is the length of fe,ik,o,d. vf,e,ik,o,dt, mf,e,ik,o,dt, and rf,e,ik,o,dt are, respectively, the travel speed, traffic load, and traffic demand at the instant t.Finally, after getting the after-evacuation travel time of each alternative path, we select the one with the shortest travel time as the optimal path for the emergency vehicle.


## 3.2. Alternative Path Planning Modeling

### 3.2.1. Decision Vector

The decision vector of the alternative path planning problem is a node sequence from the starting nodenkc to the ending node noa. For example, the node sequence n1c,n2,n4,n1a represents that the vehicle c1 starts from the node n1c, passes through nodes n2 and n4 in sequence, and finally arrives at the node n1a.


### 3.2.2. Objective Function

We are aiming at minimizing the length of pathpk,o=nkc,…,ni,nj,…,noa from each node nkc,k=1,2,...,K to each node noa,o=1,2,…,O. All the road sections of path pk,o form a set Ek,o, and the length of pk,o equals the total length of all the road sections ei,j=ni,nj∈Ek,o. The objective function of the alternative path planning model is to get the first D paths with the minimum length.(1)min∑ei,j∈Ek,oli,j,∀ck∈C,∀ao∈A.


### 3.2.3. Constraint Conditions

The emergency vehiclec1 starts from the node n1c, passes through all the nodes of the path pk,o in sequence, and finally arrives at the node n1a. The adjacent nodes ni and nj are connected by the road section ei,j∈E, and all the nodes of the path pk,o are different. The constraint conditions of the model are(2)nkc,…,ni,nj,…,noa∈N,(3)nkc≠⋯≠ni≠nj≠⋯≠noa,(4)ei,j=ni,nj∈E,Equation (2) shows that nkc,…,ni,nj,…,noa are the nodes in the road network.Equation (3) indicates that nodes nkc,…,ni,nj,…,noa are different.Equation (4) indicates that adjacent nodes are connected in turn to form a path.


## 3.2.1. Decision Vector

The decision vector of the alternative path planning problem is a node sequence from the starting nodenkc to the ending node noa. For example, the node sequence n1c,n2,n4,n1a represents that the vehicle c1 starts from the node n1c, passes through nodes n2 and n4 in sequence, and finally arrives at the node n1a.


## 3.2.2. Objective Function

We are aiming at minimizing the length of pathpk,o=nkc,…,ni,nj,…,noa from each node nkc,k=1,2,...,K to each node noa,o=1,2,…,O. All the road sections of path pk,o form a set Ek,o, and the length of pk,o equals the total length of all the road sections ei,j=ni,nj∈Ek,o. The objective function of the alternative path planning model is to get the first D paths with the minimum length.(1)min∑ei,j∈Ek,oli,j,∀ck∈C,∀ao∈A.


## 3.2.3. Constraint Conditions

The emergency vehiclec1 starts from the node n1c, passes through all the nodes of the path pk,o in sequence, and finally arrives at the node n1a. The adjacent nodes ni and nj are connected by the road section ei,j∈E, and all the nodes of the path pk,o are different. The constraint conditions of the model are(2)nkc,…,ni,nj,…,noa∈N,(3)nkc≠⋯≠ni≠nj≠⋯≠noa,(4)ei,j=ni,nj∈E,Equation (2) shows that nkc,…,ni,nj,…,noa are the nodes in the road network.Equation (3) indicates that nodes nkc,…,ni,nj,…,noa are different.Equation (4) indicates that adjacent nodes are connected in turn to form a path.


## 3.3. Traffic Evacuation Modeling

### 3.3.1. Decision Variables

We suppose that the instant when the emergency vehicleck enters the road section ek,o,d after traffic evacuation is te,ik,o,d. Traffic demands of ek,o,d are distributed to ek,o,d and its adjacent road sections fe,ik,o,d∈Fe,ik,o,d over a period of time tsek,o,d=to,te,ik,o,d. The decision variables of the traffic evacuation problem are two types of inflow rates uek,o,dt and uf,e,ik,o,dt, and they represent inflow rates of ek,o,d and fe,ik,o,d at the instant t∈tsek,o,d individually.


### 3.3.2. Objective Function

We are targeting minimizing the timeTek,o,dte,ik,o,d for an emergency vehicle ck, entering at the instant te,ik,o,d, traveling through the road section ek,o,d of pk,od∈Pk,o. The objective function of the traffic evacuation model is(5)minTek,o,dte,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d,(6)te,ik,o,d=te−1,ik,o,d+Te−1k,o,dte−1,ik,o,d,nik,o,d≠nkc,to,nik,o,d=nkc.Equation (6) calculates the instant te,ik,o,d when the emergency vehicle ck enters the road section ek,o,d, where te−1,ik,o,d is the instant when the vehicle enters the previous road section of ek,o,d on the path pk,od, and the travel time of this road section is Te−1k,o,dt.


### 3.3.3. Constraint Conditions

(1) Evacuation Impact Constraint. Traffic congestion is easy to cause drivers to have negative moods. Traffic congestion index (TCI) can indicate drivers’ feelings about changes in road conditions. When speed changes in the range of a certain traffic congestion index, drivers do not feel this change obviously, so we use TCI to measure the impact of evacuation on background traffic. According to the classification standard adopted by the Beijing Municipal Commission of Transport (BMCT), TCI is divided into five levels. Based on real-time data of TCI published on the website of BMCT, the speed range of each level is obtained as shown in Table 1.Table 1
Traffic congestion index.
LevelLower speed (km/h)Upper speed (km/h)147.0580.00238.7047.05330.4038.70423.5530.40518.5523.55For eachfe,ik,o,d, we calculate its average speed avf,e,ik,o,d′ in the period tsek,o,d before traffic evacuation, look up TCI level of avf,e,ik,o,d′ in Table 1, and then get the lower speed dvf,e,ik,o,d of this TCI level. During traffic evacuation, we try to ensure that the average speed avf,e,ik,o,d is not slower than dvf,e,ik,o,d. The evacuation impact constraint of the model is(7)avf,e,ik,o,d≥dvf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.If the constraint condition cannot be satisfied, the lower speed will be reduced by one level, and so on until this constraint condition is satisfied.(2) Evacuation Requirement Constraint. At the instant t, it is to ensure that the total inflow rates distributed to ek,o,d and fe,ik,o,d is greater than the traffic demand of ek,o,d.(8)uek,o,dt+∑fe,ik,o,d∈Fe,ik,o,duf,e,ik,o,dt≥rek,o,dt,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.(3) Flow Conservation Constraints. (9)mek,o,dt+1=mek,o,dt+uek,o,dt−hek,o,dt,where hek,o,dt is the outflow rate of ek,o,d at the instant t.(10)mf,e,ik,o,dt+1=mf,e,ik,o,dt+uf,e,ik,o,dt+rf,e,ik,o,dt−hf,e,ik,o,dt,where hf,e,ik,o,dt is the outflow rate of fe,ik,o,d at the instant t. uf,e,ik,o,dt is the inflow rate evacuated from ek,o,d to fe,ik,o,d at the instant t.Vehicles, enteringek,o,d at the instant t, will drive out at the instant t+Tek,o,dt.(11)uek,o,dt=hek,o,dt+Tek,o,dt.(4) Calculation of the Travel Speed and Travel Time. (12)vek,o,dt=vek,o,d∗×1−mek,o,dtmek,o,d∗.where vek,o,d∗ is maximum travel speed of ek,o,d, and mek,o,d∗ is maximum traffic load of ek,o,d.(13)Tek,o,dt=lek,o,dvek,o,dt,vf,e,ik,o,dt=vf,e,ik,o,d∗×1−mf,e,ik,o,dtmf,e,ik,o,d∗.where vf,e,ik,o,d∗ is maximum travel speed of fe,ik,o,d and mf,e,ik,o,d∗ is maximum traffic load of fe,ik,o,d.(5) Evacuation Direction Constraint. We set that traffic demands of ek,o,d can only be evacuated to the road section of which the included angle with ek,o,d is less than ξ.


## 3.3.1. Decision Variables

We suppose that the instant when the emergency vehicleck enters the road section ek,o,d after traffic evacuation is te,ik,o,d. Traffic demands of ek,o,d are distributed to ek,o,d and its adjacent road sections fe,ik,o,d∈Fe,ik,o,d over a period of time tsek,o,d=to,te,ik,o,d. The decision variables of the traffic evacuation problem are two types of inflow rates uek,o,dt and uf,e,ik,o,dt, and they represent inflow rates of ek,o,d and fe,ik,o,d at the instant t∈tsek,o,d individually.


## 3.3.2. Objective Function

We are targeting minimizing the timeTek,o,dte,ik,o,d for an emergency vehicle ck, entering at the instant te,ik,o,d, traveling through the road section ek,o,d of pk,od∈Pk,o. The objective function of the traffic evacuation model is(5)minTek,o,dte,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d,(6)te,ik,o,d=te−1,ik,o,d+Te−1k,o,dte−1,ik,o,d,nik,o,d≠nkc,to,nik,o,d=nkc.Equation (6) calculates the instant te,ik,o,d when the emergency vehicle ck enters the road section ek,o,d, where te−1,ik,o,d is the instant when the vehicle enters the previous road section of ek,o,d on the path pk,od, and the travel time of this road section is Te−1k,o,dt.


## 3.3.3. Constraint Conditions

(1) Evacuation Impact Constraint. Traffic congestion is easy to cause drivers to have negative moods. Traffic congestion index (TCI) can indicate drivers’ feelings about changes in road conditions. When speed changes in the range of a certain traffic congestion index, drivers do not feel this change obviously, so we use TCI to measure the impact of evacuation on background traffic. According to the classification standard adopted by the Beijing Municipal Commission of Transport (BMCT), TCI is divided into five levels. Based on real-time data of TCI published on the website of BMCT, the speed range of each level is obtained as shown in Table 1.Table 1
Traffic congestion index.
LevelLower speed (km/h)Upper speed (km/h)147.0580.00238.7047.05330.4038.70423.5530.40518.5523.55For eachfe,ik,o,d, we calculate its average speed avf,e,ik,o,d′ in the period tsek,o,d before traffic evacuation, look up TCI level of avf,e,ik,o,d′ in Table 1, and then get the lower speed dvf,e,ik,o,d of this TCI level. During traffic evacuation, we try to ensure that the average speed avf,e,ik,o,d is not slower than dvf,e,ik,o,d. The evacuation impact constraint of the model is(7)avf,e,ik,o,d≥dvf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.If the constraint condition cannot be satisfied, the lower speed will be reduced by one level, and so on until this constraint condition is satisfied.(2) Evacuation Requirement Constraint. At the instant t, it is to ensure that the total inflow rates distributed to ek,o,d and fe,ik,o,d is greater than the traffic demand of ek,o,d.(8)uek,o,dt+∑fe,ik,o,d∈Fe,ik,o,duf,e,ik,o,dt≥rek,o,dt,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,d.(3) Flow Conservation Constraints. (9)mek,o,dt+1=mek,o,dt+uek,o,dt−hek,o,dt,where hek,o,dt is the outflow rate of ek,o,d at the instant t.(10)mf,e,ik,o,dt+1=mf,e,ik,o,dt+uf,e,ik,o,dt+rf,e,ik,o,dt−hf,e,ik,o,dt,where hf,e,ik,o,dt is the outflow rate of fe,ik,o,d at the instant t. uf,e,ik,o,dt is the inflow rate evacuated from ek,o,d to fe,ik,o,d at the instant t.Vehicles, enteringek,o,d at the instant t, will drive out at the instant t+Tek,o,dt.(11)uek,o,dt=hek,o,dt+Tek,o,dt.(4) Calculation of the Travel Speed and Travel Time. (12)vek,o,dt=vek,o,d∗×1−mek,o,dtmek,o,d∗.where vek,o,d∗ is maximum travel speed of ek,o,d, and mek,o,d∗ is maximum traffic load of ek,o,d.(13)Tek,o,dt=lek,o,dvek,o,dt,vf,e,ik,o,dt=vf,e,ik,o,d∗×1−mf,e,ik,o,dtmf,e,ik,o,d∗.where vf,e,ik,o,d∗ is maximum travel speed of fe,ik,o,d and mf,e,ik,o,d∗ is maximum traffic load of fe,ik,o,d.(5) Evacuation Direction Constraint. We set that traffic demands of ek,o,d can only be evacuated to the road section of which the included angle with ek,o,d is less than ξ.


## 4. Solution for the Model

### 4.1. Basic Principle of Salp Swarm Algorithm

The populationS consists of Q salps including leaders and followers. In B-dimensional space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B of each salp sq,q=1,2,…,Q represents a feasible solution of the optimization problem. Each position Xq corresponds to a performance function value YXq related to the optimization objective. We suppose that there is a food source Φ=ϕ1,ϕ2,…,ϕb,…,ϕB in the search space.


#### 4.1.1. Rules for Updating the Leader’s Position

The upper and lower bounds of the search space areα=α1,α2,…,αb,…,αB and β=β1,β2,…,βb,…,βB. The rules for position updating of the leader S1 are shown in (14)xb1φ=ϕbφ−1+λ1×λ2×αb−βb+βbλ3≥0.5ϕbφ−1−λ1×λ2×αb−βb+βbλ3<0.5,b=1,2,…,B,where φ is the current iteration. xb1φ is the position of the leader S1 in the b-th dimension after the φ-th iteration. ϕbφ−1 shows the position of the food source in the b-th dimension after the φ−1-th iteration. λ2,λ3∈0,1 are random variables with uniform distribution. The parameter λ1 is called the convergence factor (or self-adapting operator). It balances the exploration and exploitation of the leader. λ1 can be obtained from (15)λ1=2×e−4×φ/Ψ2,where Ψ is the maximum number of iterations.


#### 4.1.2. Rules for Updating the Follower’s Position

The rules for position updating of the followerSg are shown in (16)xbgφ=xbgφ−1+xbg−1φ−12,where xbgφ is the position of the follower Sg in the b-th dimension after the φ-th iteration. xbgφ−1 and xbg−1φ−1 show the position of the followers Sg and Sg−1 in the b-th dimension after the φ−1-th iteration.


### 4.2. Solution for the Alternative Path Planning Model Based on Hybrid Salp Swarm Algorithm

The solution of the model needs to obtain multiple relatively optimal solutions as alternatives. It benefits from the chain movement mode of SSA, which ensures the diversity of the population more effectively than the general with swarm movement behavior, thus avoiding the case that the algorithm converges too quickly to a single optimal solution. This means that SSA is easier to obtain multiple relatively optimal solutions. It can be seen that the SSA algorithm is more suitable for solving the alternative path planning model in this paper.The decision vectors of the alternative path planning model are sequences of nodes that meet the path connectivity constraints. If we use updating rules of equations (14)–(16), a large number of invalid solutions will be generated, which will have repercussions for the performance of the algorithm. Therefore, based on the implementation steps of the SSA, we redefine the encoding plan and the position updating rules and design an algorithm applicable to solve the alternative path planning model. Furthermore, combining it with Dijkstra algorithm to improve its performance.


#### 4.2.1. Encoding

The decision vector of the problem is encoded as a positive integer vector. For example, the decision vectorn1c,n2,n4,…,n1a can be encoded as n1c,2,4,…,n1a.For any nodeni, if node nj satisfies ni,nj∈E, then nj is defined as the adjacent node of ni. All the adjacent nodes of ni form a set ρi. The random adjacent node search strategy is used to ensure that adjacent nodes are connected to form a path. Its implementation steps are as follows:Step 1. Suppose that the current path sequence is ω=nkc,…,ni. CNω is the complement set of ω. Randomly select a node nj from the set ρi∩CNω, and update the current path sequence to ω=nkc,…,ni,nj.Step 2. Repeat Step 1 until the node noa is found, and then the coding of a salp is obtained.


#### 4.2.2. Rules for Updating the Leader’s Position

At theφ−1-th iteration, the position of the food source is Φφ−1=nkc,…,niϕφ−1,njϕφ−1,…,noa which represents a path from node nkc to noa. Similarly, X1φ−1=nkc,…,ni1φ−1,nj1φ−1,…,noa is the position of the leader. Rules for updating the leader’s position are as follows:Step 1. Randomly select a node niϕφ−1 from Φφ−1.Step 2. Update position of X1 according to λ11, where λ11∈0,1 is a random variable with uniform distribution.ifλ11<0.5Use the random adjacent node search strategy to generate a path fragment fromniϕφ−1 to noa, and then replace niϕφ−1,njϕφ−1,…,noa in Φφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ at the φ-th iteration.elseGenerate a path fragment fromnkc to niϕφ−1, and then replace nkc,…,niϕφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ.end


#### 4.2.3. Rules for Updating the Follower’s Position

The position of theg-th follower is Xgφ−1=nkc,…,nigφ−1,njgφ−1,…,noa. Xg−1φ−1=nkc,…,nig−1φ−1,njg−1φ−1,…,noa shows the position of the g−1 -th follower. Determine the start position for updating Xgφ−1 according to λ12, and then update its position according to λ13, where λ12,λ13∈0,1 are random variables with uniform distribution. Rules for updating the follower’s position are as follows:ifλ12<0.5Randomly select a nodenigφ−1 from Xgφ−1.ifλ13<0.5Generate a path fragment fromnigφ−1 to noa, and then replace nigφ−1,njgφ−1,…,noa in Xgφ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nigφ−1, and then replace nkc,...,nigφ−1 in Xgφ−1 with the path fragment to form a new position Xgφ.endelseRandomly select a nodenig−1φ−1 from Xg−1φ−1.ifλ13<0.5Generate a path fragment fromnig−1φ−1 to noa, and then replace nig−1φ−1,njg−1φ−1,…,noa in Xg−1φ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nig−1φ−1, and then replace nkc,…,nig−1φ−1 in Xg−1φ−1 with the path fragment to form a new position Xgφ.endend


#### 4.2.4. Performance Function

The performance function is related to the objective function of the alternative path planning model:(17)y1=−∑ei,j∈Ek,oli,j∀ck∈C,∀ao∈A.


#### 4.2.5. Implementation Steps of the Hybrid Algorithm for Solving the Alternative Path Planning Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is generated to form the population S. Positions of the first Q−1 salps are randomly generated according to the encoding plan shown in ‘4.2.1 Encoding’ of this section, and the position of the Q-th salp is the optimal solution obtained by Dijkstra algorithm.Step 2. Calculate the initial performance values, and select the food source. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ.Step 3. Select leaders and followers. To balance the randomness and stability of the algorithm, the top Tq salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 4. Update the position of each salp. The positions of leaders are updated according to the rules shown in ‘4.2.2 Rules for updating the leader’s position’ of this section. The positions of followers are updated according to the rules shown in ‘4.2.3 Rules for updating the follower’s position’ of this section.Step 5. Calculate the performance values, and update the food source position. The performance value of the current food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 6. Repeat Steps 4–5 until the max number of iterations ψ is completed. Output the position of the food source and its performance value.


### 4.3. Solution for the Traffic Evacuation Model Based on Improved Salp Swarm Algorithm

Different from the alternative path planning model, the solution of the traffic evacuation model only needs to obtain a unique optimal plan. This requires the algorithm to explore extensively the feasible search space and converge to the optimal solution in a short time. Therefore, this paper proposes an improved algorithm by adding the steps of population grouping and mixing on the basis of SSA. This algorithm enhances exploration ability through the parallel movement of multiple salp chains, which effectively improves its performance.


#### 4.3.1. Encoding

The decision variables of the problem consist of inflow ratesuek,o,dt and uf,e,ik,o,dt. In order to facilitate actual traffic control, we assume that inflow rates are fixed during the period tsek,o,d. The salp position coding can be expressed as(18)uq=uek,o,d,uf,e,ik,o,d.


#### 4.3.2. Performance Function

The performance function is related to the objective function (5) and the constraint condition (7). For salps that do not satisfy the constraint (8), their performance function values are infinitesimal.(19)y2=−Tek,o,dte,ik,o,d+∑fe,ik,o,d∈Fe,ik,o,dMM×max0,dvf,e,ik,o,d−avf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,dwhere MM is a very large number.


#### 4.3.3. Population Grouping Strategy

In the basic salp swarm algorithm, the population will move in a chain towards the food source position, and this single chain has a low search efficiency and limited search area. Therefore, this paper groups the population to form multiple subgroups and enhances exploration ability through the parallel movement of multiple chains, so as to increase the possibility of obtaining the global optimal solution while improving the calculation speed. The grouping strategy is defined as follows.TheQ salps in population S are ranked in descending order of their fitness values, and the set of sorted positions is X′=X1′,X2′,…,Xq′,…,XQ′. According to equation (20), Q salps are divided equally into GN subgroups, and the number of salps in each subgroup is GM.(20)GxGn,Gm=XGn′Gm=1XGm×GN−Gn+1′Gm=2,3,…,GM,Gn=1,2,…,GN.where GxGn,Gm is the position of the Gm-th salp in the Gn-th subgroup.We assume that the total number of salps isQ=12, the number of subgroups is GN=3, and the positions of the sorted salps are shown in Table 2.Table 2
Positions of the sorted salps.
X1′X2′X3′X4′X5′X6′X7′X8′X9′X10′X11′X12′According to the grouping strategy shown in equation (20), individuals in each subgroup are shown in Table 3.Table 3
Salps in each subgroup.
1st subgroupGx1,1=X1′Gx1,2=X6′Gx1,3=X9′Gx1,4=X12′2nd subgroupGx2,1=X2′Gx2,2=X5′Gx2,3=X8′Gx2,4=X11′3rd subgroupGx3,1=X3′Gx3,2=X4′Gx3,3=X7′Gx3,4=X10′The above grouping strategy makes each subgroup contain individuals with better and worse fitness, which ensures the diversity of individuals in the subgroup. At the same time, the average fitness of salps in each subgroup is similar to that in other subgroups, which makes the superiority and inferiority of the initial individuals more balanced among the subgroups.


#### 4.3.4. Implementation Steps of the Improved Algorithm for Solving the Traffic Evacuation Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is randomly generated to form the population S.Step 2. Calculate the performance values, and select the food source of the population. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ of the population.Step 3. Group the population and optimize in subgroups. The Q salps are divided into GN subgroups according to equation (20), and the optimal salp within each subgroup is marked as its food source position GΦ. Perform the following steps for each subgroup:Step 3.1. Select leaders and followers of the subgroup. To balance the randomness and stability of the algorithm, the top 1/2 salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 3.2. Update the position of each salp in the subgroup. The positions of leaders are updated according to equations (14) and (15). The positions of followers are updated according to equation (16).Step 3.3. Calculate the performance values, and update the food source position of the subgroup. The performance value of the current subgroup food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 3.4. Repeat Steps 3.2–3.3 until the max number of subgroup iterations ψ1 is completed.Step 4. Mix subgroups. The updated GN subgroups are recombined to form the population S.Step 5. Repeat Steps 2–4 until the max number of iterations ψ is completed. Output the position Φ of the food source and its performance value.The calculation process of the algorithm is shown in Figure2.Figure 2
Calculation process of the ISSA.


### 4.4. Illustrative Examples

As shown in Figure3, the road network with 47 nodes was used to demonstrate the efficacy of the model and algorithm. The period T was [9 : 30, 10 : 30], and the interval τ was 60 seconds. The travel speed of the road section at the instant t∈9:30,9:35,…,10:30 could be seen in reference [22].Figure 3
Road network. The map comes from Bing Maps.Data cleansing and interpolation were performed to ensure the data continuity and integrity. The speed limit of urban expressway is 80 km/h, so the speed greater than 80 km/h was defined as abnormal value, which was deleted and filled by linear interpolation value. For the missing data, linear interpolation values were used to fill them.According to the linear speed-density model, the traffic load of the road section could be calculated. The polygonal-shaped travel speed function in reference [22] was used to calculate the travel time of the road section. Traffic demand was randomly generated in the range of 0.95×TFi,jt,1.05×TFi,jt, where TFi,jt is the traffic flow of the road section ni,nj at the instant t calculated by the speed-flow model. Traffic demand of road section ni,nj at the instant t is given in Appendix. At 9 : 30, a traffic accident a1 happened at the node n1a, and it was at the midpoint of the road section n21,n22. A traffic accident a2 happened at the node n2a, and it was at the midpoint of the road section n39,n38. A traffic accident a3 happened at the node n3a, and it overlapped with the node n28. Three emergency vehicles were located at nodes n1c, n2c and n3c, in which n1c and n2c were at the midpoint of road sections n18,n17 and n1,n2, and n3c overlapped with the node n6.


### 4.5. Calculation of D Alternative Paths from the Emergency Vehicle to the Accident

The alternative path planning model and algorithm were used to calculate the first five shortest paths from each vehicle nodes to each accident nodes. The starting and ending points in each example are shown in Table4. The algorithm was realized by MATLAB 2019 software. After some tests, the parameters of the algorithm are defined in Table 5.Table 4
Starting and ending points in each example.
Example no.IIIIIIIVVVIVIIVIIIIXStartingn1cn2cn1cn2cn3cn3cn1cn2cn3cEndingn1an2an2an1an1an2an3an3an3aTable 5
Selection of parameters of the alternative path planning algorithm.
ParametersQΨTqBValues2030747The SSA algorithm is a metaheuristic algorithm, and the first five paths obtained from one run are not necessarily the optimal solutions, so we improve the possibility of obtaining the optimal solution through multiple runs. After running the algorithm, we got the first five shortest paths as shown in Tables6–14 .It should be noted that, for theSd-th, Sd=2,3,4,5 of the first five shortest paths, if the node set of a certain path from 1st to Sd−1-th is really included in the node set of the Sd-th, it indicates that there are redundant sections in the Sd-th path. In this situation, this path should be removed from the set of alternative paths.Figures4–9 show the evolutionary processes of the algorithms for solving examples I and II. In order to verify the performance of the algorithm, the hybrid salp swarm algorithm (HSSA) was compared with SSA and bat algorithm (BA) [49].Figure 4
Evolutionary process of the HSSA for solving example I.Figure 5
Evolutionary process of the SSA for solving example I.Figure 6
Evolutionary process of the BA for solving example I.Figure 7
Evolutionary process of the HSSA for solving example II.Figure 8
Evolutionary process of the SSA for solving example II.Figure 9
Evolutionary process of the BA for solving example II.Table 6
Alternative paths from the noden1c to n1a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21⟶n1a20.052772.812n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a20.452807.733n1c⟶n17⟶n18⟶n7⟶n1⟶n2⟶n10⟶n21⟶n1a20.452947.234n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n10⟶n21⟶n1a20.552853.395n1c⟶n17⟶n18⟶n6⟶n1⟶n9⟶n20⟶n21⟶n1a20.752855.82Table 7
Alternative paths from the noden2c to n2a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a22.953685.052n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a23.153939.133n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n38⟶n39⟶n2a23.953617.284n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n25⟶n39⟶n2a24.153862.205n2c⟶n2⟶n3⟶n12⟶n23⟶n24⟶n38⟶n39⟶n2a25.053447.20Table 8
Alternative paths from the noden1c to n2a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a30.903995.962n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n25⟶n39⟶n2a31.104445.333n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n25⟶n39⟶n2a31.104452.424n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a31.404137.515n1c⟶n17⟶n16⟶n15⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a32.004004.23Table 9
Alternative paths from the noden2c to n1a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n10⟶n21⟶n1a8.101273.462n2c⟶n2⟶n1⟶n9⟶n20⟶n21⟶n1a13.401988.52Table 10
Alternative paths from the noden3c to n1a.
No.PathLength (km)Travel time (s)1n6⟶n1⟶n2⟶n10⟶n21⟶n1a9.252271.572n6⟶n1⟶n9⟶n20⟶n21⟶n1a9.952176.773n6⟶n1⟶n9⟶n10⟶n21⟶n1a10.052495.98Table 11
Alternative paths from the noden3c to n2a.
No.PathLength (km)Travel time (s)1n6⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a26.804444.962n6⟶n5⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a27.005006.153n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a29.204220.254n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a29.404740.325n6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a29.904024.37Table 12
Alternative paths from the noden1c to n3a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n16⟶n15⟶n29⟶n2815.502171.192n1c⟶n17⟶n31⟶n30⟶n29⟶n2820.102513.483n1c⟶n17⟶n18⟶n6⟶n5⟶n15⟶n29⟶n2820.202786.864n1c⟶n17⟶n16⟶n30⟶n29⟶n2820.502518.17Table 13
Alternative paths from the noden2c to n3a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n2823.053305.392n2c⟶n2⟶n3⟶n4⟶n13⟶n14⟶n27⟶n2826.153887.683n2c⟶n2⟶n3⟶n12⟶n13⟶n14⟶n27⟶n2827.153827.004n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n26⟶n27⟶n2828.154297.00Table 14
Alternative paths from the noden3c to n3a.
No.PathLength (km)Travel time (s)1n6⟶n5⟶n15⟶n29⟶n2814.502329.842n6⟶n18⟶n17⟶n16⟶n15⟶n29⟶n2819.803122.743n6⟶n5⟶n15⟶n14⟶n27⟶n2823.303845.244n6⟶n18⟶n17⟶n31⟶n30⟶n29⟶n2824.403927.12According to the results of 100 runs, performances of the three algorithms are shown in Table15.Table 15
Performance of the alternative path planning algorithm.
Example no.AlgorithmAlternative paths obtained in one runAverage evolution time (s)Number of runs for getting five alternative pathsIBA3.931.12385SSA2.880.68978HSSA3.490.43145IIBA3.871.18374SSA2.670.80029HSSA3.370.47655IIIBA3.451.06107SSA2.630.84819HSSA3.030.52587IVBA2.290.737617SSA2.870.42946HSSA2.410.26339VBA2.880.898312SSA2.680.581912HSSA2.900.364211VIBA3.181.12817SSA2.070.829116HSSA2.400.503110VIIBA3.231.12528SSA2.560.703114HSSA3.040.42239VIIIBA3.261.580611SSA2.280.883316HSSA2.810.531815IXBA3.561.004915SSA2.070.774720HSSA2.390.476514Example no.AlgorithmStandard deviation of fitnessMinimum fitnessMaximum fitnessAverage fitnessIBA8047.41166007450021689.80SSA17286.94166009350029540.80HSSA9681.80166008130022618.30IIBA7197.52209007100025814.45SSA18151.862090010470034502.35HSSA9824.61209008680026631.80IIIBA6690.68293008200035188.85SSA15708.312930010550042051.10HSSA9798.34293008520036358.20IVBA4554.284200728005426.95SSA9735.264200568009152.05HSSA3762.434200453005447.40VBA6903.33116006860015343.55SSA14304.40116008340021544.35HSSA7646.12116005860015595.05VIBA6750.60259007320032153.20SSA17549.092590010760040413.05HSSA10703.22259008290033641.55VIIBA7327.68148007210018846.60SSA15259.18148008710025721.45HSSA8184.21148007400019181.60VIIIBA7863.53219007990030109.50SSA19012.12219009990039124.70HSSA11584.79219008860031911.60IXBA10457.47145008320022779.60SSA20715.991450010110031066.20HSSA12665.72145008280022588.60


### 4.6. Calculation of the Evacuation Plan for Each Alternative Path

Traffic evacuation model and algorithm were used to calculate the evacuation plan of each alternative path in Tables6–14. After some tests, the parameters of the algorithm are defined as Table 16.Table 16
Selection of parameters of traffic evacuation algorithm.
ParametersQΨGNGMΨ1Values20221025The ISSA was compared with SSA, BA, and particle swarm optimization (PSO). Taking pathn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21 as an example, the evolutionary processes of the four algorithms are shown in Figure 10. Tables 17–25 show the evacuation results.Figure 10
Evolutionary processes of algorithms. (a) PSO, BA, SSAn17⟶n18. (b) ISSA n17⟶n18. (c) PSO, BA, SSA n18⟶n6. (d) ISSA n18⟶n6. (e) PSO, BA, SSA n6⟶n1. (f) ISSA n6⟶n1. (g) PSO, BA, SSA n1⟶n2. (h) ISSA n1⟶n2. (i) PSO, BA, SSA n2⟶n10. (j) ISSA n2⟶n10. (k) PSO, BA, SSA n10⟶n21. (l) ISSA n10⟶n21.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 17
Evacuation results of alternative paths from the noden1c to n1a.
No.PathTravel time (s)1n1c⟶n17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21⟶n1a2184.132n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a1875.533n1c⟶n17⟶n18⟶n7⟶n1⟶n2⟶n10⟶n21⟶n1a2178.494n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n10⟶n21⟶n1a2134.115n1c⟶n17⟶n18⟶n6⟶n1⟶n9⟶n20⟶n21⟶n1a2061.81Table 18
Evacuation results of alternative paths from the noden2c to n2a.
No.PathTravel time (s)1n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3084.282n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a2984.843n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n38⟶n39⟶n2a3082.904n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n25⟶n39⟶n2a3063.825n2c⟶n2⟶n3⟶n12⟶n23⟶n24⟶n38⟶n39⟶n2a3119.76Table 19
Evacuation results of alternative paths from the noden1c to n2a.
No.PathTravel time (s)1n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3136.472n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n25⟶n39⟶n2a3138.943n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n25⟶n39⟶n2a3111.154n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a3027.765n1c⟶n17⟶n16⟶n15⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3366.31Table 20
Evacuation results of alternative paths from the noden2c to n1a.
No.PathTravel time (s)1n2c⟶n2⟶n10⟶n21⟶n1a1142.162n2c⟶n2⟶n1⟶n9⟶n20⟶n21⟶n1a1502.06Table 21
Evacuation results of alternative paths from the noden3c to n1a.
No.PathTravel time (s)1n6⟶n1⟶n2⟶n10⟶n21⟶n1a2136.502n6⟶n1⟶n9⟶n20⟶n21⟶n1a1923.823n6⟶n1⟶n9⟶n10⟶n21⟶n1a2160.92Table 22
Evacuation results of alternative paths from the noden3c to n2a.
No.PathTravel time (s)1n6⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3366.622n6⟶n5⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a3271.053n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3792.814n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a4202.635n6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3232.71Table 23
Evacuation results of alternative paths from the noden1c to n3a.
No.PathTravel time (s)1n1c⟶n17⟶n16⟶n15⟶n29⟶n281308.322n1c⟶n17⟶n31⟶n30⟶n29⟶n282051.663n1c⟶n17⟶n18⟶n6⟶n5⟶n15⟶n29⟶n281569.724n1c⟶n17⟶n16⟶n30⟶n29⟶n281988.58Table 24
Evacuation results of alternative paths from the noden2c to n3a.
No.PathTravel time (s)1n2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n281878.552n2c⟶n2⟶n3⟶n4⟶n13⟶n14⟶n27⟶n282767.813n2c⟶n2⟶n3⟶n12⟶n13⟶n14⟶n27⟶n283000.944n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n26⟶n27⟶n283016.44Table 25
Evacuation results of alternative paths from the noden3c to n3a.
No.PathTravel time (s)1n6⟶n5⟶n15⟶n29⟶n281544.842n6⟶n18⟶n17⟶n16⟶n15⟶n29⟶n281987.783n6⟶n5⟶n15⟶n14⟶n27⟶n282032.784n6⟶n18⟶n17⟶n31⟶n30⟶n29⟶n282620.59According to the results of 10 runs, the performances of the four algorithms for solving pathsn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21 and n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21are shown in Tables 26 and 27 .Table 26
Performances of the four algorithms for solving pathn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21.
Road sectionAlgorithmMinimum fitnessMaximum fitnessAverage fitnessStandard deviation of fitnessAverage evolution time (s)n17⟶n18PSO153.42468.91157.3735.270.0862BA155.27161.40155.521.030.0683SSA137.94153.86143.086.710.0733ISSA129.95143.69136.829.720.0496n18⟶n6PSO326.42332.27326.490.650.1032BA357.78449.99361.3215.210.0968SSA311.26419.52333.5525.810.0967ISSA312.51327.05319.7810.280.0780n6⟶n1PSO747.931216.44759.6473.610.0949BA769.16835.91772.1410.000.0916SSA707.79785.39734.3127.550.1075ISSA707.90708.04707.970.100.0586n1⟶n2PSO307.06307.06307.060.000.1472BA252.03253.67252.220.410.1316SSA238.15247.37239.252.780.1364ISSA238.17238.66238.420.350.0991n2⟶n10PSO620.92620.92620.920.000.1256BA199.881663.21284.88224.700.1234SSA142.94538.26303.47183.020.1228ISSA122.70125.28123.991.820.0778n10⟶n21PSO1279.101279.101279.100.000.1729BA392.011905.22428.23215.370.1715SSA402.50558.92462.0059.030.1625ISSA402.59405.18403.891.830.0925Table 27
Performances of the four algorithms for solving pathn17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21.
Road sectionAlgorithmMinimum fitnessMaximum fitnessAverage fitnessStandard deviation of fitnessAverage evolution time (s)n17⟶n18PSO160.16165.30160.481.100.0963BA155.17222.64156.739.510.0744SSA139.69184.40142.547.800.0609ISSA129.73152.07140.9015.800.0613n18⟶n7PSO575.95593.53578.376.090.1084BA579.12588.21579.351.300.1004SSA563.92629.57584.5025.110.0942ISSA580.96593.97587.469.200.0804n7⟶n8PSO165.59347.03170.1628.500.1106BA164.80190.95165.683.900.1051SSA147.37292.28172.7739.830.1056ISSA162.08165.66163.872.540.0756n8⟶n9PSO580.76580.76580.760.000.1061BA304.93448.05330.1846.080.1038SSA269.39653.22378.46148.170.1248ISSA286.14292.93289.534.800.0737n9⟶n20PSO156.83363.00174.8758.620.1455BA167.54700.15185.6275.380.1562SSA161.94472.57193.4881.840.1913ISSA159.60159.60159.600.000.1117n20⟶n21PSO398.05398.05398.050.000.1182BA250.83874.07263.2988.140.1546SSA222.562476.07283.27316.930.1293ISSA216.29227.52221.907.940.0802Taking pathn2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39 as an example, Figure 11 shows evacuation plans of the relevant road sections.Figure 11
Evacuation plans of the road sections. (a) Evacuation plans of sectionn2⟶n3. (b) Evacuation plans of section n3⟶n4. (c) Evacuation plans of section n4⟶n13. (d) Evacuation plans of section n13⟶n24. (e) Evacuation plans of section n24⟶n38. (f) Evacuation plans of section n38⟶n39.
(a)(b)(c)(d)(e)(f)Interpretation of data in Figure11 (Take (a) for example):2⟶3 (road section of the path): [emergency vehicle entry time (s): 115.57; travel time of the road section (s): 696.61; length of the road section (km): 4.60; inflow rate of the road section (vehicle/min): 50.00]2⟶1 (adjacent road section ofn2⟶n3): [inflow rate of the road section (vehicle/min):0; average speed before evacuation (km/h):23.97; average speed during evacuation(km/h): 23.97]2⟶10 (adjacent road section ofn2⟶n3): [inflow rate of the road section (vehicle/min):0; average speed before evacuation (km/h): 16.15; average speed during evacuation(km/h): 16.15]In nine examples, for each alternative path, TCI of its adjacent road sections after evacuation is the same as before. Travel time of the pathn1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a is the shortest in example I. Therefore, this is the optimal path for emergency vehicle c1 to accident a1. Similarly, we can obtain the optimal paths of other examples and list them in Table 28.Table 28
Optimal paths of nine examples.
Example no.Optimal pathTravel time (s)In1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a1875.53IIn2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a2984.84IIIn1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a3027.76IVn2c⟶n2⟶n10⟶n21⟶n1a1142.16Vn6⟶n1⟶n9⟶n20⟶n21⟶n1a1923.82VIn6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3232.71VIIn1c⟶n17⟶n16⟶n15⟶n29⟶n281308.32VIIIn2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n281878.55IXn6⟶n5⟶n15⟶n29⟶n281544.84


## 4.1. Basic Principle of Salp Swarm Algorithm

The populationS consists of Q salps including leaders and followers. In B-dimensional space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B of each salp sq,q=1,2,…,Q represents a feasible solution of the optimization problem. Each position Xq corresponds to a performance function value YXq related to the optimization objective. We suppose that there is a food source Φ=ϕ1,ϕ2,…,ϕb,…,ϕB in the search space.


### 4.1.1. Rules for Updating the Leader’s Position

The upper and lower bounds of the search space areα=α1,α2,…,αb,…,αB and β=β1,β2,…,βb,…,βB. The rules for position updating of the leader S1 are shown in (14)xb1φ=ϕbφ−1+λ1×λ2×αb−βb+βbλ3≥0.5ϕbφ−1−λ1×λ2×αb−βb+βbλ3<0.5,b=1,2,…,B,where φ is the current iteration. xb1φ is the position of the leader S1 in the b-th dimension after the φ-th iteration. ϕbφ−1 shows the position of the food source in the b-th dimension after the φ−1-th iteration. λ2,λ3∈0,1 are random variables with uniform distribution. The parameter λ1 is called the convergence factor (or self-adapting operator). It balances the exploration and exploitation of the leader. λ1 can be obtained from (15)λ1=2×e−4×φ/Ψ2,where Ψ is the maximum number of iterations.


### 4.1.2. Rules for Updating the Follower’s Position

The rules for position updating of the followerSg are shown in (16)xbgφ=xbgφ−1+xbg−1φ−12,where xbgφ is the position of the follower Sg in the b-th dimension after the φ-th iteration. xbgφ−1 and xbg−1φ−1 show the position of the followers Sg and Sg−1 in the b-th dimension after the φ−1-th iteration.


## 4.1.1. Rules for Updating the Leader’s Position

The upper and lower bounds of the search space areα=α1,α2,…,αb,…,αB and β=β1,β2,…,βb,…,βB. The rules for position updating of the leader S1 are shown in (14)xb1φ=ϕbφ−1+λ1×λ2×αb−βb+βbλ3≥0.5ϕbφ−1−λ1×λ2×αb−βb+βbλ3<0.5,b=1,2,…,B,where φ is the current iteration. xb1φ is the position of the leader S1 in the b-th dimension after the φ-th iteration. ϕbφ−1 shows the position of the food source in the b-th dimension after the φ−1-th iteration. λ2,λ3∈0,1 are random variables with uniform distribution. The parameter λ1 is called the convergence factor (or self-adapting operator). It balances the exploration and exploitation of the leader. λ1 can be obtained from (15)λ1=2×e−4×φ/Ψ2,where Ψ is the maximum number of iterations.


## 4.1.2. Rules for Updating the Follower’s Position

The rules for position updating of the followerSg are shown in (16)xbgφ=xbgφ−1+xbg−1φ−12,where xbgφ is the position of the follower Sg in the b-th dimension after the φ-th iteration. xbgφ−1 and xbg−1φ−1 show the position of the followers Sg and Sg−1 in the b-th dimension after the φ−1-th iteration.


## 4.2. Solution for the Alternative Path Planning Model Based on Hybrid Salp Swarm Algorithm

The solution of the model needs to obtain multiple relatively optimal solutions as alternatives. It benefits from the chain movement mode of SSA, which ensures the diversity of the population more effectively than the general with swarm movement behavior, thus avoiding the case that the algorithm converges too quickly to a single optimal solution. This means that SSA is easier to obtain multiple relatively optimal solutions. It can be seen that the SSA algorithm is more suitable for solving the alternative path planning model in this paper.The decision vectors of the alternative path planning model are sequences of nodes that meet the path connectivity constraints. If we use updating rules of equations (14)–(16), a large number of invalid solutions will be generated, which will have repercussions for the performance of the algorithm. Therefore, based on the implementation steps of the SSA, we redefine the encoding plan and the position updating rules and design an algorithm applicable to solve the alternative path planning model. Furthermore, combining it with Dijkstra algorithm to improve its performance.


### 4.2.1. Encoding

The decision vector of the problem is encoded as a positive integer vector. For example, the decision vectorn1c,n2,n4,…,n1a can be encoded as n1c,2,4,…,n1a.For any nodeni, if node nj satisfies ni,nj∈E, then nj is defined as the adjacent node of ni. All the adjacent nodes of ni form a set ρi. The random adjacent node search strategy is used to ensure that adjacent nodes are connected to form a path. Its implementation steps are as follows:Step 1. Suppose that the current path sequence is ω=nkc,…,ni. CNω is the complement set of ω. Randomly select a node nj from the set ρi∩CNω, and update the current path sequence to ω=nkc,…,ni,nj.Step 2. Repeat Step 1 until the node noa is found, and then the coding of a salp is obtained.


### 4.2.2. Rules for Updating the Leader’s Position

At theφ−1-th iteration, the position of the food source is Φφ−1=nkc,…,niϕφ−1,njϕφ−1,…,noa which represents a path from node nkc to noa. Similarly, X1φ−1=nkc,…,ni1φ−1,nj1φ−1,…,noa is the position of the leader. Rules for updating the leader’s position are as follows:Step 1. Randomly select a node niϕφ−1 from Φφ−1.Step 2. Update position of X1 according to λ11, where λ11∈0,1 is a random variable with uniform distribution.ifλ11<0.5Use the random adjacent node search strategy to generate a path fragment fromniϕφ−1 to noa, and then replace niϕφ−1,njϕφ−1,…,noa in Φφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ at the φ-th iteration.elseGenerate a path fragment fromnkc to niϕφ−1, and then replace nkc,…,niϕφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ.end


### 4.2.3. Rules for Updating the Follower’s Position

The position of theg-th follower is Xgφ−1=nkc,…,nigφ−1,njgφ−1,…,noa. Xg−1φ−1=nkc,…,nig−1φ−1,njg−1φ−1,…,noa shows the position of the g−1 -th follower. Determine the start position for updating Xgφ−1 according to λ12, and then update its position according to λ13, where λ12,λ13∈0,1 are random variables with uniform distribution. Rules for updating the follower’s position are as follows:ifλ12<0.5Randomly select a nodenigφ−1 from Xgφ−1.ifλ13<0.5Generate a path fragment fromnigφ−1 to noa, and then replace nigφ−1,njgφ−1,…,noa in Xgφ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nigφ−1, and then replace nkc,...,nigφ−1 in Xgφ−1 with the path fragment to form a new position Xgφ.endelseRandomly select a nodenig−1φ−1 from Xg−1φ−1.ifλ13<0.5Generate a path fragment fromnig−1φ−1 to noa, and then replace nig−1φ−1,njg−1φ−1,…,noa in Xg−1φ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nig−1φ−1, and then replace nkc,…,nig−1φ−1 in Xg−1φ−1 with the path fragment to form a new position Xgφ.endend


### 4.2.4. Performance Function

The performance function is related to the objective function of the alternative path planning model:(17)y1=−∑ei,j∈Ek,oli,j∀ck∈C,∀ao∈A.


### 4.2.5. Implementation Steps of the Hybrid Algorithm for Solving the Alternative Path Planning Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is generated to form the population S. Positions of the first Q−1 salps are randomly generated according to the encoding plan shown in ‘4.2.1 Encoding’ of this section, and the position of the Q-th salp is the optimal solution obtained by Dijkstra algorithm.Step 2. Calculate the initial performance values, and select the food source. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ.Step 3. Select leaders and followers. To balance the randomness and stability of the algorithm, the top Tq salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 4. Update the position of each salp. The positions of leaders are updated according to the rules shown in ‘4.2.2 Rules for updating the leader’s position’ of this section. The positions of followers are updated according to the rules shown in ‘4.2.3 Rules for updating the follower’s position’ of this section.Step 5. Calculate the performance values, and update the food source position. The performance value of the current food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 6. Repeat Steps 4–5 until the max number of iterations ψ is completed. Output the position of the food source and its performance value.


## 4.2.1. Encoding

The decision vector of the problem is encoded as a positive integer vector. For example, the decision vectorn1c,n2,n4,…,n1a can be encoded as n1c,2,4,…,n1a.For any nodeni, if node nj satisfies ni,nj∈E, then nj is defined as the adjacent node of ni. All the adjacent nodes of ni form a set ρi. The random adjacent node search strategy is used to ensure that adjacent nodes are connected to form a path. Its implementation steps are as follows:Step 1. Suppose that the current path sequence is ω=nkc,…,ni. CNω is the complement set of ω. Randomly select a node nj from the set ρi∩CNω, and update the current path sequence to ω=nkc,…,ni,nj.Step 2. Repeat Step 1 until the node noa is found, and then the coding of a salp is obtained.


## 4.2.2. Rules for Updating the Leader’s Position

At theφ−1-th iteration, the position of the food source is Φφ−1=nkc,…,niϕφ−1,njϕφ−1,…,noa which represents a path from node nkc to noa. Similarly, X1φ−1=nkc,…,ni1φ−1,nj1φ−1,…,noa is the position of the leader. Rules for updating the leader’s position are as follows:Step 1. Randomly select a node niϕφ−1 from Φφ−1.Step 2. Update position of X1 according to λ11, where λ11∈0,1 is a random variable with uniform distribution.ifλ11<0.5Use the random adjacent node search strategy to generate a path fragment fromniϕφ−1 to noa, and then replace niϕφ−1,njϕφ−1,…,noa in Φφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ at the φ-th iteration.elseGenerate a path fragment fromnkc to niϕφ−1, and then replace nkc,…,niϕφ−1 with the path fragment to form a new path. This new path is the leader’s position X1φ.end


## 4.2.3. Rules for Updating the Follower’s Position

The position of theg-th follower is Xgφ−1=nkc,…,nigφ−1,njgφ−1,…,noa. Xg−1φ−1=nkc,…,nig−1φ−1,njg−1φ−1,…,noa shows the position of the g−1 -th follower. Determine the start position for updating Xgφ−1 according to λ12, and then update its position according to λ13, where λ12,λ13∈0,1 are random variables with uniform distribution. Rules for updating the follower’s position are as follows:ifλ12<0.5Randomly select a nodenigφ−1 from Xgφ−1.ifλ13<0.5Generate a path fragment fromnigφ−1 to noa, and then replace nigφ−1,njgφ−1,…,noa in Xgφ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nigφ−1, and then replace nkc,...,nigφ−1 in Xgφ−1 with the path fragment to form a new position Xgφ.endelseRandomly select a nodenig−1φ−1 from Xg−1φ−1.ifλ13<0.5Generate a path fragment fromnig−1φ−1 to noa, and then replace nig−1φ−1,njg−1φ−1,…,noa in Xg−1φ−1 with the path fragment to form a new position Xgφ.elseGenerate a path fragment fromnkc to nig−1φ−1, and then replace nkc,…,nig−1φ−1 in Xg−1φ−1 with the path fragment to form a new position Xgφ.endend


## 4.2.4. Performance Function

The performance function is related to the objective function of the alternative path planning model:(17)y1=−∑ei,j∈Ek,oli,j∀ck∈C,∀ao∈A.


## 4.2.5. Implementation Steps of the Hybrid Algorithm for Solving the Alternative Path Planning Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is generated to form the population S. Positions of the first Q−1 salps are randomly generated according to the encoding plan shown in ‘4.2.1 Encoding’ of this section, and the position of the Q-th salp is the optimal solution obtained by Dijkstra algorithm.Step 2. Calculate the initial performance values, and select the food source. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ.Step 3. Select leaders and followers. To balance the randomness and stability of the algorithm, the top Tq salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 4. Update the position of each salp. The positions of leaders are updated according to the rules shown in ‘4.2.2 Rules for updating the leader’s position’ of this section. The positions of followers are updated according to the rules shown in ‘4.2.3 Rules for updating the follower’s position’ of this section.Step 5. Calculate the performance values, and update the food source position. The performance value of the current food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 6. Repeat Steps 4–5 until the max number of iterations ψ is completed. Output the position of the food source and its performance value.


## 4.3. Solution for the Traffic Evacuation Model Based on Improved Salp Swarm Algorithm

Different from the alternative path planning model, the solution of the traffic evacuation model only needs to obtain a unique optimal plan. This requires the algorithm to explore extensively the feasible search space and converge to the optimal solution in a short time. Therefore, this paper proposes an improved algorithm by adding the steps of population grouping and mixing on the basis of SSA. This algorithm enhances exploration ability through the parallel movement of multiple salp chains, which effectively improves its performance.


### 4.3.1. Encoding

The decision variables of the problem consist of inflow ratesuek,o,dt and uf,e,ik,o,dt. In order to facilitate actual traffic control, we assume that inflow rates are fixed during the period tsek,o,d. The salp position coding can be expressed as(18)uq=uek,o,d,uf,e,ik,o,d.


### 4.3.2. Performance Function

The performance function is related to the objective function (5) and the constraint condition (7). For salps that do not satisfy the constraint (8), their performance function values are infinitesimal.(19)y2=−Tek,o,dte,ik,o,d+∑fe,ik,o,d∈Fe,ik,o,dMM×max0,dvf,e,ik,o,d−avf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,dwhere MM is a very large number.


### 4.3.3. Population Grouping Strategy

In the basic salp swarm algorithm, the population will move in a chain towards the food source position, and this single chain has a low search efficiency and limited search area. Therefore, this paper groups the population to form multiple subgroups and enhances exploration ability through the parallel movement of multiple chains, so as to increase the possibility of obtaining the global optimal solution while improving the calculation speed. The grouping strategy is defined as follows.TheQ salps in population S are ranked in descending order of their fitness values, and the set of sorted positions is X′=X1′,X2′,…,Xq′,…,XQ′. According to equation (20), Q salps are divided equally into GN subgroups, and the number of salps in each subgroup is GM.(20)GxGn,Gm=XGn′Gm=1XGm×GN−Gn+1′Gm=2,3,…,GM,Gn=1,2,…,GN.where GxGn,Gm is the position of the Gm-th salp in the Gn-th subgroup.We assume that the total number of salps isQ=12, the number of subgroups is GN=3, and the positions of the sorted salps are shown in Table 2.Table 2
Positions of the sorted salps.
X1′X2′X3′X4′X5′X6′X7′X8′X9′X10′X11′X12′According to the grouping strategy shown in equation (20), individuals in each subgroup are shown in Table 3.Table 3
Salps in each subgroup.
1st subgroupGx1,1=X1′Gx1,2=X6′Gx1,3=X9′Gx1,4=X12′2nd subgroupGx2,1=X2′Gx2,2=X5′Gx2,3=X8′Gx2,4=X11′3rd subgroupGx3,1=X3′Gx3,2=X4′Gx3,3=X7′Gx3,4=X10′The above grouping strategy makes each subgroup contain individuals with better and worse fitness, which ensures the diversity of individuals in the subgroup. At the same time, the average fitness of salps in each subgroup is similar to that in other subgroups, which makes the superiority and inferiority of the initial individuals more balanced among the subgroups.


### 4.3.4. Implementation Steps of the Improved Algorithm for Solving the Traffic Evacuation Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is randomly generated to form the population S.Step 2. Calculate the performance values, and select the food source of the population. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ of the population.Step 3. Group the population and optimize in subgroups. The Q salps are divided into GN subgroups according to equation (20), and the optimal salp within each subgroup is marked as its food source position GΦ. Perform the following steps for each subgroup:Step 3.1. Select leaders and followers of the subgroup. To balance the randomness and stability of the algorithm, the top 1/2 salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 3.2. Update the position of each salp in the subgroup. The positions of leaders are updated according to equations (14) and (15). The positions of followers are updated according to equation (16).Step 3.3. Calculate the performance values, and update the food source position of the subgroup. The performance value of the current subgroup food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 3.4. Repeat Steps 3.2–3.3 until the max number of subgroup iterations ψ1 is completed.Step 4. Mix subgroups. The updated GN subgroups are recombined to form the population S.Step 5. Repeat Steps 2–4 until the max number of iterations ψ is completed. Output the position Φ of the food source and its performance value.The calculation process of the algorithm is shown in Figure2.Figure 2
Calculation process of the ISSA.


## 4.3.1. Encoding

The decision variables of the problem consist of inflow ratesuek,o,dt and uf,e,ik,o,dt. In order to facilitate actual traffic control, we assume that inflow rates are fixed during the period tsek,o,d. The salp position coding can be expressed as(18)uq=uek,o,d,uf,e,ik,o,d.


## 4.3.2. Performance Function

The performance function is related to the objective function (5) and the constraint condition (7). For salps that do not satisfy the constraint (8), their performance function values are infinitesimal.(19)y2=−Tek,o,dte,ik,o,d+∑fe,ik,o,d∈Fe,ik,o,dMM×max0,dvf,e,ik,o,d−avf,e,ik,o,d,∀fe,ik,o,d∈Fe,ik,o,d,∀ek,o,d∈Ek,o,d,∀pk,od∈Pk,o,∀ck∈C,∀ao∈A,∀t∈tsek,o,dwhere MM is a very large number.


## 4.3.3. Population Grouping Strategy

In the basic salp swarm algorithm, the population will move in a chain towards the food source position, and this single chain has a low search efficiency and limited search area. Therefore, this paper groups the population to form multiple subgroups and enhances exploration ability through the parallel movement of multiple chains, so as to increase the possibility of obtaining the global optimal solution while improving the calculation speed. The grouping strategy is defined as follows.TheQ salps in population S are ranked in descending order of their fitness values, and the set of sorted positions is X′=X1′,X2′,…,Xq′,…,XQ′. According to equation (20), Q salps are divided equally into GN subgroups, and the number of salps in each subgroup is GM.(20)GxGn,Gm=XGn′Gm=1XGm×GN−Gn+1′Gm=2,3,…,GM,Gn=1,2,…,GN.where GxGn,Gm is the position of the Gm-th salp in the Gn-th subgroup.We assume that the total number of salps isQ=12, the number of subgroups is GN=3, and the positions of the sorted salps are shown in Table 2.Table 2
Positions of the sorted salps.
X1′X2′X3′X4′X5′X6′X7′X8′X9′X10′X11′X12′According to the grouping strategy shown in equation (20), individuals in each subgroup are shown in Table 3.Table 3
Salps in each subgroup.
1st subgroupGx1,1=X1′Gx1,2=X6′Gx1,3=X9′Gx1,4=X12′2nd subgroupGx2,1=X2′Gx2,2=X5′Gx2,3=X8′Gx2,4=X11′3rd subgroupGx3,1=X3′Gx3,2=X4′Gx3,3=X7′Gx3,4=X10′The above grouping strategy makes each subgroup contain individuals with better and worse fitness, which ensures the diversity of individuals in the subgroup. At the same time, the average fitness of salps in each subgroup is similar to that in other subgroups, which makes the superiority and inferiority of the initial individuals more balanced among the subgroups.


## 4.3.4. Implementation Steps of the Improved Algorithm for Solving the Traffic Evacuation Model

Step 1. Initialize population. In the search space, the position Xq=xq,1,xq,2,…,xq,b,…,xq,B, q=1,2,...,Q of each salp is randomly generated to form the population S.Step 2. Calculate the performance values, and select the food source of the population. The Q salps are ranked in descending order of the performance value. The position of the first salp is selected as the food source position Φ of the population.Step 3. Group the population and optimize in subgroups. The Q salps are divided into GN subgroups according to equation (20), and the optimal salp within each subgroup is marked as its food source position GΦ. Perform the following steps for each subgroup:Step 3.1. Select leaders and followers of the subgroup. To balance the randomness and stability of the algorithm, the top 1/2 salps with better performance values are regarded as leaders, whereas the rest of salps are considered as followers.Step 3.2. Update the position of each salp in the subgroup. The positions of leaders are updated according to equations (14) and (15). The positions of followers are updated according to equation (16).Step 3.3. Calculate the performance values, and update the food source position of the subgroup. The performance value of the current subgroup food is compared with that of each updated one. If the updated salp is better, the position of this salp is taken as the new food.Step 3.4. Repeat Steps 3.2–3.3 until the max number of subgroup iterations ψ1 is completed.Step 4. Mix subgroups. The updated GN subgroups are recombined to form the population S.Step 5. Repeat Steps 2–4 until the max number of iterations ψ is completed. Output the position Φ of the food source and its performance value.The calculation process of the algorithm is shown in Figure2.Figure 2
Calculation process of the ISSA.


## 4.4. Illustrative Examples

As shown in Figure3, the road network with 47 nodes was used to demonstrate the efficacy of the model and algorithm. The period T was [9 : 30, 10 : 30], and the interval τ was 60 seconds. The travel speed of the road section at the instant t∈9:30,9:35,…,10:30 could be seen in reference [22].Figure 3
Road network. The map comes from Bing Maps.Data cleansing and interpolation were performed to ensure the data continuity and integrity. The speed limit of urban expressway is 80 km/h, so the speed greater than 80 km/h was defined as abnormal value, which was deleted and filled by linear interpolation value. For the missing data, linear interpolation values were used to fill them.According to the linear speed-density model, the traffic load of the road section could be calculated. The polygonal-shaped travel speed function in reference [22] was used to calculate the travel time of the road section. Traffic demand was randomly generated in the range of 0.95×TFi,jt,1.05×TFi,jt, where TFi,jt is the traffic flow of the road section ni,nj at the instant t calculated by the speed-flow model. Traffic demand of road section ni,nj at the instant t is given in Appendix. At 9 : 30, a traffic accident a1 happened at the node n1a, and it was at the midpoint of the road section n21,n22. A traffic accident a2 happened at the node n2a, and it was at the midpoint of the road section n39,n38. A traffic accident a3 happened at the node n3a, and it overlapped with the node n28. Three emergency vehicles were located at nodes n1c, n2c and n3c, in which n1c and n2c were at the midpoint of road sections n18,n17 and n1,n2, and n3c overlapped with the node n6.


## 4.5. Calculation of D Alternative Paths from the Emergency Vehicle to the Accident

The alternative path planning model and algorithm were used to calculate the first five shortest paths from each vehicle nodes to each accident nodes. The starting and ending points in each example are shown in Table4. The algorithm was realized by MATLAB 2019 software. After some tests, the parameters of the algorithm are defined in Table 5.Table 4
Starting and ending points in each example.
Example no.IIIIIIIVVVIVIIVIIIIXStartingn1cn2cn1cn2cn3cn3cn1cn2cn3cEndingn1an2an2an1an1an2an3an3an3aTable 5
Selection of parameters of the alternative path planning algorithm.
ParametersQΨTqBValues2030747The SSA algorithm is a metaheuristic algorithm, and the first five paths obtained from one run are not necessarily the optimal solutions, so we improve the possibility of obtaining the optimal solution through multiple runs. After running the algorithm, we got the first five shortest paths as shown in Tables6–14 .It should be noted that, for theSd-th, Sd=2,3,4,5 of the first five shortest paths, if the node set of a certain path from 1st to Sd−1-th is really included in the node set of the Sd-th, it indicates that there are redundant sections in the Sd-th path. In this situation, this path should be removed from the set of alternative paths.Figures4–9 show the evolutionary processes of the algorithms for solving examples I and II. In order to verify the performance of the algorithm, the hybrid salp swarm algorithm (HSSA) was compared with SSA and bat algorithm (BA) [49].Figure 4
Evolutionary process of the HSSA for solving example I.Figure 5
Evolutionary process of the SSA for solving example I.Figure 6
Evolutionary process of the BA for solving example I.Figure 7
Evolutionary process of the HSSA for solving example II.Figure 8
Evolutionary process of the SSA for solving example II.Figure 9
Evolutionary process of the BA for solving example II.Table 6
Alternative paths from the noden1c to n1a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21⟶n1a20.052772.812n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a20.452807.733n1c⟶n17⟶n18⟶n7⟶n1⟶n2⟶n10⟶n21⟶n1a20.452947.234n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n10⟶n21⟶n1a20.552853.395n1c⟶n17⟶n18⟶n6⟶n1⟶n9⟶n20⟶n21⟶n1a20.752855.82Table 7
Alternative paths from the noden2c to n2a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a22.953685.052n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a23.153939.133n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n38⟶n39⟶n2a23.953617.284n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n25⟶n39⟶n2a24.153862.205n2c⟶n2⟶n3⟶n12⟶n23⟶n24⟶n38⟶n39⟶n2a25.053447.20Table 8
Alternative paths from the noden1c to n2a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a30.903995.962n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n25⟶n39⟶n2a31.104445.333n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n25⟶n39⟶n2a31.104452.424n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a31.404137.515n1c⟶n17⟶n16⟶n15⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a32.004004.23Table 9
Alternative paths from the noden2c to n1a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n10⟶n21⟶n1a8.101273.462n2c⟶n2⟶n1⟶n9⟶n20⟶n21⟶n1a13.401988.52Table 10
Alternative paths from the noden3c to n1a.
No.PathLength (km)Travel time (s)1n6⟶n1⟶n2⟶n10⟶n21⟶n1a9.252271.572n6⟶n1⟶n9⟶n20⟶n21⟶n1a9.952176.773n6⟶n1⟶n9⟶n10⟶n21⟶n1a10.052495.98Table 11
Alternative paths from the noden3c to n2a.
No.PathLength (km)Travel time (s)1n6⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a26.804444.962n6⟶n5⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a27.005006.153n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a29.204220.254n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a29.404740.325n6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a29.904024.37Table 12
Alternative paths from the noden1c to n3a.
No.PathLength (km)Travel time (s)1n1c⟶n17⟶n16⟶n15⟶n29⟶n2815.502171.192n1c⟶n17⟶n31⟶n30⟶n29⟶n2820.102513.483n1c⟶n17⟶n18⟶n6⟶n5⟶n15⟶n29⟶n2820.202786.864n1c⟶n17⟶n16⟶n30⟶n29⟶n2820.502518.17Table 13
Alternative paths from the noden2c to n3a.
No.PathLength (km)Travel time (s)1n2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n2823.053305.392n2c⟶n2⟶n3⟶n4⟶n13⟶n14⟶n27⟶n2826.153887.683n2c⟶n2⟶n3⟶n12⟶n13⟶n14⟶n27⟶n2827.153827.004n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n26⟶n27⟶n2828.154297.00Table 14
Alternative paths from the noden3c to n3a.
No.PathLength (km)Travel time (s)1n6⟶n5⟶n15⟶n29⟶n2814.502329.842n6⟶n18⟶n17⟶n16⟶n15⟶n29⟶n2819.803122.743n6⟶n5⟶n15⟶n14⟶n27⟶n2823.303845.244n6⟶n18⟶n17⟶n31⟶n30⟶n29⟶n2824.403927.12According to the results of 100 runs, performances of the three algorithms are shown in Table15.Table 15
Performance of the alternative path planning algorithm.
Example no.AlgorithmAlternative paths obtained in one runAverage evolution time (s)Number of runs for getting five alternative pathsIBA3.931.12385SSA2.880.68978HSSA3.490.43145IIBA3.871.18374SSA2.670.80029HSSA3.370.47655IIIBA3.451.06107SSA2.630.84819HSSA3.030.52587IVBA2.290.737617SSA2.870.42946HSSA2.410.26339VBA2.880.898312SSA2.680.581912HSSA2.900.364211VIBA3.181.12817SSA2.070.829116HSSA2.400.503110VIIBA3.231.12528SSA2.560.703114HSSA3.040.42239VIIIBA3.261.580611SSA2.280.883316HSSA2.810.531815IXBA3.561.004915SSA2.070.774720HSSA2.390.476514Example no.AlgorithmStandard deviation of fitnessMinimum fitnessMaximum fitnessAverage fitnessIBA8047.41166007450021689.80SSA17286.94166009350029540.80HSSA9681.80166008130022618.30IIBA7197.52209007100025814.45SSA18151.862090010470034502.35HSSA9824.61209008680026631.80IIIBA6690.68293008200035188.85SSA15708.312930010550042051.10HSSA9798.34293008520036358.20IVBA4554.284200728005426.95SSA9735.264200568009152.05HSSA3762.434200453005447.40VBA6903.33116006860015343.55SSA14304.40116008340021544.35HSSA7646.12116005860015595.05VIBA6750.60259007320032153.20SSA17549.092590010760040413.05HSSA10703.22259008290033641.55VIIBA7327.68148007210018846.60SSA15259.18148008710025721.45HSSA8184.21148007400019181.60VIIIBA7863.53219007990030109.50SSA19012.12219009990039124.70HSSA11584.79219008860031911.60IXBA10457.47145008320022779.60SSA20715.991450010110031066.20HSSA12665.72145008280022588.60


## 4.6. Calculation of the Evacuation Plan for Each Alternative Path

Traffic evacuation model and algorithm were used to calculate the evacuation plan of each alternative path in Tables6–14. After some tests, the parameters of the algorithm are defined as Table 16.Table 16
Selection of parameters of traffic evacuation algorithm.
ParametersQΨGNGMΨ1Values20221025The ISSA was compared with SSA, BA, and particle swarm optimization (PSO). Taking pathn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21 as an example, the evolutionary processes of the four algorithms are shown in Figure 10. Tables 17–25 show the evacuation results.Figure 10
Evolutionary processes of algorithms. (a) PSO, BA, SSAn17⟶n18. (b) ISSA n17⟶n18. (c) PSO, BA, SSA n18⟶n6. (d) ISSA n18⟶n6. (e) PSO, BA, SSA n6⟶n1. (f) ISSA n6⟶n1. (g) PSO, BA, SSA n1⟶n2. (h) ISSA n1⟶n2. (i) PSO, BA, SSA n2⟶n10. (j) ISSA n2⟶n10. (k) PSO, BA, SSA n10⟶n21. (l) ISSA n10⟶n21.
(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)Table 17
Evacuation results of alternative paths from the noden1c to n1a.
No.PathTravel time (s)1n1c⟶n17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21⟶n1a2184.132n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a1875.533n1c⟶n17⟶n18⟶n7⟶n1⟶n2⟶n10⟶n21⟶n1a2178.494n1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n10⟶n21⟶n1a2134.115n1c⟶n17⟶n18⟶n6⟶n1⟶n9⟶n20⟶n21⟶n1a2061.81Table 18
Evacuation results of alternative paths from the noden2c to n2a.
No.PathTravel time (s)1n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3084.282n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a2984.843n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n38⟶n39⟶n2a3082.904n2c⟶n2⟶n3⟶n12⟶n13⟶n24⟶n25⟶n39⟶n2a3063.825n2c⟶n2⟶n3⟶n12⟶n23⟶n24⟶n38⟶n39⟶n2a3119.76Table 19
Evacuation results of alternative paths from the noden1c to n2a.
No.PathTravel time (s)1n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3136.472n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n25⟶n39⟶n2a3138.943n1c⟶n17⟶n16⟶n15⟶n14⟶n13⟶n24⟶n25⟶n39⟶n2a3111.154n1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a3027.765n1c⟶n17⟶n16⟶n15⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3366.31Table 20
Evacuation results of alternative paths from the noden2c to n1a.
No.PathTravel time (s)1n2c⟶n2⟶n10⟶n21⟶n1a1142.162n2c⟶n2⟶n1⟶n9⟶n20⟶n21⟶n1a1502.06Table 21
Evacuation results of alternative paths from the noden3c to n1a.
No.PathTravel time (s)1n6⟶n1⟶n2⟶n10⟶n21⟶n1a2136.502n6⟶n1⟶n9⟶n20⟶n21⟶n1a1923.823n6⟶n1⟶n9⟶n10⟶n21⟶n1a2160.92Table 22
Evacuation results of alternative paths from the noden3c to n2a.
No.PathTravel time (s)1n6⟶n5⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3366.622n6⟶n5⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a3271.053n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39⟶n2a3792.814n6⟶n1⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a4202.635n6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3232.71Table 23
Evacuation results of alternative paths from the noden1c to n3a.
No.PathTravel time (s)1n1c⟶n17⟶n16⟶n15⟶n29⟶n281308.322n1c⟶n17⟶n31⟶n30⟶n29⟶n282051.663n1c⟶n17⟶n18⟶n6⟶n5⟶n15⟶n29⟶n281569.724n1c⟶n17⟶n16⟶n30⟶n29⟶n281988.58Table 24
Evacuation results of alternative paths from the noden2c to n3a.
No.PathTravel time (s)1n2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n281878.552n2c⟶n2⟶n3⟶n4⟶n13⟶n14⟶n27⟶n282767.813n2c⟶n2⟶n3⟶n12⟶n13⟶n14⟶n27⟶n283000.944n2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n26⟶n27⟶n283016.44Table 25
Evacuation results of alternative paths from the noden3c to n3a.
No.PathTravel time (s)1n6⟶n5⟶n15⟶n29⟶n281544.842n6⟶n18⟶n17⟶n16⟶n15⟶n29⟶n281987.783n6⟶n5⟶n15⟶n14⟶n27⟶n282032.784n6⟶n18⟶n17⟶n31⟶n30⟶n29⟶n282620.59According to the results of 10 runs, the performances of the four algorithms for solving pathsn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21 and n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21are shown in Tables 26 and 27 .Table 26
Performances of the four algorithms for solving pathn17⟶n18⟶n6⟶n1⟶n2⟶n10⟶n21.
Road sectionAlgorithmMinimum fitnessMaximum fitnessAverage fitnessStandard deviation of fitnessAverage evolution time (s)n17⟶n18PSO153.42468.91157.3735.270.0862BA155.27161.40155.521.030.0683SSA137.94153.86143.086.710.0733ISSA129.95143.69136.829.720.0496n18⟶n6PSO326.42332.27326.490.650.1032BA357.78449.99361.3215.210.0968SSA311.26419.52333.5525.810.0967ISSA312.51327.05319.7810.280.0780n6⟶n1PSO747.931216.44759.6473.610.0949BA769.16835.91772.1410.000.0916SSA707.79785.39734.3127.550.1075ISSA707.90708.04707.970.100.0586n1⟶n2PSO307.06307.06307.060.000.1472BA252.03253.67252.220.410.1316SSA238.15247.37239.252.780.1364ISSA238.17238.66238.420.350.0991n2⟶n10PSO620.92620.92620.920.000.1256BA199.881663.21284.88224.700.1234SSA142.94538.26303.47183.020.1228ISSA122.70125.28123.991.820.0778n10⟶n21PSO1279.101279.101279.100.000.1729BA392.011905.22428.23215.370.1715SSA402.50558.92462.0059.030.1625ISSA402.59405.18403.891.830.0925Table 27
Performances of the four algorithms for solving pathn17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21.
Road sectionAlgorithmMinimum fitnessMaximum fitnessAverage fitnessStandard deviation of fitnessAverage evolution time (s)n17⟶n18PSO160.16165.30160.481.100.0963BA155.17222.64156.739.510.0744SSA139.69184.40142.547.800.0609ISSA129.73152.07140.9015.800.0613n18⟶n7PSO575.95593.53578.376.090.1084BA579.12588.21579.351.300.1004SSA563.92629.57584.5025.110.0942ISSA580.96593.97587.469.200.0804n7⟶n8PSO165.59347.03170.1628.500.1106BA164.80190.95165.683.900.1051SSA147.37292.28172.7739.830.1056ISSA162.08165.66163.872.540.0756n8⟶n9PSO580.76580.76580.760.000.1061BA304.93448.05330.1846.080.1038SSA269.39653.22378.46148.170.1248ISSA286.14292.93289.534.800.0737n9⟶n20PSO156.83363.00174.8758.620.1455BA167.54700.15185.6275.380.1562SSA161.94472.57193.4881.840.1913ISSA159.60159.60159.600.000.1117n20⟶n21PSO398.05398.05398.050.000.1182BA250.83874.07263.2988.140.1546SSA222.562476.07283.27316.930.1293ISSA216.29227.52221.907.940.0802Taking pathn2⟶n3⟶n4⟶n13⟶n24⟶n38⟶n39 as an example, Figure 11 shows evacuation plans of the relevant road sections.Figure 11
Evacuation plans of the road sections. (a) Evacuation plans of sectionn2⟶n3. (b) Evacuation plans of section n3⟶n4. (c) Evacuation plans of section n4⟶n13. (d) Evacuation plans of section n13⟶n24. (e) Evacuation plans of section n24⟶n38. (f) Evacuation plans of section n38⟶n39.
(a)(b)(c)(d)(e)(f)Interpretation of data in Figure11 (Take (a) for example):2⟶3 (road section of the path): [emergency vehicle entry time (s): 115.57; travel time of the road section (s): 696.61; length of the road section (km): 4.60; inflow rate of the road section (vehicle/min): 50.00]2⟶1 (adjacent road section ofn2⟶n3): [inflow rate of the road section (vehicle/min):0; average speed before evacuation (km/h):23.97; average speed during evacuation(km/h): 23.97]2⟶10 (adjacent road section ofn2⟶n3): [inflow rate of the road section (vehicle/min):0; average speed before evacuation (km/h): 16.15; average speed during evacuation(km/h): 16.15]In nine examples, for each alternative path, TCI of its adjacent road sections after evacuation is the same as before. Travel time of the pathn1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a is the shortest in example I. Therefore, this is the optimal path for emergency vehicle c1 to accident a1. Similarly, we can obtain the optimal paths of other examples and list them in Table 28.Table 28
Optimal paths of nine examples.
Example no.Optimal pathTravel time (s)In1c⟶n17⟶n18⟶n7⟶n8⟶n9⟶n20⟶n21⟶n1a1875.53IIn2c⟶n2⟶n3⟶n4⟶n13⟶n24⟶n25⟶n39⟶n2a2984.84IIIn1c⟶n17⟶n16⟶n15⟶n14⟶n27⟶n26⟶n40⟶n39⟶n2a3027.76IVn2c⟶n2⟶n10⟶n21⟶n1a1142.16Vn6⟶n1⟶n9⟶n20⟶n21⟶n1a1923.82VIn6⟶n5⟶n15⟶n14⟶n13⟶n24⟶n38⟶n39⟶n2a3232.71VIIn1c⟶n17⟶n16⟶n15⟶n29⟶n281308.32VIIIn2c⟶n2⟶n1⟶n6⟶n5⟶n15⟶n29⟶n281878.55IXn6⟶n5⟶n15⟶n29⟶n281544.84


## 5. Result Analysis

### 5.1. Travel Time of the Alternative Path

Tables29–37 list the travel time of the alternative path before and after evacuation.In example I, the reduction of path 2 is the most obvious, and its travel time is 33.20% shorter than before. After the evacuation, the average value of 5 alternative paths is 2086.81 s, and it is 26.71% shorter than before. The shortest path before evacuation is path 1, while it becomes path 2 after evacuation. It can be seen that the optimal path obtained by using the model in this paper is not necessarily the shortest time path based on the existing road conditions. The evacuation effect will be different according to the road conditions of the alternative paths and its adjacent sections.In example II, the reduction of path 2 is the most obvious, and its travel time is 24.23% shorter than before. After the evacuation, the average value of 5 alternative paths is 3067.08 s, and it is 17.33% shorter than before. In other examples, there are different degrees of reduction in the average travel time after evacuation than that before evacuation. It is thus clear that traffic evacuation can significantly shorten the travel time of emergency vehicles and further shorten the response time of the accident.Table 29
Travel time of the alternative path before and after evacuation of example I.
No.Travel time before (s)Travel time after (s)Reduction (%)12772.812184.1321.23%22807.731875.5333.20%32947.232178.4926.08%42853.392134.1125.21%52855.822061.8127.80%Average2847.402086.8126.71%Table 30
Travel time of the alternative path before and after evacuation of example II.
No.Travel time before (s)Travel time after (s)Reduction (%)13685.053084.2816.30%23939.132984.8424.23%33617.283082.9014.77%43862.203063.8220.67%53447.203119.769.50%Average3710.173067.0817.33%Table 31
Travel time of the alternative path before and after evacuation of example III.
No.Travel time before (s)Travel time after (s)Reduction (%)13995.963136.4721.51%24445.333138.9429.39%34452.423111.1530.12%44137.513027.7626.82%54004.233366.3115.93%Average4207.093156.1324.98%Table 32
Travel time of the alternative path before and after evacuation of example IV.
No.Travel time before (s)Travel time after (s)Reduction (%)11273.461142.1610.31%21988.521502.0624.46%Average1630.991322.1118.94%Table 33
Travel time of the alternative path before and after evacuation of example V.
No.Travel time before (s)Travel time after (s)Reduction (%)12271.572136.505.95%22176.771923.8211.62%32495.982160.9213.42%Average2314.772073.7510.41%Table 34
Travel time of the alternative path before and after evacuation of example VI.
No.Travel time before (s)Travel time after (s)Reduction (%)12271.572136.505.95%22176.771923.8211.62%32495.982160.9213.42%Average2314.772073.7510.41%Table 35
Travel time of the alternative path before and after evacuation of example VII.
No.Travel time before (s)Travel time after (s)Reduction (%)12171.191308.3239.74%22513.482051.6618.37%32786.861569.7243.67%42518.171988.5821.03%Average2497.431729.5730.75%Table 36
Travel time of the alternative path before and after evacuation of example VIII.
No.Travel time before (s)Travel time after (s)Reduction (%)13305.391878.5543.17%23887.682767.8128.81%33827.003000.9421.59%44297.003016.4429.80%Average3829.272665.9430.38%Table 37
Travel time of the alternative path before and after evacuation of example IX.
No.Travel time before (s)Travel time after (s)Reduction (%)12329.841544.8433.69%23122.741987.7836.35%33845.242032.7847.14%43927.122620.5933.27%Average3306.242046.5038.10%


### 5.2. Impact of Evacuation on Background Traffic

Traffic congestion index (TCI) of alternative paths does not change before and after evacuation, and it demonstrates that the evacuation impact constraint can be satisfied without adjustment of the TCI level. The TCI element can control the change of speed within the range that drivers cannot obviously feel. That is, the impact of evacuation on the background traffic is acceptable. In order to further shorten the response time, the level of TCI needs to be increased after evacuation. This requires decision-makers to weigh the benefits of the plan against the costs involved according to the severity of the accident.


### 5.3. Algorithm Performance Analysis

#### 5.3.1. Alternative Path Planning Algorithm Performance Analysis

It can be seen from Table15 that, in terms of the ability to find the optimal solution, the average number of runs to obtain five paths when using HSSA, SSA, and BA to solve the eight cases is 9, 12, and 10, which shows that it is easier for HSSA to find the optimal solution of the model compared with the other two algorithms. In terms of computation speed, the average computation times of HSSA, SSA, and BA are 0.4439 s, 0.7266 s, and 1.0937 s, so the computation time of HSSA is 38.91% and 59.41% shorter than that of SSA and BA.The ascending sort of the three algorithms according to the standard deviation of fitness is BA, HSSA, and SSA. It indicates that the dispersion degree of the HSSA population is in the middle of the three algorithms. We make further analysis in combination with Figures4–9; all bats in the population will gradually approach the minimum value during the evolutionary process, while the distribution of individuals in the SSA population is more diversified. The convergence performance of HSSA is between BA and SSA. It also maintains the dispersion of the population while converging faster, which makes HSSA perform better than the other two in terms of both optimization ability and computation speed.


#### 5.3.2. Traffic Evacuation Algorithm Performance Analysis

According to Tables26 and 27, the improvement degree of the performance of ISSA compared with SSA, BA, and PSO is calculated, as shown in Table 38.Table 38
Performance improvement of ISSA algorithm.
AlgorithmMinimum fitnessMaximum fitnessAverage fitnessAverage evolution timeSSA0.97%35.41%12.72%30.60%BA10.06%38.37%12.61%30.15%PSO25.92%40.98%25.85%33.51%As can be seen from Table38, the ISSA algorithm has significantly improved in minimum fitness, maximum fitness, average fitness, and computation time compared with SSA, BA, and PSO. It can be seen that the ISSA algorithm performs better than the other three algorithms in solving the traffic evacuation model.


## 5.1. Travel Time of the Alternative Path

Tables29–37 list the travel time of the alternative path before and after evacuation.In example I, the reduction of path 2 is the most obvious, and its travel time is 33.20% shorter than before. After the evacuation, the average value of 5 alternative paths is 2086.81 s, and it is 26.71% shorter than before. The shortest path before evacuation is path 1, while it becomes path 2 after evacuation. It can be seen that the optimal path obtained by using the model in this paper is not necessarily the shortest time path based on the existing road conditions. The evacuation effect will be different according to the road conditions of the alternative paths and its adjacent sections.In example II, the reduction of path 2 is the most obvious, and its travel time is 24.23% shorter than before. After the evacuation, the average value of 5 alternative paths is 3067.08 s, and it is 17.33% shorter than before. In other examples, there are different degrees of reduction in the average travel time after evacuation than that before evacuation. It is thus clear that traffic evacuation can significantly shorten the travel time of emergency vehicles and further shorten the response time of the accident.Table 29
Travel time of the alternative path before and after evacuation of example I.
No.Travel time before (s)Travel time after (s)Reduction (%)12772.812184.1321.23%22807.731875.5333.20%32947.232178.4926.08%42853.392134.1125.21%52855.822061.8127.80%Average2847.402086.8126.71%Table 30
Travel time of the alternative path before and after evacuation of example II.
No.Travel time before (s)Travel time after (s)Reduction (%)13685.053084.2816.30%23939.132984.8424.23%33617.283082.9014.77%43862.203063.8220.67%53447.203119.769.50%Average3710.173067.0817.33%Table 31
Travel time of the alternative path before and after evacuation of example III.
No.Travel time before (s)Travel time after (s)Reduction (%)13995.963136.4721.51%24445.333138.9429.39%34452.423111.1530.12%44137.513027.7626.82%54004.233366.3115.93%Average4207.093156.1324.98%Table 32
Travel time of the alternative path before and after evacuation of example IV.
No.Travel time before (s)Travel time after (s)Reduction (%)11273.461142.1610.31%21988.521502.0624.46%Average1630.991322.1118.94%Table 33
Travel time of the alternative path before and after evacuation of example V.
No.Travel time before (s)Travel time after (s)Reduction (%)12271.572136.505.95%22176.771923.8211.62%32495.982160.9213.42%Average2314.772073.7510.41%Table 34
Travel time of the alternative path before and after evacuation of example VI.
No.Travel time before (s)Travel time after (s)Reduction (%)12271.572136.505.95%22176.771923.8211.62%32495.982160.9213.42%Average2314.772073.7510.41%Table 35
Travel time of the alternative path before and after evacuation of example VII.
No.Travel time before (s)Travel time after (s)Reduction (%)12171.191308.3239.74%22513.482051.6618.37%32786.861569.7243.67%42518.171988.5821.03%Average2497.431729.5730.75%Table 36
Travel time of the alternative path before and after evacuation of example VIII.
No.Travel time before (s)Travel time after (s)Reduction (%)13305.391878.5543.17%23887.682767.8128.81%33827.003000.9421.59%44297.003016.4429.80%Average3829.272665.9430.38%Table 37
Travel time of the alternative path before and after evacuation of example IX.
No.Travel time before (s)Travel time after (s)Reduction (%)12329.841544.8433.69%23122.741987.7836.35%33845.242032.7847.14%43927.122620.5933.27%Average3306.242046.5038.10%


## 5.2. Impact of Evacuation on Background Traffic

Traffic congestion index (TCI) of alternative paths does not change before and after evacuation, and it demonstrates that the evacuation impact constraint can be satisfied without adjustment of the TCI level. The TCI element can control the change of speed within the range that drivers cannot obviously feel. That is, the impact of evacuation on the background traffic is acceptable. In order to further shorten the response time, the level of TCI needs to be increased after evacuation. This requires decision-makers to weigh the benefits of the plan against the costs involved according to the severity of the accident.


## 5.3. Algorithm Performance Analysis

### 5.3.1. Alternative Path Planning Algorithm Performance Analysis

It can be seen from Table15 that, in terms of the ability to find the optimal solution, the average number of runs to obtain five paths when using HSSA, SSA, and BA to solve the eight cases is 9, 12, and 10, which shows that it is easier for HSSA to find the optimal solution of the model compared with the other two algorithms. In terms of computation speed, the average computation times of HSSA, SSA, and BA are 0.4439 s, 0.7266 s, and 1.0937 s, so the computation time of HSSA is 38.91% and 59.41% shorter than that of SSA and BA.The ascending sort of the three algorithms according to the standard deviation of fitness is BA, HSSA, and SSA. It indicates that the dispersion degree of the HSSA population is in the middle of the three algorithms. We make further analysis in combination with Figures4–9; all bats in the population will gradually approach the minimum value during the evolutionary process, while the distribution of individuals in the SSA population is more diversified. The convergence performance of HSSA is between BA and SSA. It also maintains the dispersion of the population while converging faster, which makes HSSA perform better than the other two in terms of both optimization ability and computation speed.


### 5.3.2. Traffic Evacuation Algorithm Performance Analysis

According to Tables26 and 27, the improvement degree of the performance of ISSA compared with SSA, BA, and PSO is calculated, as shown in Table 38.Table 38
Performance improvement of ISSA algorithm.
AlgorithmMinimum fitnessMaximum fitnessAverage fitnessAverage evolution timeSSA0.97%35.41%12.72%30.60%BA10.06%38.37%12.61%30.15%PSO25.92%40.98%25.85%33.51%As can be seen from Table38, the ISSA algorithm has significantly improved in minimum fitness, maximum fitness, average fitness, and computation time compared with SSA, BA, and PSO. It can be seen that the ISSA algorithm performs better than the other three algorithms in solving the traffic evacuation model.


## 5.3.1. Alternative Path Planning Algorithm Performance Analysis

It can be seen from Table15 that, in terms of the ability to find the optimal solution, the average number of runs to obtain five paths when using HSSA, SSA, and BA to solve the eight cases is 9, 12, and 10, which shows that it is easier for HSSA to find the optimal solution of the model compared with the other two algorithms. In terms of computation speed, the average computation times of HSSA, SSA, and BA are 0.4439 s, 0.7266 s, and 1.0937 s, so the computation time of HSSA is 38.91% and 59.41% shorter than that of SSA and BA.The ascending sort of the three algorithms according to the standard deviation of fitness is BA, HSSA, and SSA. It indicates that the dispersion degree of the HSSA population is in the middle of the three algorithms. We make further analysis in combination with Figures4–9; all bats in the population will gradually approach the minimum value during the evolutionary process, while the distribution of individuals in the SSA population is more diversified. The convergence performance of HSSA is between BA and SSA. It also maintains the dispersion of the population while converging faster, which makes HSSA perform better than the other two in terms of both optimization ability and computation speed.


## 5.3.2. Traffic Evacuation Algorithm Performance Analysis

According to Tables26 and 27, the improvement degree of the performance of ISSA compared with SSA, BA, and PSO is calculated, as shown in Table 38.Table 38
Performance improvement of ISSA algorithm.
AlgorithmMinimum fitnessMaximum fitnessAverage fitnessAverage evolution timeSSA0.97%35.41%12.72%30.60%BA10.06%38.37%12.61%30.15%PSO25.92%40.98%25.85%33.51%As can be seen from Table38, the ISSA algorithm has significantly improved in minimum fitness, maximum fitness, average fitness, and computation time compared with SSA, BA, and PSO. It can be seen that the ISSA algorithm performs better than the other three algorithms in solving the traffic evacuation model.


## 6. Conclusion

In the emergency rescue of traffic accidents, traffic evacuation can assist emergency vehicles to arrive at the accident locations in time. Firstly, the length, travel time, traffic load, etc. were taken as link weights, and a time-varying directed network model was built to describe the urban road network. Secondly, the decision-making process of path planning and traffic evacuation was analyzed. Thirdly, a D shortest path model was established to get multiple alternative paths, and a traffic evacuation model with evacuation impact constraint was built to distribute traffic on each alternative path, and then the optimal rescue path with the shortest travel time was obtained. In addition, an improved algorithm based on the principle of SSA was proposed to solve the model. Finally, a 47-node road network was used to demonstrate the efficacy of the model and the algorithm. The results show that (1) the path planning algorithm based on SSA can obtain D alternative paths that satisfy the path connectivity constraint. (2) The time for the emergency vehicle traveling from its location to the accident location is obviously reduced after traffic evacuation than before, while the impact of evacuation on the background traffic is acceptable. (3) The traffic evacuation algorithm based on ISSA can obtain an optimal path that satisfies constraints of evacuation impact and evacuation requirement. Compared with SSA, BA, and PSO, the ISSA algorithm has been improved in terms of both the optimization capability and the computation speed.The model in this paper is only one idea of combining emergency vehicle path planning with traffic evacuation. In the future, we can further analyze the cooperation of the two problems using methods such as bilevel programming and dynamic games. In addition, more complex factors in urban traffic accident rescue can be added to improve the model. And more new intelligent algorithms can also be combined with existing algorithms to further improve the solution performance.



---

*Source: 7862746-2022-04-25.xml*