# Emergency Vehicle Dispatching and Redistribution in Highway Network Based on Bilevel Programming

Authors: Xiaohong Duan; Shouxin Song; Jiandong Zhao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Response time is a key factor in the emergency vehicle dispatching problem. Because regional emergency vehicles are limited, vehicle gaps will be created in the rescue station after vehicles are dispatched to several accidents, which affects quick response to the subsequent incidents. To solve this problem, a bilevel programming model for emergency vehicle dispatching and redistribution is established, of which the optimal objectives are the shortest rescue time for current accidents and the shortest time for vehicle redistribution, and the key constraints are emergency vehicle requirements and accident time windows. In the precondition of effective rescue of current accidents, emergency vehicles are redistributed according to the potential risks in the rescue station coverage area. A bilevel shuffled frog leaping algorithm is proposed to solve the bilevel programming model. The dispatching results of examples show that the model conforms to dispatching decision rule and the bilevel shuffled frog leaping algorithm can resolve the bilevel programming model fast and efficiently.


---

## Body

## 1. Introduction

Traffic accidents pose a serious threat to the safety of people’s life and property. Only in 2012, the number of death tolls in the road traffic accidents in China reached 59,997, and the direct economic loss was 1.175 billion yuan [1]. After traffic accidents, the completion of rescue within limited time can effectively reduce accident loss and prevent the matters from deteriorating and spreading. Emergency vehicle dispatching problem is the key to the emergency rescue. It is of crucial significance to study how to reasonably dispatch the limited vehicles to achieve an in time rescue.At present, the study on emergency vehicle dispatching problem mainly focuses on dispatching model and dispatching algorithm. For dispatching model, Church and Roberts [2] formulated the relationship between the quality of service and the response time. The results show that the benefit of emergency rescue is proportional to incident response speed. Haghani and Oh [3] defined emergency resource dispatch issue as a multicommodity and multimodal network flow problem with time window aiming for minimum transportation cost. Also a multiobjective model to solve the emergency materials dispatch problem was established. Carter et al. [4] advocated that if the future requirement was taken into consideration, it was not always the optimal strategy to dispatch the available vehicles nearest to the accident sites. With the use of Carter’s thoughts for reference, Sherali and Subramanian [5] set up opportunity cost-based models, and vehicles were dispatched to handle the current accidents with taking into account opportunity cost of the rescue of the future incidents, thereby to minimize the overall costs of emergency rescue. Kolesar and Walker [6] put forward an idea of fire vehicles reposition. Vehicles that had not been distributed to the current accidents were repositioned, to reduce the future incident loss. In order to solve the issue that there will be regional vehicle gaps after emergency vehicles are dispatched out, Yang et al. [7] set up an emergency vehicle dispatching model. The model was targeted to minimize the weighted sum of the travel time, to realize the optimal dispatching of emergency vehicles, and to redistribute the idle vehicles regarding the area coverage as constraints. Chai et al. [8] defined all the possible future incidents, such as traffic incident black spots and secondary incidents, as potential incidents. After analyzing their impact on emergency vehicle dispatching strategy, he improved the opportunity cost-based models. Jia et al. [9] and Zhao et al. [10] optimized opportunity cost-based models as well.For dispatching algorithm, Ichoua et al. [11] used parallel tabu search heuristic to solve the vehicle dispatching models, respectively, based on static and dynamic parameters. With the use of ant colony optimization algorithm, Yi and Kumar [12] resolved the vehicle route construction problem and multicommodity dispatch problem in emergency rescue in two phases. Li et al. [13] designed a heuristic algorithm based on network optimization in graph theory and linear programming to solve the emergency dispatching model for multiresource and multiaccident problem. Zhang et al. [14] applied the improved ant colony algorithm to solve the most satisfying model of emergency resource dispatching.According to the review of literature and the scholars, when modeling emergency vehicle dispatching problem, consider more about such factors as response time, time windows, and potential incidents. The vehicle redistribution method with area coverage constraints has been used to resolve the regional vehicle gaps in the process of the rescue. However, due to the differences of current accidents, vehicles, roads, and environments within each coverage area of the rescue station, the potential risks are different. In the situation of limited vehicles, it is more rational to regard the potential risks as a key factor for redistribution and preferentially guarantee the vehicle requirements of high risk areas. In view of the above and taking potential risks into consideration, we have set up themultiobjective programming model of vehicle dispatching and redistribution based on shuffled frog leaping algorithm (SF-M) in the previous work and solved the model with weight-based shuffled frog leaping algorithm [15]. But it is revealed at the same time that because of the different attributes of all the objectives, it is hard to determine the weight value scientifically and objectively. However, bilevel programming model can better describe the restrictive relation between the object in current accident rescue and the vehicle redistribution, thus guaranteeing the preferential decision-making power of the objective function of the first level and avoiding the objective weight successfully. Because of its inherent complexity,bilevel programming problem (BLP) has been proved to be a NP-hard problem. In addition, themultiple-incident and multiple-response (MIMR) emergency vehicle dispatching problems are large-scale variable problems, and heuristic algorithm is superior in solving this kind of problems [16–18]. Above all, with the aim to solve the emergency vehicle dispatching and redistribution problem in MIMR situation, this paper sets up a bilevel programming model of which the minimum time for the rescue of current accidents is the objective function of the first level and the minimum time for vehicle redistribution is the objective function of the second level, and then a bilevel shuffled frog leaping algorithm is put forward to solve the model.


## 2. Problem Statement

As shown in Figure1, there are I (I
≥
2) rescue stations in the area PL. At a certain moment, J (J
≥
2) accidents occur at the same time, and the required number of vehicles at the accident site e
j
(
e
j
∈
E
,
j
=
1,2
,
…
,
J
) is N
j
>
0. The total number of emergency vehicles in the area PL is K, and ∑
N
j
<
K. When there is coupling between current accidents and road network factors, it is easy to trigger potential incidents, which may result in new rescue requirements. The potential risks within the coverage area D
i of the rescue station s
i
(
s
i
∈
S
,
i
=
1,2
,
…
,
I
) can be quantized as R
i [19]. In the precondition of guaranteeing the requirements of current accidents, vehicles should be redistributed according to R
i, thus to improve the overall rescue efficiency. Suppose that the potentially required number of vehicles within D
i is Q
i, while the travel time for the emergency vehicle v
k
(
v
k
∈
V
,
k
=
1,2
,
…
,
K
) to arrive at the accident site e
j and the rescue station s
i is t
k
j
1
>
0 and t
k
i
2
≥
0, respectively.Figure 1
MIMR emergency vehicle dispatching problem.


### 2.1. Soft Time Window Constraints

The time sensibility of emergency rescue requires that the emergency vehicle should arrive at the accident site within certain time window. If the earliest timet
min
⁡
j spent by the vehicles to arrive at the accident site e
j is shorter than T
min
⁡
j, then there may be opportunity cost for the vehicles to wait here, and the ability of evacuating the accident site will be influenced, so it should be punished with C
t
min
⁡
j. If the latest time t
max
⁡
j spent by the vehicles to arrive at the accident site e
j is longer than T
max
⁡
j, then the rescue will be delayed, so it should be punished with C
t
max
⁡
j. Consider the following:
(1)
C
t
min
⁡
j
=
α
×
E
c
j
-
1
,
(2)
C
t
max
⁡
j
=
β
×
S
j
,
where E
c
j and S
j stand for the evacuation ability of accident site e
j and accident severity and α and β are scale factors.


### 2.2. Vehicle Requirements Constraints

Emergency vehicles are limited, so they cannot completely satisfy the requirements of current accidents and potential incidents. If the vehicle requirements of the accidente
j cannot be satisfied, it should be punished with C
n
j, while if the vehicle requirements of potential incidents within D
i are not satisfied, it should be punished with C
q
i. Consider the following:
(3)
C
n
j
=
θ
×
S
j
,
C
q
i
=
χ
×
R
i
,
where R
i represents the potential risks within D
i and θ and χ are scale factors.


## 2.1. Soft Time Window Constraints

The time sensibility of emergency rescue requires that the emergency vehicle should arrive at the accident site within certain time window. If the earliest timet
min
⁡
j spent by the vehicles to arrive at the accident site e
j is shorter than T
min
⁡
j, then there may be opportunity cost for the vehicles to wait here, and the ability of evacuating the accident site will be influenced, so it should be punished with C
t
min
⁡
j. If the latest time t
max
⁡
j spent by the vehicles to arrive at the accident site e
j is longer than T
max
⁡
j, then the rescue will be delayed, so it should be punished with C
t
max
⁡
j. Consider the following:
(1)
C
t
min
⁡
j
=
α
×
E
c
j
-
1
,
(2)
C
t
max
⁡
j
=
β
×
S
j
,
where E
c
j and S
j stand for the evacuation ability of accident site e
j and accident severity and α and β are scale factors.


## 2.2. Vehicle Requirements Constraints

Emergency vehicles are limited, so they cannot completely satisfy the requirements of current accidents and potential incidents. If the vehicle requirements of the accidente
j cannot be satisfied, it should be punished with C
n
j, while if the vehicle requirements of potential incidents within D
i are not satisfied, it should be punished with C
q
i. Consider the following:
(3)
C
n
j
=
θ
×
S
j
,
C
q
i
=
χ
×
R
i
,
where R
i represents the potential risks within D
i and θ and χ are scale factors.


## 3. Mathematical Modeling

Bilevel programming originates from the game theory of Stackelberg about the market economy [20]. In the BLP model, the leader should make decisions at first to make its objective function as optimal as possible, while the follower should judge to make the second level objective function as optimal as possible according to the decisions of the leader. Based on the bilevel programming, the emergency vehicle dispatching and redistribution model can be formulated as follows:
(4)
min
⁡
F
=
∑
j
∑
k
t
k
j
1
×
x
k
j
1
+
∑
j
C
n
j
×
y
j
+
∑
i
C
q
i
×
γ
i
+
∑
j
C
t
min
⁡
j
×
z
j
+
∑
j
C
t
max
⁡
j
×
w
j
,
(5)
s
.
t
.
N
j
-
∑
k
x
k
j
1
≤
M
×
y
j
,
∀
e
j
∈
E
,
(6)
Q
i
-
∑
k
x
k
i
2
≤
M
×
γ
i
,
∀
s
i
∈
S
,
(7)
t
max
⁡
j
-
T
max
⁡
j
≤
M
×
w
j
,
t
max
⁡
j
=
max
⁡
x
k
j
1
×
t
k
j
1
,
∀
e
j
∈
E
,
(8)
T
min
⁡
j
-
t
min
⁡
j
≤
M
×
z
j
,
t
min
⁡
j
=
min
⁡
x
k
j
1
×
t
k
j
1
,
∀
e
j
∈
E
,
(9)
min
⁡
f
=
∑
i
∑
k
t
k
i
2
×
x
k
i
2
,
(10)
s
.
t
.
g
x
k
j
1
,
x
k
i
2
=
∑
j
x
k
j
1
+
∑
i
x
k
i
2
-
1
,
∀
v
k
∈
V
,
(11)
g
(
x
k
j
1
,
x
k
i
2
)
=
0
.Formula (4) is the objective function of the first level. With respect to the significance of response time in emergency rescue, while taking into consideration the analysis of the above mentioned problem constraints, the total travel time of vehicles and punishment of unmet key constraints are minimized by the first-level objective function.Formula (5) is the vehicle requirements constraints for current accidents. If the vehicle requirements of the accident e
j cannot be satisfied, then y
j
=
1, otherwise y
j
=
0. M is a huge constant.Formula (6) is the vehicle requirements constraints for potential incidents. If the vehicle requirements of potential incidents within D
i are not satisfied, then γ
i
=
1, otherwise γ
i
=
0.Formulas (7) and (8) are soft time window constraints. If the latest time t
max
⁡
j spent by the vehicles to arrive at the accident site e
j is longer than T
max
⁡
j, w
j
=
1, otherwise w
j
=
0. If the earliest time t
min
⁡
j spent by the vehicles to arrive at the accident site e
j is shorter than T
min
⁡
j, z
j
=
1, otherwise z
j
=
0.Formula (9) is the objective function of the second level. It minimizes the travel time for vehicle redistribution.Formulas (10) and (11) are constraints for the state of the vehicle. If the vehicle v
k is dispatched to accident e
j, then the decision variable x
k
j
1
=
1, else x
k
j
1
=
0. If the vehicle v
k is redistributed to station s
i, then the decision variable x
k
i
2
=
1, else x
k
i
2
=
0. The vehicle v
k can only be in one of two states.


## 4. Solution Method for the Vehicle Dispatching Model Based on Bilevel Shuffled Frog Leaping Algorithm

Shuffled frog leaping algorithm(SFLA) is a relatively new memetic metaheuristic algorithm which was firstly applied to water distribution problem by Eusuff and Lansey in 2003 [21]. It combines the advantages ofparticle swarm optimization algorithm(PSO) andshuffled complex evolution algorithm(SCE) and has been proved to have a good performance in convergence speed and solution precision [22]. The algorithm simulates the process during which the frog population seeks for food; the frog population is divided into some memeplexes. Frogs within each memeplex perform local search through information interchange. After a while, all the memeplexes will be mixed together to make the information exchanged within the whole population.The mathematical model of shuffled frog leaping algorithm is as follows.(1) Initialization. Algorithm population P is made up of F frogs. The position X
m
=
[
x
m
1
,
…
,
x
m
n
]
T, m
=
1,2
,
…
,
F of each frog represents a feasible decision vector. Each decision vector corresponds to a performance function value f
(
X
m
) related to the optimization objectives.(2) Ranking and Grouping. F frogs are ranked in descending order of performance function value. In addition, according to the formula (12), they are distributed into a memeplexes, each of which contains b frogs. Consider the following:
(12)
M
o
=
X
o
+
a
l
-
1
∈
P
∣
1
≤
l
≤
b
1
≤
o
≤
a
.(3) Local Search. According to the formulas (13) and (14), the worst frog’s position P
w in each memeplex is renewed along with the best frog’s position P
b in the memeplex or the best frog’s position P
x in the population until the specified iterative times It are completed. Consider the following:
(13)
D
s
=
MIN
INT
r
×
P
b
-
P
w
,
D
max
⁡
,
P
b
-
P
w
≥
0
MAX
INT
r
×
P
b
-
P
w
,
-
D
max
⁡
,
P
b
-
P
w
<
0
(14)
new
P
w
=
old
P
w
+
D
s
,
where r is a random number and r
∈
[
0,1
]. D
s means the adjustment vector of the frog individual. D
max
⁡ represents the maximum adjustment step size vector.(4) Mixing and Global Search. All the memeplexes, which have completed local search, are mixed again. After ranking, it is feasible to implement the next grouping and local search for the specified iterative times IT.


### 4.1. The Bilevel Shuffled Frog Leaping Algorithm

For the proposed emergency vehicle dispatching and redistribution model, the decision vector of the first levelx
1, x
1
∈
{
0,1
}
K
×
J consists of the elements x
k
j
1, k
=
1,2
,
…
,
K, j
=
1,2
,
…
,
J, and the decision vector of the second level x
2, x
2
∈
{
0,1
}
K
×
I consists of the elements x
k
i
2, k
=
1,2
,
…
,
K, i
=
1,2
,
…
,
I. In order to solve this model, some sets are defined as follows.Definition 1.
The search space of emergency vehicle dispatching and redistribution model is as follows:(15)
Ω
=
(
x
1
,
x
2
)
∣
x
1
∈
0,1
K
×
J
,
x
2
∈
0,1
K
×
I
.Definition 2.
Constrained set of emergency vehicle dispatching and redistribution model is as follows:(16)
S
=
(
x
1
,
x
2
)
∈
Ω
∣
g
(
x
k
j
1
,
x
k
i
2
)
=
0
.Definition 3.
The decision set allowed by the first level model is as follows:(17)
T
=
x
1
∣
(
x
1
,
x
2
)
∈
S
.Definition 4.
For anyx
1
∈
T, the feasible set of the second level model is as follows:
(18)
S
x
1
=
x
2
∣
(
x
1
,
x
2
)
∈
S
.Definition 5.
For anyx
1
∈
T, the rational reaction set of the second level model is as follows:
(19)
M
x
1
=
x
2
∣
x
2
∈
arg
min
⁡
[
f
(
x
1
,
x
2
)
∣
x
2
∈
S
x
1
]
.Definition 6.
The feasible solution set of the emergency vehicle dispatching and redistribution model is as follows:(20)
D
=
(
x
1
,
x
2
)
∣
(
x
1
,
x
2
)
∈
S
,
x
2
∈
M
(
x
1
)
.A kind of hierarchical structure is designed for bilevel shuffled frog leaping algorithm. The structure integrates two basic shuffled frog leaping algorithm models, SFLA_U and SFLA_D, which are, respectively, used to solve the first-level and the second-level optimization problems.The algorithm follows the decision rule of bilevel programming problems: The SFLA_U randomly generatesF decision vectors X
m
(
m
=
1,2
,
…
,
F
) in searching space Ω. X
m consists of x
m
1
(
m
=
1,2
,
…
,
F
) and x
m
2
(
m
=
1,2
,
…
,
F
). For each x
m
1, the SFLA_D regards it as parameter and makes decisions freely within S
(
x
m
1
), to obtain the optimum reaction x
m
2
*
∈
M
(
x
m
1
). Taking (
x
m
1
,
x
m
2
*
) as parameter, the SFLA_U obtains the optimal solution (
x
1
*
,
x
2
*
) in line with its own objectives. The principle of the bilevel shuffled frog leaping algorithm is as shown in Figure 2.Figure 2
The principle of bilevel shuffled frog leaping algorithm.


### 4.2. Encoding and Decoding

The working object of shuffled frog leaping algorithm is integer vector, so it is necessary to encode it according to the features of decision variables. The decision variables of the bilevel programming model in this paper are 0-1 numerical variablesx
k
j
1 and x
k
i
2, which, respectively, express whether the vehicle should be dispatched to accident sites and whether they should be redistributed to rescue stations. In order to make them better suitable for shuffled frog leap frog algorithm, decision variables are converted to integer variable x
k. x
k represents the dispatching strategy of the kth (
k
=
1
,
…
,
K
) vehicle, and each vehicle can go to one of the accident sites e
1
,
e
2
,
…
,
e
J and the rescue stations s
1
,
s
2
,
…
,
s
I. The feasible set of x
k is {
1,2
,
…
,
J
,
J
+
1
,
…
,
J
+
I
}. In this case, the encoding of frog position can be expressed with a row vector matrix. Consider the following:
(21)
X
m
,
:
=
x
m
,
1
,
x
m
,
2
,
…
,
x
m
,
k
,
…
,
x
m
,
K
,
k
=
1
,
…
,
K
.After calculating and obtaining the value ofx
k, they should be decoded in the reverse way of encoding.The process of encoding and decoding can be expressed as in(22)
e
1
e
2
e
3
⋯
e
j
⋯
e
J
s
1
s
2
s
3
⋯
s
i
⋯
s
I
v
1
v
2
v
3
v
4
⋮
v
k
⋮
v
K
0
1
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
1
0
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
1
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
1
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
0
⋯
0
1
0
0
⋯
0
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0
0
0
0
⋯
0
0
0
0
⋯
0
⋯
1
⇄
encoding
decoding





x
1

x
2
x
3
x
4
⋯
x
k
⋯
x
K
2
1
j
J
+
i
⋯
J
+
1
⋯
J
+
I
.


### 4.3. Performance Function

Performance value is the symbol of measuring the individual advantages and disadvantages, as well as the power driving the evolution of frog population. Just as the objective function, the performance function of the first-level and second-level algorithm isf
_
U
(
X
) and f
_
D
(
X
), respectively. Consider the following:
(23)
f
_
U
(
X
)
=
-
∑
j
∑
k
t
k
j
1
×
x
k
j
1
-
∑
j
C
n
j
×
max
⁡
0
,
N
j
-
∑
k
x
k
j
1
-
∑
i
C
q
i
×
max
⁡
0
,
Q
i
-
∑
k
x
k
i
2
-
∑
j
C
t
min
⁡
j
×
max
⁡
0
,
T
min
⁡
j
-
t
min
⁡
j
-
∑
j
C
t
max
⁡
j
×
max
⁡
0
,
t
max
⁡
j
-
T
max
⁡
j
,
f
_
D
X
=
-
∑
i
∑
k
t
k
i
2
×
x
k
i
2
.The accident severityS
j is divided into four levels by referring to the country’s division of road traffic accident severity, and the value of accident severity is shown in Table 1.Table 1
The 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
Extraserious accident
Situation 1
⩾3
—
—
—
100
Situation 2
—
⩾11
—
—
Situation 3
1
⩾8
—
—
Situation 4
2
⩾5
—
—
Situation 5
—
—
—
⩾60,000In order to guarantee that the requirements of current accidents are satisfied firstly, the scale factorsθ and χ of (3) are selected, and the accident punishment C
n
j and potential incidents punishment C
q
i should satisfy the following conditions:
(24)
min
⁡
C
n
j
>
max
⁡
C
q
i
.According to the number of lanes affected by traffic accident, the evacuation abilityE
c
j is divided into four levels; let the scale factor in (1)  α
=
100; C
t
min
⁡
j is shown in Table 2.Table 2
Punishment for time window constraints.
The number of affected lanes
The evacuation ability
C
t
min
⁡
j
1
8
12.5
2
6
16.7
3
4
25
>3
2
50


### 4.4. Process of the Algorithm

The bilevel shuffled frog leaping algorithm for emergency vehicle dispatching problem initializes the vehicle dispatching strategy on the basis of the encoding method. The frog population of each level is guided by the performance function to evolve constantly. The variables transmit between the first level and the second level populations, and the performance functions finally converge at the best dispatching strategy. The process is shown in Algorithm1.Algorithm 1:Bilevel shuffled frog leaping algorithm for emergency vehicle dispatching problem.
Input: The population sizeF, the number of memeplexes a, local search iterations It, global search iterations IT, the
maximum step sizeD
max
⁡, the accident’s requirements N
j, the potential incident’s requirements Q
i, the punishment
for accident requirementsC
n
j, the punishment for potential incident requirements C
q
i, the time window T
max
⁡
j, T
min
⁡
j,
the punishment for the time window constraintsC
t
max
⁡
j, C
t
min
⁡
j, the travel time t
k
j
1, t
k
i
2.
Output: Process of optimization off
_
U
(
X
), the optimal dispatching strategy.
Begin
(0.0) Parameter initialization;
(0.1) Initialize the position of frogsX
[
m
]
,
m
=
1,2
,
.
.
.
,
F randomly;
(0.2) Form
=
1
:
F
(1.0) Substitutex
1
[
m
] into the second-level model, apply S
F
L
A
_
D, and iterate with f
_
D
(
X
) as guidance until the
optimal solution to the second-level model x
2
*
[
m
] is obtained;
(1.1) Substitute(
x
1
[
m
]
,
x
2
*
[
m
]
) into the first-level model, calculate f
_
U
(
X
[
m
]
) of frog m.
End
(0.3) For IT >0
(2.0)F frogs are ranked in descending order of the value f
_
U
(
X
[
m
]
), and record position of the best frog P
x;
(2.1) According to the formula (12), F frogs are distributed into a memeplexes, each of which contains b frogs;
(2.2) Forl
=
1
:
a
ForIt
>
0
(3.0) Renew the position of the worst frogP
w according to the formula (13) and (14);
(3.1) If Step (3.0) fails to improve thef
_
U
(
X
) value of the worst frog, then replace the P
b
in formula (13) with P
x and renew the position of the worst frog;
(3.2)It
=
It
-
1.
End
End
(2.3) Mix all the memeplexes;
(2.4)IT
=
IT
-
1.
End
(0.4) Output the optimal solutionX and the performance function value f
_
U
(
X
), and the algorithm stops running.
End


## 4.1. The Bilevel Shuffled Frog Leaping Algorithm

For the proposed emergency vehicle dispatching and redistribution model, the decision vector of the first levelx
1, x
1
∈
{
0,1
}
K
×
J consists of the elements x
k
j
1, k
=
1,2
,
…
,
K, j
=
1,2
,
…
,
J, and the decision vector of the second level x
2, x
2
∈
{
0,1
}
K
×
I consists of the elements x
k
i
2, k
=
1,2
,
…
,
K, i
=
1,2
,
…
,
I. In order to solve this model, some sets are defined as follows.Definition 1.
The search space of emergency vehicle dispatching and redistribution model is as follows:(15)
Ω
=
(
x
1
,
x
2
)
∣
x
1
∈
0,1
K
×
J
,
x
2
∈
0,1
K
×
I
.Definition 2.
Constrained set of emergency vehicle dispatching and redistribution model is as follows:(16)
S
=
(
x
1
,
x
2
)
∈
Ω
∣
g
(
x
k
j
1
,
x
k
i
2
)
=
0
.Definition 3.
The decision set allowed by the first level model is as follows:(17)
T
=
x
1
∣
(
x
1
,
x
2
)
∈
S
.Definition 4.
For anyx
1
∈
T, the feasible set of the second level model is as follows:
(18)
S
x
1
=
x
2
∣
(
x
1
,
x
2
)
∈
S
.Definition 5.
For anyx
1
∈
T, the rational reaction set of the second level model is as follows:
(19)
M
x
1
=
x
2
∣
x
2
∈
arg
min
⁡
[
f
(
x
1
,
x
2
)
∣
x
2
∈
S
x
1
]
.Definition 6.
The feasible solution set of the emergency vehicle dispatching and redistribution model is as follows:(20)
D
=
(
x
1
,
x
2
)
∣
(
x
1
,
x
2
)
∈
S
,
x
2
∈
M
(
x
1
)
.A kind of hierarchical structure is designed for bilevel shuffled frog leaping algorithm. The structure integrates two basic shuffled frog leaping algorithm models, SFLA_U and SFLA_D, which are, respectively, used to solve the first-level and the second-level optimization problems.The algorithm follows the decision rule of bilevel programming problems: The SFLA_U randomly generatesF decision vectors X
m
(
m
=
1,2
,
…
,
F
) in searching space Ω. X
m consists of x
m
1
(
m
=
1,2
,
…
,
F
) and x
m
2
(
m
=
1,2
,
…
,
F
). For each x
m
1, the SFLA_D regards it as parameter and makes decisions freely within S
(
x
m
1
), to obtain the optimum reaction x
m
2
*
∈
M
(
x
m
1
). Taking (
x
m
1
,
x
m
2
*
) as parameter, the SFLA_U obtains the optimal solution (
x
1
*
,
x
2
*
) in line with its own objectives. The principle of the bilevel shuffled frog leaping algorithm is as shown in Figure 2.Figure 2
The principle of bilevel shuffled frog leaping algorithm.


## 4.2. Encoding and Decoding

The working object of shuffled frog leaping algorithm is integer vector, so it is necessary to encode it according to the features of decision variables. The decision variables of the bilevel programming model in this paper are 0-1 numerical variablesx
k
j
1 and x
k
i
2, which, respectively, express whether the vehicle should be dispatched to accident sites and whether they should be redistributed to rescue stations. In order to make them better suitable for shuffled frog leap frog algorithm, decision variables are converted to integer variable x
k. x
k represents the dispatching strategy of the kth (
k
=
1
,
…
,
K
) vehicle, and each vehicle can go to one of the accident sites e
1
,
e
2
,
…
,
e
J and the rescue stations s
1
,
s
2
,
…
,
s
I. The feasible set of x
k is {
1,2
,
…
,
J
,
J
+
1
,
…
,
J
+
I
}. In this case, the encoding of frog position can be expressed with a row vector matrix. Consider the following:
(21)
X
m
,
:
=
x
m
,
1
,
x
m
,
2
,
…
,
x
m
,
k
,
…
,
x
m
,
K
,
k
=
1
,
…
,
K
.After calculating and obtaining the value ofx
k, they should be decoded in the reverse way of encoding.The process of encoding and decoding can be expressed as in(22)
e
1
e
2
e
3
⋯
e
j
⋯
e
J
s
1
s
2
s
3
⋯
s
i
⋯
s
I
v
1
v
2
v
3
v
4
⋮
v
k
⋮
v
K
0
1
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
1
0
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
1
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
0
⋯
0
0
0
0
⋯
1
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
0
⋯
0
1
0
0
⋯
0
⋯
0
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
0
0
0
0
⋯
0
0
0
0
⋯
0
⋯
1
⇄
encoding
decoding





x
1

x
2
x
3
x
4
⋯
x
k
⋯
x
K
2
1
j
J
+
i
⋯
J
+
1
⋯
J
+
I
.


## 4.3. Performance Function

Performance value is the symbol of measuring the individual advantages and disadvantages, as well as the power driving the evolution of frog population. Just as the objective function, the performance function of the first-level and second-level algorithm isf
_
U
(
X
) and f
_
D
(
X
), respectively. Consider the following:
(23)
f
_
U
(
X
)
=
-
∑
j
∑
k
t
k
j
1
×
x
k
j
1
-
∑
j
C
n
j
×
max
⁡
0
,
N
j
-
∑
k
x
k
j
1
-
∑
i
C
q
i
×
max
⁡
0
,
Q
i
-
∑
k
x
k
i
2
-
∑
j
C
t
min
⁡
j
×
max
⁡
0
,
T
min
⁡
j
-
t
min
⁡
j
-
∑
j
C
t
max
⁡
j
×
max
⁡
0
,
t
max
⁡
j
-
T
max
⁡
j
,
f
_
D
X
=
-
∑
i
∑
k
t
k
i
2
×
x
k
i
2
.The accident severityS
j is divided into four levels by referring to the country’s division of road traffic accident severity, and the value of accident severity is shown in Table 1.Table 1
The 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
Extraserious accident
Situation 1
⩾3
—
—
—
100
Situation 2
—
⩾11
—
—
Situation 3
1
⩾8
—
—
Situation 4
2
⩾5
—
—
Situation 5
—
—
—
⩾60,000In order to guarantee that the requirements of current accidents are satisfied firstly, the scale factorsθ and χ of (3) are selected, and the accident punishment C
n
j and potential incidents punishment C
q
i should satisfy the following conditions:
(24)
min
⁡
C
n
j
>
max
⁡
C
q
i
.According to the number of lanes affected by traffic accident, the evacuation abilityE
c
j is divided into four levels; let the scale factor in (1)  α
=
100; C
t
min
⁡
j is shown in Table 2.Table 2
Punishment for time window constraints.
The number of affected lanes
The evacuation ability
C
t
min
⁡
j
1
8
12.5
2
6
16.7
3
4
25
>3
2
50


## 4.4. Process of the Algorithm

The bilevel shuffled frog leaping algorithm for emergency vehicle dispatching problem initializes the vehicle dispatching strategy on the basis of the encoding method. The frog population of each level is guided by the performance function to evolve constantly. The variables transmit between the first level and the second level populations, and the performance functions finally converge at the best dispatching strategy. The process is shown in Algorithm1.Algorithm 1:Bilevel shuffled frog leaping algorithm for emergency vehicle dispatching problem.
Input: The population sizeF, the number of memeplexes a, local search iterations It, global search iterations IT, the
maximum step sizeD
max
⁡, the accident’s requirements N
j, the potential incident’s requirements Q
i, the punishment
for accident requirementsC
n
j, the punishment for potential incident requirements C
q
i, the time window T
max
⁡
j, T
min
⁡
j,
the punishment for the time window constraintsC
t
max
⁡
j, C
t
min
⁡
j, the travel time t
k
j
1, t
k
i
2.
Output: Process of optimization off
_
U
(
X
), the optimal dispatching strategy.
Begin
(0.0) Parameter initialization;
(0.1) Initialize the position of frogsX
[
m
]
,
m
=
1,2
,
.
.
.
,
F randomly;
(0.2) Form
=
1
:
F
(1.0) Substitutex
1
[
m
] into the second-level model, apply S
F
L
A
_
D, and iterate with f
_
D
(
X
) as guidance until the
optimal solution to the second-level model x
2
*
[
m
] is obtained;
(1.1) Substitute(
x
1
[
m
]
,
x
2
*
[
m
]
) into the first-level model, calculate f
_
U
(
X
[
m
]
) of frog m.
End
(0.3) For IT >0
(2.0)F frogs are ranked in descending order of the value f
_
U
(
X
[
m
]
), and record position of the best frog P
x;
(2.1) According to the formula (12), F frogs are distributed into a memeplexes, each of which contains b frogs;
(2.2) Forl
=
1
:
a
ForIt
>
0
(3.0) Renew the position of the worst frogP
w according to the formula (13) and (14);
(3.1) If Step (3.0) fails to improve thef
_
U
(
X
) value of the worst frog, then replace the P
b
in formula (13) with P
x and renew the position of the worst frog;
(3.2)It
=
It
-
1.
End
End
(2.3) Mix all the memeplexes;
(2.4)IT
=
IT
-
1.
End
(0.4) Output the optimal solutionX and the performance function value f
_
U
(
X
), and the algorithm stops running.
End


## 5. Illustrative Examples

In order to demonstrate the efficacy ofvehicle dispatching and redistribution model based on bilevel shuffled frog-leaping algorithm (S-B-M), two illustrative examples with different parameters were used. Tables 3, 4, and 5 list the parameters of examples.Table 3
Accident parameters.
e
j
Example number
N
j
S
j
E
c
j
T
max
⁡
j
T
min
⁡
j
α
β
θ
C
n
j
C
t
max
⁡
j
C
t
min
⁡
j
e
1
I
2
60
4
15
5
60
60
25
II
1
40
8
10
0
40
40
12.5
e
2
I
1
40
8
8
0
100
1
1
40
40
12.5
II
1
60
6
20
10
60
60
16.7
e
3
I
—
—
—
—
—
—
—
—
II
1
80
4
15
6
80
80
25Table 4
Rescue station parameters.
s
i
Example number
Q
i
R
i
χ
C
q
i
s
1
I
25
25
II
21
21
s
2
I
22
22
II
1
24
1
24
s
3
I
17
17
II
27
27
s
4
I
10
10
II
10
10Table 5
Travel time matrix.
Example number
e
1
e
2
e
3
s
1
s
2
s
3
s
4
v
1
I
8
10
—
0
10
5
14
II
6
8
12
v
2
I
12
6
—
10
0
12
8
II
12
8
14
v
3
I
6
12
—
11
11
6
14
II
7
13
13
v
4
I
7
15
—
13
12
0
9
II
9
16
7
v
5
I
13
10
—
16
6
15
5
II
15
14
9S-B-M was used to find the optimum dispatching and redistribution strategy. Then S-B-M was compared with SF-M established in our previous study [15], and S-B algorithm was compared withbilevel particle swarm optimization (P-B) presented by Zhao et al. [16]. After some testing, the S-B algorithm parameters were defined as Table 6.Table 6
Selection of parameters of S-B.
Example number
F
a
It
IT
D
max
⁡
[
1,5
]
F
1
a
1
It1
IT1
D
1
max
⁡
[
1,5
]
I
300
20
15
5
[
6
,
…
,
6
]
150
15
10
5
[
6
,
…
,
6
]
II
500
25
20
5
[
7
,
…
,
7
]
150
15
10
5
[
7
,
…
,
7
]After ten runs, the best solutions found in previous studies and that were obtained by using S-B-M are summarized in Table7. Figure 3 shows the evolutionary processes of the first level SFLA and PSO.Table 7
The best solutions of examples.
Example number
The optimal value of the objective function
The optimal value of the first-level objective function
The optimal value of the second-level objective function
The optimal solution
The average number of iterations
The average evolution time (s)
Success rate (%)in ten runs
SF-M
S-B-M
P-B
S-B-M
P-B
S-B-M
P-B
SF-M
S-B
P-B
S-B
P-B
S-B
P-B
I
53
46
11
3, 2, 1, 1, 4
1, 2, 1, 5, 4
4.3
30.4
7.43
21.82
90
40
II
59
57
15
1, 5, 2, 3, 6
1, 5, 2, 6, 3
5.2
43.2
13.12
43.05
80
50(a) Evolutionary processes of the first level algorithm in example I. (b) Evolutionary processes of the first level algorithm in example II.
(a)
(b)(1) Result Analysis of Example I. The best solution obtained by using S-B-M was [
3,2
,
1,1
,
4
] compared to [
1,2
,
1,5
,
4
] for SF-M. We decoded these two solutions and listed the corresponding optimum strategies in Table 8 for comparison.Table 8
The comparison of two optimum strategies of example I obtained by using S-B-M and SF-M.
The optimal solution
The optimal dispatching and redistribution strategy
Total rescue time for current accidents (min)
Total punishment for the time window constraints
Total punishment for current accidents requirements
Total punishment for potential incidents requirements
Total time for vehicle redistribution (min)
S-B-M
[
3,2
,
1,1
,
4
]
v
1
→
s
1,
v
2
→
e
2,
v
3
→
e
1,
v
4
→
e
1,
v
5
→
s
2
19
0
0
27
6
SF-M
[
1,2
,
1,5
,
4
]
v
1
→
e
1,
v
2
→
e
2,
v
3
→
e
1,
v
4
→
s
3,
v
5
→
s
2
20
0
0
35
6The optimal total rescue time for current accidents calculated by S-B-M was 19 min and was 1 min shorter than that of SF-M. It was in conformity with the objective function for the current accidents rescue. The total punishment for unmet the requirements of potential incidents calculated by S-B-M was 8 shorter than that of SF-M. That is to say, through emergency vehicle redistribution, S-B-M met the requirements in the area exposed to higher risks in priority. It was also in accordance with the objective function of emergency vehicle dispatching and redistribution problem.(2) Result Analysis of Example II. The best solution obtained by using S-B-M was [
1,5
,
2,3
,
6
] compared to [
1,5
,
2,6
,
3
] for SF-M. We decoded these two solutions and listed the corresponding optimum strategies in Table 9 for comparison.Table 9
The comparison of two optimum strategies of example II obtained by using S-B-M and SF-M.
The optimal solution
The optimal dispatching and redistribution strategy
Total rescue time for current accidents (min)
Total punishment for the time window constraints
Total punishment for current accidents requirements
Total punishment for potential incidents requirements
Total time for vehicle redistribution (min)
S-B-M
[
1,5
,
2,3
,
6
]
v
1
→
e
1,
v
2
→
s
2,
v
3
→
e
2,
v
4
→
e
3,
v
5
→
s
3
26
0
0
31
15
SF-M
[
1,5
,
2,6
,
3
]
v
1
→
e
1,
v
2
→
s
2,
v
3
→
e
2,
v
4
→
s
3,
v
5
→
e
3
28
0
0
31
0The optimal total time for vehicle redistribution calculated by S-B-M was longer than that of SF-M. However, the total rescue time for current accidents obtained by using S-B-M was 2 min shorter than that of SF-M. It agreed with the objective function that emergency vehicles were redistributed in the premise of prompt rescue for current accidents. The further analysis of the solution of S-B-M implied the following.(a)
The travel timest
11
1, t
32
1, and t
43
1 for vehicles to arrive at accidents were 6 min, 13 min, and 7 min. The time window of accidents e
1, e
2, and e
3 was [
0,10
], [
10,20
], and [
6,15
]. t
11
1, t
32
1, and t
43
1 were all within their time window, and they were close to the lower limit of the time window, which was in accordance with the first-level objective function (the shortest travel time).
(b)
After the vehicle requirements of current accidentse
1, e
2, and e
3 were satisfied, the strategy firstly ensured that the rescue stations s
2 and s
3 with higher risks were redistributed with vehicles, and then vehicles were specifically redistributed according to the objective function of the second level (the shortest travel time for the redistributed vehicles). For instance, aiming at the shortest travel time for the redistributed vehicles, idle vehicle v
5 should be redistributed to the rescue station s
4, but the potential risk R
3 was higher than R
4. As a result, vehicle v
5 was redistributed to the rescue station s
3.
(c)
The first-level objective function (the shortest vehicle travel time) was optimized earlier than the second-level objective function (the shortest travel time for the redistributed vehicles).From the above analysis, S-B-M was more appropriate to the decision rule of emergency dispatching and redistribution than SF-M. The optimal dispatching and redistribution strategies are shown in Figure4.(a) The optimal dispatching and redistribution strategy of example I. (b) The optimal dispatching and redistribution strategy of example II.
(a)
(b)(3) Performance Analysis of S-B Algorithm. The solutions obtained by using S-B were equivalent to results obtained by using P-B. However, S-B found the optimal solution more quickly than P-B. The optimum solution of the example I was found in the average of 4.3 iterations using S-B compared to 30.4 iterations required by P-B, and it was found in the average of 7.43 s evolution time using S-B compared to 21.82 s evolution time for P-B. The optimum solution of the example II was found in the average of 5.2 iterations using S-B compared to 43.2 iterations required by P-B, and it was found in the average of 13.12 s evolution time using S-B compared to 43.05 s evolution time for P-B.Success rate in ten runs of example I was 90% using S-B compared to 40% for P-B, and that of example II was 80% using S-B compared to 50% for P-B. Therefore, S-B algorithm preceded P-B algorithm in realizing the optimal resolution for the bilevel programming mode.


## 6. Conclusion

After the accidents, emergency vehicles should be dispatched to perform effective emergency rescue, and they should also be redistributed according to the potential risks of the coverage area of rescue station, thus to shorten the response time for future incidents. In this paper, we analyze the key constraints and relevant punishments, of vehicle dispatching and redistribution problem, and quantify the punishment coefficient in levels. Then we point out that the emergency vehicle dispatching and redistribution problem is a bilevel programming problem, as a result of which S-B-M is established to solve the problem. Then the efficacy of S-B-M was tested by solving two illustrative examples. The results imply the following.(
1
) S-B-M is more compatible for solving the issue of emergency vehicle dispatching and redistribution than SF-M. (
2
) According to the optimized order of the emergency vehicle dispatching and redistribution problem, S-B-M optimizes the total rescue time for current accidents firstly, then the idle emergency vehicles are redistributed to the rescue station with higher potential risks, and then the travel time of the redistributed vehicles is optimized. (
3
) The shuffled frog leaping algorithm designed on the basis of the bilevel programming decision rule can solve the emergency vehicle dispatching model well. S-B finds the optimal solutions faster than P-B.



---

*Source: 731492-2015-03-02.xml*