# An Improved Shuffled Frog Leaping Algorithm and Its Application in Dynamic Emergency Vehicle Dispatching

Authors: Xiaohong Duan; Tianyong Niu; Qi Huang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The traditional method for solving the dynamic emergency vehicle dispatching problem can only get a local optimal strategy in each horizon. In order to obtain the dispatching strategy that can better respond to changes in road conditions during the whole dispatching process, the real-time and time-dependent link travel speeds are fused, and a time-dependent polygonal-shaped link travel speed function is set up to simulate the predictable changes in road conditions. Response times, accident severity, and accident time windows are taken as key factors to build an emergency vehicle dispatching model integrating dynamic emergency vehicle routing and selection. For the unpredictable changes in road conditions caused by accidents, the dispatching strategy is adjusted based on the real-time link travel speed. In order to solve the dynamic emergency vehicle dispatching model, an improved shuffled frog leaping algorithm (ISFLA) is proposed. The global search of the improved algorithm uses the probability model of estimation of distribution algorithm to avoid the partial optimal solution. Based on the Beijing expressway network, the efficacy of the model and the improved algorithm were tested from three aspects. The results have shown the following:(1) Compared with SFLA, the optimization performance of ISFLA is getting better and better with the increase of the number of decision variables. When the possible emergency vehicle selection strategies are 815, the objective function value of optimal selection strategies obtained by the base algorithm is 210.10% larger than that of ISFLA. (2) The prediction error of the travel speed affects the accuracy of the initial emergency vehicle dispatching. The prediction error of ±10 can basically meet the requirements of the initial dispatching. (3) The adjustment of emergency vehicle dispatching strategy can successfully bypassed road sections affected by accidents and shorten the response time.


---

## Body

## 1. Introduction

Urban Expressway can ease the traffic pressure on large cities and plays an important role in the urban traffic system. However, with the increasing amount of traffic, accidents often happen on expressways and cause great damage to people’s life and property. Rapid emergency rescue can effectively reduce accident loss, and emergency vehicle dispatching is the key to emergency rescue.Research of emergency vehicle dispatching started with assumptions of static travel time or distance, and the original dispatching problem mainly included two basic issues. In the problem with one accident, we only need to choose the nearest emergency vehicle to rescue the accident. The core is the shortest paths of emergency vehicles in the road network [1]. In the problem with multiple accidents, choosing the nearest emergency vehicle need not be an optimal decision [2]. We also need to select suitable emergency vehicles for different accidents to minimize their response times. It is a combinatorial optimization problem. Therefore, models for solving combinatorial optimization, such as Hungarian method, direct cost model, and opportunity cost model, were used to solve the emergency vehicle dispatching [3]. Aiming at the random resource requirements of potential incidents, Ozbay et al. used probabilistic constraint to improve the opportunity cost model [4]. Emergency vehicle dispatching with multiple accidents is a complex problem relating to various factors. In addition to response time, factors such as fairness, cost, and loss were considered to set up multiobjective dispatching models [5, 6]. In order to solve these NP-hard problems, ant colony algorithm [7], particle swarm optimization [8], genetic algorithm [9], and other intelligent optimization algorithms had been widely applied.Emergency vehicle dispatching problem considering the dynamic change of link weight (travel time, distance) started in the late 1990s. Taking the minimum response time as objective, Zografos et al. [10] integrated routing and dispatching module to set up an emergency response decision support system. Haghani et al. [11] built a simulation model of emergency vehicle dispatching. The model can assist decision makers to select suitable emergency vehicles and guide them to avoid congested areas. Dan et al. [12] divided dynamic dispatching problem into a series of static problems. Dispatching strategy was updated based on the time axis. A multiobjective model was established to solve these static problems. Yang et al. [13] set up an online dispatching and routing model for emergency vehicles. One day was divided into a number of intervals, and dispatching strategy was updated according to link travel time in each interval. Fu et al. [14] calculated the earliest response time using iteration method. A dynamic emergency resource dispatching system was designed. This research is essentially a static method for solving the dynamic problem. Dispatching strategies are continuously adjusted based on real-time traffic data at each decision-making instant. They suppose traffic data remain unchanged in the decision-making horizon. Emergency vehicles may be stopped up on the way to accidents because of changes in road conditions.If link weight is thought to be a time-dependence function, this network is a kind of time-dependence network. Research on the time-dependence network still focuses on universal shortest path problem. On the assumption of discrete link weight based on travel time, Cooke and Halsey [15] proposed a model of the time-dependence network. Iteration method was used to solve the shortest path problem. Kaufman and Smith [16] proved that the time-dependence shortest path problem can be solved by polynomials only when the network satisfies the first-in-first-out (FIFO) property. Most of the research on the shortest path of time-dependence traffic network is based on FIFO property [17]. However, road network with discrete link travel time proposed by Cooke is not FIFO [16]. In order to solve this problem, Duan et al. [18] proposed a universal shuffled frog leaping algorithm for solving the shortest path of the non-FIFO and FIFO network. Ichoua et al. [19] replaced link travel time with link travel speed to build time-dependent function. Travel time calculated by travel speed function changes continuously and satisfies the FIFO property. Since link travel speed cannot be known ahead of the decision-making instant, Ichoua et al. divided a day into three horizons to distinguish between congestion and free flow. During each time horizon, link travel speed remains unchanged. If this travel speed function is used to solve emergency vehicle dispatching problem, the whole dispatching process may be at a certain time horizon with constant link travel speed. This travel speed function cannot satisfy the requirement of emergency vehicle dispatching. On the assumption that link travel speed decreases continuously with the entry instant, Yuan and Wang [20] proposed an emergency vehicle routing model taking the shortest travel time as objective. Zhou et al. [21] built a multiobjective optimization model to solve the multiperiod dynamic emergency resource scheduling problems. In order to solve the model, a multiobjective evolutionary algorithm was proposed. Zhou and Liu [22] designed a multiagent genetic algorithm to solve the multiperiod emergency resource scheduling problem considering the uncertainty of traffic. The experimental results show that the multiagent genetic algorithm precedes genetic algorithm for the problem.According to the review of the literature, link travel speed function can reflect the dynamic changes of road conditions. However, it is difficult to model link travel speed function and solve the dynamic dispatching problem, and the dynamic problem is usually divided into a series of static problems. It only can get a local optimal strategy in each horizon. In order to get the overall optimal strategy, real-time data (reflecting the real-time road condition at decision-making instant) fuses with prediction data (reflecting the change of road condition in the whole dispatching process) to establish the link travel speed function. Meanwhile, considering the unpredictable changes in road conditions during the dispatching process, dispatching strategies are adjusted according to real-time travel speed. Multiple-incident and multiple-response (MIMR) emergency vehicle dispatching discussed in this paper is NP-hard problem with large scale variables. The metaheuristic algorithm has advantages in solving the NP-hard problem. Shuffled frog leaping algorithm (SFLA) is a relatively new heuristic algorithm. It was first proposed and applied in water distribution network designed by Eusuff et al. [23, 24]. This algorithm combines the advantages of particle swarm optimization (PSO) and shuffled complex evolution (SCE) algorithm, and it has been proved that the algorithm has good performance in convergence speed and solution precision [25, 26]. It was used to solve many real-word problems such as job shop scheduling and cloud computing resource allocation [27–29].According to the above, in this paper, the polygonal time-dependent function based on real-time and prediction link travel speed is built to simulate real road conditions in expressway network. Integrating routing and selection of emergency vehicles, a dynamic dispatching model is built. The model takes time-dependent travel speed, response time, time window, and accident severity as key factors to get the optimal strategy. And the dispatching strategy is adjusted when the new accidents happen. An improved shuffled frog leaping algorithm (IFSLA) is put forward to solve the dynamic dispatching model. The algorithm uses the probabilistic model of the distribution estimation algorithm to generate new frog population. It can avoid a local optimum of shuffled frog leaping algorithm.


## 2. Problem Statement

Based on graph theory, the expressway network is abstracted as a time-dependent directed network modelN,E,Tt×Q as shown in Figure 1. N=n1,n2,…,nM is the node set. It consists of hubs and interchanges on the expressway. M is the total number of nodes. The link arc between adjacent nodes ni and nj is road section ni,nj∈E. The expressway network is a directed network, so ni,nj≠nj,ni. Emergency vehicles must run along the direction of the road section, and they can change the direction at the nodes. Q is the interested time horizon. Tijt∈Tt is the link travel time function defined in time horizon Q. It represents a time for the emergency vehicle, leaving at an instant t, traveling from node ni to nj. ∀t∈Q, t+Tijt is always defined. For t∉Q, Tij(t) is defined as infinity.Figure 1
Expressway network model.(  1) Link Travel Time Function.Taking κ as the minimum time interval, Q is divided into discrete time intervals, that are Q=t0,t1,t1,t2,…,tϕ,tϕ+1,…,tΦ-1,tΦ, tϕ=t0+ϕ·κ, ϕ=0,1,…,Φ-1. t0 is the initial dispatching decision-making instant. tΦ=t0+Φ·κ is the last instant, and make sure it is large enough for the emergency vehicle to arrive at the accident during the time period [t0,tΦ]. vij(t) is the link travel speed function. It represents the average speed of the road section ni,nj∈E at t∈[t0,tΦ]. Based on the link travel speed function of Ichoua et al. [19], it is assumed that travel speed in each time interval changes in the form of the polygonal line, and the polygonal-shaped travel speed function is shown in Figure 2. At the decision-making instant t0, the real-time link travel speed vij1t0 is known. However, the real-time link travel speed vij1t, t∈t1,t2,…,tϕ,…,tΦ, tϕ=t0+ϕ·κ, ϕ=1,2,…,Φ, cannot be obtained. Therefore, they are approximated by the prediction travel speeds vij2ϕt0.Figure 2
Polygonal-shaped travel speed function.The polygonal-shaped travel speed function shown in Figure2 can be expressed as(1)vijtt0=vij21t0-vij1t0κ·t+t1·vij1t0-t0·vij21t0κt0≤t<t1vij2ϕ+1t0-vij2ϕt0κ·t+tϕ+1·vij2ϕt0-tϕ·vij2ϕ+1t0κtϕ≤t<tϕ+1,ϕ=1,…,Φ-1.v i j t t 0 is continuous on [t0,tΦ], and it must be integrable on the interval [t0,tΦ]. If the emergency vehicle enters the road section ni,nj at the instant yy≥t0, its travel distance is a function of travel time xy≤x≤tΦ.(2)∫yxvijtt0dt=∫t0xvijtt0dt-∫t0yvijtt0dt=ηx-ϑy,in which,(3)ηx=∫t0xvijtt0dt=∫vijxt0dx+C1,ϑy=∫t0yvijtt0dt=∫vijyt0dy+C2.Let formula (2) equal to the length Lsij of the road section ni,nj; the time when the emergency vehicle leaves the road section is(4)x=gLsij+ϑy,in which, g is the inverse function of η.When the emergency vehicle enters the road section at instantt, the travel time function of the road section is(5)Tijt=gLsij+ϑt-t.(  2) Dynamic Emergency Vehicle Dispatching Process. U t accidents are waiting for rescue at the instant t, and they compose set ACt. Acut∈ACt is the uth accident, u=1,2,…,Ut. The road section where the accident Acut occurred is expressed as n0u,n1u∈E, and its location node is Ncut, its rescue time window is 0,Tmaxut, and the required number of emergency vehicles is Naut>0. Asut represents the severity of the accident Acut. EVt is the emergency vehicle set, and Evlt∈EVt, l=1,2,…,Lt, stands for the lth emergency vehicle. Lt is the total number of emergency vehicles. The road section where the emergency vehicle Evlt is locat﻿ed is expressed as n0l,n1l∈E, and its location node is Nvlt. When the emergency vehicle Evlt∈EVt starts traveling at an instant t, the shortest time path to the accident Acut∈ACt is Plut, and the shortest travel time is Tlut.The basic purpose of emergency vehicle dispatching is to shorten the response time of accidents. The response time mainly depends on the travel time of the emergency vehicles. In the complex expressway network, emergency vehicles can reach accidents through multiple paths. Therefore, the shortest time path problem should be solved and the shortest travel timeTlut from each emergency vehicle Evlt∈EVt to each accident Acut∈ACt should be obtained firstly. Then, taking Tlut as the key factor, the suitable emergency vehicles are selected to rescue the accidents, that is, to solve the problem of emergency vehicle selection.According to the emergency vehicle selection strategy, emergency vehicles head for accidents along the shortest paths. In this process, if there are no new accidents in the road network, travel speed function of each road section does not change obviously, but once an accident happened, travel speeds of road sections in the accident area will be greatly affected. In order to avoid the rescue delay caused by sudden changes in road conditions, it is necessary to update link travel speed function according to the real-time speed, and the dispatching decision should be adjusted. We only need to update the travel time functions of road sections where the new accidents are located and their upstream road sections. If the rescue paths of the accident go through the new accidents, the rescue strategy for the affected accident needs to be recalculated, and the rescue strategies for the new accidents need to be calculated too.The dynamic dispatching process consists of two stages:(1) At the decision instant t=tφ, taking the polygonal-shaped travel speed function as the weight of the road section, the travel path from Evltφ to Acutφ is planned and the shortest travel time Tlutφ is obtained. (2) Taking the shortest travel time Tlutφ as input, emergency vehicles are selected to rescue the accidents. (3) At the instant t=tφ+1, a new accident occurs in the road network. The dispatching strategy, including vehicle routing and selection, is dynamically adjusted according to the updated real-time link travel speed.


## 3. Dynamic Emergency Vehicle Dispatching Modeling

At the decision-making instantt=tφ, the shortest travel time, the required number of emergency vehicles, the upper limit of rescue time window, and the accident severity are taken as the key factors. A dynamic dispatching model with vehicle routing is built. A list of all symbols is given in Symbols.(6)min∑u∑lAsutφ×Tlutφ×xlutφ+∑uM×zutφ,Evl∈EVtφ,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(7)s.t.∑lxlutφ=Nautφ,Evl∈EVtφ,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(8)tmaxutφ-Tmaxutφ≤M×zutφ,tmaxutφ=maxTlutφ×xlutφ,Evl∈EVtφ,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(9)∑uxlutφ+∑lxxltφ=1,Acu∈ACtφ,∀Evl∈EVtφ(10)∑lxlutφ+∑lxxltφ=Ltφ,Evl∈EVtφ,∀Acu∈ACtφ(11)xlutφ=0,1,∀Evl∈EVtφ,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(12)zutφ=0,1,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(13)xxltφ=0,1,∀Evltφ∈EVtφ(14)Tlutφ=min∑ni=Nvltn0uTi,i+1titφ,∀Evltφ∈EVtφ,∀Acu∈ACtφtφ=t0AC1tφtφ≠t0(15)s.t.ti=ti-1+Ti-1,iti-1t0ni=n1l,…,n0ut0ni=Nvlt(16)Nvlt,n1l,n1l,n2l,…,ni,ni+1,…,n-1u,n0u,n0u,Ncut∈E(17)Nvlt,n1l,…,ni,…,n0u,Ncut∈N(18)n1l≠⋯≠ni≠⋯≠n0u(19)n1l,n2l,…,ni,ni+1,…,n-1u,n0u≠n0u′,n1u′,Acu≠Acu′.Formula (6) is the objective function of emergency vehicle dispatching. It consists of two parts, the total travel time for emergency vehicles Evl to arrive at accidents Acu and the punishment caused by the exceeding rescue time. In which, M is a huge constant. At the initial decision-making instant tφ=t0, every accident Acu∈ACt0 needs to be rescued. At other decision-making instants, accident set AC1tφ includes new accidents that happened at tφ and the accidents whose rescue paths at tφ-1 are affected by new accidents. Emergency vehicle set EVtφ contains all emergency vehicles.Formulas (7) are the emergency vehicle requirements constraints. They make sure that the vehicle requirements of each accident can be satisfied.Formulas (8) are time window constraints of accidents. They guarantee that the latest arrival time tmaxutφ of emergency vehicle does not exceed the upper limit of the time window Tmaxutφ.Formulas (9) are constraints for the state of emergency vehicles. The emergency vehicle Evl can only be dispatched to an accident Acu or in an idle state.Formula (10) is the constraint for the total number of emergency vehicles. It ensures that the total number of emergency vehicles dispatched to the accidents and in the idle state is L.Formulas (11) are constraints for the state of variables xlutφ. At the decision-making instant tφ, if the emergency vehicle Evl,l=1,2,…,L, is dispatched to the accident Acu,u=1,2,…,U, then xlutφ=1; otherwise, xlutφ=0.Formulas (12) are constraints for the state of variables zutφ. At the decision-making instant tφ, if the latest rescue time for accident Acu,u=1,2,…,U, exceeds the upper limit of rescue time window, then zutφ=1; otherwise, zutφ=0.Formulas (13) are constraints for the state of variables xxltφ. At the decision-making instant tφ, if the emergency vehicle Evl,l=1,2,…,L, is in the idle state, then xxltφ=1; otherwise, xxltφ=0.Formula (14) is the objective function of rescue path for the accident Acutφ. It minimizes the travel time of the emergency vehicle from node Nvltφ to the destination Ncutφ, where road sections ni,ni+1 and ni+1,ni+2 are connected.Formula (15) calculates the instant ti when the emergency vehicle enters the road section ni,ni+1,ni=Nvlt,…,n0u.Formulas (16)–(18) are connectivity constraints of the path. They ensure that there are no loops in the path sequence.Formulas (19) ensure that the emergency vehicles do not pass road sections with accidents.


## 4. Solution for the Emergency Vehicle Dispatching Model

The shuffled frog leaping algorithm (SFLA) is a kind of metaheuristic algorithm that imitates the frog population’s behavior in obtaining food. The initial frog population is generated and divided into several memeplexes. Then the frogs search for the optimal solution within each memeplex for the defined number of times. Then frogs in different memeplex are shuffled so that the information can be exchanged globally. The group optimization and global information exchange alternate with each other until the convergence condition is satisfied. The mathematical model of SFLA is as follows.(  1) Initialization. H frogs are randomly generated to compose the initial population IP. The position of the hth frog is encoded as Xh=[xh1,xh2,…,xhd,…,xhD], h=1,…,H, in which, D is the dimension of the optimization problem. Each Xh represents a feasible solution to the optimization problem. And each feasible solution corresponds to a performance function f(Xh) associated with the optimization objective.(  2) Rank and Grouping. H frogs are ranked in descending order of performance function value. Position Px=px1,px2,…,pxd,…,pxD of the optimal frog in the population is marked. The population IP is divided into a memeplexes, and there are c frogs in each memeplex according to(20)Mo1=Xo1+ao2-1∈IP∣1≤o2≤c1≤o1≤a.(  3) Local Search. Within each memeplex, the local optimization process is repeated for the specified number of iterations It.(3.1) Positions of the frogs in the memeplex, the best and the worst, are marked asPb=pb1,pb2,…,pbd,…,pbD and Pw=pw1,pw2,…,pwd,…,pwD, respectively. Pw is renewed along with Pb according to (21)Dsd=min⁡INTr×pbd-pwd,Ddmaxpbd-pwd≥0max⁡INTr×pbd-pwd,-Ddmaxpbd-pwd<0,d=1,2,…,D,(22)pwd′=pwd+Dsd,d=1,2,…,D(23)pwd′=Zdmaxpwd′>Zdmaxpwd′Zdmin≤pwd′≤ZdmaxZdminpwd′<Zdmin,d=1,2,…,Din which, r is a random number, r∈[0,1]. Dsd is the adjustment of the dth decision variable, d=1,2,…,D. Ddmax is the maximum adjustment of the dth decision variable. pwd′ is the renewed position of the dth decision variable. Zdmax and Zdmin are the upper and lower limits of the position of the dth decision variable.(3.2) If the performance value ofPw′=pw1′,pw2′,…,pwd′,…,pwD′ is better than Pw, then Pw=Pw′; otherwise, Pb in formula (21) is replaced with Px, and the position updating is executed repeatedly.(3.3) If the performance value ofPw is still better than Pw′, then Pw is substituted by a random frog location.(  4) Mix and Global Search. After a local search, all memeplexes are shuffled to form a new population. Frogs are ranked and the best frog Px is marked. Then the next grouping and local search are performed until the specified number of global iterations IT is completed.


### 4.1. Solution for the Emergency Vehicle Dispatching Model Based on Improved Shuffled Frog Leaping Algorithm

In order to solve the dynamic emergency vehicle dispatching model, an improved shuffled frog leaping algorithm (ISFLA) is proposed. As shown in Figure3, the improved algorithm is guided by the idea of a base SFLA. The local search uses the optimization strategy of SFLA, and the global search uses the probability model of estimation of distribution algorithms (EDA) to avoid the partial optimal solution.Figure 3
Principle of the ISFLA.
(a) (b)


#### 4.1.1. Encoding and Decoding

Decision variables of the emergency vehicle dispatching are 0-1 numerical variablesxlutφ, which express whether the vehicle Evltφ should be dispatched to the accident Acutφ. The working object of SFLA is integer vector, so it is necessary to convert xlutφ to integer variable xltφ. xltφ represents the dispatching strategy of Evltφ,l=1,2,…,L at the decision-making instant tφ. Each vehicle can go to one of the accidents Acutφ,u=1,2,…,U or in the idle state. The feasible set of xltφ is xltφ=0,1,2,…,U. The emergency vehicle is an idle vehicle while xltφ=0. In this case, the encoding of frog position can be expressed as a row vector matrix.(24)Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ.Similarly,xltφ should be decoded in the reverse way of encoding, and we can get the emergency vehicle dispatching strategy.


#### 4.1.2. Performance Function

According to the objective function of the dynamic dispatching model of emergency vehicles, the performance function is defined as(25)fXtφ=-∑u∑lAsu×Tlutφ×xlutφ+∑uM×yutφ+∑uM×zutφyutφ=Nautφ-∑uxlutφzutφ=max⁡0,tmaxutφ-Tmaxutφ,tmaxutφ=max⁡Tlutφ×xlutφ.Using the quantification method in the literature [30], the accident severity Asu is divided into four levels, and the value is shown in Table 1.Table 1
Value of accident severity.
Accident level Description of the accident Accident severity Death toll The number of serious injuries (SI) The number of slight injuries Property loss (L) Minor accident Situation 1 - - 1-2 - 40 Situation 2 - - - Motor vehicle accidents: <1,000Nonmotor vehicle accidents: <200  Ordinary accident Situation 1 - 1-2 - - 60 Situation 2 - - ⩾3 - Situation 3 - - - <30,000  Major accident Situation 1 1-2 - - - 80 Situation 2 - 3 ⩽ SI < 10 - - Situation 3 - - - 30,000 ⩽L < 60,000  Extra serious accident Situation 1 ⩾3 - - - 100 Situation 2 - ⩾11 - - Situation 3 1 ⩾8 - - Situation 4 2 ⩾5 - - Situation 5 - - - ⩾60,000


#### 4.1.3. Process of the Improved Shuffled Frog Leaping Algorithm

Process of the ISFLA is shown in Figure4, and the specific process is as follows.Figure 4
Process of the improved SFLA.(  1) Build Probability Model. The decision vector of emergency vehicle dispatching is Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ, xltφ=0,1,2,…,U. U×L dimensional matrix BU×L is used to describe the probability distribution of the frog population. bu×l∈0,1 is the element of the matrix BU×L. It represents the probability that the lth decision variable xltφ is valued as u.(  2) Generate the Initial Population. The value of the element bu×l is set as 1/U. According to a uniform distribution, H frogs are generated randomly to form the initial population IP. Each frog’s position Xh=xh,1,xh,2,…,xh,L represents a feasible decision vector.(  3) Local Search. H frogs are ranked in descending order of performance function value fXh. Location Px of the optimal frog in the population is marked. The population IP is divided into a memeplexes, and there are c frogs in each memeplex according to formula (20). Within each memeplex, the local optimization process is repeated for the specified number of iterations It according to formula (21)–(23).(  4) Select the Superior Individual and Update the Probability Model. The performance function value fXh of each frog in the population is calculated. H frogs are reordered in descending order of performance function value. The first H/2 frogs are selected to calculate the distribution of decision variables, and then the probability matrix B′ is obtained. The updated probability model is(26)B=θ·B′+1-θ·B,in which, θ is the forgetting factor.(  5) Generate New Population. According to the updated probability model BU×L, H frogs are generated to form a new population IP.


## 4.1. Solution for the Emergency Vehicle Dispatching Model Based on Improved Shuffled Frog Leaping Algorithm

In order to solve the dynamic emergency vehicle dispatching model, an improved shuffled frog leaping algorithm (ISFLA) is proposed. As shown in Figure3, the improved algorithm is guided by the idea of a base SFLA. The local search uses the optimization strategy of SFLA, and the global search uses the probability model of estimation of distribution algorithms (EDA) to avoid the partial optimal solution.Figure 3
Principle of the ISFLA.
(a) (b)


### 4.1.1. Encoding and Decoding

Decision variables of the emergency vehicle dispatching are 0-1 numerical variablesxlutφ, which express whether the vehicle Evltφ should be dispatched to the accident Acutφ. The working object of SFLA is integer vector, so it is necessary to convert xlutφ to integer variable xltφ. xltφ represents the dispatching strategy of Evltφ,l=1,2,…,L at the decision-making instant tφ. Each vehicle can go to one of the accidents Acutφ,u=1,2,…,U or in the idle state. The feasible set of xltφ is xltφ=0,1,2,…,U. The emergency vehicle is an idle vehicle while xltφ=0. In this case, the encoding of frog position can be expressed as a row vector matrix.(24)Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ.Similarly,xltφ should be decoded in the reverse way of encoding, and we can get the emergency vehicle dispatching strategy.


### 4.1.2. Performance Function

According to the objective function of the dynamic dispatching model of emergency vehicles, the performance function is defined as(25)fXtφ=-∑u∑lAsu×Tlutφ×xlutφ+∑uM×yutφ+∑uM×zutφyutφ=Nautφ-∑uxlutφzutφ=max⁡0,tmaxutφ-Tmaxutφ,tmaxutφ=max⁡Tlutφ×xlutφ.Using the quantification method in the literature [30], the accident severity Asu is divided into four levels, and the value is shown in Table 1.Table 1
Value of accident severity.
Accident level Description of the accident Accident severity Death toll The number of serious injuries (SI) The number of slight injuries Property loss (L) Minor accident Situation 1 - - 1-2 - 40 Situation 2 - - - Motor vehicle accidents: <1,000Nonmotor vehicle accidents: <200  Ordinary accident Situation 1 - 1-2 - - 60 Situation 2 - - ⩾3 - Situation 3 - - - <30,000  Major accident Situation 1 1-2 - - - 80 Situation 2 - 3 ⩽ SI < 10 - - Situation 3 - - - 30,000 ⩽L < 60,000  Extra serious accident Situation 1 ⩾3 - - - 100 Situation 2 - ⩾11 - - Situation 3 1 ⩾8 - - Situation 4 2 ⩾5 - - Situation 5 - - - ⩾60,000


### 4.1.3. Process of the Improved Shuffled Frog Leaping Algorithm

Process of the ISFLA is shown in Figure4, and the specific process is as follows.Figure 4
Process of the improved SFLA.(  1) Build Probability Model. The decision vector of emergency vehicle dispatching is Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ, xltφ=0,1,2,…,U. U×L dimensional matrix BU×L is used to describe the probability distribution of the frog population. bu×l∈0,1 is the element of the matrix BU×L. It represents the probability that the lth decision variable xltφ is valued as u.(  2) Generate the Initial Population. The value of the element bu×l is set as 1/U. According to a uniform distribution, H frogs are generated randomly to form the initial population IP. Each frog’s position Xh=xh,1,xh,2,…,xh,L represents a feasible decision vector.(  3) Local Search. H frogs are ranked in descending order of performance function value fXh. Location Px of the optimal frog in the population is marked. The population IP is divided into a memeplexes, and there are c frogs in each memeplex according to formula (20). Within each memeplex, the local optimization process is repeated for the specified number of iterations It according to formula (21)–(23).(  4) Select the Superior Individual and Update the Probability Model. The performance function value fXh of each frog in the population is calculated. H frogs are reordered in descending order of performance function value. The first H/2 frogs are selected to calculate the distribution of decision variables, and then the probability matrix B′ is obtained. The updated probability model is(26)B=θ·B′+1-θ·B,in which, θ is the forgetting factor.(  5) Generate New Population. According to the updated probability model BU×L, H frogs are generated to form a new population IP.


## 4.1.1. Encoding and Decoding

Decision variables of the emergency vehicle dispatching are 0-1 numerical variablesxlutφ, which express whether the vehicle Evltφ should be dispatched to the accident Acutφ. The working object of SFLA is integer vector, so it is necessary to convert xlutφ to integer variable xltφ. xltφ represents the dispatching strategy of Evltφ,l=1,2,…,L at the decision-making instant tφ. Each vehicle can go to one of the accidents Acutφ,u=1,2,…,U or in the idle state. The feasible set of xltφ is xltφ=0,1,2,…,U. The emergency vehicle is an idle vehicle while xltφ=0. In this case, the encoding of frog position can be expressed as a row vector matrix.(24)Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ.Similarly,xltφ should be decoded in the reverse way of encoding, and we can get the emergency vehicle dispatching strategy.


## 4.1.2. Performance Function

According to the objective function of the dynamic dispatching model of emergency vehicles, the performance function is defined as(25)fXtφ=-∑u∑lAsu×Tlutφ×xlutφ+∑uM×yutφ+∑uM×zutφyutφ=Nautφ-∑uxlutφzutφ=max⁡0,tmaxutφ-Tmaxutφ,tmaxutφ=max⁡Tlutφ×xlutφ.Using the quantification method in the literature [30], the accident severity Asu is divided into four levels, and the value is shown in Table 1.Table 1
Value of accident severity.
Accident level Description of the accident Accident severity Death toll The number of serious injuries (SI) The number of slight injuries Property loss (L) Minor accident Situation 1 - - 1-2 - 40 Situation 2 - - - Motor vehicle accidents: <1,000Nonmotor vehicle accidents: <200  Ordinary accident Situation 1 - 1-2 - - 60 Situation 2 - - ⩾3 - Situation 3 - - - <30,000  Major accident Situation 1 1-2 - - - 80 Situation 2 - 3 ⩽ SI < 10 - - Situation 3 - - - 30,000 ⩽L < 60,000  Extra serious accident Situation 1 ⩾3 - - - 100 Situation 2 - ⩾11 - - Situation 3 1 ⩾8 - - Situation 4 2 ⩾5 - - Situation 5 - - - ⩾60,000


## 4.1.3. Process of the Improved Shuffled Frog Leaping Algorithm

Process of the ISFLA is shown in Figure4, and the specific process is as follows.Figure 4
Process of the improved SFLA.(  1) Build Probability Model. The decision vector of emergency vehicle dispatching is Xtφ=x1tφ,x2tφ,…,xltφ,…,xLtφ, xltφ=0,1,2,…,U. U×L dimensional matrix BU×L is used to describe the probability distribution of the frog population. bu×l∈0,1 is the element of the matrix BU×L. It represents the probability that the lth decision variable xltφ is valued as u.(  2) Generate the Initial Population. The value of the element bu×l is set as 1/U. According to a uniform distribution, H frogs are generated randomly to form the initial population IP. Each frog’s position Xh=xh,1,xh,2,…,xh,L represents a feasible decision vector.(  3) Local Search. H frogs are ranked in descending order of performance function value fXh. Location Px of the optimal frog in the population is marked. The population IP is divided into a memeplexes, and there are c frogs in each memeplex according to formula (20). Within each memeplex, the local optimization process is repeated for the specified number of iterations It according to formula (21)–(23).(  4) Select the Superior Individual and Update the Probability Model. The performance function value fXh of each frog in the population is calculated. H frogs are reordered in descending order of performance function value. The first H/2 frogs are selected to calculate the distribution of decision variables, and then the probability matrix B′ is obtained. The updated probability model is(26)B=θ·B′+1-θ·B,in which, θ is the forgetting factor.(  5) Generate New Population. According to the updated probability model BU×L, H frogs are generated to form a new population IP.


## 5. Illustrative Examples

Beijing expressway network shown as in Figure1 was taken as an example to demonstrate the efficacy of the model and the improved algorithm. The interested time horizon Q was 9:30 to 10:30 on December 1, 2016. The minimum time interval κ was 5 minutes. Real link travel speeds at the instant t∈{9:30,9:35,9:40,…,10:30} are given in Table 2. The upper limit of the time window Tmaxu was 50 minutes. Firstly, based on real link travel speeds at the instant t∈9:30,9:35,9:40,…,10:30, five examples with different scale variable were used to test the performance of the emergency vehicle dispatching based on ISFLA. Secondly, based on prediction link travel speeds with different error ranges, two examples were used to test the performance of the dynamic emergency vehicle dispatching based on the polygonal-shaped travel speed function. Thirdly, we simulated a scene of a new accident to demonstrate the efficacy of adjustment mechanism of dispatching strategy.Table 2
The table gives travel speeds ofni,nj at 9:30,9:35,9:40,…,10:30 on December 1, 2016. In which, ni,nj is the road section of Beijing expressway network. They are the basic data of illustrative examples in Section 5.
Road section 9:30 9:35 9:40 9:45 9:50 9:55 10:00 10:05 10:10 10:15 10:20 10:25 10:30 n 1 , n 2 35.8215 20.3765 28.2279 31.8677 35.7043 38.8095 28.6015 17.5589 22.8039 20.5689 33.2365 23.6908 26.1908 n 1 , n 6 22.5825 33.7016 14.5643 26.573 27.6807 19.0503 22.7254 23.13 22.2 21.6732 11.8164 23.3327 26.3327 n 1 , n 7 19.7129 20.9999 15.7227 20.0905 17.6481 23.1212 26.4123 24.617 21.1975 17.4778 29.8401 32.2002 27.2002 n 1 , n 9 15.355 15.528 11.5561 20.1183 19.7576 17.6415 22.0847 14.5041 14.1869 15.4142 16.9405 20.3074 22.5378 n 2 , n 1 23.1756 27.1385 29.4663 30.5464 19.6817 24.3868 17.9294 18.4325 23.9658 31.6632 20.1517 25.8569 24.6569 n 2 , n 3 26.4831 27.1754 21.7814 24.0784 17.1708 23.5244 17.2602 26.6113 35.9275 19.6655 23.9367 22.5875 17.5875 n 2 , n 10 16.693 13.9778 11.2268 18.5879 15.5855 17.1857 13.8282 10.7979 18.6863 17.7514 22.7961 21.2068 16.2068 n 3 , n 2 25.0379 30.4431 22.1758 18.9887 28.441 25.1131 27.0197 33.0966 27.4579 26.9891 33.9385 21.9777 26.9777 n 3 , n 4 21.4607 30.1089 16.8812 11.7818 11.621 26.9056 21.581 39.804 35.43943 28.224 21.4316 34.3545 29.3545 n 3 , n 12 23.7186 13.5768 22.6461 28.554 22.1646 13.8365 19.1874 18.0001 21.5321 21.6481 21.622 18.5449 23.5449 n 4 , n 3 15.4424 20.2254 30.8515 25.626 23.4888 22.7928 25.596 25.40945 41.652 34.4304 25.5643 19.6756 22.6436 n 4 , n 5 30.2678 19.3306 39.0199 32.8014 27.6075 30.1831 27.904 39.059 11.088 15.9983 27.7148 25.7315 28.6734 n 4 , n 13 20.139 21.9476 18.3451 21.4544 12.4372 24.3021 13.8022 9.6058 25.6725 18.4364 20.9946 16.9337 11.9337 n 5 , n 4 9.3128 23.4184 15.3372 48.2641 31.6018 36.0318 16.5346 22.9536 28.1376 21.2511 22.8202 18.4113 23.4113 n 5 , n 6 35.7092 42.1002 34.1108 37.9314 35.7767 28.5644 32.7456 25.1776 36.9073 22.659 23.2064 25.022 27.0654 n 5 , n 15 18.1438 22.07 25.7119 21.4686 15.3884 22.5308 15.1383 16.1952 17.7313 14.853 19.6452 16.5002 11.5002 n 6 , n 1 15.6426 36.723 22.8957 30.8007 25.6438 32.4282 25.1974 49.986 33.9197 35.9149 21.4228 37.6876 32.6876 n 6 , n 5 25.1075 31.5886 11.1249 26.73 24.013 15.8807 20.2512 24.1323 40.3112 36.2664 15.6697 26.0462 21.0462 n 6 , n 18 24.2849 18.1288 17.2682 25.7382 30.8254 14.5333 20.753 22.5785 13.04 27.2062 20.9267 32.5609 27.5609 n 7 , n 1 33.1513 25.6162 28.3083 24.1654 28.8115 17.0718 25.6522 24.2943 26.9422 30.1469 29.6986 38.7776 33.7776 n 7 , n 8 45.289 42.7567 39.8016 45.4383 43.9181 54.312 36.4771 36.7876 46.5368 53.676 29.1054 41.8043 36.8043 n 7 , n 18 24.2919 26.4158 27.8619 15.4707 24.595 9.864 24.684 7.38 22.212 32.076 21.8051 19.9445 23.3452 n 8 , n 7 45.2188 42.6165 48.6611 48.0486 34.7927 42.0564 32.445 55.548 40.0004 29.4257 47.3986 39.5606 34.5606 n 8 , n 9 24.8046 34.816 22.4496 28.5366 24.6233 16.668 12.8682 7.38 19.1072 28.6751 24.6707 18.2876 23.2876 n 8 , n 19 23.6014 17.8158 18.7145 22.1506 22.0417 18.6709 23.9033 29.3326 21.7442 21.9771 11.9924 19.1274 17.1434 n 9 , n 1 25.5525 22.7526 26.5187 19.5367 34.5426 25.6112 30.2352 23.8654 25.1875 29.4503 28.7788 20.3987 15.3987 n 9 , n 8 31.4897 36.8907 32.8745 42.5121 33.336 34.4962 42.436 38.276 31.005 29.628 26.215 31.2124 26.2124 n 9 , n 10 12.4945 15.9981 11.0279 18.8998 12.4372 25.544 14.796 22.2355 10.6805 15.7968 12.1055 28.9159 23.9159 n 9 , n 20 26.3711 18.6249 20.6505 13.2397 22.2702 19.9457 12.22 18.1987 15.747 18.5462 16.7472 17.0505 12.0505 n 10 , n 2 23.482 19.0404 27.7911 20.6294 22.1208 27.5455 18.4591 16.173 30.329 29.8818 23.7257 29.2399 34.2399 n 10 , n 9 19.6502 21.1314 19.5799 16.8456 17.5475 29.628 21.7406 12.8068 26.6456 22.2932 27.195 24.6179 22.3426 n 10 , n 11 11.6789 25.0173 23.1734 15.8519 10.4692 15.7769 17.2203 19.3803 17.6942 21.2171 20.9595 12.7466 17.7466 n 10 , n 21 16.6906 23.4181 21.1797 23.4837 21.5237 16.9955 16.4308 22.9818 15.644 24.9333 22.9535 20.4386 15.4386 n 11 , n 10 21.1883 19.3399 21.2697 30.4105 18.6214 20.5809 19.44 17.1289 23.0388 22.6296 31.6504 22.7549 27.7549 n 11 , n 12 29.7455 23.1488 36.2439 41.5484 32.6593 48.132 30.6737 32.5309 32.5309 26.2273 31.0559 33.5541 28.5541 n 11 , n 22 19.6753 16.1579 22.8854 19.7345 28.2388 23.4119 33.845 32.5529 25.8201 23.5862 30.7608 19.2675 23.2453 n 12 , n 3 31.2132 24.0045 23.2547 21.9237 29.9919 39.1563 30.9103 24.9077 32.3465 24.4867 23.3021 31.8698 29.4568 n 12 , n 11 33.088 35.2858 30.6669 28.0342 25.4681 38.1852 29.059 32.6558 38.8695 32.2736 27.1765 33.8246 28.8246 n 12 , n 13 15.7673 18.1255 24.3937 18.8885 22.8062 14.7927 21.5846 19.7057 16.6918 25.0319 24.1279 23.1339 25.3462 n 12 , n 23 15.5967 22.1842 30.6917 11.3833 18.6417 10.7881 24.5125 25.0496 9.6873 27.7184 12.5765 19.1341 14.1341 n 13 , n 4 22.9506 21.4434 25.3072 15.7694 23.0083 22.2823 20.4405 28.2635 21.3286 27.7032 29.8792 24.2156 29.2156 n 13 , n 12 21.9029 30.2519 25.8323 13.7023 33.4922 27.0706 25.3517 29.1525 26.6141 14.5851 11.252 22.3766 17.3766 n 13 , n 14 11.1064 25.6402 15.2103 19.3209 26.4223 30.3127 13.0589 32.0853 27.2811 25.506 21.4571 20.4382 15.4382 n 13 , n 24 15.4208 17.5974 24.8324 25.0641 21.4277 24.1301 23.3536 17.0912 21.1445 17.5043 14.5007 22.1737 27.1737 n 14 , n 13 23.6147 38.1495 28.9343 24.2838 40.8111 24.048 28.2018 45.36 25.2878 27.65 23.2166 21.039 26.039 n 14 , n 15 25.379 22.6816 16.5716 19.1937 21.2507 25.92 30.8738 16.8351 26.708 23.8517 20.5968 15.6582 20.6582 n 14 , n 27 21.3262 21.9084 24.3039 28.8116 24.2594 30.2419 11.8582 19.7537 23.18 17.8241 15.6202 25.0852 20.0852 n 15 , n 5 21.8971 11.6351 30.1314 25.5666 26.0133 29.028 19.9033 23.3528 32.7366 29.9893 20.5936 15.9837 21.2351 n 15 , n 14 22.5953 26.6376 28.3237 25.4259 21.0793 19.422 15.9731 25.92 26.6161 46.296 29.4048 34.293 36.3256 n 15 , n 16 24.8356 29.7005 35.0005 13.6867 36.468 22.2797 20.34 24.7755 11.088 33.676 30.3817 27.5295 32.5295 n 15 , n 29 23.5872 31.4391 20.8336 9.2175 28.447 26.4114 17.0868 21.1131 23.8973 21.9235 23.4818 19.4364 14.4364 n 16 , n 15 28.7868 28.331 27.7535 22.1266 29.8588 36.296 19.422 31.4111 25.0175 26.1084 44.1895 19.9332 25.3457 n 16 , n 17 23.5312 20.7604 22.3994 35.63 34.2775 19.7144 21.6727 27.5377 26.1173 20.34 25.3507 30.9571 35.9571 n 16 , n 30 26.7026 16.7753 19.1615 25.0103 22.2606 30.4504 30.7058 21.096 28.3757 30.9772 25.6049 32.1169 27.1169 n 17 , n 16 16.9842 34.7854 32.1204 28.8798 29.7914 26.69 25.211 36.1121 26.7128 39.1083 29.6514 27.4658 22.4658 n 17 , n 18 26.443 28.7525 32.2085 27.9107 33.5474 42.424 33.1352 44.132 29.628 21.285 38.88 22.4163 27.4163 n 17 , n 31 20.0635 18.4469 18.9766 12.6472 14.5116 16.4666 13.5609 18.6594 28.8261 14.5888 20.2372 11.8279 6.8279 n 18 , n 6 28.5716 27.6879 36.1665 27.9511 27.4823 33.0515 30.2954 22.6653 21.871 20.1762 43.026 34.8619 38.3462 n 18 , n 7 17.1967 25.6923 22.2066 30.8889 40.716 15.114 12.96 5.544 25.92 13.0093 18.7247 23.7387 28.7387 n 18 , n 17 32.0776 31.2593 49.3007 31.5098 56.466 46.3468 24.048 24.048 41.652 23.13 23.3579 31.7037 36.7037 n 18 , n 32 21.765 13.6177 24.1532 20.6376 22.2606 17.6057 20.226 26.3626 7.6245 10.8335 21.0773 15.7262 17.5275 n 19 , n 8 30.0455 34.0459 26.2879 28.8757 26.1564 33.9629 38.5092 29.0318 34.1819 29.4782 32.5105 37.9813 36.3864 n 19 , n 20 9.971 19.224 11.088 24.048 14.796 24.048 21.3077 28.6925 20.7057 10.2956 16.9843 15.5002 10.5002 n 19 , n 33 37.9415 31.3179 23.2697 28.7727 26.4532 38.88 27.6162 26.532 46.296 32.088 34.3308 27.6593 22.6593 n 19 , n 34 24.5436 17.0723 22.9667 30.4918 19.9406 17.1968 15.9998 23.2988 27.0237 31.7541 19.3243 19.9782 20.2351 n 20 , n 9 16.0336 21.0688 25.6279 30.6163 31.9925 22.4156 21.399 27.0876 25.4508 26.8263 26.8914 15.5985 20.5985 n 20 , n 19 26.5774 22.212 17.5736 27.2318 15.442 13.6652 26.5167 17.5446 24.1079 30.6512 24.6187 27.79 32.79 n 20 , n 21 31.4044 31.4625 47.808 37.008 40.1212 35.172 42.588 23.882 33.7562 36.6223 31.0834 29.3702 24.3702 n 21 , n 10 19.8354 23.3835 28.8326 33.7234 19.1974 36.8871 32.6304 25.8425 23.494 21.5067 29.1639 21.527 26.527 n 21 , n 20 28.3482 29.4714 19.5844 21.8987 25.765 28.5483 33.6437 26.5502 35.3078 31.3771 34.8706 29.6347 32.5326 n 21 , n 22 26.0216 27.5469 21.8179 32.4478 33.4188 21.0689 23.4394 28.1423 24.1956 32.7357 29.0167 20.4584 29.5815 n 21 , n 35 22.5705 28.1672 18.9582 31.5342 35.7092 23.1775 24.9478 28.0398 32.2195 28.1321 27.3823 22.1031 32.4264 n 22 , n 11 32.0161 33.8281 49.6334 31.4378 24.217 41.5755 35.0492 28.7604 45.0867 34.7548 33.471 28.1108 23.1108 n 22 , n 21 21.5587 24.7503 13.8207 28.1799 36.1223 28.797 22.4211 26.1431 19.8201 34.3893 29.7035 28.9367 33.9367 n 22 , n 23 12.8279 35.172 20.358 10.17 23.1605 21.7582 22.824 29.3252 17.6377 28.4508 16.513 25.1189 30.1189 n 22 , n 36 16.8102 19.7036 20.046 17.7061 18.0843 19.2021 21.7497 26.6898 22.7205 17.28 22.5881 17.5268 22.5268 n 23 , n 12 26.3685 19.6544 20.9984 19.641 25.8781 19.1095 17.6822 25.7649 20.8829 24.8079 21.2406 24.3477 29.3477 n 23 , n 22 16.8402 20.5886 16.65 29.8227 21.1968 19.2456 17.586 16.668 30.4934 20.9667 24.2786 25.0395 20.0395 n 23 , n 24 29.2047 24.7494 18.3338 26.4002 14.7043 28.692 24.4668 11.088 20.34 25.92 27.8506 24.2783 19.2783 n 23 , n 37 23.8144 22.3499 18.5552 20.8287 21.6968 11.4653 20.4559 26.4973 18.5754 24.9654 27.9486 28.4628 33.4628 n 24 , n 13 30.4946 25.7359 36.4783 38.7628 25.6916 15.4647 23.175 20.7594 21.1762 19.3615 25.3909 35.5331 30.5331 n 24 , n 23 36.1943 31.331 37.8856 28.1583 27.6649 37.044 39.9093 25.92 24.432 27.98 34.4391 29.0487 24.0487 n 24 , n 25 27.5556 25.9729 24.751 29.2513 28.6489 25.1988 20.5482 25.7422 30.9605 16.9408 24.8777 15.2558 20.2558 n 24 , n 38 26.3805 23.4738 24.2851 21.887 18.8264 21.3668 22.3002 12.6113 22.0732 26.5655 20.3389 30.4344 35.4344 n 25 , n 24 25.331 28.2618 26.6353 30.4132 31.0304 22.7455 27.2853 21.2781 20.3911 31.6241 27.0002 26.7254 21.7254 n 25 , n 26 16.8309 27.0856 23.9089 19.3628 24.066 34.794 20.89029 46.908 29.004 19.89 25.92 24.7748 29.7748 n 25 , n 39 19.7948 24.4553 22.3961 13.2497 13.9135 29.1571 18.4512 35.4701 9.6681 25.6926 23.0038 18.4626 13.4626 n 26 , n 25 27.6015 29.85 28.5529 18.1117 23.5015 44.424 33.3481 23.598 18.504 34.254 31.464 25.7385 20.7385 n 26 , n 27 14.2224 19.9524 16.5509 16.6665 31.572 24.3207 20.976 20.5671 7.38 12.96 21.9918 24.4198 19.4198 n 26 , n 40 33.5522 19.6369 25.2266 22.8186 25.8973 13.3329 34.1434 28.2749 37.0596 33.5 25.0689 19.3657 19.2819 n 27 , n 14 30.6965 22.8707 28.1807 28.9659 20.5081 25.7812 32.9863 25.5622 23.4569 27.2833 23.6245 27.2157 32.2157 n 27 , n 26 29.3327 37.7083 34.5393 35.3089 27.3833 33.152 55.548 36.1578 25.9193 31.8867 18.8907 25.4497 25.3257 n 27 , n 28 34.5428 33.1044 26.3141 38.216 36.9792 19.828 37.179 26.652 21.296 28.5949 40.3886 37.2857 42.2857 n 27 , n 41 22.6554 18.3384 20.6647 19.5223 20.0416 21.7215 15.3789 14.2179 21.1639 30.3106 17.1591 12.9237 14.3215 n 28 , n 27 24.7294 13.4349 23.6613 27.7224 22.9866 23.672 35.172 25.92 15.732 7.38 23.5587 20.7311 25.7311 n 28 , n 29 27.7343 45.2357 46.278 48.204 18.504 29.628 30.9123 31.895 42.7445 24.5717 19.9995 39.019 44.019 n 28 , n 42 32.757 35.1901 29.7974 36.8838 39.0422 31.2206 43.6835 27.4834 34.6492 28.0919 34.9322 29.0565 24.0565 n 29 , n 15 18.7413 22.9066 30.6725 31.2796 26.8011 27.437 29.1645 18.7048 23.0915 16.8493 23.7545 30.7464 32.7321 n 29 , n 28 16.5841 23.1357 17.9721 5.544 24.984 26.1818 31.1185 28.4255 21.7963 16.2167 34.7601 26.723 21.723 n 29 , n 30 35.7481 41.2172 50.004 58.632 23.6078 36.4782 55.548 46.296 34.4414 36.9133 41.7204 39.5694 44.5694 n 29 , n 43 24.4832 35.7813 28.6492 24.5854 50.2455 34.5999 38.4233 43.1548 25.8914 38.4789 39.0105 36.4984 31.4984 n 30 , n 16 32.8059 33.4404 29.0517 40.1148 33.0317 36.4324 28.7253 27.6238 32.5452 31.7361 38.9741 36.0303 41.0303 n 30 , n 29 33.3402 32.9426 26.4765 40.716 32.813 22.212 29.628 27.7627 32.9475 25.4733 23.6324 29.8145 24.8145 n 30 , n 31 18.0093 23.7247 25.822 28.7387 24.6348 33.8815 23.5953 27.6376 30.3237 27.4259 31.4048 28.6161 23.6161 n 30 , n 47 29.9271 28.0907 21.013 30.969 20.7049 37.5447 31.1589 29.5889 25.6384 14.9421 20.8261 30.192 35.192 n 31 , n 17 27.3122 23.0705 26.384 22.972 19.9255 23.7923 22.1811 20.1768 30.8551 23.1064 35.6519 20.5192 25.5192 n 31 , n 30 13.3395 29.7268 20.8545 17.9808 23.7303 17.8568 24.8957 22.1967 36.8889 31.6923 13.5156 28.2066 26.3212 n 31 , n 32 29.9233 27.5431 24.8307 20.7151 25.5793 26.5665 19.653 27.9609 23.8885 27.5288 29.6811 23.4767 28.4767 n 31 , n 47 18.2443 21.0437 26.6463 22.7714 18.1332 14.5623 21.7784 22.6731 20.7887 22.4282 17.4275 27.2954 22.2954 n 32 , n 18 34.6978 23.1543 29.0436 24.907 30.5601 28.0568 27.7801 42.7455 24.8498 27.7656 41.4151 22.2665 23.066 n 32 , n 31 20.0793 14.9731 33.293 20.9773 25.5168 27.8158 25.568 20.4764 23.6614 25.3756 33.3948 21.6959 21.3256 n 32 , n 33 22.4128 20.5054 20.34 35.796 14.796 45.548 29.3574 26.5325 26.7919 20.8342 33.6774 31.6365 26.6365 n 32 , n 45 20.3312 24.4924 24.2836 31.2118 30.8979 28.6509 25.9583 22.4449 28.0319 34.8349 30.5642 29.0862 24.0862 n 33 , n 19 34.5595 27.3606 36.8804 38.7388 41.0041 30.1619 38.1456 35.7044 34.9696 43.0544 21.1344 32.4679 27.4679 n 33 , n 32 28.0225 19.644 36.4511 20.716 38.88 20.34 13.672 25.7334 31.2822 23.6385 24.025 29.1403 34.1403 n 33 , n 46 16.0562 29.5635 23.2929 36.0355 39.4106 26.7698 36.1572 34.7219 20.5097 28.7999 30.5667 32.138 28.3215 n 34 , n 19 28.3858 34.4957 41.3754 26.8214 20.2584 29.8203 17.0806 23.3569 26.6312 33.9373 33.6228 24.8346 19.8346 n 34 , n 35 38.7342 42.1347 43.8738 47.8653 39.3315 48.2212 46.5461 55.2707 45.5078 46.0586 38.8005 37.3032 42.3032 n 34 , n 46 45.4 34.8313 33.05829 51.8472 28.38 42.5736 49.98857 43.7484 47.011 41.9231 58.2984 34.9144 32.4512 n 35 , n 21 28.2038 41.6719 31.5473 29.1606 45.1054 36.8593 36.2981 25.9666 34.6039 35.1209 25.4465 30.6452 25.6452 n 35 , n 34 38.3401 35.6249 48.5614 38.4442 40.0985 32.3709 22.9813 29.4015 27.6955 29.0522 36.886 29.1026 24.1026 n 35 , n 36 45.1644 46.6339 42.4113 35.9576 59.1703 28.4833 41.4302 35.7486 41.5471 48.225 46.9663 41.0249 46.0249 n 36 , n 22 22.611 27.6803 34.0971 27.4104 16.7638 26.5984 23.4473 22.5357 22.6849 18.7214 22.0752 19.2935 21.2924 n 36 , n 35 17.8407 29.7715 34.5095 28.9844 30.6518 27.3529 19.6213 29.6933 37.7258 43.1677 27.9886 19.6087 24.6087 n 36 , n 37 43.7953 54.4549 61.5546 31.3509 68.5008 36.09 35.0472 66.11143 49.50514 41.346 35.172 57.6846 45.4344 n 37 , n 23 19.3156 15.9166 19.7184 28.5772 26.2822 25.679 30.2439 26.0461 26.2169 33.6578 34.694 44.6195 49.6195 n 37 , n 36 23.8205 32.8456 23.8767 28.0697 27.765 25.64229 23.42025 25.82571 30.67714 23.35015 32.391 32.8346 37.8346 n 37 , n 38 34.1043 48.0765 36.7424 37.1687 44.4156 40.54 41.9454 47.7629 52.3747 42.4163 46.6214 42.0936 47.0936 n 38 , n 24 32.6611 14.441 24.6137 33.4089 30.3681 28.0291 30.6215 34.7804 28.9226 23.4482 26.919 26.7533 31.7533 n 38 , n 37 44.8318 51.211 52.254 60.2107 65.5371 60.4039 55.0154 64.5239 65.3911 59.9616 63.57 62.3024 67.3024 n 38 , n 39 37.1429 49.9001 44.5609 36.0501 40.989 47.9961 38.0558 53.7996 41.8743 51.4709 38.3611 48.5935 45.4235 n 39 , n 25 34.3629 28.4779 30.0763 29.3488 32.4467 35.5281 29.2485 33.7507 41.5317 36.5889 35.9516 26.1112 31.1112 n 39 , n 38 47.4719 62.2148 68.7616 56.3855 66.4986 64.3643 51.5869 63.1797 57.5995 65.7155 60.4977 44.8243 49.8243 n 39 , n 40 51.8907 47.8745 58.5121 49.4962 62.436 42.215 52.2124 45.918 53.8011 31.5118 53.7514 38.3837 42.3321 n 40 , n 26 35.4259 28.2369 38.1587 33.4012 23.1637 18.4515 31.297 39.8748 34.087 33.3255 37.1265 24.6396 19.6396 n 40 , n 39 48.7455 42.1488 55.2439 60.5484 52.6593 50.6737 52.5309 46.2273 52.0559 54.5541 56.3667 55.4897 50.4897 n 40 , n 41 40.428 41.73709 51.84 36.22629 44.79943 56.88655 51.228 40.9608 48.7695 43.925 45.6818 52.9536 52.9536 n 41 , n 27 21.5665 32.1018 33.315 38.2749 26.2941 36.7688 32.4286 27.3579 36.645 33.5939 30.5894 43.2638 38.2638 n 41 , n 40 49.7784 60.5336 44.939 57.9558 64.3915 59.1353 62.1333 60.4039 47.4822 54.6687 67.7975 57.6513 59.6323 n 41 , n 42 46.8069 54.2979 43.1809 42.617 57.6107 39.9223 43.9772 51.3589 46.1985 56.2395 53.273 47.3326 46.3216 n 42 , n 28 23.5687 22.0959 23.0359 27.8531 24.22 21.4339 22.3374 17.0648 19.8429 16.522 21.9041 18.4894 17.4394 n 42 , n 41 41.7558 50.9238 45.4815 42.6664 58.9132 52.9074 55.1869 59.0718 54.4421 57.4068 58.4637 62.3649 59.3321 n 42 , n 43 22.452 37.3327 45.7083 42.5393 44.3089 36.3833 42.152 27.8907 35.9193 35.4497 46.1578 41.8867 36.8867 n 43 , n 29 26.551 25.5558 22.89 17.6108 33.3904 42.0009 43.34 27.0469 29.724 27.2055 30.4557 24.4874 19.4874 n 43 , n 42 50.6882 50.4938 70.0271 61.6079 51.544 60.1915 52.1194 60.6471 56.3798 69.9701 57.2431 46.103 51.103 n 43 , n 44 51.9058 24.5301 43.5541 43.2413 65.1582 32.2113 45.666 53.676 42.588 29.616 47.6023 31.0086 36.0086 n 44 , n 43 41.0666 47.6639 50.3153 57.3912 49.8147 42.576 56.672 57.4133 55.8927 59.5123 69.7826 64.2306 69.2306 n 44 , n 45 28.6551 34.8394 33.4949 33.7306 45.8684 35.6184 47.1494 33.747 46.7805 34.822 40.4126 46.7659 41.7659 n 44 , n 47 19.9468 15.8323 23.3384 13.9004 14.2217 23.352 29.1193 16.6816 15.9695 21.4484 25.4341 24.8079 29.8079 n 45 , n 32 24.7969 26.8204 20.6999 26.4952 22.3768 23.7876 20.971 24.3051 47.4192 46.4452 32.8815 30.7235 25.7235 n 45 , n 44 37.7425 56.6497 42.6488 44.8774 54.1986 44.5991 55.2349 44.2395 56.1024 53.0347 46.2959 41.0744 40.0421 n 45 , n 46 33.3609 41.1878 35.4696 36.3263 38.1141 41.0098 49.226 44.7845 31.1314 26.2193 38.532 25.257 30.257 n 46 , n 33 30.9449 30.5055 17.3013 27.1126 24.4442 14.7958 19.0287 25.0807 31.9526 25.6242 28.5735 21.6121 26.6121 n 46 , n 34 35.3327 29.628 26.838 32.908 37.332 45.66 44.424 45.1164 37.9687 39.0396 37.2611 40.5312 35.5312 n 46 , n 45 44.8368 46.52 38.0651 45.1987 48.8088 44.7385 57.8387 39.1315 39.1035 31.001 52.2839 51.9367 46.9367 n 47 , n 30 11.9523 25.8677 29.0142 19.907 24.6575 26.7507 21.3123 24.9181 27.4727 19.3771 30.0109 31.5672 31.5672 n 47 , n 31 30.0607 30.0464 30.0704 24.1245 28.2755 12.4826 18.9899 33.2118 22.0356 27.9654 35.0488 20.6665 22.6325 n 47 , n 44 23.6209 18.1936 25.7786 21.5246 30.2617 13.5507 22.8474 29.7383 19.0304 18.2511 16.3982 20.3277 25.3277


### 5.1. Illustrative Examples of Emergency Vehicle Dispatching Based on the Improved Shuffled Frog Leaping Algorithm

(  1) Calculating Link Travel Time Time-Dependent Function. Real link travel speeds vij1t at instant t∈9:30,9:35,9:40,…,10:30 were used to build the polygonal-shaped travel speed function. Then the travel time function Tijt, t∈9:30,10:30, of each road section was calculated according to formula (5). Figure 5 shows travel speed time-dependent functions of road sections n1,n2, n2,n1, n18,n32, n32,n18, and Figure 6 shows corresponding travel time time-dependent functions of these road sections.Figure 5
Link travel speed time-dependent functions.Figure 6
Link travel time time-dependent functions.(  2) Parameters of Illustrative Examples of Emergency Vehicle Dispatching. We assume that there are 15 emergency vehicles at most in the expressway network. At 9:30, 7 accidents at most occurred simultaneously. Tables 3 and 4 list the parameters of the example.Table 3
Accident parameters of the illustrative example.
Accident no. Accident node Road section of accident Location of accident Accident level Accident severity Accident demand 1 N c 1 / n 48 n 21 , n 22 L 21,48 = L 48,22 Minor 40 1 2 N c 2 / n 49 n 6 , n 5 L 6,49 = L 49,5 Ordinary 60 2 3 N c 3 / n 50 n 27 , n 14 L 27,50 = L 50,14 Major 80 2 4 N c 4 / n 51 n 16 , n 15 L 16,51 = L 51,15 Minor 40 1 5 N c 5 / n 52 n 9 , n 20 L 9,52 = L 52,20 Minor 40 2 6 N c 6 / n 53 n 38 , n 39 L 38,53 = L 53,39 Ordinary 60 2 7 N c 7 / n 54 n 47 , n 44 L 47,54 = L 54,44 Minor 40 1Table 4
Emergency vehicle parameters of the illustrative example.
Vehicle no. 1 2 3 4 5 Vehicle node N v 1 / n 55 N v 2 / n 56 N v 3 / n 57 N v 4 / n 58 N v 5 / n 59 Road section of vehicle n 2 , n 3 n 9 , n 8 n 12 , n 13 n 18 , n 17 n 15 , n 29 Location of vehicle L 2,55 = L 55,3 L 9,56 = L 56,8 L 12,57 = L 57,13 L 18,58 = L 58,17 L 15,59 = L 59,29 Vehicle no. 6 7 8 9 10 Vehicle node N v 6 / n 60 N v 7 / n 61 N v 8 / n 62 N v 9 / n 63 N v 10 / n 64 Road section of vehicle n 39 , n 25 n 30 , n 31 n 33 , n 32 n 19 , n 33 n 24 , n 13 Location of vehicle L 39,60 = L 60,25 L 30,61 = L 61,31 L 33,62 = L 62,32 L 19,63 = L 63,33 L 24,64 = L 64,13 Vehicle no. 11 12 13 14 15 Vehicle node N v 11 / n 65 N v 12 / n 66 N v 13 / n 67 N v 14 / n 68 N v 15 / n 69 Road section of vehicle n 28 , n 29 n 12 , n 23 n 27 , n 28 n 2 , n 10 n 18 , n 32 Location of vehicle L 28,65 = L 65,29 L 12,66 = L 66,23 L 27,67 = L 67,28 L 2,68 = L 68,10 L 18,69 = L 69,32(  3) Calculating the Shortest Travel Time for Each Emergency Vehicle to Each Accident. We assume 5 emergency vehicle dispatching examples with different complexity. The first example has 8 emergency vehicles and 3 accidents. Then, the numbers of emergency vehicles and accidents gradually increase, and the other four examples are formed. Emergency vehicles and accidents in each example are shown in Table 5.Table 5
Emergency vehicles and accidents in each example.
Example no. Vehicle no. Accident no. I 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3 II 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1, 2, 3, 4 III 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 1, 2, 3, 4, 5 IV 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 1, 2, 3, 4, 5, 6 V 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 1, 2, 3, 4, 5, 6, 7The dynamic shortest path algorithm of emergency vehicles in expressway network proposed in our previous research [18] was used to calculate the shortest travel time and path, and the results are shown in Tables 6 and 7.Table 6
The shortest travel time of the illustrative examples based on the real link travel speed.
Vehicle no. Example no. Accident no. 1 2 3 4 5 6 7 1 I 31.2925 38.9665 54.9495 -- -- -- -- II 31.2925 38.9665 54.9495 54.2331 -- -- -- III 31.2925 38.9665 54.9495 54.2331 34.8666 -- -- IV 31.2925 38.9665 54.9495 54.2331 34.8666 45.2505 -- V 31.2925 38.9665 54.9495 54.2331 34.8666 45.2505 ∞  2 I 22.1482 31.9124 ∞ -- -- -- -- II 22.1482 31.9124 ∞ 28.8721 -- -- -- III 26.9763 31.9124 ∞ 28.8721 15.2541 -- -- IV 26.9763 31.9124 ∞ 28.8721 15.2541 ∞ -- V 26.9763 31.9124 ∞ 28.8721 15.2541 ∞ 38.6391  3 I 48.3611 47.2027 33.8637 -- -- -- -- II 48.3611 47.2027 33.8637 59.0018 -- -- -- III 48.3611 47.2027 33.8637 59.0018 54.0921 -- -- IV 48.3611 47.2027 33.8637 59.0018 54.0921 28.6649 -- V 48.3611 47.2027 33.8637 59.0018 54.0921 28.6649 ∞  4 I 41.0760 16.3454 53.4742 -- -- -- -- II 41.0760 16.3454 ∞ 10.1881 -- -- -- III 41.0760 16.3454 ∞ 10.1881 35.6330 -- -- IV 41.0760 16.3454 ∞ 10.1881 35.6330 ∞ -- V 41.0760 16.3454 ∞ 10.1881 35.6330 ∞ 19.4956  5 I 49.9989 25.1126 38.7917 -- -- -- -- II 49.9989 25.1126 38.7917 19.8843 -- -- -- III 49.9989 25.1126 38.7917 19.8843 43.5353 -- -- IV 49.9989 25.1126 38.7917 19.8843 43.5353 45.7355 -- V 49.9989 25.1126 38.7917 19.8843 43.5353 45.7355 23.4806  6 I 44.4116 ∞ 26.3079 -- -- -- -- II 44.4116 ∞ 26.3079 ∞ -- -- -- III 44.4116 ∞ 26.3079 ∞ 54.4887 -- -- IV 44.4116 ∞ 26.3079 ∞ 54.4887 21.4419 -- V 44.4116 ∞ 26.3079 ∞ 54.4887 21.4419 ∞  7 I 43.6867 23.4594 56.5536 -- -- -- -- II 43.6867 23.4594 56.5536 14.4705 -- -- -- III 43.6867 23.4594 56.5536 14.4705 41.8074 -- -- IV 43.6867 23.4594 56.5536 14.4705 41.8074 ∞ -- V 43.6867 23.4594 56.5536 14.4705 41.8074 ∞ 12.3566  8 I 42.6146 21.7823 ∞ -- -- -- -- II 42.6146 21.7823 ∞ 21.3312 -- -- -- III 42.6146 21.7823 ∞ 21.3312 40.7481 -- -- IV 42.6146 21.7823 ∞ 21.3312 40.7481 ∞ -- V 42.6146 21.7823 ∞ 21.3312 40.7481 ∞ 20.0396  9 II 37.8754 33.6324 ∞ 30.5210 -- -- -- III 37.8754 33.6324 ∞ 30.5210 42.3188 -- -- IV 37.8754 33.6324 ∞ 30.5210 42.3188 ∞ -- V 37.8754 33.6324 ∞ 30.5210 42.3188 ∞ 29.6284  10 II 42.3397 40.7709 28.2020 52.5731 -- -- -- III 42.3397 40.7709 28.2020 52.5731 47.7124 -- -- IV 42.3397 40.7709 28.2020 52.5731 47.7124 24.0304 -- V 42.3397 40.7709 28.2020 52.5731 47.7124 24.0304 ∞  11 III ∞ 27.4119 40.8674 21.9920 45.8012 -- -- IV ∞ 27.4119 40.8674 21.9920 45.8012 48.8987 -- V ∞ 27.4119 40.8674 21.9920 45.8012 48.8987 25.3691  12 III 25.3758 49.7617 48.7390 ∞ 33.5190 -- -- IV 25.3758 49.7617 48.7390 ∞ 33.5190 32.6388 -- V 25.3758 49.7617 48.7390 ∞ 33.5190 32.6388 ∞  13 IV ∞ 34.0944 21.9164 31.4456 54.1145 37.1084 -- V ∞ 34.0944 21.9164 31.4456 54.1145 37.1084 33.8540  14 IV 10.1994 32.9815 ∞ 48.1107 13.8316 54.7018 -- V 10.1994 32.9815 ∞ 48.1107 13.8316 54.7018 ∞  15 V 43.5208 22.7684 ∞ 22.3348 41.7501 ∞ 20.7021Table 7
The shortest travel time path of the illustrative examples based on the real link travel speed.
Vehicle no. Example no. Accident no. 1 2 3 4 5 6 7 1 I 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- II 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 III 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 -- -- IV 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 3, 12, 23, 37, 38 V 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 3, 12, 23, 37, 38 BL  2 I 8, 9, 20, 21 8, 7, 18, 6 BL -- II 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 III 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 -- -- IV 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 BL V 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 BL 8, 7, 18, 17, 16, 30, 47  3 I 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- II 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 III 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 -- -- IV 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 -- V 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 BL  4 I 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- II 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 III 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 -- -- IV 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 BL -- V 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 BL 17, 31, 47  5 I 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- II 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 III 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 -- -- IV 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 -- V 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 29, 30, 47  6 I 25, 24, 23, 22, 21 BL 25, 26, 27 -- II 25, 24, 23, 22, 21 BL 25, 26, 27 BL III 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 -- -- IV 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 25, 24, 38 -- V 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 25, 24, 38 BL  7 I 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- II 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 III 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 -- -- IV 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 BL -- V 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 BL 31, 47  8 I 32, 33, 19, 20, 21 32, 18, 6 BL -- II 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 III 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 -- -- IV 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL -- V 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL 32, 31, 47  9 II 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 III 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 -- -- IV 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 BL -- V 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 BL 33, 32, 31, 47  10 II 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 III 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 -- -- IV 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 -- V 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 BL  11 III BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 -- -- IV BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 -- V BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 29, 30, 47  12 III 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 -- -- IV 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 23, 37, 38 -- V 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 23, 37, 38 BL  13 IV BL 28, 29, 15, 5, 6 28, 27 28, 29, 15, 16 28, 29, 15, 5, 6, 1, 9 28, 42, 41, 40, 39, 38 -- V BL 28, 29, 15, 5, 6 28, 27 28, 29, 15, 16 28, 29, 15, 5, 6, 1, 9 28, 42, 41, 40, 39, 38 28, 29, 30, 47  14 IV 10, 21 10, 2, 1, 6 BL 10, 9, 8, 7, 18, 17, 16 10, 9 10, 21, 35, 36, 37, 38 -- V 10, 21 10, 2, 1, 6 BL 10, 9, 8, 7, 18, 17, 16 10, 9 10, 21, 35, 36, 37, 38 BL  15 V 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL 32, 31, 47 Note. BL means that the travel time of the optimal path exceeds the upper limit of the time window.The expressway network is a directed network. When the emergency vehicleEvl,l=1,2,…,L, goes to the accident Acu,u=1,2,…,U, it must run along the direction of the road section to arrive at the node n1l and then choose the next road section. In which, n1l is the end of the road section n0l,n1l where the emergency vehicle Evl is located. Road section from the emergency vehicle’s location Nvl to node n1l is a necessary way for emergency vehicle Evl. In the same way, the emergency vehicle must arrive at the node n0u and then run along the direction of the road section to reach the accident node Ncu. In which, n0u is the start of the road section n0u,n1u where the accident Acu is located. Road section from the node n0u to the accident’s location Ncu is a necessary way for emergency vehicle Evl too. We only need to calculate the optimal path from the node n1l to the node n0u, so the optimal path from the node n1l to the node n0u is given in Table 7.(  4) Calculating the Optimal Dispatching Strategy. ISFLA was used to find the optimal dispatching strategy of the five examples. The improved algorithm was compared with SFLA. After some testing, parameters of ISFLA were defined as in Table 8. After ten runs, the best solutions of the five examples obtained by using these two algorithms are summarized in Table 9. Figure 7 shows the evolutionary processes of the two algorithms of example I and example V.Table 8
Parameter selection of ISFLA.
Example no. I P a c I T D d m a x  d=1,…,D Z d m a x  d=1,…,D Z d m i n  d=1,…,D D θ I 150 15 10 150 3 4 1 8 0.05 II 150 15 10 350 4 5 1 10 0.05 III 300 20 15 600 5 6 1 12 0.05 IV 374 22 17 800 5 7 1 14 0.05 V 500 25 20 900 6 8 1 15 0.05Table 9
Optimal emergency vehicle dispatching strategy of the illustrative examples based on the real link travel speed.
Example no. Example parameters Algorithm The optimal solution Optimal emergency vehicle dispatching strategy Travel time (min) I Total number of vehicles 8 ISFLA 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 3 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 Accident severity A s 1 = 40 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 A s 2 = 60 SFLA 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 A s 3 = 80 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Accident demand N a 1 = 1 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 N a 2 = 2 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 N a 3 = 2 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079  II Total number of vehicles 10 ISFLA 0,1,0,2,0,3,4,2,0,3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 4 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 Accident severity A s 1 = 40 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 A s 2 = 60 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 A s 3 = 80 SFLA 0,1,0,4,2,3,0,0,2,3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 A s 4 = 40 E v 5 to Ac2: Nv5→n29→n15→n5→n6→Nc2 25.1126 Accident demand N a 1 = 1 E v 9 to Ac2: Nv9→n33→n32→n18→n6→Nc2 33.6324 N a 2 = 2 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 N a 3 = 2 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 N a 4 = 1 E v 4 to Ac4: Nv4→n17→n16→Nc4 10.1881  III Total number of vehicles 12 ISFLA 5,5,0,2,0,3,4,2,0,3,0,1 E v 1 to Ac5: Nv1→n3→n2→n1→n9→Nc5 34.8666 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 5 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 Accident severity A s 1 = 40 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 A s 2 = 60 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 A s 3 = 80 SFLA 0,2,3,5,0,3,4,5,0,2,0,1 E v 2 to Ac2: Nv2→n8→n7→n18→n6→Nc2 31.9124 A s 4 = 40 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 A s 5 = 40 E v 4 to Ac5: Nv4→n17→n18→n7→n8→n9→Nc5 35.6330 Accident demand N a 1 = 1 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 N a 2 = 2 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 N a 3 = 2 E v 8 to Ac5: Nv8→n32→n18→n6→n1→n9→Nc5 40.7481 N a 4 = 1 E v 10 to Ac2: Nv10→n13→n4→n5→n6→Nc2 40.7709 N a 5 = 2 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758  IV Total number of vehicles 14 ISFLA 0,5,6,2,0,6,4,2,0,3,0,1,3,5 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 3 to Ac6: Nv3→n13→n24→n38→Nc6 28.6649 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 Total number of accidents 6 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 Accident severity A s 1 = 40 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164 A s 2 = 60 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 A s 3 = 80 SFLA 6,0,0,5,0,6,2,2,1,5,4,3,3,0 E v 1 to Ac6: Nv1→n3→n12→n23→n37→n38→Nc6 45.2505 A s 4 = 40 E v 4 to Ac5: Nv4→n17→n18→n7→n8→n9→Nc5 35.6330 A s 5 = 40 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 A s 6 = 60 E v 7 to Ac2: Nv7→n31→n17→n18→n6→Nc2 23.4594 Accident demand N a 1 = 1 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 N a 2 = 2 E v 9 to Ac1: Nv9→n33→n19→n20→n21→Nc1 37.8754 N a 3 = 2 E v 10 to Ac5: Nv10→n13→n12→n11→n10→n9→Nc5 47.7124 N a 4 = 1 E v 11 to Ac4: Nv11→n29→n15→n16→Nc4 21.9920 N a 5 = 2 E v 12 to Ac3: Nv12→n23→n24→n25→n26→n27→Nc3 48.7390 N a 6 = 2 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164  V Total number of vehicles 15 ISFLA 0,5,3,2,4,6,7,2,0,6,0,1,3,5,0 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 E v 5 to Ac4: Nv5→n29→n15→n16→Nc4 19.8843 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 Total number of accidents 7 E v 7 to Ac7: Nv7→n31→n47→Nc7 12.3566 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 10 to Ac6: Nv10→n13→n24→n38→Nc6 24.0304 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164 Accident severity A s 1 = 40 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 A s 2 = 60 SFLA 1,2,0,7,4,3,7,5,2,6,3,0,6,5,5 E v 1 to Ac1: Nv1→n3→n2→n10→n21→Nc1 31.2925 A s 3 = 80 E v 2 to Ac2: Nv2→n8→n7→n18→n6→Nc2 31.9124 A s 4 = 40 E v 4 to Ac7: Nv4→n17→n31→n47→Nc7 19.4956 A s 5 = 40 E v 5 to Ac4: Nv5→n29→n15→n16→Nc4 19.8843 A s 6 = 60 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 A s 7 = 40 E v 7 to Ac7: Nv7→n31→n47→Nc7 12.3566 Accident demand N a 1 = 1 E v 8 to Ac5: Nv8→n32→n18→n6→n1→n9→Nc5 40.7481 N a 2 = 2 E v 9 to Ac2: Nv9→n33→n32→n18→n6→Nc2 33.6324 N a 3 = 2 E v 10 to Ac6: Nv10→n13→n24→n38→Nc6 24.0304 N a 4 = 1 E v 11 to Ac3: Nv11→n29→n28→n27→Nc3 21.9920 N a 5 = 2 E v 13 to Ac6: Nv13→n28→n42→n41→n40→n39→n38→Nc6 37.1084 N a 6 = 2 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 N a 7 = 1 E v 15 to Ac5: Nv15→n32→n18→n6→n1→n9→Nc5 41.7501  Example no. The total number of feasible solutions Algorithm Objective function value The average evolution time (s) Success rate (%) in ten runs  I 48 ISFLA 7987 2.723 100 SFLA 7987 2.809 30 II 510 ISFLA 8113 15.643 100 SFLA 9179 5.324 0 III 612 ISFLA 10247 25.534 100 SFLA 13824 25.163 0 IV 714 ISFLA 12061 97.333 100 SFLA 18097 51.567 0 V 815 ISFLA 12947 144.199 100 SFLA 40149 101.786 0Figure 7
Evolutionary processes of the two algorithms for solving the illustrative examples.(  5) Result Analysis. The applicability of the model and the improved algorithm for solving the emergency vehicle dispatching problems with different complexity were verified by the five illustrative examples. Under the constraints of emergency vehicle requirements and time windows, the optimal dispatching strategy takes accident severity as key factor to optimize the total travel times of emergency vehicles. The results correspond to the decision rules of emergency vehicle dispatching.In example I, there are48 possible emergency vehicle selection strategies. Analyzing Table 9 shows that SFLA and ISFLA get the same optimal selection strategies. Their objective function values are 7987.In example II, there are510 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 8113. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 13.14% larger than that of ISFLA.In example III, there are612 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 10247. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 34.91% larger than that of ISFLA.In example IV, there are714 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 12061. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 50.04% larger than that of ISFLA.In example V, there are815 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 12947. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 210.10% larger than that of ISFLA.Therefore, compared with SFLA, the optimization performance of ISFLA is getting better and better with the increase of the number of decision variables. ISFLA preceded SFLA in realizing the optimal resolution for the complicated emergency vehicle selection problem.


### 5.2. Illustrative Examples of Dynamic Emergency Vehicle Dispatching Based on the Prediction Link Travel Speed

Examples I and II in Section5.1 were used to test the performance of dynamic emergency vehicle dispatching based on the prediction link travel speed. Polygonal-shaped travel speed functions vijt,t∈9:30,10:30,∀ni,nj∈E, were built using prediction travel speeds with different absolute error intervals (±3 km/h, ±5 km/h, and ±10 km/h). The present prediction methods can control the maximum absolute error of the prediction travel speed within ±10 km/h [31, 32], so the maximum prediction error was assumed as ±10 km/h. The prediction travel speed vij2ϕt0 was randomly generated within the interval vij1tϕ-10,vij1tϕ+10, in which, vij1tϕ is the real vehicle speed at the instant tϕ. In order to analyze the effect of the decrease of prediction error on the initial emergency vehicle dispatching strategy, the two prediction errors ±3 km/h and ±5 km/h were assumed. Then the travel time functions Tijt,t∈9:30,10:30, of each road section were calculated according to formula (5). The dynamic shortest path algorithm of emergency vehicles in expressway network proposed in our previous research [18] was used to calculate the shortest travel time and path, and the results are shown in Tables 10 and 11.Table 10
The shortest travel time of the illustrative examples based on the prediction link travel speed.
Vehicle no. Example no. Prediction error (km/h) Accident no. 1 2 3 4 1 I 0 31.2925 38.9665 54.9495 -- ±3 31.2737 38.5534 54.9460 -- ±5 32.1368 38.4649 55.5341 -- ±10 31.5763 42.7993 50.3388 -- II 0 31.2925 38.9665 54.9495 54.2331 ±3 31.2737 38.5534 54.9460 53.9916 ±5 32.1368 38.4649 55.5341 53.4761 ±10 31.5763 42.7993 50.3388 ∞  2 I 0 22.1482 31.9124 ∞ -- ±3 20.8670 32.3468 ∞ -- ±5 23.1840 31.3765 ∞ -- ±10 18.3767 32.2828 ∞ -- II 0 22.1482 31.9124 ∞ 28.8721 ±3 20.8670 32.3468 ∞ 28.8694 ±5 23.1840 31.3765 ∞ 30.9670 ±10 18.3767 32.2828 ∞ 26.4442  3 I 0 48.3611 47.2027 33.8637 -- ±3 46.8840 47.3166 33.7495 -- ±5 46.8704 47.2581 33.8035 -- ±10 46.4381 52.2131 33.2153 -- II 0 48.3611 47.2027 33.8637 59.0018 ±3 46.8840 47.3166 33.7495 59.8245 ±5 46.8704 47.2581 33.8035 ∞ ±10 46.4381 52.2131 33.2153 58.7999  4 I 0 41.0760 16.3454 53.4742 -- ±3 41.2953 16.4075 54.8336 -- ±5 41.6761 16.6789 52.0917 -- ±10 40.3378 17.3145 53.4260 -- II 0 41.0760 16.3454 ∞ 10.1881 ±3 41.2953 16.4075 ∞ 10.5117 ±5 41.6761 16.6789 ∞ 9.5027 ±10 40.3378 17.3145 ∞ 9.6885  5 I 0 49.9989 25.1126 38.7917 -- ±3 49.5269 25.4762 38.9094 -- ±5 50.8201 24.7458 38.8310 -- ±10 50.8567 28.2398 38.5163 -- II 0 49.9989 25.1126 38.7917 19.8843 ±3 49.5269 25.4762 38.9094 19.9819 ±5 50.8201 24.7458 38.8310 18.5017 ±10 50.8567 28.2398 38.5163 22.5535  6 I 0 44.4116 ∞ 26.3079 -- ±3 43.5208 51.2845 25.8029 -- ±5 47.1051 51.4706 25.4729 -- ±10 50.1697 54.9481 31.6198 -- II 0 44.4116 ∞ 26.3079 ∞ ±3 43.5208 51.2845 25.8029 59.7672 ±5 47.1051 51.4706 25.4729 ∞ ±10 50.1697 54.9481 31.6198 ∞  7 I 0 43.6867 23.4594 56.5536 -- ±3 43.8486 23.8514 56.9816 -- ±5 42.8287 22.6855 53.4435 -- ±10 42.4865 24.9977 55.1983 -- II 0 43.6867 23.4594 56.5536 14.4705 ±3 43.8486 23.8514 56.9816 14.7354 ±5 42.8287 22.6855 53.4435 13.9424 ±10 42.4865 24.9977 55.1983 13.5972  8 I 0 42.6146 21.7823 ∞ -- ±3 42.7782 21.8997 ∞ -- ±5 42.5819 21.8541 ∞ -- ±10 40.9011 26.2546 ∞ -- II 0 42.6146 21.7823 ∞ 21.3312 ±3 42.7782 21.8997 ∞ 21.5001 ±5 42.5819 21.8541 ∞ 20.9878 ±10 40.9011 26.2546 ∞ 22.7096  9 II 0 37.8754 33.6324 ∞ 30.5210 ±3 37.3625 33.4413 ∞ 29.9943 ±5 39.1213 34.4820 ∞ 31.7022 ±10 37.5274 35.6110 ∞ 29.7247  10 II 0 42.3397 40.7709 28.2020 52.5731 ±3 40.9388 40.6356 28.5534 53.1496 ±5 42.4467 40.9227 28.6415 55.0761 ±10 41.3142 41.4190 26.8230 51.2051Table 11
The shortest travel time path of the illustrative examples based on the prediction link travel speed.
Vehicle no. Example no. Prediction error (km/h) Accident no. 1 2 3 4 1 I 0 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±3 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±5 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±10 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- II 0 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±3 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±5 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±10 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 BL  2 I 0 8, 9, 20, 21 8, 7, 18, 6 BL -- ±3 8, 9, 20, 21 8, 7, 18, 6 BL -- ±5 8, 9, 20, 21 8, 7, 1, 6 BL -- ±10 8, 9, 20, 21 8, 7, 18, 6 BL -- II 0 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 ±3 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 ±5 8, 9, 20, 21 8, 7, 1, 6 BL 8, 7, 18, 17, 16 ±10 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16  3 I 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- II 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 BL ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 14, 15, 16  4 I 0 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±3 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±5 17, 18, 7, 8, 19, 20, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±10 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- II 0 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 ±3 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 ±5 17, 18, 7, 8, 19, 20, 21 17, 18, 6 BL 17, 16 ±10 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16  5 I 0 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±3 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±5 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±10 29, 15, 5, 6, 1, 9, 20, 21 29, 15, 5, 6 29, 28, 27 -- II 0 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±3 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±5 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±10 29, 15, 5, 6, 1, 9, 20, 21 29, 15, 5, 6 29, 28, 27 29, 30, 16  6 I 0 25, 24, 23, 22, 21 BL 25, 26, 27 -- ±3 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- ±5 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- ±10 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- II 0 25, 24, 23, 22, 21 BL 25, 26, 27 BL ±3 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 25, 24, 13, 4, 5, 15, 16 ±5 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 BL ±10 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 BL  7 I 0 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±3 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±5 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±10 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 43, 42, 41, 27 -- II 0 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±3 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±5 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±10 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 43, 42, 41, 27 31, 30, 16  8 I 0 32, 33, 19, 20, 21 32, 18, 6 BL -- ±3 32, 33, 19, 20, 21 32, 18, 6 BL -- ±5 32, 33, 19, 20, 21 32, 18, 6 BL -- ±10 32, 33, 19, 20, 21 32, 18, 6 BL -- II 0 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±3 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±5 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±10 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16  9 II 0 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 ±3 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 ±5 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 31, 30, 16 ±10 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16  10 II 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 14, 15, 16 Note. BL means that the travel time of the optimal path exceeds the upper limit of the time window.ISFLA was used to find the optimal dispatching strategy of the two examples under three prediction errors, and the best solutions are shown in Table12.Table 12
Optimal emergency vehicle dispatching strategy of the illustrative examples based on the prediction link travel speed.
Example no. Prediction error (km/h) The optimal solution Objective function value based on the prediction travel speed Objective function value based on the real travel speed  I 0 0, 1, 3, 2, 0, 3, 0, 2 -- 7987 ±3 0, 1, 3, 2, 0, 3, 0, 2 7897 7987 ±5 0, 1, 3, 2, 0, 3, 0, 2 7981 7987 ±10 0, 1, 3, 2, 0, 3, 2, 0 8461 8088  II 0 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8113 8113 ±3 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8071 8113 ±5 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8126 8113 ±10 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8569 8113  Example no. Prediction error (km/h) Optimal emergency vehicle dispatching strategy Prediction travel time (min) Real travel time (min)  I 0 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 -- 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 -- 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 -- 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 -- 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 -- 26.3079 ±3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 20.8670 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.4075 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8997 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.7495 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.8029 26.3079 ±5 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 23.1840 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.6789 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8541 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8035 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.4729 26.3079 ±10 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 18.3767 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 17.3145 16.3454 E v 7 to Ac2: Nv7→n31→n17→n18→n6→Nc2 24.9977 23.4594 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.2153 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 31.6198 26.3079  II 0 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 -- 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 -- 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 -- 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 -- 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 -- 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 -- 14.4705 ±3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 20.8670 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.4075 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8997 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.8029 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.5534 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.7354 14.4705 ±5 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 23.1840 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.6789 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8541 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.4729 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.6415 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 13.9424 14.4705 ±10 E v 2 to Ac1:Nv2→n8→n9→n20→n21→Nc1 18.3767 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 17.3145 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 26.2546 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 31.6198 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 26.8230 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 13.5972 14.4705In example I, the optimal emergency vehicle dispatching strategy (including vehicle routing and selection), which is based on the prediction link travel speed with prediction errors of ±3, ±5, is the same as the actual optimal strategy. However, when the prediction error is ±10, the rescue vehicle for the accidentAc2 is different from the actual optimal strategy. The emergency vehicle Ev7 instead of the vehicle Ev8 is dispatched to the accident Ac2. This led to a 23.4594 − 21.7823 = 1.6771 minutes extension of the rescue time for the accident Ac2. The objective function value based on the prediction travel speed is 101 more than that based on the real travel speed. It can be seen that the prediction error of the travel speed affects the accuracy of the initial emergency vehicle dispatching, but when the absolute prediction error is within ±10, the effect is not obvious.In example II, the optimal emergency vehicle dispatching strategy (including vehicle routing and selection), which is based on the prediction link travel speed with prediction errors of ±3, ±5, and ±10, is the same as the actual optimal strategy.It is known from the two examples that the prediction error of ±10 can basically meet the requirements of the initial dispatching.


### 5.3. Illustrative Example of Dynamic Adjustment of Dispatching Strategy

Example I in Section5.2 was used to test the performance of dynamic adjustment of dispatching strategy. Suppose that the prediction error of link travel speed was ±5. At 9:30, emergency vehicles were dispatched to accidents according to the optimal dispatching strategy obtained in Section 5.2. Emergency vehicle Ev2 was dispatched to accident Ac1. Emergency vehicle Ev3 was dispatched to accident Ac3. Emergency vehicle Ev4 was dispatched to accident Ac2. Emergency vehicle Ev6 was dispatched to accident Ac3. Emergency vehicle Ev8 was dispatched to accident Ac2. Emergency vehicles Ev1, Ev5, and Ev7 were idle vehicles. The optimal dispatching strategy is shown in Figure 8.Figure 8
Optimal emergency vehicle dispatching strategy at 9:30.At 9:35, a new accidentAc4 happens on the road section 9,20. According to the real link travel speed, location of each emergency vehicle was calculated. They are shown in Figure 9.Figure 9
Locations of emergency vehicles and accidents at 9:35.Due to the influence of the accidentAc4, road conditions of the accident section 9,20 and its upstream sections 8,9 and 1,9 changed. In order to consider the impact of accident Ac4 on upstream sections, a weakening factor αijt to the travel speed of upstream section ni,nj was introduced. Therefore, the travel speed functions of sections 8,9 and 1,9 were v8,9′t=α8,9t·v8,9t, v1,9′t=α1,9t·v1,9t, respectively. Suppose that αij decreases linearly with time t. The initial value αijt=tφ=0.7. When t=tφ+30min, αijt=0.53.The travel speed of each road section was recollected at 9:35, and the prediction travel speed function was calculated. We suppose that travel speed prediction error of road sections8,9 and 1,9 was ±10 and that of other road sections was ±5. Then, travel paths of emergency vehicles were replanned, and the dispatching strategy was adjusted. The optimal dispatching strategy at 9:35 is shown in Figure 10. The dynamic emergency vehicle dispatching process is shown in Table 13.Table 13
Dynamic emergency vehicle dispatching process.
Decision making instant Vehicle no. Road section of vehicle Location of vehicle The optimal solution Optimal emergency vehicle dispatching strategy 9:30 1 n 2 , n 3 L 2,55 = L 55,3 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 Ev4 to Ac2: Nv4→n17→n18→n6→Nc2 Ev8 to Ac2: Nv8→n32→n18→n6→Nc2 Ev3 to Ac3: Nv3→n13→n14→n27→Nc3 Ev6 to Ac3: Nv6→n25→n26→n27→Nc3 2 n 9 , n 8 L 9,56 = L 56,8 3 n 12 , n 13 L 12,57 = L 57,13 4 n 18 , n 17 L 18,58 = L 58,17 5 n 15 , n 29 L 15,59 = L 59,29 6 n 39 , n 25 L 39,60 = L 60,25 7 n 30 , n 31 L 30,61 = L 61,31 8 n 33 , n 32 L 33,62 = L 62,32  9:35 1 n 2 , n 3 L 2,55 = L 55,3 1,4,3,2,0,3,0,2 E v 1 to Ac1: Nv1→n3→n2→n10→n21→Nc1 Ev4 to Ac2: Nv4→n6→Nc2 Ev8 to Ac2: Nv8→n18→n6→Nc2 Ev3 to Ac3: Nv3→n13→n14→Nc3 Ev6 to Ac3: Nv6→n25→n26→n27→Nc3 Ev2 to Ac4: Nv2→n9→Nc4 2 n 8 , n 9 L 8,56 = 0.12 × L 8,9 L 56,9 = 0.88 × L 8,9 3 n 12 , n 13 L 12,57 = 0.77 × L 12,13 L 57,13 = 0.23 × L 12,13 4 n 18 , n 6 L 18,58 = 0.10 × L 18,6 L 58,6 = 0.90 × L 18,6 5 n 15 , n 29 L 15,59 = L 59,29 6 n 25 n 25 7 n 30 , n 31 L 30,61 = L 61,31 8 n 32 , n 18 L 32,62 = 0.16  ×  L 32,18 L 62,18 = 0.84  ×  L 32,18Figure 10
Optimal emergency vehicle dispatching strategy at 9:35.When the accidentAc4 happened at 9:35, the dynamical adjustment mechanism timely responded to sudden changes in road conditions of the optimal path 8,9,20,21 of emergency vehicle Ev2. After recalculating the dispatching strategy, the idle emergency vehicle Ev1 replaced the emergency vehicle Ev2 to rescue the accident Ac1. The emergency vehicle successfully bypassed road sections 9,20 and 8,9 to ensure the time limit for emergency rescue. Meanwhile, the emergency vehicle Ev2 with the shortest travel time was dispatched to the new accident Ac4. Therefore, the adjustment of emergency vehicle dispatching strategy can effectively shorten the response time of accident.


## 5.1. Illustrative Examples of Emergency Vehicle Dispatching Based on the Improved Shuffled Frog Leaping Algorithm

(  1) Calculating Link Travel Time Time-Dependent Function. Real link travel speeds vij1t at instant t∈9:30,9:35,9:40,…,10:30 were used to build the polygonal-shaped travel speed function. Then the travel time function Tijt, t∈9:30,10:30, of each road section was calculated according to formula (5). Figure 5 shows travel speed time-dependent functions of road sections n1,n2, n2,n1, n18,n32, n32,n18, and Figure 6 shows corresponding travel time time-dependent functions of these road sections.Figure 5
Link travel speed time-dependent functions.Figure 6
Link travel time time-dependent functions.(  2) Parameters of Illustrative Examples of Emergency Vehicle Dispatching. We assume that there are 15 emergency vehicles at most in the expressway network. At 9:30, 7 accidents at most occurred simultaneously. Tables 3 and 4 list the parameters of the example.Table 3
Accident parameters of the illustrative example.
Accident no. Accident node Road section of accident Location of accident Accident level Accident severity Accident demand 1 N c 1 / n 48 n 21 , n 22 L 21,48 = L 48,22 Minor 40 1 2 N c 2 / n 49 n 6 , n 5 L 6,49 = L 49,5 Ordinary 60 2 3 N c 3 / n 50 n 27 , n 14 L 27,50 = L 50,14 Major 80 2 4 N c 4 / n 51 n 16 , n 15 L 16,51 = L 51,15 Minor 40 1 5 N c 5 / n 52 n 9 , n 20 L 9,52 = L 52,20 Minor 40 2 6 N c 6 / n 53 n 38 , n 39 L 38,53 = L 53,39 Ordinary 60 2 7 N c 7 / n 54 n 47 , n 44 L 47,54 = L 54,44 Minor 40 1Table 4
Emergency vehicle parameters of the illustrative example.
Vehicle no. 1 2 3 4 5 Vehicle node N v 1 / n 55 N v 2 / n 56 N v 3 / n 57 N v 4 / n 58 N v 5 / n 59 Road section of vehicle n 2 , n 3 n 9 , n 8 n 12 , n 13 n 18 , n 17 n 15 , n 29 Location of vehicle L 2,55 = L 55,3 L 9,56 = L 56,8 L 12,57 = L 57,13 L 18,58 = L 58,17 L 15,59 = L 59,29 Vehicle no. 6 7 8 9 10 Vehicle node N v 6 / n 60 N v 7 / n 61 N v 8 / n 62 N v 9 / n 63 N v 10 / n 64 Road section of vehicle n 39 , n 25 n 30 , n 31 n 33 , n 32 n 19 , n 33 n 24 , n 13 Location of vehicle L 39,60 = L 60,25 L 30,61 = L 61,31 L 33,62 = L 62,32 L 19,63 = L 63,33 L 24,64 = L 64,13 Vehicle no. 11 12 13 14 15 Vehicle node N v 11 / n 65 N v 12 / n 66 N v 13 / n 67 N v 14 / n 68 N v 15 / n 69 Road section of vehicle n 28 , n 29 n 12 , n 23 n 27 , n 28 n 2 , n 10 n 18 , n 32 Location of vehicle L 28,65 = L 65,29 L 12,66 = L 66,23 L 27,67 = L 67,28 L 2,68 = L 68,10 L 18,69 = L 69,32(  3) Calculating the Shortest Travel Time for Each Emergency Vehicle to Each Accident. We assume 5 emergency vehicle dispatching examples with different complexity. The first example has 8 emergency vehicles and 3 accidents. Then, the numbers of emergency vehicles and accidents gradually increase, and the other four examples are formed. Emergency vehicles and accidents in each example are shown in Table 5.Table 5
Emergency vehicles and accidents in each example.
Example no. Vehicle no. Accident no. I 1, 2, 3, 4, 5, 6, 7, 8 1, 2, 3 II 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 1, 2, 3, 4 III 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 1, 2, 3, 4, 5 IV 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 1, 2, 3, 4, 5, 6 V 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 1, 2, 3, 4, 5, 6, 7The dynamic shortest path algorithm of emergency vehicles in expressway network proposed in our previous research [18] was used to calculate the shortest travel time and path, and the results are shown in Tables 6 and 7.Table 6
The shortest travel time of the illustrative examples based on the real link travel speed.
Vehicle no. Example no. Accident no. 1 2 3 4 5 6 7 1 I 31.2925 38.9665 54.9495 -- -- -- -- II 31.2925 38.9665 54.9495 54.2331 -- -- -- III 31.2925 38.9665 54.9495 54.2331 34.8666 -- -- IV 31.2925 38.9665 54.9495 54.2331 34.8666 45.2505 -- V 31.2925 38.9665 54.9495 54.2331 34.8666 45.2505 ∞  2 I 22.1482 31.9124 ∞ -- -- -- -- II 22.1482 31.9124 ∞ 28.8721 -- -- -- III 26.9763 31.9124 ∞ 28.8721 15.2541 -- -- IV 26.9763 31.9124 ∞ 28.8721 15.2541 ∞ -- V 26.9763 31.9124 ∞ 28.8721 15.2541 ∞ 38.6391  3 I 48.3611 47.2027 33.8637 -- -- -- -- II 48.3611 47.2027 33.8637 59.0018 -- -- -- III 48.3611 47.2027 33.8637 59.0018 54.0921 -- -- IV 48.3611 47.2027 33.8637 59.0018 54.0921 28.6649 -- V 48.3611 47.2027 33.8637 59.0018 54.0921 28.6649 ∞  4 I 41.0760 16.3454 53.4742 -- -- -- -- II 41.0760 16.3454 ∞ 10.1881 -- -- -- III 41.0760 16.3454 ∞ 10.1881 35.6330 -- -- IV 41.0760 16.3454 ∞ 10.1881 35.6330 ∞ -- V 41.0760 16.3454 ∞ 10.1881 35.6330 ∞ 19.4956  5 I 49.9989 25.1126 38.7917 -- -- -- -- II 49.9989 25.1126 38.7917 19.8843 -- -- -- III 49.9989 25.1126 38.7917 19.8843 43.5353 -- -- IV 49.9989 25.1126 38.7917 19.8843 43.5353 45.7355 -- V 49.9989 25.1126 38.7917 19.8843 43.5353 45.7355 23.4806  6 I 44.4116 ∞ 26.3079 -- -- -- -- II 44.4116 ∞ 26.3079 ∞ -- -- -- III 44.4116 ∞ 26.3079 ∞ 54.4887 -- -- IV 44.4116 ∞ 26.3079 ∞ 54.4887 21.4419 -- V 44.4116 ∞ 26.3079 ∞ 54.4887 21.4419 ∞  7 I 43.6867 23.4594 56.5536 -- -- -- -- II 43.6867 23.4594 56.5536 14.4705 -- -- -- III 43.6867 23.4594 56.5536 14.4705 41.8074 -- -- IV 43.6867 23.4594 56.5536 14.4705 41.8074 ∞ -- V 43.6867 23.4594 56.5536 14.4705 41.8074 ∞ 12.3566  8 I 42.6146 21.7823 ∞ -- -- -- -- II 42.6146 21.7823 ∞ 21.3312 -- -- -- III 42.6146 21.7823 ∞ 21.3312 40.7481 -- -- IV 42.6146 21.7823 ∞ 21.3312 40.7481 ∞ -- V 42.6146 21.7823 ∞ 21.3312 40.7481 ∞ 20.0396  9 II 37.8754 33.6324 ∞ 30.5210 -- -- -- III 37.8754 33.6324 ∞ 30.5210 42.3188 -- -- IV 37.8754 33.6324 ∞ 30.5210 42.3188 ∞ -- V 37.8754 33.6324 ∞ 30.5210 42.3188 ∞ 29.6284  10 II 42.3397 40.7709 28.2020 52.5731 -- -- -- III 42.3397 40.7709 28.2020 52.5731 47.7124 -- -- IV 42.3397 40.7709 28.2020 52.5731 47.7124 24.0304 -- V 42.3397 40.7709 28.2020 52.5731 47.7124 24.0304 ∞  11 III ∞ 27.4119 40.8674 21.9920 45.8012 -- -- IV ∞ 27.4119 40.8674 21.9920 45.8012 48.8987 -- V ∞ 27.4119 40.8674 21.9920 45.8012 48.8987 25.3691  12 III 25.3758 49.7617 48.7390 ∞ 33.5190 -- -- IV 25.3758 49.7617 48.7390 ∞ 33.5190 32.6388 -- V 25.3758 49.7617 48.7390 ∞ 33.5190 32.6388 ∞  13 IV ∞ 34.0944 21.9164 31.4456 54.1145 37.1084 -- V ∞ 34.0944 21.9164 31.4456 54.1145 37.1084 33.8540  14 IV 10.1994 32.9815 ∞ 48.1107 13.8316 54.7018 -- V 10.1994 32.9815 ∞ 48.1107 13.8316 54.7018 ∞  15 V 43.5208 22.7684 ∞ 22.3348 41.7501 ∞ 20.7021Table 7
The shortest travel time path of the illustrative examples based on the real link travel speed.
Vehicle no. Example no. Accident no. 1 2 3 4 5 6 7 1 I 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- II 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 III 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 -- -- IV 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 3, 12, 23, 37, 38 V 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 3, 2, 1, 9 3, 12, 23, 37, 38 BL  2 I 8, 9, 20, 21 8, 7, 18, 6 BL -- II 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 III 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 -- -- IV 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 BL V 8, 9, 10, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 8, 9 BL 8, 7, 18, 17, 16, 30, 47  3 I 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- II 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 III 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 -- -- IV 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 -- V 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 BL  4 I 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- II 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 III 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 -- -- IV 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 BL -- V 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 17, 18, 7, 8, 9 BL 17, 31, 47  5 I 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- II 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 III 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 -- -- IV 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 -- V 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 29, 30, 47  6 I 25, 24, 23, 22, 21 BL 25, 26, 27 -- II 25, 24, 23, 22, 21 BL 25, 26, 27 BL III 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 -- -- IV 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 25, 24, 38 -- V 25, 24, 23, 22, 21 BL 25, 26, 27 BL 25, 24, 23, 12, 11, 10, 9 25, 24, 38 BL  7 I 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- II 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 III 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 -- -- IV 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 BL -- V 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 31, 17, 18, 6, 1, 9 BL 31, 47  8 I 32, 33, 19, 20, 21 32, 18, 6 BL -- II 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 III 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 -- -- IV 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL -- V 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL 32, 31, 47  9 II 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 III 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 -- -- IV 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 BL -- V 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 33, 19, 8, 9 BL 33, 32, 31, 47  10 II 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 III 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 -- -- IV 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 -- V 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 13, 12, 11, 10, 9 13, 24, 38 BL  11 III BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 -- -- IV BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 -- V BL 29, 15, 5, 6 29, 28, 27 29, 15, 16 29, 15, 5, 6, 1, 9 29, 43, 42, 41, 40, 39, 38 29, 30, 47  12 III 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 -- -- IV 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 23, 37, 38 -- V 23, 22, 21 23, 12, 3, 2, 1, 6 23, 24, 25, 26, 27 BL 23, 12, 11, 10, 9 23, 37, 38 BL  13 IV BL 28, 29, 15, 5, 6 28, 27 28, 29, 15, 16 28, 29, 15, 5, 6, 1, 9 28, 42, 41, 40, 39, 38 -- V BL 28, 29, 15, 5, 6 28, 27 28, 29, 15, 16 28, 29, 15, 5, 6, 1, 9 28, 42, 41, 40, 39, 38 28, 29, 30, 47  14 IV 10, 21 10, 2, 1, 6 BL 10, 9, 8, 7, 18, 17, 16 10, 9 10, 21, 35, 36, 37, 38 -- V 10, 21 10, 2, 1, 6 BL 10, 9, 8, 7, 18, 17, 16 10, 9 10, 21, 35, 36, 37, 38 BL  15 V 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 32, 18, 6, 1, 9 BL 32, 31, 47 Note. BL means that the travel time of the optimal path exceeds the upper limit of the time window.The expressway network is a directed network. When the emergency vehicleEvl,l=1,2,…,L, goes to the accident Acu,u=1,2,…,U, it must run along the direction of the road section to arrive at the node n1l and then choose the next road section. In which, n1l is the end of the road section n0l,n1l where the emergency vehicle Evl is located. Road section from the emergency vehicle’s location Nvl to node n1l is a necessary way for emergency vehicle Evl. In the same way, the emergency vehicle must arrive at the node n0u and then run along the direction of the road section to reach the accident node Ncu. In which, n0u is the start of the road section n0u,n1u where the accident Acu is located. Road section from the node n0u to the accident’s location Ncu is a necessary way for emergency vehicle Evl too. We only need to calculate the optimal path from the node n1l to the node n0u, so the optimal path from the node n1l to the node n0u is given in Table 7.(  4) Calculating the Optimal Dispatching Strategy. ISFLA was used to find the optimal dispatching strategy of the five examples. The improved algorithm was compared with SFLA. After some testing, parameters of ISFLA were defined as in Table 8. After ten runs, the best solutions of the five examples obtained by using these two algorithms are summarized in Table 9. Figure 7 shows the evolutionary processes of the two algorithms of example I and example V.Table 8
Parameter selection of ISFLA.
Example no. I P a c I T D d m a x  d=1,…,D Z d m a x  d=1,…,D Z d m i n  d=1,…,D D θ I 150 15 10 150 3 4 1 8 0.05 II 150 15 10 350 4 5 1 10 0.05 III 300 20 15 600 5 6 1 12 0.05 IV 374 22 17 800 5 7 1 14 0.05 V 500 25 20 900 6 8 1 15 0.05Table 9
Optimal emergency vehicle dispatching strategy of the illustrative examples based on the real link travel speed.
Example no. Example parameters Algorithm The optimal solution Optimal emergency vehicle dispatching strategy Travel time (min) I Total number of vehicles 8 ISFLA 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 3 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 Accident severity A s 1 = 40 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 A s 2 = 60 SFLA 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 A s 3 = 80 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Accident demand N a 1 = 1 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 N a 2 = 2 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 N a 3 = 2 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079  II Total number of vehicles 10 ISFLA 0,1,0,2,0,3,4,2,0,3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 4 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 Accident severity A s 1 = 40 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 A s 2 = 60 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 A s 3 = 80 SFLA 0,1,0,4,2,3,0,0,2,3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 22.1482 A s 4 = 40 E v 5 to Ac2: Nv5→n29→n15→n5→n6→Nc2 25.1126 Accident demand N a 1 = 1 E v 9 to Ac2: Nv9→n33→n32→n18→n6→Nc2 33.6324 N a 2 = 2 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 N a 3 = 2 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 N a 4 = 1 E v 4 to Ac4: Nv4→n17→n16→Nc4 10.1881  III Total number of vehicles 12 ISFLA 5,5,0,2,0,3,4,2,0,3,0,1 E v 1 to Ac5: Nv1→n3→n2→n1→n9→Nc5 34.8666 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 Total number of accidents 5 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 Accident severity A s 1 = 40 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 A s 2 = 60 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 A s 3 = 80 SFLA 0,2,3,5,0,3,4,5,0,2,0,1 E v 2 to Ac2: Nv2→n8→n7→n18→n6→Nc2 31.9124 A s 4 = 40 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 A s 5 = 40 E v 4 to Ac5: Nv4→n17→n18→n7→n8→n9→Nc5 35.6330 Accident demand N a 1 = 1 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 N a 2 = 2 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 N a 3 = 2 E v 8 to Ac5: Nv8→n32→n18→n6→n1→n9→Nc5 40.7481 N a 4 = 1 E v 10 to Ac2: Nv10→n13→n4→n5→n6→Nc2 40.7709 N a 5 = 2 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758  IV Total number of vehicles 14 ISFLA 0,5,6,2,0,6,4,2,0,3,0,1,3,5 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 3 to Ac6: Nv3→n13→n24→n38→Nc6 28.6649 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 Total number of accidents 6 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.4705 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.2020 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 Accident severity A s 1 = 40 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164 A s 2 = 60 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 A s 3 = 80 SFLA 6,0,0,5,0,6,2,2,1,5,4,3,3,0 E v 1 to Ac6: Nv1→n3→n12→n23→n37→n38→Nc6 45.2505 A s 4 = 40 E v 4 to Ac5: Nv4→n17→n18→n7→n8→n9→Nc5 35.6330 A s 5 = 40 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 A s 6 = 60 E v 7 to Ac2: Nv7→n31→n17→n18→n6→Nc2 23.4594 Accident demand N a 1 = 1 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 N a 2 = 2 E v 9 to Ac1: Nv9→n33→n19→n20→n21→Nc1 37.8754 N a 3 = 2 E v 10 to Ac5: Nv10→n13→n12→n11→n10→n9→Nc5 47.7124 N a 4 = 1 E v 11 to Ac4: Nv11→n29→n15→n16→Nc4 21.9920 N a 5 = 2 E v 12 to Ac3: Nv12→n23→n24→n25→n26→n27→Nc3 48.7390 N a 6 = 2 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164  V Total number of vehicles 15 ISFLA 0,5,3,2,4,6,7,2,0,6,0,1,3,5,0 E v 2 to Ac5: Nv2→n8→n9→Nc5 15.2541 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8637 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.3454 E v 5 to Ac4: Nv5→n29→n15→n16→Nc4 19.8843 E v 6 to Ac6: Nv6→n25→n24→n38→Nc6 21.4419 Total number of accidents 7 E v 7 to Ac7: Nv7→n31→n47→Nc7 12.3566 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.7823 E v 10 to Ac6: Nv10→n13→n24→n38→Nc6 24.0304 E v 12 to Ac1: Nv12→n23→n22→n21→Nc1 25.3758 E v 13 to Ac3: Nv13→n28→n27→Nc3 21.9164 Accident severity A s 1 = 40 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 A s 2 = 60 SFLA 1,2,0,7,4,3,7,5,2,6,3,0,6,5,5 E v 1 to Ac1: Nv1→n3→n2→n10→n21→Nc1 31.2925 A s 3 = 80 E v 2 to Ac2: Nv2→n8→n7→n18→n6→Nc2 31.9124 A s 4 = 40 E v 4 to Ac7: Nv4→n17→n31→n47→Nc7 19.4956 A s 5 = 40 E v 5 to Ac4: Nv5→n29→n15→n16→Nc4 19.8843 A s 6 = 60 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 26.3079 A s 7 = 40 E v 7 to Ac7: Nv7→n31→n47→Nc7 12.3566 Accident demand N a 1 = 1 E v 8 to Ac5: Nv8→n32→n18→n6→n1→n9→Nc5 40.7481 N a 2 = 2 E v 9 to Ac2: Nv9→n33→n32→n18→n6→Nc2 33.6324 N a 3 = 2 E v 10 to Ac6: Nv10→n13→n24→n38→Nc6 24.0304 N a 4 = 1 E v 11 to Ac3: Nv11→n29→n28→n27→Nc3 21.9920 N a 5 = 2 E v 13 to Ac6: Nv13→n28→n42→n41→n40→n39→n38→Nc6 37.1084 N a 6 = 2 E v 14 to Ac5: Nv14→n10→n9→Nc5 13.8316 N a 7 = 1 E v 15 to Ac5: Nv15→n32→n18→n6→n1→n9→Nc5 41.7501  Example no. The total number of feasible solutions Algorithm Objective function value The average evolution time (s) Success rate (%) in ten runs  I 48 ISFLA 7987 2.723 100 SFLA 7987 2.809 30 II 510 ISFLA 8113 15.643 100 SFLA 9179 5.324 0 III 612 ISFLA 10247 25.534 100 SFLA 13824 25.163 0 IV 714 ISFLA 12061 97.333 100 SFLA 18097 51.567 0 V 815 ISFLA 12947 144.199 100 SFLA 40149 101.786 0Figure 7
Evolutionary processes of the two algorithms for solving the illustrative examples.(  5) Result Analysis. The applicability of the model and the improved algorithm for solving the emergency vehicle dispatching problems with different complexity were verified by the five illustrative examples. Under the constraints of emergency vehicle requirements and time windows, the optimal dispatching strategy takes accident severity as key factor to optimize the total travel times of emergency vehicles. The results correspond to the decision rules of emergency vehicle dispatching.In example I, there are48 possible emergency vehicle selection strategies. Analyzing Table 9 shows that SFLA and ISFLA get the same optimal selection strategies. Their objective function values are 7987.In example II, there are510 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 8113. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 13.14% larger than that of ISFLA.In example III, there are612 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 10247. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 34.91% larger than that of ISFLA.In example IV, there are714 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 12061. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 50.04% larger than that of ISFLA.In example V, there are815 possible emergency vehicle selection strategies. Analyzing Table 9 shows that the objective function of optimal selection strategy obtained by using ISFLA is 12947. The SFLA is unwanted early convergence. Its objective function value of optimal selection strategies is 210.10% larger than that of ISFLA.Therefore, compared with SFLA, the optimization performance of ISFLA is getting better and better with the increase of the number of decision variables. ISFLA preceded SFLA in realizing the optimal resolution for the complicated emergency vehicle selection problem.


## 5.2. Illustrative Examples of Dynamic Emergency Vehicle Dispatching Based on the Prediction Link Travel Speed

Examples I and II in Section5.1 were used to test the performance of dynamic emergency vehicle dispatching based on the prediction link travel speed. Polygonal-shaped travel speed functions vijt,t∈9:30,10:30,∀ni,nj∈E, were built using prediction travel speeds with different absolute error intervals (±3 km/h, ±5 km/h, and ±10 km/h). The present prediction methods can control the maximum absolute error of the prediction travel speed within ±10 km/h [31, 32], so the maximum prediction error was assumed as ±10 km/h. The prediction travel speed vij2ϕt0 was randomly generated within the interval vij1tϕ-10,vij1tϕ+10, in which, vij1tϕ is the real vehicle speed at the instant tϕ. In order to analyze the effect of the decrease of prediction error on the initial emergency vehicle dispatching strategy, the two prediction errors ±3 km/h and ±5 km/h were assumed. Then the travel time functions Tijt,t∈9:30,10:30, of each road section were calculated according to formula (5). The dynamic shortest path algorithm of emergency vehicles in expressway network proposed in our previous research [18] was used to calculate the shortest travel time and path, and the results are shown in Tables 10 and 11.Table 10
The shortest travel time of the illustrative examples based on the prediction link travel speed.
Vehicle no. Example no. Prediction error (km/h) Accident no. 1 2 3 4 1 I 0 31.2925 38.9665 54.9495 -- ±3 31.2737 38.5534 54.9460 -- ±5 32.1368 38.4649 55.5341 -- ±10 31.5763 42.7993 50.3388 -- II 0 31.2925 38.9665 54.9495 54.2331 ±3 31.2737 38.5534 54.9460 53.9916 ±5 32.1368 38.4649 55.5341 53.4761 ±10 31.5763 42.7993 50.3388 ∞  2 I 0 22.1482 31.9124 ∞ -- ±3 20.8670 32.3468 ∞ -- ±5 23.1840 31.3765 ∞ -- ±10 18.3767 32.2828 ∞ -- II 0 22.1482 31.9124 ∞ 28.8721 ±3 20.8670 32.3468 ∞ 28.8694 ±5 23.1840 31.3765 ∞ 30.9670 ±10 18.3767 32.2828 ∞ 26.4442  3 I 0 48.3611 47.2027 33.8637 -- ±3 46.8840 47.3166 33.7495 -- ±5 46.8704 47.2581 33.8035 -- ±10 46.4381 52.2131 33.2153 -- II 0 48.3611 47.2027 33.8637 59.0018 ±3 46.8840 47.3166 33.7495 59.8245 ±5 46.8704 47.2581 33.8035 ∞ ±10 46.4381 52.2131 33.2153 58.7999  4 I 0 41.0760 16.3454 53.4742 -- ±3 41.2953 16.4075 54.8336 -- ±5 41.6761 16.6789 52.0917 -- ±10 40.3378 17.3145 53.4260 -- II 0 41.0760 16.3454 ∞ 10.1881 ±3 41.2953 16.4075 ∞ 10.5117 ±5 41.6761 16.6789 ∞ 9.5027 ±10 40.3378 17.3145 ∞ 9.6885  5 I 0 49.9989 25.1126 38.7917 -- ±3 49.5269 25.4762 38.9094 -- ±5 50.8201 24.7458 38.8310 -- ±10 50.8567 28.2398 38.5163 -- II 0 49.9989 25.1126 38.7917 19.8843 ±3 49.5269 25.4762 38.9094 19.9819 ±5 50.8201 24.7458 38.8310 18.5017 ±10 50.8567 28.2398 38.5163 22.5535  6 I 0 44.4116 ∞ 26.3079 -- ±3 43.5208 51.2845 25.8029 -- ±5 47.1051 51.4706 25.4729 -- ±10 50.1697 54.9481 31.6198 -- II 0 44.4116 ∞ 26.3079 ∞ ±3 43.5208 51.2845 25.8029 59.7672 ±5 47.1051 51.4706 25.4729 ∞ ±10 50.1697 54.9481 31.6198 ∞  7 I 0 43.6867 23.4594 56.5536 -- ±3 43.8486 23.8514 56.9816 -- ±5 42.8287 22.6855 53.4435 -- ±10 42.4865 24.9977 55.1983 -- II 0 43.6867 23.4594 56.5536 14.4705 ±3 43.8486 23.8514 56.9816 14.7354 ±5 42.8287 22.6855 53.4435 13.9424 ±10 42.4865 24.9977 55.1983 13.5972  8 I 0 42.6146 21.7823 ∞ -- ±3 42.7782 21.8997 ∞ -- ±5 42.5819 21.8541 ∞ -- ±10 40.9011 26.2546 ∞ -- II 0 42.6146 21.7823 ∞ 21.3312 ±3 42.7782 21.8997 ∞ 21.5001 ±5 42.5819 21.8541 ∞ 20.9878 ±10 40.9011 26.2546 ∞ 22.7096  9 II 0 37.8754 33.6324 ∞ 30.5210 ±3 37.3625 33.4413 ∞ 29.9943 ±5 39.1213 34.4820 ∞ 31.7022 ±10 37.5274 35.6110 ∞ 29.7247  10 II 0 42.3397 40.7709 28.2020 52.5731 ±3 40.9388 40.6356 28.5534 53.1496 ±5 42.4467 40.9227 28.6415 55.0761 ±10 41.3142 41.4190 26.8230 51.2051Table 11
The shortest travel time path of the illustrative examples based on the prediction link travel speed.
Vehicle no. Example no. Prediction error (km/h) Accident no. 1 2 3 4 1 I 0 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±3 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±5 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- ±10 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 -- II 0 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±3 3, 2, 10, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±5 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 3, 2, 1, 6, 18, 17, 16 ±10 3, 12, 11, 22, 21 3, 2, 1, 6 3, 12, 13, 14, 27 BL  2 I 0 8, 9, 20, 21 8, 7, 18, 6 BL -- ±3 8, 9, 20, 21 8, 7, 18, 6 BL -- ±5 8, 9, 20, 21 8, 7, 1, 6 BL -- ±10 8, 9, 20, 21 8, 7, 18, 6 BL -- II 0 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 ±3 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16 ±5 8, 9, 20, 21 8, 7, 1, 6 BL 8, 7, 18, 17, 16 ±10 8, 9, 20, 21 8, 7, 18, 6 BL 8, 7, 18, 17, 16  3 I 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 -- II 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 BL ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 14, 15, 16  4 I 0 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±3 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±5 17, 18, 7, 8, 19, 20, 21 17, 18, 6 17, 16, 15, 14, 27 -- ±10 17, 18, 6, 1, 2, 10, 21 17, 18, 6 17, 16, 15, 14, 27 -- II 0 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 ±3 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16 ±5 17, 18, 7, 8, 19, 20, 21 17, 18, 6 BL 17, 16 ±10 17, 18, 6, 1, 2, 10, 21 17, 18, 6 BL 17, 16  5 I 0 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±3 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±5 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 -- ±10 29, 15, 5, 6, 1, 9, 20, 21 29, 15, 5, 6 29, 28, 27 -- II 0 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±3 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±5 29, 15, 5, 6, 1, 2, 10, 21 29, 15, 5, 6 29, 28, 27 29, 15, 16 ±10 29, 15, 5, 6, 1, 9, 20, 21 29, 15, 5, 6 29, 28, 27 29, 30, 16  6 I 0 25, 24, 23, 22, 21 BL 25, 26, 27 -- ±3 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- ±5 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- ±10 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 -- II 0 25, 24, 23, 22, 21 BL 25, 26, 27 BL ±3 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 25, 24, 13, 4, 5, 15, 16 ±5 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 BL ±10 25, 24, 23, 22, 21 25, 24, 13, 4, 5, 6 25, 26, 27 BL  7 I 0 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±3 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±5 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 -- ±10 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 43, 42, 41, 27 -- II 0 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±3 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±5 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 28, 27 31, 30, 16 ±10 31, 32, 33, 19, 20, 21 31, 17, 18, 6 31, 30, 29, 43, 42, 41, 27 31, 30, 16  8 I 0 32, 33, 19, 20, 21 32, 18, 6 BL -- ±3 32, 33, 19, 20, 21 32, 18, 6 BL -- ±5 32, 33, 19, 20, 21 32, 18, 6 BL -- ±10 32, 33, 19, 20, 21 32, 18, 6 BL -- II 0 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±3 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±5 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16 ±10 32, 33, 19, 20, 21 32, 18, 6 BL 32, 18, 17, 16  9 II 0 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 ±3 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16 ±5 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 31, 30, 16 ±10 33, 19, 20, 21 33, 32, 18, 6 BL 33, 32, 18, 17, 16  10 II 0 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±3 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±5 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 4, 5, 15, 16 ±10 13, 12, 11, 22, 21 13, 4, 5, 6 13, 14, 27 13, 14, 15, 16 Note. BL means that the travel time of the optimal path exceeds the upper limit of the time window.ISFLA was used to find the optimal dispatching strategy of the two examples under three prediction errors, and the best solutions are shown in Table12.Table 12
Optimal emergency vehicle dispatching strategy of the illustrative examples based on the prediction link travel speed.
Example no. Prediction error (km/h) The optimal solution Objective function value based on the prediction travel speed Objective function value based on the real travel speed  I 0 0, 1, 3, 2, 0, 3, 0, 2 -- 7987 ±3 0, 1, 3, 2, 0, 3, 0, 2 7897 7987 ±5 0, 1, 3, 2, 0, 3, 0, 2 7981 7987 ±10 0, 1, 3, 2, 0, 3, 2, 0 8461 8088  II 0 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8113 8113 ±3 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8071 8113 ±5 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8126 8113 ±10 0, 1, 0, 2, 0, 3, 4, 2, 0, 3 8569 8113  Example no. Prediction error (km/h) Optimal emergency vehicle dispatching strategy Prediction travel time (min) Real travel time (min)  I 0 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 -- 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 -- 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 -- 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 -- 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 -- 26.3079 ±3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 20.8670 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.4075 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8997 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.7495 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.8029 26.3079 ±5 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 23.1840 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.6789 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8541 21.7823 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.8035 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.4729 26.3079 ±10 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 18.3767 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 17.3145 16.3454 E v 7 to Ac2: Nv7→n31→n17→n18→n6→Nc2 24.9977 23.4594 E v 3 to Ac3: Nv3→n13→n14→n27→Nc3 33.2153 33.8637 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 31.6198 26.3079  II 0 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 -- 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 -- 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 -- 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 -- 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 -- 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 -- 14.4705 ±3 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 20.8670 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.4075 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8997 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.8029 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.5534 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 14.7354 14.4705 ±5 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 23.1840 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 16.6789 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 21.8541 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 25.4729 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 28.6415 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 13.9424 14.4705 ±10 E v 2 to Ac1:Nv2→n8→n9→n20→n21→Nc1 18.3767 22.1482 E v 4 to Ac2: Nv4→n17→n18→n6→Nc2 17.3145 16.3454 E v 8 to Ac2: Nv8→n32→n18→n6→Nc2 26.2546 21.7823 E v 6 to Ac3: Nv6→n25→n26→n27→Nc3 31.6198 26.3079 E v 10 to Ac3: Nv10→n13→n14→n27→Nc3 26.8230 28.2020 E v 7 to Ac4: Nv7→n31→n30→n16→Nc4 13.5972 14.4705In example I, the optimal emergency vehicle dispatching strategy (including vehicle routing and selection), which is based on the prediction link travel speed with prediction errors of ±3, ±5, is the same as the actual optimal strategy. However, when the prediction error is ±10, the rescue vehicle for the accidentAc2 is different from the actual optimal strategy. The emergency vehicle Ev7 instead of the vehicle Ev8 is dispatched to the accident Ac2. This led to a 23.4594 − 21.7823 = 1.6771 minutes extension of the rescue time for the accident Ac2. The objective function value based on the prediction travel speed is 101 more than that based on the real travel speed. It can be seen that the prediction error of the travel speed affects the accuracy of the initial emergency vehicle dispatching, but when the absolute prediction error is within ±10, the effect is not obvious.In example II, the optimal emergency vehicle dispatching strategy (including vehicle routing and selection), which is based on the prediction link travel speed with prediction errors of ±3, ±5, and ±10, is the same as the actual optimal strategy.It is known from the two examples that the prediction error of ±10 can basically meet the requirements of the initial dispatching.


## 5.3. Illustrative Example of Dynamic Adjustment of Dispatching Strategy

Example I in Section5.2 was used to test the performance of dynamic adjustment of dispatching strategy. Suppose that the prediction error of link travel speed was ±5. At 9:30, emergency vehicles were dispatched to accidents according to the optimal dispatching strategy obtained in Section 5.2. Emergency vehicle Ev2 was dispatched to accident Ac1. Emergency vehicle Ev3 was dispatched to accident Ac3. Emergency vehicle Ev4 was dispatched to accident Ac2. Emergency vehicle Ev6 was dispatched to accident Ac3. Emergency vehicle Ev8 was dispatched to accident Ac2. Emergency vehicles Ev1, Ev5, and Ev7 were idle vehicles. The optimal dispatching strategy is shown in Figure 8.Figure 8
Optimal emergency vehicle dispatching strategy at 9:30.At 9:35, a new accidentAc4 happens on the road section 9,20. According to the real link travel speed, location of each emergency vehicle was calculated. They are shown in Figure 9.Figure 9
Locations of emergency vehicles and accidents at 9:35.Due to the influence of the accidentAc4, road conditions of the accident section 9,20 and its upstream sections 8,9 and 1,9 changed. In order to consider the impact of accident Ac4 on upstream sections, a weakening factor αijt to the travel speed of upstream section ni,nj was introduced. Therefore, the travel speed functions of sections 8,9 and 1,9 were v8,9′t=α8,9t·v8,9t, v1,9′t=α1,9t·v1,9t, respectively. Suppose that αij decreases linearly with time t. The initial value αijt=tφ=0.7. When t=tφ+30min, αijt=0.53.The travel speed of each road section was recollected at 9:35, and the prediction travel speed function was calculated. We suppose that travel speed prediction error of road sections8,9 and 1,9 was ±10 and that of other road sections was ±5. Then, travel paths of emergency vehicles were replanned, and the dispatching strategy was adjusted. The optimal dispatching strategy at 9:35 is shown in Figure 10. The dynamic emergency vehicle dispatching process is shown in Table 13.Table 13
Dynamic emergency vehicle dispatching process.
Decision making instant Vehicle no. Road section of vehicle Location of vehicle The optimal solution Optimal emergency vehicle dispatching strategy 9:30 1 n 2 , n 3 L 2,55 = L 55,3 0,1,3,2,0,3,0,2 E v 2 to Ac1: Nv2→n8→n9→n20→n21→Nc1 Ev4 to Ac2: Nv4→n17→n18→n6→Nc2 Ev8 to Ac2: Nv8→n32→n18→n6→Nc2 Ev3 to Ac3: Nv3→n13→n14→n27→Nc3 Ev6 to Ac3: Nv6→n25→n26→n27→Nc3 2 n 9 , n 8 L 9,56 = L 56,8 3 n 12 , n 13 L 12,57 = L 57,13 4 n 18 , n 17 L 18,58 = L 58,17 5 n 15 , n 29 L 15,59 = L 59,29 6 n 39 , n 25 L 39,60 = L 60,25 7 n 30 , n 31 L 30,61 = L 61,31 8 n 33 , n 32 L 33,62 = L 62,32  9:35 1 n 2 , n 3 L 2,55 = L 55,3 1,4,3,2,0,3,0,2 E v 1 to Ac1: Nv1→n3→n2→n10→n21→Nc1 Ev4 to Ac2: Nv4→n6→Nc2 Ev8 to Ac2: Nv8→n18→n6→Nc2 Ev3 to Ac3: Nv3→n13→n14→Nc3 Ev6 to Ac3: Nv6→n25→n26→n27→Nc3 Ev2 to Ac4: Nv2→n9→Nc4 2 n 8 , n 9 L 8,56 = 0.12 × L 8,9 L 56,9 = 0.88 × L 8,9 3 n 12 , n 13 L 12,57 = 0.77 × L 12,13 L 57,13 = 0.23 × L 12,13 4 n 18 , n 6 L 18,58 = 0.10 × L 18,6 L 58,6 = 0.90 × L 18,6 5 n 15 , n 29 L 15,59 = L 59,29 6 n 25 n 25 7 n 30 , n 31 L 30,61 = L 61,31 8 n 32 , n 18 L 32,62 = 0.16  ×  L 32,18 L 62,18 = 0.84  ×  L 32,18Figure 10
Optimal emergency vehicle dispatching strategy at 9:35.When the accidentAc4 happened at 9:35, the dynamical adjustment mechanism timely responded to sudden changes in road conditions of the optimal path 8,9,20,21 of emergency vehicle Ev2. After recalculating the dispatching strategy, the idle emergency vehicle Ev1 replaced the emergency vehicle Ev2 to rescue the accident Ac1. The emergency vehicle successfully bypassed road sections 9,20 and 8,9 to ensure the time limit for emergency rescue. Meanwhile, the emergency vehicle Ev2 with the shortest travel time was dispatched to the new accident Ac4. Therefore, the adjustment of emergency vehicle dispatching strategy can effectively shorten the response time of accident.


## 6. Conclusions

The emergency vehicle dispatching in urban expressway network includes dynamic routing and emergency vehicles election. And the dispatching strategy needs to be adjusted according to the dynamic road conditions. Firstly, polygonal-shaped travel speed function based on real-time and prediction link travel speed is set up, and the dynamic emergency vehicle dispatching process is illustrated. Secondly, taking the accident severity as the key factor and the travel time as the objective function, a dynamic dispatching model considering the vehicle routing was established. The model consists of two stages: initial dispatching and dynamic adjustment. Thirdly, in order to avoid unwanted early convergence of SFLA in solving complex dispatching problems, the basic SFLA was combined with the probabilistic model of EDA, and the SFLA was improved. Finally, Beijing expressway network was taken as an example to test the efficacy of the model and the algorithm from three aspects. First, based on the real link travel speed, 5 emergency vehicle dispatching problems with different scale variable were modeled and solved by the improved shuffled frog leaping algorithm. Second, based on the prediction link travel speed and the real-time link travel speed, the dynamic emergency vehicle dispatching model and the improved SFLA were used to calculate the global optimal dispatching strategy. Third, a scene in which a new accident happened on the rescue path was simulated, and the dispatching strategy was adjusted. The results show the following:(1) The emergency vehicle dispatching model can obtain the optimal dispatching strategy under the constraints of accident demands and time windows. (2) For solving the complicated emergency vehicle selection problem, the improved SFLA has stronger search ability compared with the SFLA and can obtain more optimal dispatching strategy. (3) The optimal strategy obtained by the emergency vehicle dispatching model based on the prediction link travel speed takes into account the dynamic changes in the road conditions during the whole dispatching process. (4) The dynamic adjustment condition can timely respond to sudden changes in the road conditions and help emergency vehicles to avoid rescue delay.



---

*Source: 7896926-2018-03-28.xml*