# A Novel Chaotic Particle Swarm Optimization Algorithm for Parking Space Guidance

Authors: Na Dong; Xing Fang; Ai-guo Wu
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

An evolutionary approach of parking space guidance based upon a novel Chaotic Particle Swarm Optimization (CPSO) algorithm is proposed. In the newly proposed CPSO algorithm, the chaotic dynamics is combined into the position updating rules of Particle Swarm Optimization to improve the diversity of solutions and to avoid being trapped in the local optima. This novel approach, that combines the strengths of Particle Swarm Optimization and chaotic dynamics, is then applied into the route optimization (RO) problem of parking lots, which is an important issue in the management systems of large-scale parking lots. It is used to find out the optimized paths between any source and destination nodes in the route network. Route optimization problems based on real parking lots are introduced for analyzing and the effectiveness and practicability of this novel optimization algorithm for parking space guidance have been verified through the application results.


---

## Body

## 1. Introduction

Recently, there are a large number of research works in the area of parking management systems [1–3]. Mei and Tian proposed a new parking guidance and information (PGI) configuration model based on the optimized combination method by analyzing of parking choice behavior [1]. Thompson et al. [2] described a behavioral model of parking choice incorporating drivers’ perceptions of waiting times at car parks based on PGI signs and formulated a mathematical program to determine the optimal display PGI sign configuration and finally applied it to an existing PGI system operating in Tama New Town near Tokyo. Lee et al. [3] designed and implemented a hybrid artificial intelligent control scheme for a car-like vehicle to perform the task of optimal parking. In the literature, there have been several algorithms to solve different path optimization problems, but they all have their own shortcomings [4]. These traditional algorithms have some major shortcomings, as they only search for the shortest route but cannot determine any other similar/nonsimilar short routes; also, they exhibit high computational complexity when solving real-time problems [5]. As the mostly used A
∗ and Dijkstra algorithms, A
∗ is a quite efficient and widely used path optimization algorithm, but the users need to balance its h
(
n
) and g
(
n
) well in order to get a most satisfying result; Dijkstra algorithm is also widely used, but it is relatively slow in searching [6–8]. Artificial neural networks (ANN) are also successfully used to solve the path optimization problems [9, 10]. However, the ANN approaches also suffer from some limitations. The complexity of the hardware increases considerably with increasing number of network nodes, while decreasing the reliability of the solution. Also, suboptimal paths cannot be obtained by the ANN approaches [5]. In the pursuit for more efficient algorithms, evolutionary programming techniques have been widely investigated among other methodologies for this problem and successful applications have been reported [11–14]. The success of these evolutionary programming approaches inspires us to investigate the use of other more powerful evolutionary algorithms for this kind of problems. And in this paper, we explore a more efficient and accurate way, based on heuristic optimizations, to solve the RO problem of the parking lot management system. This study of the parking inducing problem aimed at specific objectives, namely, searching the parking spaces with the shortest distance by a newly proposed Chaotic Particle Swarm Optimization algorithm.Particle Swarm Optimization (PSO) technique is considered as one of the modern stochastic search algorithms for optimization introduced by Kennedy and Eberhart [15]. Due to its simple concept, easy implementation, and quick convergence, nowadays, PSO has gained much attention and wide applications in different fields. For examples, Sun [16] applied PSO to roundness measurement under a machine vision system and Omran et al. [17] proposed a PSO-based image clustering method. However, the standard PSO greatly depends on its parameters and exists as a premature phenomenon, especially in solving complex problems [18]. Also, PSO has an excessive decrease of particle variety as the number of generations increases and the swarm becomes stagnated after a certain number of iterations, which means it lacks the ability to achieve sustainable development. In order to keep the particles from the stagnation state and improve the PSO algorithm, the chaos optimization mechanism is introduced in this paper and a novel chaotic optimization algorithm is proposed.Chaos is a kind of characteristic of nonlinear systems and chaotic motion can traverse every state in a certain region by its own regularity and, nowadays, has been applied in different fields [19, 20]. Due to the unique ergodicity and special ability in avoiding being trapped in local optima, chaos search has been proved to be much more efficient than some other stochastic algorithms [21], and chaotic systems have been exploited in some metaheuristic methods to solve global optimization problems with a large number of local minima. By making use of chaotic behaviors, those optimization methods search extensively for solutions and are able to find a desirable solution within a practical time. It has been indicated that a chaotic variable has three basic traits, namely, pseudorandomness, ergodicity, and irregularity, which makes it generally exhibit better numerical performance than random operators in searching [22]. A lot of existing optimization results demonstrated that chaos optimization algorithms (COAs) and hybrid COA can more easily escape from local minima than classical stochastic optimization algorithms and they have been proven to be more effective than stochastic algorithms [23–25]. Recently, several attempts for evolutionary optimization algorithms using chaos methods were made [26–28] and obtained rich harvests. Xie et al. [26] introduced chaos into the system by randomly reinitializing the particle positions with a small constant probability. Liu et al. [27] incorporated chaos into PSO with adaptive inertia weight factor to construct a Chaotic PSO. Chauhan et al. [28] investigated a Chaotic PSO, namely, Totally Disturbed Particle Swarm Optimization (TDPSO), and employed this enhanced variant of PSO for obtaining the optimal machining conditions during multipass turning operations subject to various constraints. In this paper, the notion of chaos is introduced into the PSO’s position updating rules and the novel chaotic optimization algorithm is then applied to solve the parking space guidance problems. Simulation tests are conducted based on a real parking lot and the effectiveness of the proposed method has been revealed through the simulation results.


## 2. Chaotic Particle Swarm Optimization

PSO is an optimization technique which maintains a population of individuals, namely, particles, where each particle is guided by the social interaction in order to reach the most promising area of the search space. The particles start at a random initial position in a multidimensional search space and search for the minimum or maximum of a given objective function by flying through the search space. Each particle flies inD-dimensional problem space with a velocity, which is adjusted at each time step. The movement of ith particle, x
i, depends on its velocity, v
i, and the location where the personal best position so far, p
i
=
(
p
i
1
,
p
i
2
,
…
,
p
i
d
), or the neighborhood best position, l
b
e
s
t
i
=
(
l
b
e
s
t
i
1
,
l
b
e
s
t
i
2
,
…
,
l
b
e
s
t
i
d
), has already been found. Equation (1) updates the velocity of each particle, whereas (2) updates each particle’s position in the search space, and c
1 and c
2 are cognitive coefficients and φ
1 and φ
2 are two uniform random numbers from U
(
0
,
1
):(1)
v
i
d
=
w
·
v
i
d
+
c
1
·
φ
1
·
p
i
d
-
x
i
d
+
c
2
·
φ
2
·
l
b
e
s
t
i
d
-
x
i
d
,
(2)
x
i
d
=
x
i
d
+
v
i
d
.Here, in order to enrich the search behavior, the chaotic dynamics is incorporated into the optimization algorithm.


### 2.1. Incorporating Chaotic Dynamics into PSO

Since it gives the uniform distribution function in the interval[
0
,
1
], the tent map shows outstanding advantages and higher iterative speed than the logistic map [29]. In this paper, the tent map is used to generate chaos variables. The tent map is defined by(3)
z
n
+
1
=
μ
1
-
2
z
n
-
0.5
,
0
≤
z
0
≤
1
,
n
=
0,1
,
2
,
…
,where u
∈
(
0,1
) is the bifurcation parameter. Specifically, when μ
=
1, the tent map exhibits entirely chaotic dynamics and ergodicity in the interval [
0
,
1
]. Figure 1 shows the distribution of two chaos sequences after 1500 iterations with the initial point (
x
10
=
0.231
,
x
20
=
0.356
) in 2D space. Each point in Figure 1 can be described by (
x
1
j
,
x
2
j
)
,
j
=
1,2
,
…
,
1500.Figure 1
Distribution of the chaos variables.The chaotic dynamic is used for initialization, which can be described as follows.Using the tent map (μ
=
1) to generate the chaos variables and rewriting (3) give(4)
z
j
i
+
1
=
μ
1
-
2
z
j
i
-
0.5
,
j
=
1,2
,
…
,
D
,where z
j denotes the jth chaos variable and i denotes the chaos iteration number. Set i
=
0 and generate D chaos variables by (4). After that, let i
=
1,2
,
…
,
N in turn and generate the initial swarm. Then, the chaos variable above z
j
(
i
)
,
i
=
1,2
,
…
,
N, will be mapped into the search range of the decision variable:(5)
x
i
j
=
x
m
i
n
,
j
+
z
j
i
x
m
a
x
,
j
-
x
m
i
n
,
j
,
j
=
1,2
,
…
,
D
.Defining (6)
x
i
=
x
i
1
,
x
i
2
,
…
,
x
i
D
,
i
=
1,2
,
…
,
N
,the chaotic initialized swarm can be obtained.According to the chaotic search, a chaotic disturbance can be added as follows:(7)
z
′
=
1
-
γ
ψ
∗
+
γ
z
,where γ is a parameter that falls in [
0
,
1
], z
′
=
(
z
1
′
,
z
2
′
,
…
,
z
D
′
) is the chaos vector where the disturbance has been added, and ψ
∗ is the optimal chaos vector where the current optima x
∗
=
(
x
1
∗
,
x
2
∗
,
…
,
x
D
∗
) are mapped into the interval [
0
,
1
]:(8)
ψ
∗
=
x
∗
-
x
m
i
n
x
m
a
x
-
x
m
i
n
.The Chaotic PSO algorithm is described as follows.Step 1.
Initialize the swarm (k
=
0) by the abovementioned chaotic initialization method according to (4)–(6).Step 2.
Evaluate the fitnessf
i and update p
i and l
b
e
s
t
i if needed.Step 3.
Update the velocityv
i and position x
i of the particle by (1) and (2), respectively.Step 4.
Rank the swarm by fitness in an ascending order. If the current iterationk
≤
(
1
/
2
)
k
m
a
x and the current optimum f
(
p
i
) stays the same for several iterations, go to Step 5; otherwise, turn to Step 6.Step 5.
Introduce the chaotic disturbance to update the best particle. Add a chaotic disturbance to the bottom 30% of particles in the swarm by (7), and, then, map them into the decision variables by (5). Rerank the swarm by fitness and find out the new best particle.Step 6.
If a stopping criterion is satisfied, stop; otherwise, letk
=
k
+
1 and go back to Step 2.


### 2.2. Benchmark Function Tests

In order to test the performance of the proposed Chaotic PSO algorithm, minimization problems of four multimodal functions [30, 31], the Ellipsoidal function (f
1), the Rosenbrock function (f
2), the generalized Griewank function (f
3), and Rastrigin’s function (f
4), are introduced for simulation tests:(9)
f
1
x
=
∑
i
=
1
D
i
x
i
2
,
-
100
≤
x
i
≤
100
,
f
2
x
=
∑
i
=
1
D
-
1
100
x
i
+
1
-
x
i
2
2
+
x
i
-
1
2
,
-
30
≤
x
i
≤
30
,
f
3
x
=
1
4000
∑
i
=
1
D
x
i
2
-
∏
i
=
1
D
c
o
s
x
i
i
+
1
,
-
600
≤
x
i
≤
600
,
f
4
x
=
∑
i
=
1
D
x
i
2
-
10
cos
⁡
2
π
x
i
+
10
,
-
5.12
≤
x
i
≤
5.12
.For both functions, the parameters are fixed as m
=
20
,
k
m
a
x
=
1500. The fitness value is set as the function value. The standard PSO, PSO with mutation (MPSO) [32], and GA are introduced here for comparison tests. For each function, different dimensions (10, 20, and 30) are tested. c
1
=
c
2
=
2, and ω is fixed as 0.5 for all PSO algorithms. The GA is real code, crossover probability p
c
=
0.8, and mutation probability p
m
=
0.1. Table 1 lists the mean minimum of 50 independent runs.Table 1
Comparison results of mean fitness forf
1 and f
2.
f
D
Algorithms
PSO
MPSO
Chaotic PSO
GA
f
1
10
5.49
E
-
28
3.67
E
-
29
2.63
E
-
29
6.81
E
-
03
20
3.28
E
-
28
5.64
E
-
30
2.152
E
-
33
3.12
E
-
03
30
8.26
E
-
27
6.28
E
-
33
8.20
E
-
33
0.0582
f
2
10
24.3651
11.5834
4.3021
35.6902
20
66.2781
17.6590
15.0153
84.6521
30
268.1459
96.4923
80.2643
329.5826
f
3
10
0.0812
0.0538
0.0237
0.0953
20
0.0350
0.0031
1.1506
E
-
6
0.0767
30
0.0218
5.2311
E
-
5
1.3451
E
-
7
0.0388
f
4
10
6.432
3.6253
2.463
2.329
20
12.325
8.7524
7.6038
23.3028
30
21.632
17.849
12.168
48.943From Table1, it can be seen that the proposed Chaotic PSO has better accuracy and is superior to other optimization algorithms in terms of the searching solutions.


## 2.1. Incorporating Chaotic Dynamics into PSO

Since it gives the uniform distribution function in the interval[
0
,
1
], the tent map shows outstanding advantages and higher iterative speed than the logistic map [29]. In this paper, the tent map is used to generate chaos variables. The tent map is defined by(3)
z
n
+
1
=
μ
1
-
2
z
n
-
0.5
,
0
≤
z
0
≤
1
,
n
=
0,1
,
2
,
…
,where u
∈
(
0,1
) is the bifurcation parameter. Specifically, when μ
=
1, the tent map exhibits entirely chaotic dynamics and ergodicity in the interval [
0
,
1
]. Figure 1 shows the distribution of two chaos sequences after 1500 iterations with the initial point (
x
10
=
0.231
,
x
20
=
0.356
) in 2D space. Each point in Figure 1 can be described by (
x
1
j
,
x
2
j
)
,
j
=
1,2
,
…
,
1500.Figure 1
Distribution of the chaos variables.The chaotic dynamic is used for initialization, which can be described as follows.Using the tent map (μ
=
1) to generate the chaos variables and rewriting (3) give(4)
z
j
i
+
1
=
μ
1
-
2
z
j
i
-
0.5
,
j
=
1,2
,
…
,
D
,where z
j denotes the jth chaos variable and i denotes the chaos iteration number. Set i
=
0 and generate D chaos variables by (4). After that, let i
=
1,2
,
…
,
N in turn and generate the initial swarm. Then, the chaos variable above z
j
(
i
)
,
i
=
1,2
,
…
,
N, will be mapped into the search range of the decision variable:(5)
x
i
j
=
x
m
i
n
,
j
+
z
j
i
x
m
a
x
,
j
-
x
m
i
n
,
j
,
j
=
1,2
,
…
,
D
.Defining (6)
x
i
=
x
i
1
,
x
i
2
,
…
,
x
i
D
,
i
=
1,2
,
…
,
N
,the chaotic initialized swarm can be obtained.According to the chaotic search, a chaotic disturbance can be added as follows:(7)
z
′
=
1
-
γ
ψ
∗
+
γ
z
,where γ is a parameter that falls in [
0
,
1
], z
′
=
(
z
1
′
,
z
2
′
,
…
,
z
D
′
) is the chaos vector where the disturbance has been added, and ψ
∗ is the optimal chaos vector where the current optima x
∗
=
(
x
1
∗
,
x
2
∗
,
…
,
x
D
∗
) are mapped into the interval [
0
,
1
]:(8)
ψ
∗
=
x
∗
-
x
m
i
n
x
m
a
x
-
x
m
i
n
.The Chaotic PSO algorithm is described as follows.Step 1.
Initialize the swarm (k
=
0) by the abovementioned chaotic initialization method according to (4)–(6).Step 2.
Evaluate the fitnessf
i and update p
i and l
b
e
s
t
i if needed.Step 3.
Update the velocityv
i and position x
i of the particle by (1) and (2), respectively.Step 4.
Rank the swarm by fitness in an ascending order. If the current iterationk
≤
(
1
/
2
)
k
m
a
x and the current optimum f
(
p
i
) stays the same for several iterations, go to Step 5; otherwise, turn to Step 6.Step 5.
Introduce the chaotic disturbance to update the best particle. Add a chaotic disturbance to the bottom 30% of particles in the swarm by (7), and, then, map them into the decision variables by (5). Rerank the swarm by fitness and find out the new best particle.Step 6.
If a stopping criterion is satisfied, stop; otherwise, letk
=
k
+
1 and go back to Step 2.


## 2.2. Benchmark Function Tests

In order to test the performance of the proposed Chaotic PSO algorithm, minimization problems of four multimodal functions [30, 31], the Ellipsoidal function (f
1), the Rosenbrock function (f
2), the generalized Griewank function (f
3), and Rastrigin’s function (f
4), are introduced for simulation tests:(9)
f
1
x
=
∑
i
=
1
D
i
x
i
2
,
-
100
≤
x
i
≤
100
,
f
2
x
=
∑
i
=
1
D
-
1
100
x
i
+
1
-
x
i
2
2
+
x
i
-
1
2
,
-
30
≤
x
i
≤
30
,
f
3
x
=
1
4000
∑
i
=
1
D
x
i
2
-
∏
i
=
1
D
c
o
s
x
i
i
+
1
,
-
600
≤
x
i
≤
600
,
f
4
x
=
∑
i
=
1
D
x
i
2
-
10
cos
⁡
2
π
x
i
+
10
,
-
5.12
≤
x
i
≤
5.12
.For both functions, the parameters are fixed as m
=
20
,
k
m
a
x
=
1500. The fitness value is set as the function value. The standard PSO, PSO with mutation (MPSO) [32], and GA are introduced here for comparison tests. For each function, different dimensions (10, 20, and 30) are tested. c
1
=
c
2
=
2, and ω is fixed as 0.5 for all PSO algorithms. The GA is real code, crossover probability p
c
=
0.8, and mutation probability p
m
=
0.1. Table 1 lists the mean minimum of 50 independent runs.Table 1
Comparison results of mean fitness forf
1 and f
2.
f
D
Algorithms
PSO
MPSO
Chaotic PSO
GA
f
1
10
5.49
E
-
28
3.67
E
-
29
2.63
E
-
29
6.81
E
-
03
20
3.28
E
-
28
5.64
E
-
30
2.152
E
-
33
3.12
E
-
03
30
8.26
E
-
27
6.28
E
-
33
8.20
E
-
33
0.0582
f
2
10
24.3651
11.5834
4.3021
35.6902
20
66.2781
17.6590
15.0153
84.6521
30
268.1459
96.4923
80.2643
329.5826
f
3
10
0.0812
0.0538
0.0237
0.0953
20
0.0350
0.0031
1.1506
E
-
6
0.0767
30
0.0218
5.2311
E
-
5
1.3451
E
-
7
0.0388
f
4
10
6.432
3.6253
2.463
2.329
20
12.325
8.7524
7.6038
23.3028
30
21.632
17.849
12.168
48.943From Table1, it can be seen that the proposed Chaotic PSO has better accuracy and is superior to other optimization algorithms in terms of the searching solutions.


## 3. Application in Parking Space Guidance

In this research, there are several assumptions about the workspace of the parking lots:(1)
Vehicles move in a limited two-dimensional space.
(2)
The paths in parking lots are equivalent to “straight line” and a vehicle is equivalent to a “particle.”
(3)
It is assumed that there is one entry and one exit, with several free parking stalls. The weight of side corresponds to the length between two continuous points. All the points are numbered from 1 ton. The issue about parking guidance is to find a collection of points P
=
{
S
,
p
1
,
p
2
,
…
,
p
n
,
G
}, where S stands for the starting point and G for the ending point; P
=
{
p
1
,
p
2
,
…
,
p
n
} is a sequence of points, named planning target. There are some requests to p
i. Firstly, p
i is a nonbarrier point. Secondly, there are no barrier points on the line connecting p
i and its adjacent point.


### 3.1. Problem Description

Let us consider a route networkL
(
Q
,
E
), where Q is the set of parking stalls and E is the set of edges. Each edge is represented by (
i
,
j
), where i
,
j
∈
Q and i is the starting node and j is its adjacent node. The paths should be found from the source s to the destination node d. Any path is represented by P
t
=
{
(
s
,
i
)
,
(
i
,
j
)
,
…
,
(
q
,
d
)
}
,
(
s
,
i
)
,
(
i
,
j
)
,
…
,
(
q
,
d
)
∈
E and s
,
i
,
j
,
…
,
q
,
d
∈
Q. In the proposed work here, each edge (i
,
j) is associated with one parameter l
(
i
,
j
), which represents the average length for the vehicle to travel on the edge (i
,
j).The route optimization problem in the parking lots can be then defined as(10)
m
i
n
i
m
i
z
e
∑
i
,
j
∈
P
t
l
i
,
j
.


### 3.2. Proposed Chaotic Optimization Algorithm for Parking Space Guidance

Let us consider a swarm ofN particles which is represented by (11)
S
m
=
P
1
,
P
2
,
P
3
,
…
,
P
N
.Any particle P
i
∈
S
m, for i
=
1 to N, is similar to P
t which was described in the previous subsection.The proposed work assumes anm-dimensional search space represented by R
m, where m is the total number of the parking points. The objective function value of any particle (P
i) can be determined by using the following formula: (12)
O
b
j
P
i
=
∑
j
=
0
m
-
2
l
p
j
,
p
j
+
1
. (p
j, p
j
+
1) represents an edge e
x
∈
E, whose starting node is p
j and ending node is p
j
+
1. In PSO, the positions of particles change iteratively during the optimization process by adding the velocities into their current positions. The velocity of any particle (P
i) at time or iteration t is represented as v
P
i
(
t
). The particles’ velocities are also updated iteratively. In PSO, the best position of any particle can be decided by (13)
arg
⁡
min
k
⁡
O
b
j
P
i
k
,where k represents the iteration count. The global best position (
k
) can be obtained as(14)
g
b
e
s
t
k
=
a
r
g
m
i
n
k
p
b
e
s
t
P
i
k
,
for
i
=
1,2
,
…
,
N
.In thekth iteration, the velocity of each particle for the next iteration k
+
1 can be calculated as (15)
v
P
i
k
+
1
=
w
v
P
i
k
+
c
1
r
1
p
b
e
s
t
P
i
k
-
P
i
k
+
c
2
r
2
g
b
e
s
t
k
-
P
i
k
,
for
i
=
1,2
,
…
,
N
.
c
1 and c
2 are real numbers between [
0
,
2
]. r
1 and r
2 are randomly generated real numbers between [
0
,
1
].The calculation of the velocities here is a little different from the traditional PSO, and it involves the notion of the difference between two particles. The method proposed to find the difference between any two particles,P
1
(
x
0
,
x
1
,
…
,
x
m
-
1
) and P
2
(
y
0
,
y
1
,
…
,
y
m
-
1
), is shown in Algorithm 1. The idea behind the proposed method is that it returns the number of nodes which exist in the particle P
1 but do not exist in the particle P
2.Algorithm 1:Pseudocode of the proposed method to find the difference between any two particles.
Input: Particles:P
1
(
x
0
,
x
1
,
…
,
x
m
-
1
) and P
2
(
y
0
,
y
1
,
…
,
y
m
-
1
)
Output:P
1
-
P
2
=
d
∈
I
n
t
e
g
e
r
s
(1)c
n
t
=
0, n
=
0
(2) fori
=
0; i
<
m
-
1; i++
(3)  forj
=
0; j
<
m
-
1; j++
(4)    ifx
i
=
=
y
j then
(5)c
n
t
=
c
n
t
+
1
(6)    end if
(7)  end for
(8)  ifc
n
t
=
=
0 then
(9)n++
(10)  end if
(11) end for
(12) returnnNow we know that, in the proposed approach, the velocity of the particle for the next iteration which is represented byv
P
i
k
+
1 is a positive real number. And after the velocities are determined, they will be used to update the particles’ positions.In the application of parking guidance here, the chaotic dynamics is mainly used to do the selection, and, thus, the scheme of chaotic selection is proposed, which can be described in the following process:(i)
Firstly, suppose the searching range is[
I
,
J
]
(
I
<
J
) and the aim is to generate one random round number in that range.
(ii)
Then, run the chaotic map once and get one chaos variablez by (4).
(iii)
Map the chaos variable into the range of the decision variable, which is [I
,
J] in this case, and get the variable x by (5).
(iv)
At last, get the round value ofx, and complete the chaotic selection for once.This work combines the chaotic selection scheme into the position updating rules and the proposed method of updating the particles is shown in Figure2. The inputs are P
i
(
k
), which is the position of the particle in the iteration k, v
P
i
(
k
+
1
) or just v
P
i, which is the velocity of the particle in the k
+
1th iteration, and N
m
∈
Z
+, which is usually predetermined. The flowchart assumes that m is the number of nonnull elements in any particle. The objective function is determined by calling the function O
b
j
(
) and O
b
j
(
P
)
=
∞ when P
=
n
u
l
l.Figure 2
Flowchart of the proposed chaotic optimization algorithm for parking space guidance.In each iteration, an element is selected by using the chaotic map fromP
i
(
k
) and storing it in p
R. Then, the function form_path
(
) is called, to build at-most N
m number of paths from p
R to the destination node. The paths are stored in the array Path
[
]. The inner loop is executed for each path in the array Path
[
]. The paths in Path
[
] exist from the node p
R to the destination node. C
m is a preset vector that controls how many newly formed paths should be evaluated for P
i. P
f contains the portion of P
i
(
k
) from its first element to the Rth position. P
b contains the path which is at the qth position in Path
[
], while q is a positive integer that is generated through chaotic mapping. The path Tem is the concatenation of the P
f and P
b paths. The variable I
b
e
s
t stores the position (or path) which has minimum value of the objective function among all the positions built in the inner loop. The last portion of the flowchart returns the position of P
i for the k
+
1th iteration which is represented by P
i
(
k
+
1
).


## 3.1. Problem Description

Let us consider a route networkL
(
Q
,
E
), where Q is the set of parking stalls and E is the set of edges. Each edge is represented by (
i
,
j
), where i
,
j
∈
Q and i is the starting node and j is its adjacent node. The paths should be found from the source s to the destination node d. Any path is represented by P
t
=
{
(
s
,
i
)
,
(
i
,
j
)
,
…
,
(
q
,
d
)
}
,
(
s
,
i
)
,
(
i
,
j
)
,
…
,
(
q
,
d
)
∈
E and s
,
i
,
j
,
…
,
q
,
d
∈
Q. In the proposed work here, each edge (i
,
j) is associated with one parameter l
(
i
,
j
), which represents the average length for the vehicle to travel on the edge (i
,
j).The route optimization problem in the parking lots can be then defined as(10)
m
i
n
i
m
i
z
e
∑
i
,
j
∈
P
t
l
i
,
j
.


## 3.2. Proposed Chaotic Optimization Algorithm for Parking Space Guidance

Let us consider a swarm ofN particles which is represented by (11)
S
m
=
P
1
,
P
2
,
P
3
,
…
,
P
N
.Any particle P
i
∈
S
m, for i
=
1 to N, is similar to P
t which was described in the previous subsection.The proposed work assumes anm-dimensional search space represented by R
m, where m is the total number of the parking points. The objective function value of any particle (P
i) can be determined by using the following formula: (12)
O
b
j
P
i
=
∑
j
=
0
m
-
2
l
p
j
,
p
j
+
1
. (p
j, p
j
+
1) represents an edge e
x
∈
E, whose starting node is p
j and ending node is p
j
+
1. In PSO, the positions of particles change iteratively during the optimization process by adding the velocities into their current positions. The velocity of any particle (P
i) at time or iteration t is represented as v
P
i
(
t
). The particles’ velocities are also updated iteratively. In PSO, the best position of any particle can be decided by (13)
arg
⁡
min
k
⁡
O
b
j
P
i
k
,where k represents the iteration count. The global best position (
k
) can be obtained as(14)
g
b
e
s
t
k
=
a
r
g
m
i
n
k
p
b
e
s
t
P
i
k
,
for
i
=
1,2
,
…
,
N
.In thekth iteration, the velocity of each particle for the next iteration k
+
1 can be calculated as (15)
v
P
i
k
+
1
=
w
v
P
i
k
+
c
1
r
1
p
b
e
s
t
P
i
k
-
P
i
k
+
c
2
r
2
g
b
e
s
t
k
-
P
i
k
,
for
i
=
1,2
,
…
,
N
.
c
1 and c
2 are real numbers between [
0
,
2
]. r
1 and r
2 are randomly generated real numbers between [
0
,
1
].The calculation of the velocities here is a little different from the traditional PSO, and it involves the notion of the difference between two particles. The method proposed to find the difference between any two particles,P
1
(
x
0
,
x
1
,
…
,
x
m
-
1
) and P
2
(
y
0
,
y
1
,
…
,
y
m
-
1
), is shown in Algorithm 1. The idea behind the proposed method is that it returns the number of nodes which exist in the particle P
1 but do not exist in the particle P
2.Algorithm 1:Pseudocode of the proposed method to find the difference between any two particles.
Input: Particles:P
1
(
x
0
,
x
1
,
…
,
x
m
-
1
) and P
2
(
y
0
,
y
1
,
…
,
y
m
-
1
)
Output:P
1
-
P
2
=
d
∈
I
n
t
e
g
e
r
s
(1)c
n
t
=
0, n
=
0
(2) fori
=
0; i
<
m
-
1; i++
(3)  forj
=
0; j
<
m
-
1; j++
(4)    ifx
i
=
=
y
j then
(5)c
n
t
=
c
n
t
+
1
(6)    end if
(7)  end for
(8)  ifc
n
t
=
=
0 then
(9)n++
(10)  end if
(11) end for
(12) returnnNow we know that, in the proposed approach, the velocity of the particle for the next iteration which is represented byv
P
i
k
+
1 is a positive real number. And after the velocities are determined, they will be used to update the particles’ positions.In the application of parking guidance here, the chaotic dynamics is mainly used to do the selection, and, thus, the scheme of chaotic selection is proposed, which can be described in the following process:(i)
Firstly, suppose the searching range is[
I
,
J
]
(
I
<
J
) and the aim is to generate one random round number in that range.
(ii)
Then, run the chaotic map once and get one chaos variablez by (4).
(iii)
Map the chaos variable into the range of the decision variable, which is [I
,
J] in this case, and get the variable x by (5).
(iv)
At last, get the round value ofx, and complete the chaotic selection for once.This work combines the chaotic selection scheme into the position updating rules and the proposed method of updating the particles is shown in Figure2. The inputs are P
i
(
k
), which is the position of the particle in the iteration k, v
P
i
(
k
+
1
) or just v
P
i, which is the velocity of the particle in the k
+
1th iteration, and N
m
∈
Z
+, which is usually predetermined. The flowchart assumes that m is the number of nonnull elements in any particle. The objective function is determined by calling the function O
b
j
(
) and O
b
j
(
P
)
=
∞ when P
=
n
u
l
l.Figure 2
Flowchart of the proposed chaotic optimization algorithm for parking space guidance.In each iteration, an element is selected by using the chaotic map fromP
i
(
k
) and storing it in p
R. Then, the function form_path
(
) is called, to build at-most N
m number of paths from p
R to the destination node. The paths are stored in the array Path
[
]. The inner loop is executed for each path in the array Path
[
]. The paths in Path
[
] exist from the node p
R to the destination node. C
m is a preset vector that controls how many newly formed paths should be evaluated for P
i. P
f contains the portion of P
i
(
k
) from its first element to the Rth position. P
b contains the path which is at the qth position in Path
[
], while q is a positive integer that is generated through chaotic mapping. The path Tem is the concatenation of the P
f and P
b paths. The variable I
b
e
s
t stores the position (or path) which has minimum value of the objective function among all the positions built in the inner loop. The last portion of the flowchart returns the position of P
i for the k
+
1th iteration which is represented by P
i
(
k
+
1
).


## 4. Simulation Analysis

In order to test the performance of the proposed methodology, a route optimization problem based on a real parking lot (shown in Figure3) is introduced for analyzing. Each parking stall has a pilot light to indicate whether this parking stall is available. As shown in Figure 3, there is one light for each stall, and when the light is on (white), it means this stall is still available, and when it is off (black), it means it is occupied. In order to facilitate the simulation test, a relatively simple parking structure is chosen here. There are one entrance and one exit for this parking lot and four blocks connected by five two-lane roads. Each block has six parking stalls. To make it more flexible, four extensible nodes are designed at the ends of the roads, denoted as P, Q, M, and N, which means they can lead to other parking areas. The simulation tests are done based on the 24-stall parking area as shown in Figure 3, and P, Q, M, and N are treated as four return points. To make it clear and easier for analysis, a sketch map is given in Figure 4.Figure 3
A 24-stall parking area.Figure 4
Sketch map of the 24-stall parking area.In the sketch, all the parking stalls and the crosses are marked by numbers and the objective is to find the shorted path from the entrance to the assigned parking stall and then to the exit. There are several assumptions:(i)
All the information of the parking lot (number and the exact locations of the parking stalls that are available) is saved on a server and real-time data can be obtained when a car comes.
(ii)
An available parking stall is assigned randomly at each time.
(iii)
The distance from one node to its adjacent node is fixed previously and is irrelevant to the nodes’ locations.The focus here is the shortest distance for a car to drive in the parking lot, which includes two parts: one is the distance from the entrance to the parking stall, and the other is the distance from the parking stall to the exit.The proposed Chaotic PSO is used for the path optimization and each particle stands for a path. Assume the parking stall number 10 is chosen at this moment, examples of the drive-in and drive-out particles can be illustrated in Figure5. Thus, the fitness function can be written as follows:(16)
J
=
m
i
n
∑
j
l
p
j
,
p
j
+
1
+
∑
h
l
p
h
,
p
h
+
1
,where l
(
a
,
b
) represents the average length for the vehicle to travel on the edge (a
,
b) and ∑
j stands for the total distance from the entrance to the chosen parking stall, while ∑
h stands for the total distance from the chosen stall to the exit. For each car entering this parking lot, once an available parking stall is assigned, run the chaotic optimization algorithm proposed above twice, to get the optimized paths to drive in from the entrance to the assigned parking stall and to drive out from the parking stall to the exit. And the complete optimized path from the entrance to the exit can be obtained by joining the two optimized paths together.Figure 5
Format of the particles.
(a)
The drive-in particle which ends at 10
(b)
The drive-out particle which starts at 10In order to test the performance of the proposed method, standard PSO and GA are introduced for comparison. They are used to search for the shortest path in the space of all the possible paths passing through a given parking stall. All the trial tests are coded in MATLAB and executed independently on a Genuine Intel 3.0 GHz CPU with a 4 G RAM desktop computer. A performance index function is introduced for comparison of different route optimization methods in terms of the effectiveness:(17)
E
=
l
m
i
n
_
i
n
+
l
m
i
n
_
o
u
t
∑
j
l
p
j
,
p
j
+
1
+
∑
h
l
p
h
,
p
h
+
1
,where l
m
i
n
_
i
n and l
m
i
n
_
o
u
t stand for the actual shortest distance from the entrance to the given parking stall and from the parking stall to the exit, while ∑
j and ∑
h stand for the corresponding distances of the optimized paths calculated by the optimization methods. Thus, 0
<
E
⩽
1, and when the route optimization algorithm gives the shortest path, E
=
1; otherwise, E will be a number between 0 and 1. The bigger E is, the better the optimized route is, which also means the corresponding route optimization method is more effective. All the simulation tests have been conducted based on the sketch map shown in Figure 4. Most of the distances between two adjacent parking stalls (noted as l
(
p
j
,
p
j
+
1
)) are fixed as 1 in the simulation tests, except for five special ones, which are fixed as l
(
S
,
1
)
=
3, l
(
19
,
G
)
=
3, l
(
7,13
)
=
2, l
(
9,15
)
=
2, and l
(
12,18
)
=
2. The distances can also be decided in other ways based on different situations when applying the path optimization method to other parking lots.Different parking stalls are assigned each time for simulation tests. GA, PSO, and our proposed method are applied independently to solve the same problem. Each method ran 30 independent trials to get the mean value ofE and its corresponding standard deviation. All data of different methods has been recorded and analyzed, and the comparison results of each test are reported in Tables 2–5. The optimized paths for different given parking stalls, which are obtained by the proposed Chaotic Particle Swarm Optimization method, are shown in Figures 6–9.Table 2
Comparison results of different methods for the given stall number 8 within 5 seconds out of 30 independent runs.
Methods
Performances
The meanE
Standard deviation
Successful rate∗ (%)
GA
0.942
0.103
66.67
PSO
0.958
9.44
E
-
02
76.67
Proposed method
1.00
0.00
100
∗Success rate means how many times that the actual shortest path can be found successfully during 30 runs.Table 3
Comparison results of different methods for the given stall number 17 within 5 seconds out of 30 independent runs.
Methods
Performances
The meanE
Standard deviation
Successful rate∗ (%)
GA
0.957
8.91
E
-
02
80.00
PSO
0.953
8.79
E
-
02
76.67
Proposed method
1.00
0.00
100
∗Success rate means how many times that the actual shortest path can be found successfully during 30 runs.Table 4
Comparison results of different methods for the given stall number 12 within 5 seconds out of 30 independent runs.
Methods
Performances
The meanE
Standard deviation
Successful rate∗ (%)
GA
0.964
8.33
E
-
02
83.33
PSO
0.978
5.67
E
-
02
86.67
Proposed method
1.00
0.00
100
∗Success rate means how many times that the actual shortest path can be found successfully during 30 runs.Table 5
Comparison results of different methods for the given stall number 4 within 5 seconds out of 30 independent runs.
Methods
Performances
The meanE
Standard deviation
Successful rate∗ (%)
GA
0.893
1.196
56.67
PSO
0.916
1.083
60.00
Proposed method
0.984
5.97
E
-
02
93.33
∗Success rate means how many times that the actual shortest path can be found successfully during 30 runs.Figure 6
The optimized route obtained by the proposed method for the given parking stall number 8.Figure 7
The optimized route obtained by the proposed method for the given parking stall number 17.Figure 8
The optimized route obtained by the proposed method for the given parking stall number 12.Figure 9
The optimized route obtained by the proposed method for the given parking stall number 4.From the comparison results shown in Tables2–5, it can be seen obviously that the proposed Chaotic PSO method gets much higher successful rate (mostly 100%) and can get the most optimized route within 5 seconds, which is quite satisfying and eligible for practical use. It can be concluded that the proposed method is more effective than the other two optimization methods and is a fast and reliable way to solve the route optimization problem of parking lots.In order to further test the proposed optimization method’s capability of handling more complex RO problems of parking lots, a larger size instance with 96 stalls (Figure10) is introduced for analyzing. Its sketch map is given in Figure 11. Parking stalls numbers 28, 82, and 56 are assigned for simulation tests. The optimized paths for different given parking stalls, which are obtained by the proposed Chaotic Particle Swarm Optimization method, are given in Figures 12–14. 30 independent trails have been run for each given stall and the average time to find the shortest paths has been recorded. For stall number 28, the average time of 30 trails is 3.276 seconds, and the optimized path is shown in Figure 12. For stalls numbers 82 and 56, the shortest paths are not unique, and here we set the algorithm to find the first three different shortest paths for each given stall. The average run time for stall number 82 is 6.732 seconds and the three shortest paths found by a single trail are given in Figure 13. For stall number 56, the average run time is 6.150 seconds and the corresponding results are shown in Figure 14.Figure 10
A 96-stall parking area.Figure 11
Sketch map of the 96-stall parking area.Figure 12
The optimized route obtained by the proposed method for the given parking stall number 28.Figure 13
The optimized route obtained by the proposed method for the given parking stall number 82.
(a)
(b)
(c)Figure 14
The optimized route obtained by the proposed method for the given parking stall number 56.
(a)
(b)
(c)The simulation results above showed that the newly proposed optimization method can successfully find out the shortest paths within an acceptable time, and, thus, the capability and effectiveness of our proposed methodology handling RO problems of parking lots under more complex circumstances have been fully illustrated.


## 5. Conclusions

This paper presents a Chaotic PSO-based route optimization method for parking guidance. The proposed method has successfully solved the route optimization problems based upon real parking lots. The first experimental results show that the proposed algorithm can successfully find the optimized route for a randomly given parking stall within 5 seconds, and with a much higher successful rate than using other approaches, which is more than 90% in all runs. Most importantly, better stability has been achieved using the proposed Chaotic PSO-based route optimization method as the standard errors ofE were 0 in most cases and are much smaller comparing with the other two approaches. The second simulation test shows the capability and effectiveness of our proposed chaotic methodology handling more complex RO problems of parking lots. The capability and applicability of the proposed method have been fully illustrated through all the simulation results. The Chaotic PSO-based approach in the area of parking guidance is still untapped; hence, our future research will aim at investigating more possible applications in some more complicated and large-scale parking lots.



---

*Source: 5126808-2016-09-21.xml*