# Dynamic Path Planning of Emergency Vehicles Based on Travel Time Prediction

Authors: Jiandong Zhao; Yujie Guo; Xiaohong Duan
Journal: Journal of Advanced Transportation
 (2017)

---

## Abstract

The dynamic paths planning problem of emergency vehicles is usually constrained by the factors including time efficiency, resources requirement, and reliability of the road network. Therefore, a two-stage model of dynamic paths planning of emergency vehicles is built with the goal of the shortest travel time and the minimum degree of traffic congestion. Firstly, according to the dynamic characteristics of road network traffic, a polyline-shaped speed function is constructed. And then, based on the real-time and historical data of travel speed, a new kernel clustering algorithm based on shuffled frog leaping algorithm is designed to predict the travel time. Secondly, combined with the expected travel time, the traffic congestion index is defined to measure the reliability of the route. Thirdly, aimed at the problem of solving two-stage target model, a two-stage shortest path algorithm is proposed, which is composed ofK-paths algorithm and shuffled frog leaping algorithm. Finally, based on the data of floating vehicles of expressway in Beijing, a simulation case is used to verify the above methods. The results show that the optimization path algorithm meets the needs of the multiple constraints.


---

## Body

## 1. Introduction

With the construction of urbanization and the increasing traffic vehicles, the frequency and impact of traffic accidents are intensifying. The research on emergency rescue is getting more and more attention. When traffic accident occurs, rescue timeliness is the key to emergency rescue. Reasonable arrangement of emergency vehicle path can avoid congestion and shorten the travel time, so that the accident loss can be reduced. Thus, the problem of path planning of emergency vehicle belongs to dynamic path planning problem (VRP) essentially.Regarding the minimum route distance as the target, Khouadjia et al. [1] proposed a method based on particle swarm optimization and variable neighborhood search paradigms to solve the dynamic vehicle routing problem; Secomandi [2] compared the performance of two neurodynamic programming algorithms to solve the vehicle routing problem with random demand. With the objective to minimize total travel time, Dapia et al. [3] proposed a branch-and-price algorithm to solve the time-dependent vehicle routing problem with time window; Cheung et al. [4] proposed a method based on genetic algorithm to solve the problem of dynamic fleet management; Montemanni et al. [5] examined the dynamic vehicle routing problem and proposed a solving strategy based on the Ant Colony System paradigm. With the objective to minimize total route cost, Li et al. [6] developed Lagrangian relaxation based-insertion heuristics to solve the vehicle rescheduling problem (VRSP). Hong [7] proposed an improved large neighborhood search algorithm to solve the dynamic vehicle routing problem with hard time window. With the objective to maximize the expected profit, Azi et al. [8] proposed a solving strategy based on the adaptive large neighborhood search heuristic algorithm to solve the dynamic vehicle routing problem with multiple delivery routes; Moretti et al. [9] made use of a new constructive heuristic that scatters vehicles in the service area and an adaptive granular local search procedure to solve the dynamic vehicle routing problem with a time window; Campbell and Savelsbergh [10] proposed an algorithm based on insertion heuristics to solve the dynamic vehicle route problem. In terms of multiple objectives, Kergosien et al. [11] studied the dial-a-ride problem by using tabu search algorithm with the objective of minimizing the total cost and travel time. Ghannadpour et al. [12] proposed a solving strategy based on the genetic algorithm and three basic modules to solve the multiobjective dynamic vehicle routing problem with fuzzy time windows, aiming at minimizing the total required fleet size, overall total traveling distance, and waiting time imposed on vehicles. Yang et al. [13] designed a modified particle swarm optimization algorithm (PSO) to solve the multiobjective dynamic vehicle routing problem with time window by considering the customers’ satisfaction degree, the cost, and both integrated conditions. With the objective of minimizing a weighted sum of operating, service cancellation, and route disruption costs, Li et al. [14] developed a Lagrangian relaxation based-heuristic to solve the dynamic vehicle routing problem with a time window.Reviewing the literature, the dynamic path planning model follows a certain system index as the optimal objective. The objectives used frequently are as follows: (1) minimizing the total cost; (2) minimizing the total travel time; (3) minimizing the total delay time; (4) minimizing the average density of vehicle, or a combination of multiple objectives. The solving algorithm includes (1) the exact algorithm (branch and bound algorithm, k-degree central tree algorithm, dynamic programming method, integrated segmentation, and column generation method); (2) traditional heuristic algorithm (C-W algorithm, sweep algorithm, greedy algorithm, local search algorithm and neighborhood search technology, and insertion algorithm); (3) metaheuristics algorithm (tabu search algorithm, simulated annealing algorithms, ant colony algorithm, genetic algorithm, and particle swarm algorithm).However, there are some differences between the emergency vehicle route problem and the VRP. Firstly, there are differences in objective. The route planning under the emergency situation follows the principle of efficiency first; that is, the shortest travel time is given priority, and the economic principle is taken into account as well. The VRP usually considers the lowest cost and the economic priority principle. Secondly, there are differences in constraints. Emergency route planning has to meet the needs of emergency resources and reflect the joint rescue timing requirements between multispectral resources. However, resource needs are not considered in ordinary condition. Thirdly, there are differences in complexity. Emergency route planning has all-to-one characteristics; VRP is a one-to-one problem. Fourthly, there are differences in the demand for path planning stability. The path planning should have a more robust nature under the emergency situation, so that the emergency vehicle can reach the scene of the accident with greater probability. It can be seen from the above that vehicle routing planning under emergency events has the characteristics of urgency and dynamic and random uncertainty.Firstly, emergency rescue needs to consider the minimum travel time as target. Thus, vehicle route problem is transformed into the shortest path problem. The shortest path problem is solved based on the shortest path algorithm. Dijkstra [15] firstly proposed the shortest path problem of static network. Based on the properties of the static shortest path, the shortest path between the source node and any node in the network could be obtained. Bellman [16] and Ford and Fulkerson [17] proposed Bellman-Ford algorithm, which was used to solve the shortest path problem with negative edge weights. Hart et al. [18] proposed a heuristic search algorithm, A∗ algorithm, for solving the static shortest path problem.Secondly, the emergency vehicle path planning must consider the dynamic time-varying characteristics of traffic flow, and then the shortest path problem is transformed into the dynamic shortest path problem. Cooke and Halsey [19] improved the Bellman-Ford algorithm to solve the shortest path problem of time-dependent network based on the discrete weight assumption by iterative method. Kaufman and Smith [20] proved that the classic shortest path algorithm could be used to solve the dynamic shortest path problem only when network meted the FIFO criteria. Nannicini et al. [21] proposed a bidirectional searching A∗ algorithm to solve the dynamic shortest path problem of FIFO network, which applied the lower bounds of link weights to constrain the path series obtained by forward searching originating from the destination node. The solving performance had been significantly improved in this way. Delling and Nannicini [22] extended the heuristic algorithm of solving the point-to-point shortest path to the dynamic network and obtained the efficient algorithm by selecting the subnetwork. Lin et al. [23, 24] proved that the shortest path problem of time-dependent network was a NP-Hard problem and put forward the concept of shortest path stability from three aspects including length stability of shortest path, optimal solution stability, and stable subbranch. And then he designed an efficient algorithm to reduce the repetitive computation by using stable information. Zhao et al. [25] aimed at the time-dependent characteristic of the highway network and proposed a novel particle swarm optimization algorithm to solve the time-dependent (dynamic) shortest path problem. The algorithm uses a way of adjacency matrix search to generate particle swarm satisfying constrains of the problem during the whole calculation. These algorithms mentioned above used road section travel time obtained by historical data or forecasting method for dynamic path planning and path choice. And then the real-time travel time forecasting becomes the key technology of path selection in dynamic traffic assignment.Thirdly, as the vehicle routing has to make a decision in advance, it will be affected by uncertainty factors whether real-time data or forecasting data is used. If the effect caused by uncertainty factors (weather, traffic congestion, traffic events, etc.) was ignored, the shortest path find by the algorithm will be not reliable. Therefore, emergency vehicle scheduling must take into account the uncertainties affecting on the dynamic characteristics of traffic flow. Sun [27] used the reliability level to characterize the dynamic characteristics of vehicle path planning. The real-time speed was transformed into reliability based on the vehicle velocity distribution. This method solved provided suggestions for residents to travel. Mendoza et al. [28] solved the multicompartment vehicle routing problem with stochastic demand by memetic algorithm. Lu et al. [26] developed bicriterion dynamic user equilibrium model, which aims to capture users’ path choices in response to time-varying toll charges. Yuan and Wang [29] proposed two optimization models in emergency logistics management by taking multifactors into consideration and modeled the road section travel speed as a function decreasing with time. And then, he established a rescue path planning model with the goal of shortest travel time where the Dijkstra algorithm was used to solve the model. The next, based on the first model, chaos, panic, and congestion in the disaster were considered to build a path planning model. Finally, an ant colony algorithm was designed to solve the model with the optimization multiobjective of travel time and path complexity. K shortest path (KSP) is an important means to solve the multiobjective and multiconstrained shortest path problem by searching for several optimal paths in the network. Günther et al. [30] introduced the concept of reduced length of edges and solved the K shortest path using Dijkstra algorithm. Androutsopoulos and Zografos [31] proposed a label setting algorithm for solving K shortest path problem given that departure and arrival are constrained within specified time windows. Liu et al. [32] proposed a Modified Continued Pulse Coupled Neural Network model to solve the two kinds of KSP problems. And the simulation for route planning was made. These K shortest path algorithms mentioned above were designed for static network.In summary, the dynamic vehicle routing planning based on real-time information always adopted the periodic updating mechanism. It is difficult to obtain the global optimal solution of the whole decision cycle without fully considering the change of the travel time while the emergency vehicle went to the accident location. However, the emergency rescue vehicle routing planning is different from the ordinary dynamic path planning and choice problem. It is necessary to consider the dynamic time-varying characteristics of road network traffic, the constraints of emergency resource requirements, the restraint of rescue time, and the reliability of the path.Therefore, the research content and framework of this paper are shown in Figure1. Firstly, a polyline-shaped travel speed function is constructed. A SFLA-KC fusion algorithm is proposed to predict the travel time based on the real-time and historical speed sample sequences. Considering the constraints of time and resource requirements, the shortest travel time is taken as the objective. Then, combining the expected travel time and forecast travel time, the degree of traffic congestion is defined, and the minimum degree of traffic congestion is established as the second objective. Then, a two-stage emergency vehicle path planning model is established. The model is solved by SFLA-KSP algorithm, and the optimal path is obtained based on the K shortest paths.Figure 1
Research content and structure.


## 2. Model Establishment in Dynamic Paths Planning of Emergency Vehicles

Dynamic paths planning of vehicles should consider the factors including travel time of vehicles, resources demand of emergent events, and the reliability of chosen route.


### 2.1. Dynamic Travel Speed Function of Links

The travel speed-dependent function can reflect the changes in road condition directly and fulfill the FIFO rules. Therefore, Ichoua et al.’s [33] travel speed-dependent function is referred to build the speed function, and the link travel time can be calculated. As shown in Figure 2, in Ichoua’s time-dependent function of the travel speed, travel speed keeps constant during the cycle Δt but jumps at the initial time of each cycle. However, the actual vehicle velocity is continuously changing with time. Therefore, based on Ichoua’s function, it is assumed that the travel speed in each cycle varies in the form of a polyline, thus forming a time-dependent function curve as shown in Figure 3, which is defined as a polyline-shaped travel speed function.Figure 2
Time-dependent function based on travel speed.Figure 3
Travel speed function.It is assumed that the emergency vehicle path planning cycle isTS. Taking Δt as the minimum time interval, TS is divided into Φ discrete time intervals TS=t0+(ϕ-1)Δt,t0+ϕΔt, where ϕ=1,2,…,Φ and t0 is the initial time. Assume that TSΦ=t0+ΦΔt is the last moment which is supposed to be large enough for emergency vehicles to arrive at the accident node in [t0,TSΦ]. Since, at the initial decision moment t0, only the real-time speed can be obtained. It is necessary to fuse and predict real-time speed and a large number of historical vehicle speed data at the corresponding time in history to predict and obtain the speed in other time of the cycle TS. Assume that the length of the link (ni,ni+1) is Li,i+1, real-time link speed is vri,i+1t0 at the moment t0, and the predicted travel speed of the moment tϕ=t0+ϕ·Δt,ϕ=1,2,…,Φ is vfi,i+1tϕt0. The speed function of link (ni,ni+1) at the moment t0 is shown in Figure 4.Figure 4
Travel speed function construction.The travel speed function is expressed as follows:(1)vi,i+1tt0=vfi,i+1tϕt0-vri,i+1t0Δt·t+tϕ·vri,i+1t0-t0·vfi,i+1tϕt0Δtt0≤t<tϕ,ϕ=1vfi,i+1tϕt0-vfi,i+1tϕ-1t0Δt·t+tϕ·vfi,i+1tϕ-1-tϕ·vfi,i+1tϕΔttϕ-1≤t<tϕ,ϕ=2,3,…,Φ.


### 2.2. Construction of Dynamic Travel Time Predicting Function

Ifvi,i+1tt0 is continuous in the interval [t0,TSΦ], it is surely integrable in this interval, when an emergency vehicle enters link (ni,ni+1) at the moment of tt≥t0 and leaves at the moment of text≤tex≤TSΦ. The function of travel distance is(2)∫ttexvi,i+1tt0dt=∫t0texvi,i+1tt0dt-∫t0tvi,i+1tt0dt=μtex-φt,where(3)μtex=∫t0texvi,i+1tt0dt=∫vi,i+1text0dtex+C=12·vfi,i+1tϕt0-vri,i+1t0Δt×tex2+tϕ·vri,i+1t0-t0·vfi,i+1tϕt0Δt×tex+C1t0≤tex<tϕ,ϕ=112·vfi,i+1tϕt0-vfi,i+1tϕ-1t0Δt×tex2+tϕ·vfi,i+1tϕ-1-tϕ-1·vfi,i+1tϕΔt×tex+Citϕ-1≤tex<tϕ,ϕ=2,3,…,Φ,φt=∫t0tvi,i+1tt0dt=∫vi,i+1tt0dt+C,where C1,Ci,i=2,3,…,Φ-1 is the integral constant, which can be obtained through the continuity of the original function of vi,i+1tt0.Let formula (2) be equal to the length of the road Li,i+1; then the departure time tex of emergency vehicles out of the link is(4)tex=gLi,i+1+φt,where g is the inverse function of μ.Then the link travel time functionTi,i+1t is obtained as follows:(5)Ti,i+1t=gLi,i+1+φt-t.


### 2.3. Degree of Traffic Congestion Function of Route

As for emergency vehicle route selection, it is necessary to ensure the reliability. A concept of degree of traffic congestion is defined to measure the reliability of route. While the degree of traffic congestion is lowe,r the selected route is more reliable.When the traffic density of link(ni,ni+1) is low and the emergency vehicle is under free-flow condition, the travel speed is close to the value of the speed limit and the expected link travel time is TDi,i+1. For the path ∏i=sd-1(ni,ni+1) originating from source node ns to the destination node nd, the emergency vehicle enters the link ni,ni+1 at the moment t and departure after Ti,i+1t.The travel time delay of the linkni,ni+1 is(6)ΔTi,i+1=Ti,i+1t-TDi,i+1.The degree of traffic congestion of route∏i=sd(ni,ni+1) is defined as(7)R∏i=sd-1ni,ni+1=∑i=sd-1Ti,i+1t-TDi,i+1∑i=sd-1TDi,i+1.


### 2.4. Dynamic Path Planning Model of Emergency Vehicles

The parameters involved in the emergency vehicle path planning model are defined as follows:Evl: the lth emergency vehicle, where l=1,2,…,EV and EV are the total number of emergency vehiclesAcu: the uth accident, where u=1,2,…,AC and AC is the total number of accidentsTlut0: at the initial decision moment t0, the travel time of the emergency vehicle Evl heading to the accident Acuxlut0: at the initial decision moment t0, if the emergency vehicle Evl head to the accident Acu, xlut0=1; otherwise xlut0=0Naut0: at the initial decision moment t0, the total number of the emergency vehicles required for accident Acuxlt0: at the initial decision moment t0, if the emergency vehicle Evl has not head to the accident Acu and is idle, xlt0=1; otherwise xlt0=0Plut0: at the initial decision moment t0, the route of emergency vehicle Evl heading to accident AcuRPlut0: at the initial decision moment t0, the degree of traffic congestion of route Plut0Tmaxut0: at the initial decision moment t0, the upper limit of rescue time of accident AcuM: a constant value which is large enoughzut0: at the initial decision moment t0, if the latest rescue time of accident Acu is out of the time limit, zut0=1; otherwise zut0=0The two-stage path planning model of emergency vehicles is built as follows:(8)min∑u∑lTlut0×xlut0+∑uM×zut0(9)s.t.∑lxlut0=Naut0,where,Evl∈EV,∀Acu∈AC,(10)∑uxlut0+∑lxlt0=1,(11)∑lxlut0+∑lxlt0=L(12)s.t.Tlut0=min⁡∑i=lu-1Ti,i+1tt0,(13)RPlut0=min⁡R∏i=lu-1ni,ni+1t0,(14)ns,n1,…,ni,ni+1,…,nd-1,nd∈E,(15)nl,n1,…,ni,…,nu-1,nu∈N,(16)nl≠n1≠⋯≠ni≠⋯≠nu-1≠nu.Formula (8) is the objective function of emergency vehicle schedule, consisting of the travel time of the emergency vehicle Evl heading to the accident Acu and the punishment caused by the rescue time limit surpassing. Since emergency rescue is restricted with time limit, the expected rescue time is set and the punishing time can be increased if it failed to arrive at the accident location on time.Formula (9) is the constraint of accident demand, which enables the emergency vehicles to satisfy the demand of accident Acu∈AC.Formula (10) is the constraint of emergency vehicles, and the emergency vehicle Evl is either idle or heading to the accident Acu.Formula (11) is the constraint of vehicles number, and the total number of emergency vehicles heading to accident and being idle is L.Formula (12) is the objective function of the first stage of emergency vehicle schedule, making the travel time of route minimum.Formula (13) is the objective function of the second stage of emergency vehicle schedule, making the degree of traffic congestion of route minimum.Formulas (14)–(16) are constraints of routes connectivity.


## 2.1. Dynamic Travel Speed Function of Links

The travel speed-dependent function can reflect the changes in road condition directly and fulfill the FIFO rules. Therefore, Ichoua et al.’s [33] travel speed-dependent function is referred to build the speed function, and the link travel time can be calculated. As shown in Figure 2, in Ichoua’s time-dependent function of the travel speed, travel speed keeps constant during the cycle Δt but jumps at the initial time of each cycle. However, the actual vehicle velocity is continuously changing with time. Therefore, based on Ichoua’s function, it is assumed that the travel speed in each cycle varies in the form of a polyline, thus forming a time-dependent function curve as shown in Figure 3, which is defined as a polyline-shaped travel speed function.Figure 2
Time-dependent function based on travel speed.Figure 3
Travel speed function.It is assumed that the emergency vehicle path planning cycle isTS. Taking Δt as the minimum time interval, TS is divided into Φ discrete time intervals TS=t0+(ϕ-1)Δt,t0+ϕΔt, where ϕ=1,2,…,Φ and t0 is the initial time. Assume that TSΦ=t0+ΦΔt is the last moment which is supposed to be large enough for emergency vehicles to arrive at the accident node in [t0,TSΦ]. Since, at the initial decision moment t0, only the real-time speed can be obtained. It is necessary to fuse and predict real-time speed and a large number of historical vehicle speed data at the corresponding time in history to predict and obtain the speed in other time of the cycle TS. Assume that the length of the link (ni,ni+1) is Li,i+1, real-time link speed is vri,i+1t0 at the moment t0, and the predicted travel speed of the moment tϕ=t0+ϕ·Δt,ϕ=1,2,…,Φ is vfi,i+1tϕt0. The speed function of link (ni,ni+1) at the moment t0 is shown in Figure 4.Figure 4
Travel speed function construction.The travel speed function is expressed as follows:(1)vi,i+1tt0=vfi,i+1tϕt0-vri,i+1t0Δt·t+tϕ·vri,i+1t0-t0·vfi,i+1tϕt0Δtt0≤t<tϕ,ϕ=1vfi,i+1tϕt0-vfi,i+1tϕ-1t0Δt·t+tϕ·vfi,i+1tϕ-1-tϕ·vfi,i+1tϕΔttϕ-1≤t<tϕ,ϕ=2,3,…,Φ.


## 2.2. Construction of Dynamic Travel Time Predicting Function

Ifvi,i+1tt0 is continuous in the interval [t0,TSΦ], it is surely integrable in this interval, when an emergency vehicle enters link (ni,ni+1) at the moment of tt≥t0 and leaves at the moment of text≤tex≤TSΦ. The function of travel distance is(2)∫ttexvi,i+1tt0dt=∫t0texvi,i+1tt0dt-∫t0tvi,i+1tt0dt=μtex-φt,where(3)μtex=∫t0texvi,i+1tt0dt=∫vi,i+1text0dtex+C=12·vfi,i+1tϕt0-vri,i+1t0Δt×tex2+tϕ·vri,i+1t0-t0·vfi,i+1tϕt0Δt×tex+C1t0≤tex<tϕ,ϕ=112·vfi,i+1tϕt0-vfi,i+1tϕ-1t0Δt×tex2+tϕ·vfi,i+1tϕ-1-tϕ-1·vfi,i+1tϕΔt×tex+Citϕ-1≤tex<tϕ,ϕ=2,3,…,Φ,φt=∫t0tvi,i+1tt0dt=∫vi,i+1tt0dt+C,where C1,Ci,i=2,3,…,Φ-1 is the integral constant, which can be obtained through the continuity of the original function of vi,i+1tt0.Let formula (2) be equal to the length of the road Li,i+1; then the departure time tex of emergency vehicles out of the link is(4)tex=gLi,i+1+φt,where g is the inverse function of μ.Then the link travel time functionTi,i+1t is obtained as follows:(5)Ti,i+1t=gLi,i+1+φt-t.


## 2.3. Degree of Traffic Congestion Function of Route

As for emergency vehicle route selection, it is necessary to ensure the reliability. A concept of degree of traffic congestion is defined to measure the reliability of route. While the degree of traffic congestion is lowe,r the selected route is more reliable.When the traffic density of link(ni,ni+1) is low and the emergency vehicle is under free-flow condition, the travel speed is close to the value of the speed limit and the expected link travel time is TDi,i+1. For the path ∏i=sd-1(ni,ni+1) originating from source node ns to the destination node nd, the emergency vehicle enters the link ni,ni+1 at the moment t and departure after Ti,i+1t.The travel time delay of the linkni,ni+1 is(6)ΔTi,i+1=Ti,i+1t-TDi,i+1.The degree of traffic congestion of route∏i=sd(ni,ni+1) is defined as(7)R∏i=sd-1ni,ni+1=∑i=sd-1Ti,i+1t-TDi,i+1∑i=sd-1TDi,i+1.


## 2.4. Dynamic Path Planning Model of Emergency Vehicles

The parameters involved in the emergency vehicle path planning model are defined as follows:Evl: the lth emergency vehicle, where l=1,2,…,EV and EV are the total number of emergency vehiclesAcu: the uth accident, where u=1,2,…,AC and AC is the total number of accidentsTlut0: at the initial decision moment t0, the travel time of the emergency vehicle Evl heading to the accident Acuxlut0: at the initial decision moment t0, if the emergency vehicle Evl head to the accident Acu, xlut0=1; otherwise xlut0=0Naut0: at the initial decision moment t0, the total number of the emergency vehicles required for accident Acuxlt0: at the initial decision moment t0, if the emergency vehicle Evl has not head to the accident Acu and is idle, xlt0=1; otherwise xlt0=0Plut0: at the initial decision moment t0, the route of emergency vehicle Evl heading to accident AcuRPlut0: at the initial decision moment t0, the degree of traffic congestion of route Plut0Tmaxut0: at the initial decision moment t0, the upper limit of rescue time of accident AcuM: a constant value which is large enoughzut0: at the initial decision moment t0, if the latest rescue time of accident Acu is out of the time limit, zut0=1; otherwise zut0=0The two-stage path planning model of emergency vehicles is built as follows:(8)min∑u∑lTlut0×xlut0+∑uM×zut0(9)s.t.∑lxlut0=Naut0,where,Evl∈EV,∀Acu∈AC,(10)∑uxlut0+∑lxlt0=1,(11)∑lxlut0+∑lxlt0=L(12)s.t.Tlut0=min⁡∑i=lu-1Ti,i+1tt0,(13)RPlut0=min⁡R∏i=lu-1ni,ni+1t0,(14)ns,n1,…,ni,ni+1,…,nd-1,nd∈E,(15)nl,n1,…,ni,…,nu-1,nu∈N,(16)nl≠n1≠⋯≠ni≠⋯≠nu-1≠nu.Formula (8) is the objective function of emergency vehicle schedule, consisting of the travel time of the emergency vehicle Evl heading to the accident Acu and the punishment caused by the rescue time limit surpassing. Since emergency rescue is restricted with time limit, the expected rescue time is set and the punishing time can be increased if it failed to arrive at the accident location on time.Formula (9) is the constraint of accident demand, which enables the emergency vehicles to satisfy the demand of accident Acu∈AC.Formula (10) is the constraint of emergency vehicles, and the emergency vehicle Evl is either idle or heading to the accident Acu.Formula (11) is the constraint of vehicles number, and the total number of emergency vehicles heading to accident and being idle is L.Formula (12) is the objective function of the first stage of emergency vehicle schedule, making the travel time of route minimum.Formula (13) is the objective function of the second stage of emergency vehicle schedule, making the degree of traffic congestion of route minimum.Formulas (14)–(16) are constraints of routes connectivity.


## 3. Travel Speed Prediction Based on SFLA-KC Algorithm

The obtaining of the link travel speed function depends on the statistical analysis of a large amount of historical data. In a certain time and space, the link travel speed is continuously changing with time. The adjacent multiple collecting cycles form time series and travel speed data of the time series constitute samples in order. It is possible to obtain the trend of the travel speed by judging the similarity between the samples in order, and then the speed value of next cycles can be estimated. This paper clustered the ordered samples, which have the similar trend of the link speed and introduced the shuffled frog leaping algorithm into kernel clustering method. This method uses excellent global searching ability of shuffled frog leaping algorithm to expend the searching scale to the whole sample space, thus obtaining the optimal cluster center and matching the similarity of real-time data and all types of samples. Finally, the real-time and time-varying travel speed can be fused.


### 3.1. SFLA-KC Algorithm Design

The kernel clustering algorithm based on shuffled frog leaping algorithm (SFLA-KC) transforms the kernel clustering problem into the optimization problem:(17)minJxc=∑c=1C∑q=1Qdcq×Kxq,xq-2Kxq,xc+Kxc,xcs.t.xc∈RQ,c=1,2,…,C,where(18)dcq=1Theqthsamplebelongstothefirstccluster0Theqthsampledoesnotbelongtothefirstccluster.The clustering centerxc is the decision variable of the optimization problem. The input space RQ is the decision space of the optimization problem, while the optimization target of the problem is to minimize the value of the clustering criterion function.The flow of SFLA-KC algorithm is shown as follows.


#### 3.1.1. Sample Standardization

Input samplexq=xq1,xq2,…,xqd,…,xqD∈RQ,q=1,2,…,Q, D is the dimension of the input sample. In order to avoid dependence of the clustering results on the unit of measure, the input samples are normalized:(19)xqd′=xqd-min⁡xq1,xq2,…,xqd,…,xqDmax⁡xq1,xq2,…,xqd,…,xqD-min⁡xq1,xq2,…,xqd,…,xqD,where xqd′ is the normalized result for xqd, and the normalized input sample is(20)xq′=xq1′,xq2′,…,xqd′,…,xqD′∈RQ,q=1,2,…,Q.


#### 3.1.2. Initialization of the Frog Group (Frog Coding Scheme)

Randomly selectC sample vectors from the input samples to form a frog code, and each frog code Xf represents a possible clustering result x1f,x2f,…,xcf,…,xCfT, where xcf represents a cluster of samples within a subclass of the center. This step should be repeated until F frog locations generated F frog location codes and form frog group P. Each frog code can be expressed as follows:(21)Xf=x1f,x2f,…,xcf,…,xCfT,xcf=xc1f,xc2f,…,xcdf,…,xcDf,f=1,2,…,F,where xc1f,xc2f,…,xcdf,…,xcDf are the eigenvector elements of the clustering center xcf.


#### 3.1.3. Construction of the Kernel Mapping Matrix

The kernel mapping matrix is obtained after the kernel function mapping between the samples. The Gauss kernel function is adopted and the form is(22)Kxq,xc=exp⁡-γxq-xc2,where γ is a customized parameter.The kernel function is calculated for any two input samplesxq′∈RQ, and the kernel mapping matrix is constructed:(23)KQ×Q=Kq,q=Kxq′,xq′.Calculate the kernel function of any input samplexq′∈RQ and cluster center xcf for each frog location code Xf=x1f,x2f,…,xcf,…,xCfT, and construct the kernel mapping matrix:(24)KQ×Cf=Kq,cf=Kxq′,xcf.Calculate the kernel function for each two clustering centersxcf and construct the kernel mapping matrix:(25)KC×Cf=Kc,cf=Kxcf,xcf.


#### 3.1.4. The Sample Similarity Calculation

Calculate the distance between input samplexq′∈RQ and clustering center xcf:(26)dHxq′,xcf=Kq,q-2Kq,cf+Kc,cf.


#### 3.1.5. The Attribution Matrix Calculation

If samplexq′ belongs to the clustering center xcf, and the element dcqf is set as 1, else as 0, the sample attribution matrix can be expressed as(27)DC×Qf=dcqf,dcqf=1dHxq′,xcf=mincdHxq′,xcf0others,f=1,2,…,F.


#### 3.1.6. The Clustering Criterion Function (Adaptation Function) Calculation

According to the sum of error square criterion function of kernel clustering, for any clustering result represented by any frog code, the clustering criterion function is(28)JXf=∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf,f=1,2,…,F.The adaptation function of frogXf is(29)fXf=-∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf.Based on the coding scheme above, the clustering result is initialized. while the frog ethnic group can be guided by its fitness function and evolved continuously. Finally, the clustering results converge to the optimal one.


### 3.2. Link Travel Speed Prediction

#### 3.2.1. Composition of Travel Speed Sample Vectors

The clustering analysis of the samples is to obtain the variation regularity of the link travel speed in a time series, so as to predict the travel speed at the following time, based on current travel speed. Therefore, several consecutive acquisition cycles[t0-Ψ1·Δt,t0+Ψ2·Δt] before and after the moment t0 are chosen to obtain travel speed as the sample vector. Then the sample vector xq can be expressed as follows:(30)xq=vqt0-Ψ1·Δt,…,vqt0-Ψ1+1·Δt,…,vqt0,…,vqt0+Ψ2-1·Δt,vqt0+Ψ2·Δt,where vqt shows the travel speed of the link at moment t in the sample xq.


#### 3.2.2. Real-Time and Time-Varying Similarity Matching Mechanism

The matching between the samples to be measured (real-time travel speed) and the class sample (time-varying travel speed) is achieved by the nearest neighbor mechanism. Assume that each subclass of the sample set is clustered at the centerxc=vct0-Ψ1·Δt,…,vct0+Ψ2·Δt,c=1,…,C. For the sample x=vt0-Ψ1·Δt,…,vt0-ψ1·Δt,…,vt0 to be tested, it is measured according to Euclidean distance:(31)Dx,xc=x-xc=∑ψ1=-Ψ10vt0+ψ1·Δt-vct0+ψ1·Δt2.In the class sample set, the nearest sample to the samplex is selected as(32)xk=vkt0-Ψ1·Δt,…,vkt0,…,vkt0+Ψ2·Δt,k=1,2,…,K,where K is the total number of samples included in the nearest neighbor sample set.The travel speed at theψ2th moments where 1≤ψ2≤Ψ2 after the decision moment t0 can be estimated as(33)vft0+ψ2·Δt=∑k=1Kvkt0+ψ2·ΔtK.


## 3.1. SFLA-KC Algorithm Design

The kernel clustering algorithm based on shuffled frog leaping algorithm (SFLA-KC) transforms the kernel clustering problem into the optimization problem:(17)minJxc=∑c=1C∑q=1Qdcq×Kxq,xq-2Kxq,xc+Kxc,xcs.t.xc∈RQ,c=1,2,…,C,where(18)dcq=1Theqthsamplebelongstothefirstccluster0Theqthsampledoesnotbelongtothefirstccluster.The clustering centerxc is the decision variable of the optimization problem. The input space RQ is the decision space of the optimization problem, while the optimization target of the problem is to minimize the value of the clustering criterion function.The flow of SFLA-KC algorithm is shown as follows.


### 3.1.1. Sample Standardization

Input samplexq=xq1,xq2,…,xqd,…,xqD∈RQ,q=1,2,…,Q, D is the dimension of the input sample. In order to avoid dependence of the clustering results on the unit of measure, the input samples are normalized:(19)xqd′=xqd-min⁡xq1,xq2,…,xqd,…,xqDmax⁡xq1,xq2,…,xqd,…,xqD-min⁡xq1,xq2,…,xqd,…,xqD,where xqd′ is the normalized result for xqd, and the normalized input sample is(20)xq′=xq1′,xq2′,…,xqd′,…,xqD′∈RQ,q=1,2,…,Q.


### 3.1.2. Initialization of the Frog Group (Frog Coding Scheme)

Randomly selectC sample vectors from the input samples to form a frog code, and each frog code Xf represents a possible clustering result x1f,x2f,…,xcf,…,xCfT, where xcf represents a cluster of samples within a subclass of the center. This step should be repeated until F frog locations generated F frog location codes and form frog group P. Each frog code can be expressed as follows:(21)Xf=x1f,x2f,…,xcf,…,xCfT,xcf=xc1f,xc2f,…,xcdf,…,xcDf,f=1,2,…,F,where xc1f,xc2f,…,xcdf,…,xcDf are the eigenvector elements of the clustering center xcf.


### 3.1.3. Construction of the Kernel Mapping Matrix

The kernel mapping matrix is obtained after the kernel function mapping between the samples. The Gauss kernel function is adopted and the form is(22)Kxq,xc=exp⁡-γxq-xc2,where γ is a customized parameter.The kernel function is calculated for any two input samplesxq′∈RQ, and the kernel mapping matrix is constructed:(23)KQ×Q=Kq,q=Kxq′,xq′.Calculate the kernel function of any input samplexq′∈RQ and cluster center xcf for each frog location code Xf=x1f,x2f,…,xcf,…,xCfT, and construct the kernel mapping matrix:(24)KQ×Cf=Kq,cf=Kxq′,xcf.Calculate the kernel function for each two clustering centersxcf and construct the kernel mapping matrix:(25)KC×Cf=Kc,cf=Kxcf,xcf.


### 3.1.4. The Sample Similarity Calculation

Calculate the distance between input samplexq′∈RQ and clustering center xcf:(26)dHxq′,xcf=Kq,q-2Kq,cf+Kc,cf.


### 3.1.5. The Attribution Matrix Calculation

If samplexq′ belongs to the clustering center xcf, and the element dcqf is set as 1, else as 0, the sample attribution matrix can be expressed as(27)DC×Qf=dcqf,dcqf=1dHxq′,xcf=mincdHxq′,xcf0others,f=1,2,…,F.


### 3.1.6. The Clustering Criterion Function (Adaptation Function) Calculation

According to the sum of error square criterion function of kernel clustering, for any clustering result represented by any frog code, the clustering criterion function is(28)JXf=∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf,f=1,2,…,F.The adaptation function of frogXf is(29)fXf=-∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf.Based on the coding scheme above, the clustering result is initialized. while the frog ethnic group can be guided by its fitness function and evolved continuously. Finally, the clustering results converge to the optimal one.


## 3.1.1. Sample Standardization

Input samplexq=xq1,xq2,…,xqd,…,xqD∈RQ,q=1,2,…,Q, D is the dimension of the input sample. In order to avoid dependence of the clustering results on the unit of measure, the input samples are normalized:(19)xqd′=xqd-min⁡xq1,xq2,…,xqd,…,xqDmax⁡xq1,xq2,…,xqd,…,xqD-min⁡xq1,xq2,…,xqd,…,xqD,where xqd′ is the normalized result for xqd, and the normalized input sample is(20)xq′=xq1′,xq2′,…,xqd′,…,xqD′∈RQ,q=1,2,…,Q.


## 3.1.2. Initialization of the Frog Group (Frog Coding Scheme)

Randomly selectC sample vectors from the input samples to form a frog code, and each frog code Xf represents a possible clustering result x1f,x2f,…,xcf,…,xCfT, where xcf represents a cluster of samples within a subclass of the center. This step should be repeated until F frog locations generated F frog location codes and form frog group P. Each frog code can be expressed as follows:(21)Xf=x1f,x2f,…,xcf,…,xCfT,xcf=xc1f,xc2f,…,xcdf,…,xcDf,f=1,2,…,F,where xc1f,xc2f,…,xcdf,…,xcDf are the eigenvector elements of the clustering center xcf.


## 3.1.3. Construction of the Kernel Mapping Matrix

The kernel mapping matrix is obtained after the kernel function mapping between the samples. The Gauss kernel function is adopted and the form is(22)Kxq,xc=exp⁡-γxq-xc2,where γ is a customized parameter.The kernel function is calculated for any two input samplesxq′∈RQ, and the kernel mapping matrix is constructed:(23)KQ×Q=Kq,q=Kxq′,xq′.Calculate the kernel function of any input samplexq′∈RQ and cluster center xcf for each frog location code Xf=x1f,x2f,…,xcf,…,xCfT, and construct the kernel mapping matrix:(24)KQ×Cf=Kq,cf=Kxq′,xcf.Calculate the kernel function for each two clustering centersxcf and construct the kernel mapping matrix:(25)KC×Cf=Kc,cf=Kxcf,xcf.


## 3.1.4. The Sample Similarity Calculation

Calculate the distance between input samplexq′∈RQ and clustering center xcf:(26)dHxq′,xcf=Kq,q-2Kq,cf+Kc,cf.


## 3.1.5. The Attribution Matrix Calculation

If samplexq′ belongs to the clustering center xcf, and the element dcqf is set as 1, else as 0, the sample attribution matrix can be expressed as(27)DC×Qf=dcqf,dcqf=1dHxq′,xcf=mincdHxq′,xcf0others,f=1,2,…,F.


## 3.1.6. The Clustering Criterion Function (Adaptation Function) Calculation

According to the sum of error square criterion function of kernel clustering, for any clustering result represented by any frog code, the clustering criterion function is(28)JXf=∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf,f=1,2,…,F.The adaptation function of frogXf is(29)fXf=-∑c=1C∑q=1Qdcqf×Kq,q-2Kq,cf+Kc,cf.Based on the coding scheme above, the clustering result is initialized. while the frog ethnic group can be guided by its fitness function and evolved continuously. Finally, the clustering results converge to the optimal one.


## 3.2. Link Travel Speed Prediction

### 3.2.1. Composition of Travel Speed Sample Vectors

The clustering analysis of the samples is to obtain the variation regularity of the link travel speed in a time series, so as to predict the travel speed at the following time, based on current travel speed. Therefore, several consecutive acquisition cycles[t0-Ψ1·Δt,t0+Ψ2·Δt] before and after the moment t0 are chosen to obtain travel speed as the sample vector. Then the sample vector xq can be expressed as follows:(30)xq=vqt0-Ψ1·Δt,…,vqt0-Ψ1+1·Δt,…,vqt0,…,vqt0+Ψ2-1·Δt,vqt0+Ψ2·Δt,where vqt shows the travel speed of the link at moment t in the sample xq.


### 3.2.2. Real-Time and Time-Varying Similarity Matching Mechanism

The matching between the samples to be measured (real-time travel speed) and the class sample (time-varying travel speed) is achieved by the nearest neighbor mechanism. Assume that each subclass of the sample set is clustered at the centerxc=vct0-Ψ1·Δt,…,vct0+Ψ2·Δt,c=1,…,C. For the sample x=vt0-Ψ1·Δt,…,vt0-ψ1·Δt,…,vt0 to be tested, it is measured according to Euclidean distance:(31)Dx,xc=x-xc=∑ψ1=-Ψ10vt0+ψ1·Δt-vct0+ψ1·Δt2.In the class sample set, the nearest sample to the samplex is selected as(32)xk=vkt0-Ψ1·Δt,…,vkt0,…,vkt0+Ψ2·Δt,k=1,2,…,K,where K is the total number of samples included in the nearest neighbor sample set.The travel speed at theψ2th moments where 1≤ψ2≤Ψ2 after the decision moment t0 can be estimated as(33)vft0+ψ2·Δt=∑k=1Kvkt0+ψ2·ΔtK.


## 3.2.1. Composition of Travel Speed Sample Vectors

The clustering analysis of the samples is to obtain the variation regularity of the link travel speed in a time series, so as to predict the travel speed at the following time, based on current travel speed. Therefore, several consecutive acquisition cycles[t0-Ψ1·Δt,t0+Ψ2·Δt] before and after the moment t0 are chosen to obtain travel speed as the sample vector. Then the sample vector xq can be expressed as follows:(30)xq=vqt0-Ψ1·Δt,…,vqt0-Ψ1+1·Δt,…,vqt0,…,vqt0+Ψ2-1·Δt,vqt0+Ψ2·Δt,where vqt shows the travel speed of the link at moment t in the sample xq.


## 3.2.2. Real-Time and Time-Varying Similarity Matching Mechanism

The matching between the samples to be measured (real-time travel speed) and the class sample (time-varying travel speed) is achieved by the nearest neighbor mechanism. Assume that each subclass of the sample set is clustered at the centerxc=vct0-Ψ1·Δt,…,vct0+Ψ2·Δt,c=1,…,C. For the sample x=vt0-Ψ1·Δt,…,vt0-ψ1·Δt,…,vt0 to be tested, it is measured according to Euclidean distance:(31)Dx,xc=x-xc=∑ψ1=-Ψ10vt0+ψ1·Δt-vct0+ψ1·Δt2.In the class sample set, the nearest sample to the samplex is selected as(32)xk=vkt0-Ψ1·Δt,…,vkt0,…,vkt0+Ψ2·Δt,k=1,2,…,K,where K is the total number of samples included in the nearest neighbor sample set.The travel speed at theψ2th moments where 1≤ψ2≤Ψ2 after the decision moment t0 can be estimated as(33)vft0+ψ2·Δt=∑k=1Kvkt0+ψ2·ΔtK.


## 4. Dynamic Path Planning Based on Two-Stage Shuffled Frog Leaping Algorithm

When the dynamic network satisfies the FIFO condition, the shuffled frog leaping algorithm shows good performance of parallel computing and can obtain multiple paths [34] with relatively short travel time. According to the two-stage target optimization model in Section 2, a shuffled frog leaping K shortest path algorithm was proposed, and the process is as follows.


### 4.1. Coding Scheme and Fitness Function

Coding is a kind of mapping from the decision space of the optimization problem to the searching space of the shuffled frog leaping algorithm. The searching spaces are subsets of integer spaces. Therefore, it needs to be mapped to the integer space according to the characteristics of the decision variables. The decision vector of the dynamic shortest time path model is the path selection schemens,…,ni,ni+1,…,nd from the emergency vehicle sourced node ns to the accident node nd, where the link of the adjacent nodes ni,ni+1∈E, ni,ni+1∈N⊂N+. N+ is the positive integer set. A random integer coding scheme is proposed to ensure that the path sequences corresponding to individual frogs satisfy the connectivity. The scheme is shown as follows.The set of adjacent nodes of the nodeni is defined as Nei⊂N+; the current path sequence is CPi={ns,n1,…,ni}. According to formula (34), after selecting a node randomly from the set Eni=Nei∩CPi¯ as a valid node ni+1 and updating the current path sequence as CPi+1={ns,n1,…,ni,ni+1}, the position code of the frog Xf=ns,…,ni,ni+1,…,nd can be formed by searching the node one by one till the accident node nd.(34)ni+1=EniINTEni×r,where r is a random number and r∈0,1.According to the first-stage objective function of the dynamic optimal path model, the adaptation function of the SFLA-KSP algorithm can be defined as follows:(35)fXf=-∑i=sd-1Ti,i+1ti.


### 4.2. Two-Stage Shuffled Frog Leaping Algorithm

The two-stage shuffled frog leaping algorithm for solving the dynamic path planning is based on the SFLA-KSP algorithm to find theK optimal paths and obtain the optimal one by taking path degree of traffic congestion as the goal.


#### 4.2.1. The Frog Ethnic Group Initialization

According to the random coding scheme,P frog ethnic group is generated consisting of F individuals in the decision space, ensuring that each frog code Xf=ns,…,nif,ni+1f,…,nd is an available path from the source node ns to the accident node nd of emergency vehicles.


#### 4.2.2. Adaptation Function Value Calculation

According to formula (35), the adaptation values of F frogs fXf are calculated, the location Px of the optimal frogs was marked, and the F frogs were sorted according to the adaptation function values.


#### 4.2.3. Grouping and Optimization of Ethnic Group

The frog ethnic group is divided into several individual groups. For each ethnic group, the following iteration process is repeated for certain IT times.Step 1.
Assume that the locations of best and worst frog in the group arePb=ns,…,nib,ni+1b,…,nd and Pw=ns,…,niw,ni+1w,…,nd. The flag bits of nodes ni+1,i=s,s+1,…,i,i+1,…,d-1 are initialized as Wni+1=0, find the overlapped nodes nk in two paths from the source node ns, and set the node’s flag bit Wnk=1.Step 2.
From the first overlapped node, compare the travel timeTskw of the path ns,…,niw,…,nk and the travel time Tskb of the path ns,…,nib,…,nk and update the flag bit according to the following formula:(36)Wnk=2Tskw>Tskb1Tskw≤Tskb.Step 3.
IfWnk=2, then randomly generate a path from the node nk-1 (flag bit Wnk=1) to the node nk to replace the subpath in Pw and form a new frog code Pw′.Step 4.
IfWnk=1, set k=k+1; jump to Steps 2 and 3 until Wnk=2 and the worst frog location Pw gets updated.Step 5.
If the adaptationPw is still better than Pw′, replace Pb with the global optimal frog Px and repeat Steps 1–4.Step 6.
If the adaptationPw is still better than Pw′, randomly generate a path connecting node ns and the accident node nd in the decision space to replace Pw.


#### 4.2.4. Global Information Exchange

Remix the ethnic groups after optimization within the group and sort and remark them asPx. Then execute the process of next grouping and local search until IT times of global iterations are completed.


#### 4.2.5. Degree of Path Traffic Congestion Calculation

According to formula (13), the degrees of traffic congestion Rk of the Kth shortest path ∏i=sd-1nik,ni+1k,k=1,…,K are calculated and the best one is selected as the optimal solution.


## 4.1. Coding Scheme and Fitness Function

Coding is a kind of mapping from the decision space of the optimization problem to the searching space of the shuffled frog leaping algorithm. The searching spaces are subsets of integer spaces. Therefore, it needs to be mapped to the integer space according to the characteristics of the decision variables. The decision vector of the dynamic shortest time path model is the path selection schemens,…,ni,ni+1,…,nd from the emergency vehicle sourced node ns to the accident node nd, where the link of the adjacent nodes ni,ni+1∈E, ni,ni+1∈N⊂N+. N+ is the positive integer set. A random integer coding scheme is proposed to ensure that the path sequences corresponding to individual frogs satisfy the connectivity. The scheme is shown as follows.The set of adjacent nodes of the nodeni is defined as Nei⊂N+; the current path sequence is CPi={ns,n1,…,ni}. According to formula (34), after selecting a node randomly from the set Eni=Nei∩CPi¯ as a valid node ni+1 and updating the current path sequence as CPi+1={ns,n1,…,ni,ni+1}, the position code of the frog Xf=ns,…,ni,ni+1,…,nd can be formed by searching the node one by one till the accident node nd.(34)ni+1=EniINTEni×r,where r is a random number and r∈0,1.According to the first-stage objective function of the dynamic optimal path model, the adaptation function of the SFLA-KSP algorithm can be defined as follows:(35)fXf=-∑i=sd-1Ti,i+1ti.


## 4.2. Two-Stage Shuffled Frog Leaping Algorithm

The two-stage shuffled frog leaping algorithm for solving the dynamic path planning is based on the SFLA-KSP algorithm to find theK optimal paths and obtain the optimal one by taking path degree of traffic congestion as the goal.


### 4.2.1. The Frog Ethnic Group Initialization

According to the random coding scheme,P frog ethnic group is generated consisting of F individuals in the decision space, ensuring that each frog code Xf=ns,…,nif,ni+1f,…,nd is an available path from the source node ns to the accident node nd of emergency vehicles.


### 4.2.2. Adaptation Function Value Calculation

According to formula (35), the adaptation values of F frogs fXf are calculated, the location Px of the optimal frogs was marked, and the F frogs were sorted according to the adaptation function values.


### 4.2.3. Grouping and Optimization of Ethnic Group

The frog ethnic group is divided into several individual groups. For each ethnic group, the following iteration process is repeated for certain IT times.Step 1.
Assume that the locations of best and worst frog in the group arePb=ns,…,nib,ni+1b,…,nd and Pw=ns,…,niw,ni+1w,…,nd. The flag bits of nodes ni+1,i=s,s+1,…,i,i+1,…,d-1 are initialized as Wni+1=0, find the overlapped nodes nk in two paths from the source node ns, and set the node’s flag bit Wnk=1.Step 2.
From the first overlapped node, compare the travel timeTskw of the path ns,…,niw,…,nk and the travel time Tskb of the path ns,…,nib,…,nk and update the flag bit according to the following formula:(36)Wnk=2Tskw>Tskb1Tskw≤Tskb.Step 3.
IfWnk=2, then randomly generate a path from the node nk-1 (flag bit Wnk=1) to the node nk to replace the subpath in Pw and form a new frog code Pw′.Step 4.
IfWnk=1, set k=k+1; jump to Steps 2 and 3 until Wnk=2 and the worst frog location Pw gets updated.Step 5.
If the adaptationPw is still better than Pw′, replace Pb with the global optimal frog Px and repeat Steps 1–4.Step 6.
If the adaptationPw is still better than Pw′, randomly generate a path connecting node ns and the accident node nd in the decision space to replace Pw.


### 4.2.4. Global Information Exchange

Remix the ethnic groups after optimization within the group and sort and remark them asPx. Then execute the process of next grouping and local search until IT times of global iterations are completed.


### 4.2.5. Degree of Path Traffic Congestion Calculation

According to formula (13), the degrees of traffic congestion Rk of the Kth shortest path ∏i=sd-1nik,ni+1k,k=1,…,K are calculated and the best one is selected as the optimal solution.


## 4.2.1. The Frog Ethnic Group Initialization

According to the random coding scheme,P frog ethnic group is generated consisting of F individuals in the decision space, ensuring that each frog code Xf=ns,…,nif,ni+1f,…,nd is an available path from the source node ns to the accident node nd of emergency vehicles.


## 4.2.2. Adaptation Function Value Calculation

According to formula (35), the adaptation values of F frogs fXf are calculated, the location Px of the optimal frogs was marked, and the F frogs were sorted according to the adaptation function values.


## 4.2.3. Grouping and Optimization of Ethnic Group

The frog ethnic group is divided into several individual groups. For each ethnic group, the following iteration process is repeated for certain IT times.Step 1.
Assume that the locations of best and worst frog in the group arePb=ns,…,nib,ni+1b,…,nd and Pw=ns,…,niw,ni+1w,…,nd. The flag bits of nodes ni+1,i=s,s+1,…,i,i+1,…,d-1 are initialized as Wni+1=0, find the overlapped nodes nk in two paths from the source node ns, and set the node’s flag bit Wnk=1.Step 2.
From the first overlapped node, compare the travel timeTskw of the path ns,…,niw,…,nk and the travel time Tskb of the path ns,…,nib,…,nk and update the flag bit according to the following formula:(36)Wnk=2Tskw>Tskb1Tskw≤Tskb.Step 3.
IfWnk=2, then randomly generate a path from the node nk-1 (flag bit Wnk=1) to the node nk to replace the subpath in Pw and form a new frog code Pw′.Step 4.
IfWnk=1, set k=k+1; jump to Steps 2 and 3 until Wnk=2 and the worst frog location Pw gets updated.Step 5.
If the adaptationPw is still better than Pw′, replace Pb with the global optimal frog Px and repeat Steps 1–4.Step 6.
If the adaptationPw is still better than Pw′, randomly generate a path connecting node ns and the accident node nd in the decision space to replace Pw.


## 4.2.4. Global Information Exchange

Remix the ethnic groups after optimization within the group and sort and remark them asPx. Then execute the process of next grouping and local search until IT times of global iterations are completed.


## 4.2.5. Degree of Path Traffic Congestion Calculation

According to formula (13), the degrees of traffic congestion Rk of the Kth shortest path ∏i=sd-1nik,ni+1k,k=1,…,K are calculated and the best one is selected as the optimal solution.


## 5. Examples Validation

### 5.1. Examples Design [35]

In this paper, we select expressway network of Beijing as the research object, and use GPS data obtained from more than 20,000 taxis to verify the model and algorithm. The main data include time, latitude, longitude, driving angle, and travel speed. Examples of emergency vehicles and accidents distribution are shown in Figure5, where the number of emergency vehicles EV=8 and the number of accidents AC=3. Accident parameters are shown in Table 1, emergency vehicle parameters are shown in Table 2.Table 1
Accident parameters.
Accident code
Accident node
Accident link
Accident location
Accident level
Number of emergency vehicles in demand
1
n
48
n
3
,
n
4
L
3,48
=
3.7 km
Minor accident
1
L
48,4
=
1.8 km
2
n
49
n
14
,
n
15
L
14,49
=
7.1 km
General accident
1
L
49,15
=
2.4km
3
n
50
n
1
,
n
6
L
1,50
=
1.7 km
Major accident
2
L
50,6
=
3.4 kmTable 2
Emergency vehicle parameters.
Vehicle code
1
2
3
4
5
6
7
8
Node of the vehicle
n
51
n
52
n
53
n
54
n
55
n
56
n
57
n
58
Link of the vehicle
n
2
,
n
3
n
4
,
n
5
n
26
,
n
40
n
23
,
n
24
n
15
,
n
16
n
29
,
n
43
n
19
,
n
33
n
7
,
n
18
Vehicle location
L
2,51
=
2.3 km
L
4,52
=
7.7 km
L
26,53
=
2.5 km
L
23,54
=
3.9 km
L
15,55
=
2.0 km
L
29,56
=
2.9 km
L
19,57
=
5.1 km
L
7,58
=
2.8 km
L
51,3
=
2.3 km
L
52,5
=
3.8 km
L
53
,
40
=
2.6 km
L
54,24
=
3.9 km
L
55,16
=
2.0 km
L
56,43
=
3.0 km
L
57,33
=
2.6 km
L
58,18
=
2.9 kmFigure 5
Distribution of the accidents and emergency vehicles.


### 5.2. Prediction of Link Travel Speed

Take the speed data (30 days) of linkn2,n3 during November 2015 as input samples and the one of December 1, 2015–December 20, 2015, as the samples to be tested. The minimum time interval Δt=5min was selected, assuming that the emergency vehicle must arrive at the accident point within 40 minutes, which means that the objective time period is TS=t0+Δt,t0+2Δt,…,t0+8Δt. The SFLA-KC algorithm was used to fit the travel speed curve of each sample in 0:00–24:00. The sample feature vector xq consists of the initial time t0 and the time-varying travel speed of three cycles before t0. The mean absolute error of predicted values and the actual values of test samples in 0:00–24:00 of December 1, 2015, were calculated and then compile statistics to obtain the relationship between the test sample error and the number of cluster, which is shown in Figure 6.Figure 6
Relationship between the number of clusters and the test errors.As is shown in Figure6, the mean absolute error reaches minimum when the number of clusters is 7, and the mean absolute error increases with the number of cluster centers increasing. Therefore the optimal number of clusters is 7.Based on the parameters above, the SFLA-KC algorithm is used to estimate the travel speed of 20 test samples of sections during 0:00–24:00 and the estimated values are compared with the actual values. One of the predicted speed curves is shown in Figure7. The average absolute error of samples during 0:00–24:00 is shown in Table 3.Table 3
Test errors of the SFLA-KC and the kernel clustering algorithm.
The sample number
Mean absolute error (km/h)
SFLA-KC optimized error reduction
SFLA-KC optimized error reduction rate
SFLA-KC
Kernel clustering algorithm
1
2.72
4.06
1.34
33%
2
2.64
4.12
1.48
36%
3
2.88
4.24
1.36
32%
4
3.03
4.43
1.4
32%
5
2.18
3.78
1.6
42%
6
1.97
3.59
1.62
45%
7
2.96
4.32
1.36
31%
8
2.58
4.26
1.68
39%
9
2.77
4.19
1.42
34%
10
2.62
4.27
1.65
39%
11
3.12
4.68
1.56
33%
12
2.02
3.88
1.86
48%
13
1.98
3.92
1.94
49%
14
2.89
4.49
1.6
36%
15
2.54
3.98
1.44
36%
16
2.37
4.26
1.89
44%
17
2.79
4.72
1.93
41%
18
2.99
4.63
1.64
35%
19
1.93
3.84
1.91
50%
20
2.21
4.01
1.8
45%
Average
2.56
4.18
1.62
39%Figure 7
The predicted travel speed curve in December 1, 2015.According to Figure7, it can be concluded that SFLA-KC algorithm test results are consistent with the actual values. It can be seen from Table 3 that the mean absolute error of the 20 test samples is reduced by about 2 km/h after SFLA-KC algorithm optimization, and the reduction rate was 39%. Therefore the SFLA-KC algorithm can effectively reduce the error of the test results and show better performance than the kernel clustering algorithm when estimating travel speed.


### 5.3. Dynamic Path Selection of Emergency Vehicles

Based on the predicted travel speed of links collected every 5 min during 8:00–9:00 of December 1, 2015, the travel speed function is fitted and the travel time function of the road is further calculated. Based on SFLA-KSP algorithm, theK shortest paths of each emergency vehicle corresponding to each accident is calculated with the weight of the link travel time function, and the optimal path is selected according to (13). The parameters of SFLA-KSP algorithm are shown in Table 4.Table 4
Parameter selection of SFLA-KSP.
Scale of frog group
Group number
Iteration time within groups
Global iteration time within groups
50
10
5
20The emergency vehicles optimal paths can be obtained by running the two-stage shuffled frog leaping process as shown in Table5, where the sixth column and the seventh column are separately the shortest paths and travel time of the dynamic traffic arrangement algorithm [26] calculated by use of the DTALite software [36]. Based on Table 5, the optimal paths of two methods are the same. However, due to the prediction accuracies of two algorithms, the travel time results are different.Table 5
Results of theK shortest paths selection.
Emergency vehicle number
Accident number
K shortest paths
Optimal path
Optimal travel time(min)
Dynamic traffic arrangement algorithm[26]
Dynamic traffic arrangement algorithm [26]
1
1
51, 3, 4, 48
51, 3, 4, 48
34.01
51, 3, 4, 48
35.27
1
2
—
—
∞
—
∞
1
3
51, 3, 2, 1, 50
51, 3, 2, 1, 50
39.98
51, 3, 2, 1, 50
38.84
2
1
—
—
∞
—
∞
2
2
52, 5, 15, 49
52, 5, 15, 49
37.42
52, 5, 15, 49
40.89
2
3
52, 5, 6, 1, 50
52, 5, 6, 1, 50
57.91
52, 5, 6, 1, 50
55.56
3
1
53, 26, 25, 24, 13, 4, 48
53, 26, 25, 24, 13, 4, 48
59.04
53, 26, 25, 24, 13, 4, 48
57.02
3
2
—
—
∞
—
∞
3
3
—
—
∞
—
∞
4
1
54, 24, 13, 4, 48
54, 24, 13, 4, 48
38.67
54, 24, 13, 4, 48
39.32
4
2
—
—
∞
—
∞
4
3
—
—
∞
—
∞
5
1
—
—
∞
—
∞
5
2
55, 15, 49
55, 15, 49
33.74
55, 15, 49
32.42
5
3
—
—
∞
—
∞
6
1
—
—
∞
—
∞
6
2
56, 29, 15, 49
56, 29, 15, 49
35.06
56, 29, 15, 49
35.92
6
3
—
—
∞
—
∞
7
1
—
—
∞
—
∞
7
2
—
—
∞
—
∞
7
3
57, 33, 32, 18, 7, 1, 50
57.36
—
∞
7
3
57, 33, 32, 18, 6, 1, 50
57, 33, 32, 18, 6, 1, 50
59.42
57, 33, 32, 18, 6, 1, 50
60.87
8
1
58, 7, 1, 2, 3, 49
58, 7, 1, 2, 3, 49
55.24
58, 7, 1, 2, 3, 49
53.94
8
2
—
—
∞
—
∞
8
3
58, 7, 1, 50
58, 7, 1, 50
30.33
58, 7, 1, 50
32.79After solving the model, it can be seen that there are two paths for the seventh vehicle heading to the third accident, and the parameters of expected travel time and predicted travel time of pathn57→n33→n32→n18→n7→n1→n50 are shown in Table 6.Table 6
The desired travel time and prediction travel time.
Link
T
D
i
,
i
+
1 (min)
T
i
,
i
+
1
t (min)
Δ
T
i
,
i
+
1 (min)
n
33
,
n
32
8.23
8.57
0.34
n
32
,
n
18
8.86
8.96
0.10
n
18
,
n
6
18.31
20.51
2.20
n
6
,
n
1
11.59
16.42
4.83
n
1
,
n
50
6.80
20.52
13.72Based on the parameters in Table6 and formula (13), the degree of traffic congestion of path n57→n33→n32→n18→n6→n1→n50 is 0.39, while the degree of traffic congestion of path n57→n33→n32→n18→n7→n1→n50 is 0.81. Therefore, the optimal path for vehicle Ev7 (at the node n57) heading to accident Ac3 (at the node n50) can be determined as the optimal path. In addition, dispatching the fourth vehicle for the first accident, the rescue time and the path can be optimal. Dispatching the fifth vehicle for the second accident, the rescue time and the path can be optimal. Dispatching the first vehicle and the eighth vehicle for the third accident, the rescue time and the path can be optimal.


## 5.1. Examples Design [35]

In this paper, we select expressway network of Beijing as the research object, and use GPS data obtained from more than 20,000 taxis to verify the model and algorithm. The main data include time, latitude, longitude, driving angle, and travel speed. Examples of emergency vehicles and accidents distribution are shown in Figure5, where the number of emergency vehicles EV=8 and the number of accidents AC=3. Accident parameters are shown in Table 1, emergency vehicle parameters are shown in Table 2.Table 1
Accident parameters.
Accident code
Accident node
Accident link
Accident location
Accident level
Number of emergency vehicles in demand
1
n
48
n
3
,
n
4
L
3,48
=
3.7 km
Minor accident
1
L
48,4
=
1.8 km
2
n
49
n
14
,
n
15
L
14,49
=
7.1 km
General accident
1
L
49,15
=
2.4km
3
n
50
n
1
,
n
6
L
1,50
=
1.7 km
Major accident
2
L
50,6
=
3.4 kmTable 2
Emergency vehicle parameters.
Vehicle code
1
2
3
4
5
6
7
8
Node of the vehicle
n
51
n
52
n
53
n
54
n
55
n
56
n
57
n
58
Link of the vehicle
n
2
,
n
3
n
4
,
n
5
n
26
,
n
40
n
23
,
n
24
n
15
,
n
16
n
29
,
n
43
n
19
,
n
33
n
7
,
n
18
Vehicle location
L
2,51
=
2.3 km
L
4,52
=
7.7 km
L
26,53
=
2.5 km
L
23,54
=
3.9 km
L
15,55
=
2.0 km
L
29,56
=
2.9 km
L
19,57
=
5.1 km
L
7,58
=
2.8 km
L
51,3
=
2.3 km
L
52,5
=
3.8 km
L
53
,
40
=
2.6 km
L
54,24
=
3.9 km
L
55,16
=
2.0 km
L
56,43
=
3.0 km
L
57,33
=
2.6 km
L
58,18
=
2.9 kmFigure 5
Distribution of the accidents and emergency vehicles.


## 5.2. Prediction of Link Travel Speed

Take the speed data (30 days) of linkn2,n3 during November 2015 as input samples and the one of December 1, 2015–December 20, 2015, as the samples to be tested. The minimum time interval Δt=5min was selected, assuming that the emergency vehicle must arrive at the accident point within 40 minutes, which means that the objective time period is TS=t0+Δt,t0+2Δt,…,t0+8Δt. The SFLA-KC algorithm was used to fit the travel speed curve of each sample in 0:00–24:00. The sample feature vector xq consists of the initial time t0 and the time-varying travel speed of three cycles before t0. The mean absolute error of predicted values and the actual values of test samples in 0:00–24:00 of December 1, 2015, were calculated and then compile statistics to obtain the relationship between the test sample error and the number of cluster, which is shown in Figure 6.Figure 6
Relationship between the number of clusters and the test errors.As is shown in Figure6, the mean absolute error reaches minimum when the number of clusters is 7, and the mean absolute error increases with the number of cluster centers increasing. Therefore the optimal number of clusters is 7.Based on the parameters above, the SFLA-KC algorithm is used to estimate the travel speed of 20 test samples of sections during 0:00–24:00 and the estimated values are compared with the actual values. One of the predicted speed curves is shown in Figure7. The average absolute error of samples during 0:00–24:00 is shown in Table 3.Table 3
Test errors of the SFLA-KC and the kernel clustering algorithm.
The sample number
Mean absolute error (km/h)
SFLA-KC optimized error reduction
SFLA-KC optimized error reduction rate
SFLA-KC
Kernel clustering algorithm
1
2.72
4.06
1.34
33%
2
2.64
4.12
1.48
36%
3
2.88
4.24
1.36
32%
4
3.03
4.43
1.4
32%
5
2.18
3.78
1.6
42%
6
1.97
3.59
1.62
45%
7
2.96
4.32
1.36
31%
8
2.58
4.26
1.68
39%
9
2.77
4.19
1.42
34%
10
2.62
4.27
1.65
39%
11
3.12
4.68
1.56
33%
12
2.02
3.88
1.86
48%
13
1.98
3.92
1.94
49%
14
2.89
4.49
1.6
36%
15
2.54
3.98
1.44
36%
16
2.37
4.26
1.89
44%
17
2.79
4.72
1.93
41%
18
2.99
4.63
1.64
35%
19
1.93
3.84
1.91
50%
20
2.21
4.01
1.8
45%
Average
2.56
4.18
1.62
39%Figure 7
The predicted travel speed curve in December 1, 2015.According to Figure7, it can be concluded that SFLA-KC algorithm test results are consistent with the actual values. It can be seen from Table 3 that the mean absolute error of the 20 test samples is reduced by about 2 km/h after SFLA-KC algorithm optimization, and the reduction rate was 39%. Therefore the SFLA-KC algorithm can effectively reduce the error of the test results and show better performance than the kernel clustering algorithm when estimating travel speed.


## 5.3. Dynamic Path Selection of Emergency Vehicles

Based on the predicted travel speed of links collected every 5 min during 8:00–9:00 of December 1, 2015, the travel speed function is fitted and the travel time function of the road is further calculated. Based on SFLA-KSP algorithm, theK shortest paths of each emergency vehicle corresponding to each accident is calculated with the weight of the link travel time function, and the optimal path is selected according to (13). The parameters of SFLA-KSP algorithm are shown in Table 4.Table 4
Parameter selection of SFLA-KSP.
Scale of frog group
Group number
Iteration time within groups
Global iteration time within groups
50
10
5
20The emergency vehicles optimal paths can be obtained by running the two-stage shuffled frog leaping process as shown in Table5, where the sixth column and the seventh column are separately the shortest paths and travel time of the dynamic traffic arrangement algorithm [26] calculated by use of the DTALite software [36]. Based on Table 5, the optimal paths of two methods are the same. However, due to the prediction accuracies of two algorithms, the travel time results are different.Table 5
Results of theK shortest paths selection.
Emergency vehicle number
Accident number
K shortest paths
Optimal path
Optimal travel time(min)
Dynamic traffic arrangement algorithm[26]
Dynamic traffic arrangement algorithm [26]
1
1
51, 3, 4, 48
51, 3, 4, 48
34.01
51, 3, 4, 48
35.27
1
2
—
—
∞
—
∞
1
3
51, 3, 2, 1, 50
51, 3, 2, 1, 50
39.98
51, 3, 2, 1, 50
38.84
2
1
—
—
∞
—
∞
2
2
52, 5, 15, 49
52, 5, 15, 49
37.42
52, 5, 15, 49
40.89
2
3
52, 5, 6, 1, 50
52, 5, 6, 1, 50
57.91
52, 5, 6, 1, 50
55.56
3
1
53, 26, 25, 24, 13, 4, 48
53, 26, 25, 24, 13, 4, 48
59.04
53, 26, 25, 24, 13, 4, 48
57.02
3
2
—
—
∞
—
∞
3
3
—
—
∞
—
∞
4
1
54, 24, 13, 4, 48
54, 24, 13, 4, 48
38.67
54, 24, 13, 4, 48
39.32
4
2
—
—
∞
—
∞
4
3
—
—
∞
—
∞
5
1
—
—
∞
—
∞
5
2
55, 15, 49
55, 15, 49
33.74
55, 15, 49
32.42
5
3
—
—
∞
—
∞
6
1
—
—
∞
—
∞
6
2
56, 29, 15, 49
56, 29, 15, 49
35.06
56, 29, 15, 49
35.92
6
3
—
—
∞
—
∞
7
1
—
—
∞
—
∞
7
2
—
—
∞
—
∞
7
3
57, 33, 32, 18, 7, 1, 50
57.36
—
∞
7
3
57, 33, 32, 18, 6, 1, 50
57, 33, 32, 18, 6, 1, 50
59.42
57, 33, 32, 18, 6, 1, 50
60.87
8
1
58, 7, 1, 2, 3, 49
58, 7, 1, 2, 3, 49
55.24
58, 7, 1, 2, 3, 49
53.94
8
2
—
—
∞
—
∞
8
3
58, 7, 1, 50
58, 7, 1, 50
30.33
58, 7, 1, 50
32.79After solving the model, it can be seen that there are two paths for the seventh vehicle heading to the third accident, and the parameters of expected travel time and predicted travel time of pathn57→n33→n32→n18→n7→n1→n50 are shown in Table 6.Table 6
The desired travel time and prediction travel time.
Link
T
D
i
,
i
+
1 (min)
T
i
,
i
+
1
t (min)
Δ
T
i
,
i
+
1 (min)
n
33
,
n
32
8.23
8.57
0.34
n
32
,
n
18
8.86
8.96
0.10
n
18
,
n
6
18.31
20.51
2.20
n
6
,
n
1
11.59
16.42
4.83
n
1
,
n
50
6.80
20.52
13.72Based on the parameters in Table6 and formula (13), the degree of traffic congestion of path n57→n33→n32→n18→n6→n1→n50 is 0.39, while the degree of traffic congestion of path n57→n33→n32→n18→n7→n1→n50 is 0.81. Therefore, the optimal path for vehicle Ev7 (at the node n57) heading to accident Ac3 (at the node n50) can be determined as the optimal path. In addition, dispatching the fourth vehicle for the first accident, the rescue time and the path can be optimal. Dispatching the fifth vehicle for the second accident, the rescue time and the path can be optimal. Dispatching the first vehicle and the eighth vehicle for the third accident, the rescue time and the path can be optimal.


## 6. Conclusions

Rapid dispatching of emergency vehicles is the core to rescue traffic accidents and reduce losses. This paper proposed that the emergency vehicle scheduling must be based on the dynamic change of the expressway network with reliable dynamic path selection as the guarantee and the actual shortest response time as optimization goal.Firstly, the polyline-shaped speed function is defined to simulate the time-dependent dynamic change of the traffic conditions by using the time-dependent speed function of the expressway network. And a new SFLA-KC algorithm is proposed based on the real-time and historical data. The first-stage target of minimum travel time is determined and the travel time prediction can be realized considering the constraints of rescue time and resources demand.Then, the path planning of emergency vehicles should take the traffic congestion into consideration. Based on the shortest path model, the index of degree of traffic congestion was defined to measure the reliability as the second-stage target, thus constructing the two-stage optimization model.Next, a two-stage shuffled frog leaping algorithm with SFLA-KSP algorithm as the core is proposed. The random integer coding scheme is used to design the internal optimal strategy of the FIFO network to solve the model. The congestion index is used for optimization searching to obtain thekth optimal paths with shortest travel time.Finally, based on the data of floating vehicles in Beijing, the validity of SFLA-KC algorithm and two-stage shuffled leapfrog algorithm is verified by examples. The results show that the prediction error of SFLA-KSP algorithm is relatively low and two-stage shuffled frog leaping algorithm can search and obtain the optimal path effectively and rapidly.



---

*Source: 9184891-2017-05-21.xml*