Dynamic Street Parking Space Using Memetic Algorithm for Optimization

Abstract

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.

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).

Notation	Denotation
i	Car entity: i = 1, 2, …. n is cars available for parking
j	Space entity: j = 1, 2, …. p is parking space available
Cij	Cost of assigning car i to parking space j
Dij	Distance between car i and parking space j
Tij	Time it takes to assign car i to parking space j
Sj	Parking space capacity

Table 1.

Meaning of notations used in this section.

Minimize:

$$\sum _{\mathrm{i}}^{\mathrm{n}}\sum _{\mathrm{j}}^{\mathrm{p}}{\mathrm{C}}_{\mathrm{ij}}{\mathrm{D}}_{\mathrm{ij}}{\mathrm{T}}_{\mathrm{ij}}{\mathrm{W}}_{\mathrm{ij}}$$E1

Subject to:

$$\sum _i^p{w}_{\mathit{ij}}\le S_j\forall j=1,2,\dots p\forall i=1,2,\dots n$$E2

$$\sum _i^n{w}_{\mathit{ij}}>0\forall j=1,2,\dots p\forall i=1,2,\dots n$$E3

$$W_{\mathit{ij}}=\left\{\begin{array}{c}1\mathit{\text{if parking space}}j\mathit{\text{is assigned to}}\mathit{car}i\\ 0\mathit{\text{otherwise}}\end{array}\right.$$E4

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.

Minimize:

$$\sum _i^n\sum _j^p{C}_{\mathit{ij}}{D}_{\mathit{ij}}{T}_{\mathit{ij}}{W}_{\mathit{ij}}+{\alpha }_g{A}_i+{\beta }_g{A}_2$$E5

A constant penalty is applied to individuals or solutions in the population sample that have violated the constraints. The penalty factors are defined by ${\alpha }_g$, ${\beta }_g{\gamma }_g,$ whereas $A_1$, $A_2,A_3$ can be described as follows:

$$A_1=\sum _{g=1}^n{\alpha }_g\ast max{\left(0,|\sum _{i=1}^n{w}_{\mathit{ij}}-s_{\mathit{ij}}|\right)}^2$$E6

$$A_2=\sum _{g=1}^p{\beta }_g\ast max{\left(0,\left(p_J-\sum _{J=1}^P{w}_{\mathit{ij}}\right)\right)}^2$$E7

where $p_J$ is the parking space and for $i=1,2,\dots ,n;j=1,2,\dots ,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.