Open access peer-reviewed chapter

Dynamic Street Parking Space Using Memetic Algorithm for Optimization

Written By

Stephen Akandwanaho and Irene Govender

Submitted: March 23rd, 2019 Reviewed: March 25th, 2019 Published: May 13th, 2019

DOI: 10.5772/intechopen.86010

Chapter metrics overview

957 Chapter Downloads

View Full Metrics


In recent years, there have been an increasing number of automobiles in cities around the world. This is due to more people living and working in cities as a result of urbanization. Street parking remains a common option for motorists, due to it being cheap and convenient. However, this option leads to a high concentration of vehicles causing congestion and obstruction of traffic. This problem is compounded as motorists wait for others to pull out of parking bays or look for empty parking spaces. In order to provide relief to this problem, an intelligent approach is proposed that generates an optimal parking space based on the vehicle location and desired destination. The proposed approach applies its operators adaptively and it derives optimality from the synergy between genetic algorithm and a local search technique in the search optimization process. The proposed method exhibits superior performance when compared with the existing methods over multiple iterations.


  • smart city
  • memetic algorithm
  • street parking system
  • optimization
  • genetic algorithm

1. Introduction

As a result of increasing industrialization and urbanization, cities around the world have experienced growing populations and as a result increasing number of vehicles. This trend is growing exponentially. Many predictors of urban population have indicated that by 2050, it is expected that 70% of the world population will be living in cities [1]. This implies that the number of vehicles will also see exponential growth as people work and study in cities. However, while the parking spaces are expanded, it does not meet the demands of growing populations. The shortage of parking spaces exerts more pressure on congested roads, which affects the travel time of motorists. This congestion of traffic leads to increase in costs in terms of fuel consumption, as well as an increase in accidents. The traffic authorities cannot cope with this burgeoning problem since it requires re-designing the parking infrastructure to make it more futuristic, so as to cater for rapid development and exponential growth in the number of motor vehicles [2]. In congested roads, the search for parking space consumes a lot of time and this negatively impacts on the economy, as people spend chunks of time waiting for limited parking spaces. This time would be well spent doing beneficial work. Moreover, the economy is also affected with respect to the environment as more carbon emissions are produced in the course of searching for parking [3]. This adds more strain on the economy as it has to deal with the effects of carbon pollution. The barrels of oil that are consumed everyday as a result of parking search are estimated at about one million rand [4]. Motorists also become fatigued from this tiring exercise of waiting and looking for parking, which affects productivity and overall health of people. Although many approaches have been proposed to tackle this problem [5], more intelligent mechanisms are needed to solve this critical problem, especially given its complexity and scalability. In many cities, parking attendants are ubiquitous as they guide motorists to empty parking bays. However, these manual controls are not efficient and do not optimize the available parking space. They are also expensive since these attendants expect a monetary reward for their services, and in many cases, they demand high charges for their unsolicited and informal services [6]. This is in addition to the formal fee that motorists pay for parking. If the informal attendants are not paid, they might damage the car or slash the tires, which creates a security risk to the motorists. As a result of this car parking problem, a safety hazard is created as carjackers and other robbers disguise themselves as parking attendants and end up inflicting harm on innocent motorists that are desperate for parking space. Due to the far-reaching impact of this problem, policymakers in some cities have attempted to introduce measures of dealing with the issue, by creating more off-street parking spaces and increasing the charges for on-street parking [7]. However, these measures have not created the desired effect as determined from many surveys; most motorists prefer on-street parking [8]. This is due to convenience and proximity of parking space to the intended destination. A long walk to the destination might impel the motorist to jostle and wait for on-street parking space. Therefore, the solution is not to walk away from reality on the off chance that creating more off-street parking would ameliorate the problem, but to face the problem and find smarter ways of optimizing the on-street parking. It is from that premise that the idea of a hybrid optimization method is proposed in this chapter. The method applies memetic algorithm, which is a blend of two algorithms. These are genetic algorithm that is used to optimize the global search based on the natural evolutionary process of generating new offspring using a set of parameters [9] and tabu search (TS) that is a metaheuristic that is used to diversify the search space by conducting neighborhood search of the individual solutions with a view to improve their fitness [10]. Unlike other heuristics, TS is memory based, such that each found solution in the course of the iteration is stored in a tabu list, so as to keep track of solutions and avoid duplicates. Its adaptive memory makes it suitable for highly dynamic problems [11], such as the street parking problem (SPP). In order to generate an optimal solution for the SPP, the synergy of these algorithms is harnessed to attain intensification and diversification search processes and enable the search reach optimum without premature convergence. The remainder of this chapter is structured as follows: related work is presented in Section 2, problem definition is talked about in Section 3, methodology is discussed in Section 4, results and discussion make Section 5, and the article concludes in Section 6.


2. Related work

A number of evolutionary algorithms have been advanced in the literature in an effort to solve the street parking problem (SPP). The review of these approaches provides an insight into what has been done and the potential impact and utility of the proposed approach in the current body of related knowledge.

2.1 Single metaheuristics

Thomas and Kovoor [12] applied genetic algorithm to create an autonomous system for parking vehicles. The approach used the roulette wheel selection method for selection of mating individuals and then used genetic operators, such as crossover and mutation to optimize fitness and produce offspring. The same principle was used by Aydin et al. [13] to develop a parking system for a smart city. Based on Internet of Things, data is transmitted across the Internet through devices. The genetic algorithm generates a vacant parking slot, which can be navigated for reservation by the motorist. This process can be done on a mobile device, which is similar to the intelligent parking system that operates on android platform [14]. In order to automate the parking guide process, a mobile robot was designed to optimize parking space using fuzzy logic [15]. The intelligent mobile robot automatically guides the motorist toward free parking space. Based on genetic algorithm, the robot is able to detect free parking space and map it to the vehicle. It also checks the dimensions of the parking bay to ensure an appropriate vehicle is assigned the bay. The deep learning of the robot system creates patterns that can be used for prediction; for example, Camero et al. [16] applied neural networks to predict the occupancy of the parking, so as to output the possible free parking spaces available through an optimization process. Han et al. [17] optimized the selection of the parking lot and route by use of Dijkstra’s algorithm. The outcome of the optimization process in terms of path and parking lot is sent to the cell phone of the driver. The travel and walking distances are considered before the automatic assignment of parking.

2.2 Hybrid metaheuristics

Dong et al. [18] hybridized the chaotic dynamics with the particle swarm optimization (PSO) to optimize the parking space. In order to avoid premature convergence, there is a constant update of the rules with a view to increase diversity and expand the search. This technique was also applied by Abidi et al. [19] whereby parking space is assigned to groups of drivers using a hybrid genetic algorithm. However, with the changing optima in the current problems related to car parking, a dynamic application of the search operators would make the methods more adaptive, so as to perform well despite the complexity and nonstationary nature of the car parking problem. Researchers have resorted to combining several algorithms to match the inherent difficulty of the problem. For example, Kantenti et al. [20] combined sensor technology with the Internet of Things. The barricade to the parking area is sensor enabled, so as to capture the details of the car including number plate and keep track of the vehicles, as well as both allocated and unallocated parking spaces. The nearest parking space is allocated to the vehicle. Sensors that are triggered when a vehicle enters or exits the parking lot include Arduino, ultrasonic sensor, and optical character recognition, among others. In order for the vehicle to be allocated the nearest parking space, a swarm intelligence mechanism was applied by Moorthy and Pabitha [21], whereby the route generator and allocator are infused into the PSO algorithm, so as to have source and destination routes generated and allocated to vehicles searching for parking space. Motorists request for parking through a request handler function that then sends the information to the route generator. The storage of this information is done by the route repository, and this information can be useful for prediction; for example, Rad et al. [22] use the data collected on vehicles for traffic flow prediction. The approach combines genetic algorithm with neural fuzzy technique for reservation of parking space. The most optimal parking space is generated using a multi-objective function that simultaneously applies genetic and fuzzy operators to the search optimization process with a view to minimize the waiting time and cost that motorists can spend on the parking space. The advent of electric cars has added another layer of difficulty to the parking space problem not only due to increase in cars but also waiting time concerns, as it affects the depletion of the battery power. Amini et al. [23] proposed a power distribution system to support parking lots for electric cars. Genetic algorithm is hybridized with particle swarm optimization algorithm to minimize loss of distribution network and optimize the allocation of parking space. The searching time for parking space can also be minimized through application of a bi-level genetic algorithm that was presented by Shen et al. [24]. The approach finds inter alia, free parking space, fees, and location, which are defined at different levels of the problem. For example, the location is produced by the upper level, while waiting and travel costs are generated by the lower level. The method aims to minimize the costs associated with obtaining the parking space.


3. Problem definition

The problem in this section is defined as an on-street parking optimization problem based on linear programming. This implies that subject to a set of constraints, the best solution is obtained from a set of feasible solutions [25] with regard to parking space. The objective function is used to calibrate the outcome of the optimization process according to the desired objective or target as per the problem features, such as maximizing or minimizing based on the decision variables and coefficients (Table 1).

iCar entity: i = 1, 2, …. n is cars available for parking
jSpace entity: j = 1, 2, …. p is parking space available
CijCost of assigning car i to parking space j
DijDistance between car i and parking space j
TijTime it takes to assign car i to parking space j
SjParking space capacity

Table 1.

Meaning of notations used in this section.



Subject to:

Wij=1if parking spacejis assigned tocari0otherwiseE4

The objective of the function defined in Eq. (1) is to minimize the following:

  1. The cost of assigning a car to an empty parking space

  2. Distance between intended destination and parking

  3. Time it takes to assign car to an empty parking space, as well as to find empty space and map it onto the waiting car

  4. Vehicle waiting time

In order to find the optimal solution, the objective function is defined with inequality constraints. The constraint in Eq. (2) indicates that the total number of assigned cars must not exceed the size or capacity of the available parking space. The vehicle cannot be assigned parking unless there is an empty parking space, as defined in Eq. (3). In order to make it easy for the proposed hybrid algorithm to solve this problem, a penalty function is applied [26]. The function in Eq. (1) is converted into unconstrained optimization problem.



A constant penalty is applied to individuals or solutions in the population sample that have violated the constraints. The penalty factors are defined by αg, βgγg, whereas A1, A2,A3 can be described as follows:


where pJ is the parking space and for i=1,2,,n;j=1,2,,p.


4. Methodology

4.1 Memetic algorithms (MAs)

Unlike genetic algorithms (GAs), MAs combine two evolutionary processes to solve problems. These include the natural process where genes are transmitted from one entity to the other through mating and the cultural process where memes are transmitted through meeting and interactions with one another [27] (Figure 1).

Figure 1.

Memetic algorithms.

These steps are followed in the implementation of the proposed algorithm. The algorithm represents a hybridized structure of evolutionary method and the local search. Memetic operators such as recombination and mutation are applied, so as to re-create new solutions through interactions between each other and the environment with a view to generate a better offspring. The local search expands the search space, which increases population diversity. The presence of multiple memes provides an opportunity for fitness comparisons, so that the best outcome is returned by the algorithm [28]. Whereas most approaches use tournament and roulette selection methods for parent individuals in the population, a random selection mechanism is used in this work [29]. The random selection of parents is conducted with a view to give each individual an equal chance for selection. The memetic operators are then applied to produce offspring. MAs are considered one of the best evolutionary methods that can solve today’s increasingly complex and dynamic problems and because of this, they have been extensively applied to solve real-life problems [30, 31].

4.2 Tabu search (TS)

In this work, TS metaheuristic is used to perform the exploitation procedure or search the local neighborhood for better solutions. TS comprises in its structure the ability to store solutions in the course of iterations [11]. Based on its memory function, TS prevents duplication of solutions by creating a sequential tabu list of solutions. The solution is added on condition that it is better than the existing previous solution [32]. The feasibility of the solutions is maintained by penalizing the infeasible solutions and concentrating the search in promising areas of the search space. The TS helps to control the search, given that it is easier to know which areas contain feasible solutions or otherwise based on the tabu list; the search can then be directed to areas of high feasibility value with a view to obtain the best solutions. The optimal parking space for the vehicle is thus obtained through search intensification and diversification. An adaptive memory configuration for TS is considered in this work. This allows automatic adjustment of the tabu list as the search progresses. The search moves that were already made or the solutions that were visited are forbidden, so as to ensure that all areas are visited during the search [33]. Swap moves are employed to focus search attention to areas that do not feature in the tabu search list. A swap move is conducted if it will yield the highest move gain [34]. The variables cannot change their status once they have been included in the tabu list, but if the search leads to a potentially better solution, then a swap move is performed. These measures enable the local neighborhood search to converge to solutions of good quality [35]. The local search technique implementation in this chapter follows the steps in Figure 2.

Figure 2.

Search technique.


5. Results and discussion

The efficiency of the proposed method, adaptive memetic algorithm (AMA), was evaluated against the existing optimization techniques in the literature with a view to investigate the performance of each method over the same set of data and defined with similar settings. The optimization techniques implemented in this work include simulated annealing (SA) [36], genetic algorithm (GA) [37], ant colony optimization (ACO) [38], and particle swarm optimization (PSO) [39]. MATLAB environment was used for the experiments in this section. The case study was taken from the city of Durban in South Africa which has an on-street parking problem (OPP) due to limited parking spaces. Anton Lembede street and Prince street are the two busy streets in Durban city that were selected for this study, and the global positioning system (GPS) data are drawn from the geographical information system of Google Maps, including the parking space coordinates. Thirty individuals are considered for the population sample size (Figures 3 and 4).

Figure 3.

Satellite view of the Anton Lembede street in Durban city.

Figure 4.

Satellite view of the Prince Street in Durban city.

Crossover and mutation probabilities are set at 25 and 75%, respectively. The performance is measured based on the average waiting time, utilization of the parking space, and allocation of appropriate parking space to the car.

The proposed AMA demonstrates the ability to explore and exploit the search better in search of higher fitness individuals during the search process, for most of the instances as shown in Figure 5.

Figure 5.

Fitness comparisons between the proposed AMA and existing algorithms.

The results indicate that parking space wastage is minimized when memetic algorithm is employed in optimization of parking space. Also, the proposed method, AMA, produces a faster convergence for most iterations as shown in Figure 6. This is due to the local search technique that adaptively conducts a neighborhood search for better solutions. Ultimately, the AMA ensures that an appropriate parking space is allocated to the car.

Figure 6.

Convergence comparisons between different techniques.


6. Conclusion

In this chapter, an adaptive memetic algorithm was employed to solve the on-street parking problem (OPP). The proposed method combined genetic algorithm (GA) and tabu search (TS) to generate the optimal solution. The method was applied to a real life problem in Durban city of South Africa whose limited parking space is under the control of eThekwini municipality. TS was used to perform neighborhood search to improve the solutions with a view to prevent premature convergence of the search process. The proposed algorithm optimized the parking space search and allocation by reducing the waiting time, cost of allocating vehicle to parking space, and enhancing parking space utilization through appropriate allocations. Given the difficulty of finding and allocating an on-street parking space, the proposed algorithm implemented the memetic operators adaptively, so as to deal with nonstationary optima. The proposed method was compared with existing algorithms, such as SA, GA, ACO, and PSO in solving the same problem, OPP, and as shown in the experiments, the proposed algorithm outperformed all algorithms on several iterations.


  1. 1. Gross M. The urbanization of our species. Current Biology. 2016;26:1205-1208. DOI: 10.1016/j.cub.2016.11.039
  2. 2. Yang S, Huang L. Research on planning and management of urban parking lot—taking Hangzhou as an example. Current Urban Studies. 2017;5:379-386. DOI: 10.4236/cus.2017.54021
  3. 3. Bharadwaj S, Ballare S, Rohit R, Chandel MK. Impact of congestion on greenhouse gas emissions for road transport in Mumbai metropolitan region. Transportation Research Procedia. 2017;25:3528-3551. DOI: 10.1016/j.trpro.2017.05.282
  4. 4. Gupta A, Kulkarni S, Jathar SV, Jain N. Smart car parking management system using IoT. American Journal of Science, Engineering and Technology. 2017;2:112-119. DOI: 10.11648/j.ajset.20170204.13
  5. 5. Abidi S, Krichen S, Alba E, Bravo JM. A hybrid heuristic for solving a parking slot assignment problem for groups of drivers. International Journal of Intelligent Transportation Systems Research. 2017;15:85-97. DOI: 10.1007/s13177-016-0123-1
  6. 6. Foster J, Chasomeris M. Examining car guarding as a livelihood in the informal sector. Local Economy: The Journal of the Local Economy Policy Unit. 2017;32:525-538. DOI: 10.1177/0269094217727990
  7. 7. Brooke S, Quddus M, Ison S. On-street parking search: A UK local authority perspective. Journal of Transport and Land Use. 2017;10:13-26. DOI: 10.5198/jtlu.2015.600
  8. 8. Brooke SL. Factors Influencing Urban on-Street Parking Search Time Using a Multilevel Modelling Approach. Loughborough, England: Loughborough University; 2015
  9. 9. Kumari J, Dubey AK. A review paper on genetic algorithm. International Journal of Advance Research in Computer Science and Management Studies. 2016;4:122-125
  10. 10. McKendall A, Li C. A tabu search heuristic for a generalized quadratic assignment problem. Journal of Industrial and Production Engineering. 2016;34:221-231. DOI: 10.1080/21681015.2016.1253620
  11. 11. Xia Y, Fu Z, Pan L, Duan F. Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order. PLoS One. 2018;13:1-19. DOI: 10.1371/journal.pone.0195457
  12. 12. Thomas D, Kovoor BC. A genetic algorithm approach to autonomous smart vehicle parking system. Procedia Computer Science. 2018;125:68-76. DOI: 10.1016/j.procs.2017.12.011
  13. 13. Aydin L, Karakose M, Karakose E. A navigation and reservation based smart parking platform using genetic optimization for smart cities. In: 5th International Istanbul Smart Grid an Cities Congress and Fair (ICSG ’17); 19-21 April 2017; Istanbul, Turkey: IEEE; 2017. pp. 120-124
  14. 14. Anitha J, Thoyajakshi Y, Ramya A, Sravani V, Kumar P. Intelligent parking system using android application. International Journal of Pure and Applied Mathematics. 2017;114:165-174
  15. 15. Aye YY, Watanabe K, Maeyama S. An automatic parking system using an optimized image-based fuzzy controller by genetic algorithms. Artificial Life and Robotics. 2017;22:139-144. DOI: 10.1007/s10015-016-0326-1
  16. 16. Camero A, Toutouh J, Stolfi DH, Alba E. Evolutionary deep learning for car park occupancy prediction in smart cities. In: Proceedings of the 12th International Conference on Learning and Intelligent Optimization (LION '18); 10-15 June 2018; Kalamata, Greece: LION; 2019. pp. 1-16
  17. 17. Han Y, Shan J, Wang M. Optimization design and evaluation of parking route based on automatic assignment mechanism of parking lot. Advances in Mechanical Engineering. 2017;9:1-9. DOI: 10.1177/1687814017712416
  18. 18. Dong N, Fang X, Wu A-G. A novel chaotic particle swarm optimization algorithm for parking space guidance. Mathematical Problems in Engineering. 2016;2016:1-14. DOI: 10.1155/2016/5126808
  19. 19. Abidi S, Krichen S, Alba E, Molina JM. A new heuristic for solving the parking assignment problem. Procedia Computer Science. 2015;60:312-321. DOI: 10.1016/j.procs.2015.08.132
  20. 20. Kantenti D, Srikar DV, Ramesh TK. Intelligent smart parking problem. In: Proceedings of the IEEE International Conference on Smart Technologies for Smart Nation (SmartTechCon ’17); 17-19 August 2017; Bangalore, India: IEEE; 2017. pp. 1-5
  21. 21. Moorthy R, Pabitha P. Novel car parking system using swarm intelligence. International Journal of Pure and Applied Mathematics. 2017;117:289-298
  22. 22. Rad F, Pazhokhzadeh H, Parvin H. A smart hybrid system for parking space reservation in VANET. Journal of Advances in Computer Engineering and Technology. 2017;3:12-18
  23. 23. Amini HM, Moghaddam MP, Karabasoglu O. Simultaneous allocation of electric vehicles’ parking lots and distributed renewable resources in smart power distribution networks. Sustainable Cities and Society. 2017;28:332-342. DOI: 10.1016/j.scs.2016.10.006
  24. 24. Shen X, Chen F, Su B, Chen Q, Yao J. Optimization of park-and-ride system: A case study of Shunyi in Beijing. Advances in Mechanical Engineering. 2017;9:1-8. DOI: 10.1177/1687814017714987
  25. 25. Rama S, Srividya S, Bellatti D. A linear programming approach for optimal scheduling of workers in a transport corporation. International Journal of Engineering Trends and Technology. 2017;45:482-487
  26. 26. Kulkarni O, Kulkarni N, Kulkarni AJ, Kakandikar G. Constrained cohort intelligence using static and dynamic penalty function approach for mechanical components design. International Journal of Parallel, Emergent and Distributed Systems. 2018;33:570-588. DOI: 10.1080/17445760.2016.1242728
  27. 27. Panteleev AV, Pismennaya VA. Application of a memetic algorithm for the optimal control of bunches of trajectories of nonlinear deterministic systems with incomplete feedback. Journal of Computer and Systems Sciences International. 2018;57:25-36
  28. 28. Wang C, Ji Z, Wang Y. A novel memetic algorithm based on decomposition for multiobjective flexible job shop scheduling problem. Mathematical Problems in Engineering. 2017;2017:1-20. DOI: 10.1155/2017/2857564
  29. 29. Wang C, Tian N, Ji Z, Wang Y. Multi-objective fuzzy flexible job shop scheduling using memetic algorithm. Journal of Statistical Computation and Simulation. 2017;87:2828-2846. DOI: 10.1080/00949655.2017.1344846
  30. 30. Pelaez JI, Ruiz JA, Veintimilla J, Vaccaro G, Witt P. Memetic computing applied to the design of composite materials and structures. Mathematical Problems in Engineering. 2017;2017:1-16. DOI: 10.1155/2017/4723863
  31. 31. Wang P, Liu R, Jiang Z. A memetic algorithm for optimization of combination chemotherapy with dose adjustment. In: Proceedings of the 13th IEEE Conference on Automation Science and Engineering (CASE '17); 20-23 August 2017; Xi’an, China: IEEE; 2017. pp. 207-212
  32. 32. Niu Y, Yang Z, Chen P, Xiao J. A hybrid tabu search algorithm for a real-world open vehicle routing problem involving fuel consumption constraints. Complexity. 2018;2018:1-12. DOI: 10.1155/2018/5754908
  33. 33. Kurt NE, Sahin BH, Kiirsad D. An adaptive tabu search algorithm for market clearing problem in Turkish day-ahead market. In: Proceedings of the 15th International Conference on the European Energy Market (EEM ’18); 27-29 June 2018; Lodz, Poland: EEM; 2018. pp. 1-6
  34. 34. Wang Y, Wu Q, Punnen AP, Glover F. Adaptive tabu search with strategic oscillation for the bipartite Boolean quadratic programming problem with partitioned variables. Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal. 2018;450:284-300. DOI: 10.1016/j.ins.2018.03.045
  35. 35. Roesener AG, Barnes WJ. An advanced tabu search approach to the dynamic airlift loading problem. Logistics Research. 2016;9:1-18. DOI: 10.1007/s12159-016-0139-6
  36. 36. Shirdel GH, Abdolhosseinzadeh M. A simulated annealing heuristic for the traveling salesman problem. Journal of Information and Optimization Sciences. 2018;39:1283-1296. DOI: 10.1080/02522667.2017.1367494
  37. 37. Zhang J, Kang M, Li X, Liu G-Y. Bio-inspired genetic algorithms with formalized crossover operators for robotic applications. Frontiers in Neurorobotics. 2017;11:1-12. DOI: 10.3389/fnbot.2017.00056
  38. 38. Mavrovouniotis M, Muller FM, Yang S. Ant colony optimization with local search for dynamic traveling salesman problems. IEEE Transactions on Cybernetics. 2017;47:1743-1756. DOI: 10.1109/TCYB.2016.2556742
  39. 39. Wang C-F, Liu K. A novel particle swarm optimization algorithm for global optimization. Computational Intelligence and Neuroscience. 2016;2016:1-9. DOI: 10.1155/2016/9482073

Written By

Stephen Akandwanaho and Irene Govender

Submitted: March 23rd, 2019 Reviewed: March 25th, 2019 Published: May 13th, 2019