A Novel Chaotic Particle Swarm Optimization Algorithm for Parking Space Guidance

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.

Na Dong 1 and Xing Fang 2 and Ai-guo Wu 1

Academic Editor:George S. Dulikravich

1, School of Electrical Engineering and Automation, Tianjin University, Tianjin 300072, China

2, Key Laboratory of Advanced Process Control for Light Industry of the Ministry of Education, School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, China

Received 5 March 2016; Revised 21 July 2016; Accepted 26 July 2016

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 [low *]} and Dijkstra algorithms, ^{A [low *]} 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 in D -dimensional problem space with a velocity, which is adjusted at each time step. The movement of i th 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 _{[straight phi] 1} and _{[straight phi] 2} are two uniform random numbers from U ( 0 , 1 ) : [figure omitted; refer to PDF] 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 [figure omitted; refer to PDF] 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.

[figure omitted; refer to PDF]

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 [figure omitted; refer to PDF] where _{z j} denotes the j th 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: [figure omitted; refer to PDF] Defining [figure omitted; refer to PDF] the chaotic initialized swarm can be obtained.

According to the chaotic search, a chaotic disturbance can be added as follows: [figure omitted; refer to PDF] where γ is a parameter that falls in [ 0 , 1 ] , ^{z [variant prime]} = ( ^{z 1 [variant prime]} , ^{z 2 [variant prime]} , ... , ^{z D [variant prime]} ) is the chaos vector where the disturbance has been added, and ^{ψ [low *]} is the optimal chaos vector where the current optima ^{x [low *]} = ( ^{x 1 [low *]} , ^{x 2 [low *]} , ... , ^{x D [low *]} ) are mapped into the interval [ 0 , 1 ] : [figure omitted; refer to PDF] 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 fitness _{f i} and update _{p i} and l b e s _{t i} if needed.

Step 3.

Update the velocity _{v 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 iteration k <= ( 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, let k = 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: [figure omitted; refer to PDF] 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 for _{f 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.943

From Table 1, 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 to n . 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 network L ( 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 [figure omitted; refer to PDF]

3.2. Proposed Chaotic Optimization Algorithm for Parking Space Guidance

Let us consider a swarm of N particles which is represented by [figure omitted; refer to PDF] 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 an m -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: [figure omitted; refer to PDF] ( _{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 [figure omitted; refer to PDF] where k represents the iteration count. The global best position ( k ) can be obtained as [figure omitted; refer to PDF]

In the k th iteration, the velocity of each particle for the next iteration k + 1 can be calculated as [figure omitted; refer to PDF] _{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) for i = 0 ; i < m - 1 ; i ++

(3) for j = 0 ; j < m - 1 ; j ++

(4) if _{x i} = = _{y j} then

(5) c n t = c n t + 1

(6) end if

(7) end for

(8) if c n t = = 0 then

(9) n ++

(10) end if

(11) end for

(12) return n

Now we know that, in the proposed approach, the velocity of the particle for the next iteration which is represented by _{v 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 variable z 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 of x , 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 Figure 2. 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 + 1 ) th 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.

[figure omitted; refer to PDF]

In each iteration, an element is selected by using the chaotic map from _{P 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 R th position. _{P b} contains the path which is at the q th 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 + 1 ) th 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 Figure 3) 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 omitted; refer to PDF]

Figure 4: Sketch map of the 24-stall parking area.

[figure omitted; refer to PDF]

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 Figure 5. Thus, the fitness function can be written as follows: [figure omitted; refer to PDF] 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

[figure omitted; refer to PDF]

(b) The drive-out particle which starts at 10

[figure omitted; refer to PDF]

In 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: [figure omitted; refer to PDF] 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 [= or <, slanted] 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 of E 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 mean E	Standard deviation	Successful rate [low *] (%)
GA	0.942	0.103	66.67
PSO	0.958	9.44 E - 02	76.67
Proposed method	1.00	0.00	100

^{[low *]} 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 mean E	Standard deviation	Successful rate [low *] (%)
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

^{[low *]} 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 mean E	Standard deviation	Successful rate [low *] (%)
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

^{[low *]} 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 mean E	Standard deviation	Successful rate [low *] (%)
GA	0.893	1.196	56.67
PSO	0.916	1.083	60.00
Proposed method	0.984	5.97 E - 02	93.33

^{[low *]} 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 omitted; refer to PDF]

Figure 7: The optimized route obtained by the proposed method for the given parking stall number 17.

[figure omitted; refer to PDF]

Figure 8: The optimized route obtained by the proposed method for the given parking stall number 12.

[figure omitted; refer to PDF]

Figure 9: The optimized route obtained by the proposed method for the given parking stall number 4.

[figure omitted; refer to PDF]

From the comparison results shown in Tables 2-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 (Figure 10) 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 omitted; refer to PDF]

Figure 11: Sketch map of the 96-stall parking area.

[figure omitted; refer to PDF]

Figure 12: The optimized route obtained by the proposed method for the given parking stall number 28.

[figure omitted; refer to PDF]

Figure 13: The optimized route obtained by the proposed method for the given parking stall number 82.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

Figure 14: The optimized route obtained by the proposed method for the given parking stall number 56.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

(c) [figure omitted; refer to PDF]

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 of E 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.

Acknowledgments

This work is supported by the Natural Science Foundation of China under Grant nos. 61403274 and 61473203 and the Application Base and Frontier Technology Research Project of Tianjin of China under 13JCQNJC03600.

References

[1] Z. Y. Mei, Y. Tian, "Optimized combination model and algorithm of parking guidance information configuration," EURASIP Journal on Wireless Communications and Networking , vol. 2011, article 104, 2011.

[2] R. G. Thompson, K. Takada, S. Kobayakawa, "Optimisation of parking guidance and information systems display configurations," Transportation Research Part C: Emerging Technologies , vol. 9, no. 1, pp. 69-85, 2001.

[3] C.-K. Lee, C.-L. Lin, B.-M. Shiu, "Autonomous vehicle parking using hybrid artificial intelligent approach," Journal of Intelligent and Robotic Systems: Theory and Applications , vol. 56, no. 3, pp. 319-343, 2009.

[4] E. L. Lawler Combinatorial Optimization: Networks and Matroids , Holt, Rinehart, and Winston, New York, NY, USA, 1976.

[5] A. W. Mohemmed, N. C. Sahoo, T. K. Geok, "Solving shortest path problem using particle swarm optimization," Applied Soft Computing Journal , vol. 8, no. 4, pp. 1643-1653, 2008.

[6] Q. Song, X. F. Wang, "Survey of speedup techniques for shortest path algorithms," Journal of University of Electronic Science and Technology of China , vol. 41, pp. 176-184, 2012.

[7] L. Fu, D. Sun, L. R. Rilett, "Heuristic shortest path algorithms for transportation applications: state of the art," Computers & Operations Research , vol. 33, no. 11, pp. 3324-3343, 2006.

[8] B. V. Cherkassky, A. V. Goldberg, T. Radzik, "Shortest paths algorithms: theory and experimental evaluation," Mathematical Programming , vol. 73, no. 2, pp. 129-174, 1996.

[9] M. K. Mehmet Ali, F. Kamoun, "Neural networks for shortest path computation and routing in computer networks," IEEE Transactions on Neural Networks , vol. 4, no. 6, pp. 941-954, 1993.

[10] F. Araújo, B. Ribeiro, L. Rodrigues, "A neural network for shortest path computation," IEEE Transactions on Neural Networks , vol. 12, no. 5, pp. 1067-1073, 2001.

[11] C.-W. Ahn, R. S. Ramakrishna, "A genetic algorithm for shortest path routing problem and the sizing of populations," IEEE Transactions on Evolutionary Computation , vol. 6, no. 6, pp. 566-579, 2002.

[12] G. R. Raidl, B. A. Julstrom, "A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem," in Proceedings of the ACM Symposium on Applied Computing (SAC '00), pp. 440-445, March 2000.

[13] Z. Fu, A. Kurnia, A. Lim, B. Rodrigues, "Shortest path problem with cache dependent path lengths," in Proceedings of the Congress on Evolutionary Computation, pp. 2756-2761, Canberra, Australia, 2003.

[14] J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, "Routing foreseeable light path demands using a tabu search meta-heuristic," in Proceedings of the IEEE Global Telecommunication Conference (GLOBECOM '02), pp. 2803-2807, Taipei, Taiwan, March 2003.

[15] J. Kennedy, R. Eberhart, "Particle swarm optimization," in Proceedings of the IEEE International Conference on Neural Network (ICNN '93), pp. 1942-1948, Perth, Australia, 1995.

[16] T.-H. Sun, "Applying particle swarm optimization algorithm to roundness measurement," Expert Systems with Applications , vol. 36, no. 2, pp. 3428-3438, 2009.

[17] M. Omran, A. P. Engelbrecht, A. Salman, "Particle swarm optimization method for image clustering," International Journal of Pattern Recognition and Artificial Intelligence , vol. 19, no. 3, pp. 297-321, 2005.

[18] P. J. Angeline, "Evolutionary optimization versus particle swarm optimization: philosophy and performance differences," Evolutionary Programming VII: 7th International Conference, EP98 San Diego, California, USA, March 25-27, 1998 Proceedings , vol. 1447, of Lecture Notes in Computer Science, pp. 601-610, Springer, Berlin, Germany, 1998.

[19] K.-W. Wong, B. S.-H. Kwok, W.-S. Law, "A fast image encryption scheme based on chaotic standard map," Physics Letters A , vol. 372, no. 15, pp. 2645-2652, 2008.

[20] C.-M. Ou, "Design of block ciphers by simple chaotic functions," IEEE Computational Intelligence Magazine , vol. 3, no. 2, pp. 54-59, 2008.

[21] B. Li, W. Jiang, "Optimizing complex functions by chaos search," Cybernetics and Systems , vol. 29, no. 4, pp. 409-419, 1998.

[22] J. A. Koupaei, S. Hosseini, F. M. Ghaini, "A new optimization algorithm based on chaotic maps and golden section search method," Engineering Applications of Artificial Intelligence , vol. 50, pp. 201-214, 2016.

[23] L. D. S. Coelho, "Reliability-redundancy optimization by means of a chaotic differential evolution approach," Chaos, Solitons and Fractals , vol. 41, no. 2, pp. 594-602, 2009.

[24] B. Liu, L. Wang, Y.-H. Jin, F. Tang, D.-X. Huang, "Improved particle swarm optimization combined with chaos," Chaos, Solitons and Fractals , vol. 25, no. 5, pp. 1261-1271, 2005.

[25] M. Bucolo, R. Caponetto, L. Fortuna, M. Frasca, A. Rizzo, "Does chaos work better than noise?," IEEE Circuits and Systems Magazine , vol. 2, no. 3, pp. 4-19, 2002.

[26] X.-F. Xie, W.-J. Zhang, Z.-L. Yang, "A dissipative particle swarm optimization," in Proceedings of the Congress on Evolutionary Computation (CEC '02), pp. 1456-1461, May 2002.

[27] B. Liu, L. Wang, Y.-H. Jin, F. Tang, D.-X. Huang, "Improved particle swarm optimization combined with chaos," Chaos, Solitons & Fractals , vol. 25, no. 5, pp. 1261-1271, 2005.

[28] P. Chauhan, M. Pant, K. Deep, "Parameter optimization of multi-pass turning using chaotic PSO," International Journal of Machine Learning and Cybernetics , vol. 6, no. 2, pp. 319-337, 2015.

[29] H. Zhang, J.-H. Shen, T.-N. Zhang, L. Yang, "An improved chaotic particle swarm optimization and its application in investment," in Proceedings of the International Symposium on Computational Intelligence and Design (ISCID '08), pp. 124-128, Wuhan, China, October 2008.

[30] J. Kennedy, R. C. Eberhart, "Particle swarm optimization," in Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948, Perth, Western Australia, 1995.

[31] X. D. Li, A. Engelbrecht, M. G. Epitropakis, "Benchmark functions for CEC'2013 special session and competition on niching methods for multimodal function optimization,", Evolutionary Computation and Machine Learning Group, RMIT University, Melbourne, Australia, 2013.

[32] A. Stacey, M. Jancic, I. Grundy, "Particle swarm optimization with mutation," in Proceedings of the Congress on Evolutionary Computation (CEC '03), vol. 2, pp. 1425-1430, IEEE, December 2003.