A Conceptual Framework for Modeling Smart Parking

Abstract

Vehicles are highly used in the city. If the drivers of vehicles have an appointment in the city, they are looking for parking. Thus, they need to know where to find one in real time. In this paper, we present a smart model that is based on a combination of multi-agent system and genetic algorithm (MAS-GA). The smart model can help the drivers find the optimal parking when the drivers make a request for parking according to their position on the road and the waiting and parking time. This smart model is based on four parameters: the availability of parking, cost of parking, the distance between the actual position of the vehicle and the destination parking, and traffic congestion. We can also add the time to arrive a destination parking. Thus, the proposed smart model helps to maximize the utilization of space resources of a city as parking and reduce the waiting and parking time.

1. Introduction

Parking in the city can be an attractive subject because 30% of traffic congestion is caused by drivers circling to find an available parking for their vehicles [1]. Thus, the vehicle needs to have a decision system that allows it to find the optimal parking in a short time. Economic income is also affected by this decision system that can manage and control the availability of parking in real time; in the same time, they often lose revenue due to inadequate meter enforcement and no parking, standing, and loading zone violations [2]. We will treat two main questions in this paper. The first is “what is the optimal method to manage, reduce, and control the parking in the city?” The second is “what is the optimal strategy which permits finding the optimal parking?”

In this paper, we propose to use a multi-agent system which allows distributing the different tasks between the agents when each agent can perform genetic algorithms to find the optimal parking in real time, thus adapting rapidly to traffic congestion the availability of place in the parking. Thus, all agents can cooperate and negotiate to find the best solution which can plan for allocation of vehicle in parking. Then, we develop a GIS system which allows knowing the position of the vehicle and all data associated with it as vehicle id, waiting time, and distance between proposed parking and vehicle.

After a deep study of the subject, we have found three factors that can affect the allocation of vehicles into the optimal parking, as the waiting and parking time, parking costs, distance between the vehicle and proposed parking.

This paper is organized as the following. Firstly, we will present a state-of-the-art review for allocation of vehicle into parking. Then, we describe our proposed approach which is based on two approaches, the multi-agent system and genetic algorithm (MAS-GA). Finally, we add some experimental results and conclusion.

2. Related works

Many works have been studied to propose an intelligent parking. In this section, we will introduce the most important works that treat this issue.

Stéphane et al. [3] propose in this paper a new system that integrates the IoT and a predictive model based on ensemble methods to optimize the prediction of the availability of parking spaces in smart parking. The tests that we carried out on the Birmingham parking data set allowed reaching a mean absolute error (MAE) of 0.06% on average with the algorithm of bagging regression (BR). These results have improved the best existing performance by over 6.6% while dramatically reducing system complexity.

Diya and Binsu [4] propose a new prototype for the smart vehicle parking system. A genetic algorithm approach has been taken to address the issue of scheduling the vehicle to the parking bay.

Li et al. [5] propose to use modern intelligent agents having the capability of planning, mobility, execution monitoring, and coordination, which take into account the negotiable space on parking prices, make a strategic decision by adopting the intelligent agent system, and then select the optimal parking for the driver. These characteristics can be utilized to build an integrated parking assistant system. The autonomous coordination activities challenge traditional approaches and call for new paradigms and supporting middleware. This agent approach is based on the coordination network. This coordination network is truly bringing benefit to drivers and parking operators.

Oyentaryo and Pasquier [6] proposed an approach that is to design a self-training system that makes use of human expertise to automatically derive a working vehicle control system. A new neuro-fuzzy architecture known as the GenSoYager fuzzy neural network has been realized and integrated with a vehicle driving simulator for training and testing purposes. This approach is based on detecting system, motion planning, and supplying information to detect the best parking.

Tang et al. [7] describe a wireless sensor network (WSN)-based intelligent car parking system. In the system, low-cost wireless sensors are deployed in a car park field, with each parking lot equipped with one sensor node, which detects and monitors the occupation of the parking lot. The status of the parking field detected by sensor nodes is reported periodically to a database via the deployed wireless sensor network and its gateway. The database can be accessed by the upper-layer management system to perform various management functions, such as finding vacant parking lots, auto-toll, security management, and statistics report.

The information about the location and availability of a parking space near the destination is provided to the drivers by the current GPS-based vehicle navigation system, which is discussed by Pullola et al. [8]. They propose a scientific solution to parking allocation problem by utilizing the history and current status of the occupancy/availability. They model the availability of a parking lot and propose an intelligent algorithm that allows drivers to choose a parking lot with the maximum probability of getting it.

Rongxing et al. [9] propose a new smart parking technique based on vehicular communication for large parking lots. This technique permits minimizing the drivers’ hassle and inconvenience. The proposed technique is characterized by employing parking lot RSUs to survey and manage the whole parking lot and is enabled by communication between vehicles and the RSUs. Once vehicles that are equipped with wireless communication devices, which are also known as onboard units, enter the parking lot, the RSUs communicate with them and provide the drivers with real-time parking navigation service and secure intelligent antitheft protection and friendly parking information dissemination.

In Banerjee [10], a new system based on image processing is proposed for the provision of parking information and guidance. The proposed system includes counting the number of parked vehicles and identifying the stalls available. The system uses images for detection of the vehicles. A camera for capturing the reference image is present at the entrance. For this purpose edge detection has been carried out using Prewitt edge detection operator and according to percentage of matching guidance and information, which is provided to the incoming driver.

Banerjee and Al-Qaheri [11] propose an intelligent and optimized scheme to solve parking space problem for a small city using a reactive search technique (named as Tabu search) assisted by rough set. Rough set is being used for the extraction of uncertain rules that exist in the databases of parking situations. The inclusion of rough set theory depicts the accuracy and roughness, which are used to characterize the uncertainty of the parking lot. Approximation accuracy is employed to depict accuracy of a rough classification according to different dynamic parking scenarios.

Geng and Cassandras [1] propose a smart parking system for an urban environment. The system assigns and reserves an optimal parking space for a driver based on the user’s requirements that combine proximity to destination and parking cost while also ensuring that the overall parking capacity is efficiently utilized. This approach solves a mixed integer linear program (MILP) problem at each decision point in a time-driven sequence. The solution of each MILP is considered as an optimal allocation based on current state information and subject to random events such as new user requests or parking spaces becoming available.

The emerging of intelligent sensors results in the emergence and development of intelligent parking. Parking survey is one of the most important things for the parking managers and corresponding planners or researchers [12]. In this work, Chen et al. [12] discuss the problem of making a parking survey in intelligent parking systems where parking spaces, entrance, and exit are detected to acquire the occupation of the parking. They present three possible sensor layouts and corresponding algorithms to obtain the characteristic index needed in a parking survey. These intelligent parking systems can also do parking survey in different times and areas with the same detection data.

3. The proposed approach

In this paper, we will propose our approach to model a smart parking. This approach is based on a multi-agent system and genetic algorithms.

3.1 Multi-agent systems

An agent is a software system that is situated in some environment and that is capable of autonomous action in order to meet its design objectives [13]. In this work, we use the multi-agent system because it provides numerous advantages in the domain of allocation of vehicle into parking and drivers’ comfort level. The proprieties of multi-agent systems offer autonomy to find the optimal parking, in real time. Thus, it provides a suitable framework for these systems. Also, they provide a number of important characteristics as the cooperation, negotiation, adaptation, and the mobility. That is, on the one hand, this autonomous agent perceives its environment, and on the other hand, the agent modifies its environment by its actions. Hence, an agent can dynamically find the adaptable parking in real time and according to the actual situation of the environment.

3.2 Genetic algorithms

Genetic algorithms are developed by Holland [14] to imitate the phenomena adaptation of living beings. They are an optimization technique based on the concepts of natural selection and genetics. It searches an optimal solution among a large number of candidate solutions within a reasonable time (the process of evolution takes place in parallel). Each of these solutions contains a set of parameters that completely describe the solution. This set of parameters can then be considered as the genome of the individual, with each parameter comprising of one or more chromosomes. They allow a population of solutions to converge step by step toward the optimal solution. To do this, they will use a selection mechanism of the population of individuals (potential solutions). The selected individuals will be crossed with each other (crossover), and some will be mutating by avoiding, whenever possible, local optima. The genetic algorithms are used primarily to treat both problems [15].

1. The search space is large, or the problem has a lot of parameters to be optimized simultaneously.

2. The problem cannot be easily described by a precise mathematical model.

We will combine multi-agent systems with genetic algorithms, for permitting the agent to choose the optimal actions. Therefore, our proposal is smart model which is based on the three following points:

1. Parking agent is a software agent which can manage, control the local optimization process, and exchange relevant information with neighboring agents.

2. Genetic patrimony which transformed between agents is used as inputs to the genetic algorithm. This genetic patrimony represents values of waiting and parking time and the distance between the vehicle and the proposed parking that are collected by sensor system.

3. Genetic algorithms are used to find the optimal solution for the current configuration; this is composed of two objective functions: one calculates the gain, and the other calculate the drivers’ comfort level.

3.2.1 System architecture

The objective of our proposed system is to find the available parking according to the traffic road conditions. The proposed system determines the optimal parking for the vehicles circulated in the road network which need to use a parking. Thus, our system considers two mainly parameters: the number of vehicles and parking and environment data and waiting and parking time. The result of a system can be suggested to the driver or can be applied automatically as a part of a control system. In Figure 1, we present the architecture of our system. In this system, we have principally three agents: vehicle agent, parking agent, and agent profile. The parking agent can find the optimal parking placement according to the profile of drivers’ vehicle, such as distance between vehicle and proposed parking and waiting and parking time.

Figure 1.

Architecture of our system.

4. Parking agent

As we mentioned previously, each parking agent is able to manage, control, and regulate its parking environment to optimize the parking allocation and increase the efficiency and productivity of systems, thus increasing the profit. Therefore, the main objective of a parking agent is to solve the conflicts which can occur during the allocation of vehicles into the optimal parking. The drivers’ comfort satisfaction is related to both the conditions of the environment and drivers’ preferences over the system. In order to evaluate the drivers’ comfort level, environmental parameters can be used as indices to form the function of drivers’ comfort by using the actual value of the environmental parameters and drivers’ preferences of these parameters. Therefore, the parking agent has been designed with three components for controlling and regulating its parking environment. These components are an optimizer, simulator, and comfort model.

4.1 An optimizer

It runs a genetic algorithm. Since heuristic algorithms have no guarantee to find the globally optimal solution within the limited iterations, in this research, GA runs 100 times in each time step to increase the possibility of achieving the global optimization, saving battery, and meeting passengers’ preferences. In this principle, more runs of the optimization algorithm will lead to higher probability of achieving better results, but it will inevitably take more computation time. After many trials, it was found that 100 is a reasonable number of runs for balancing the solution quality and computation time cost.

4.2 Simulator

Each parking agent has a simulator that is used together to discover the drivers’ comfort level and find the optimal parking in the prevailing conditions. The results of simulator could be optimized to achieve a satisfactory balance between discovery time and system performance. The optimizer repeatedly runs the vehicle flow simulations for every time and calculates the satisfaction of drivers’ comfort level. The best drivers’ comfort level is then used to generate the subsequent generation of general drivers’ comfort level, and over a number of generations, the best candidates’ comfort level is identified.

4.3 Comfort model

The drivers’ comfort model permits to control the drivers’ preferences via computer techniques to find the optimal parking which satisfies drivers’ comfort and increases the efficiency and productivity of the system. In order to meet the compromise between system efficiency and drivers’ comfort level, a parking agent needs to evaluate the number of vehicles in the parking and a drivers’ comfort level that demand parking in response to maximizing the gain. However, drivers’ comfort level and the cost of parking usually affect each other in an opposite way. Therefore, the main goal of a parking agent is to solve the conflicts between maximizing the gain and increasing drivers’ comfort level. The drivers’ comfort level is related to both the traffic road conditions and drivers’ preferences over the environment. In order to evaluate the drivers’ comfort in the vehicle, environmental parameters can be used as indices to form the function of drivers’ comfort by using the actual value of the corresponding environmental parameters and drivers’ preferences of these parameters. Generally, the distance between the vehicle and proposed parking and the waiting and parking time are used as parameters to evaluate the drivers’ comfort level. Also, the cost and the gains of parking can be used as parameters to evaluate the revenues of the system.

5. Optimization process of parking allocation

As we say previously, the parking agent has an optimizer and simulator that are used together to discover the optimal parking that can satisfy the comfort level of drivers. The use of genetic algorithm has a major advantage over systems that rely on predefined values, as each parking agent enables a genetic algorithm to discover the optimal parking that may not resemble any predefined values, but may be optimal values for the current conditions of the road condition, as congestion. The optimizers should achieve a satisfactory balance between the revenue of solutions and drivers’ comfort level. Thus, each parking agent executes a genetic algorithm to find the optimal parking that can be attributed to each system to perform optimal waiting time, increasing the drivers’ comfort level.

5.1 Chromosomes’ structure

To apply the genetic algorithm, we should define the genes. The gene can be characterized by its identifier and a set of values of parameters that can be applied to define the optimal parking that satisfies the drivers’ comfort level. We use multiple forms in coding the genes. Firstly, we use the strings in encoding the identifiers of vehicle, and then we use real number for encoding the values of waiting and parking time and the distance between the vehicle and the proposed parking. Figure 2 presents the structure of the gene.

Figure 2.

Gene’s structure.

To identify the best chromosome from the population, the optimizer runs a genetic algorithm with its different classic steps, as selection, crossover, and mutation. The parking agent has a simulator, which permits it to identify the best available solution from the population; the optimizer repeatedly runs the waiting time simulator for each vehicle in a given generation. After a number of generations, the best candidate values of parameters are identified. Figure 3 shows an example chromosome of the parking agent.

Figure 3.

An example of chromosome solution.

5.2 Initialization, crossover, and mutation

Firstly, the initialization operator determines how each chromosome is initialized to participate in the population of genetic algorithm. Here, the chromosome is filled with the genetic material from which all new solutions will evolve [16]. This strategy means that the newly generated offspring may or may not remain within the new population, depending upon how they measure up against the existing members of the population [16].

Then, the crossover operator defines the procedure for generating a child from two parent chromosomes. The crossover operator produces new individuals as offspring, which share some features taken from each parent. The probability of crossover determines how often crossover will occur in each generation. In this approach, we will use the single-point crossover strategy which was adopted for all experiments. In this paper, the results for all experiments presented were generated using a crossover percentage of 50%, which is to say that at each generation, 50% of the new population were generated by splicing two parts of each chromosome’s parents together to make another chromosome [16]. Figure 4 presents the crossover operator.

Figure 4.

The crossover operator.

Finally, the mutation operator will be applied. It defines the procedure for mutating the chromosome. Mutation, when applied to a child, randomly alters a gene with a small probability. In this work, the results presented here were generated using a 1% mutation probability, which was determined experimentally, utilizing a single case of vector drivers’ comfort level [16]. Figure 5 presents the operator of mutation.

Figure 5.

The operator of mutation.

5.3 Evaluation of solutions

The purpose of evaluation system is to provide a measure for any given solution that represents its relative quality. In our resolution method for parking allocation problem for vehicles, the objective function used here works by calculating and summing the penalties associated with the waiting time, the parking time, and the distance between vehicle and proposed parking. Thus, we will use the objective functions to evaluate solutions of the parking allocation problem and examine the weighted relationship between the actual measured values of the waiting time, the parking time, and distance between vehicle and proposed parking. The objective functions used to evaluate solutions require a number of definitions that model the problem underlying structure, specifically.

• $V=\left\{V_1,V_2,V_3,..\dots \dots V_n\right\}$ is the set of all vehicles in the road.

• $P=\left\{P_1,P_2,P_3,..\dots \dots P_n\right\}$ is the set of all parking in city.

• N1 and N2 are the numbers of all parking in the city and all vehicles, respectively,

• WT_m, PT_m, and Dist_m are the measured values of the waiting time, the parking time, and the closest distance, respectively.

• WT_c, PT_c, and Dist_c are the comfort values of the waiting time, the parking time, and the closest distance, respectively.

• [Dist_min, Dist_max] represents the distance comfort range. This range can be defined by drivers.

• [T_min, T_max] represents the waiting time range.

Two important parameters are in our MAS-GA: the optimal assigned values of waiting and parking time and the closest assigned values to the distance between vehicle and proposed parking.

In this context, we have mainly two important functions f(C) and f(G) which permit evaluating the performance and efficiency of the proposed approach. These two functions are calculated by the parking agent.

The objective of this optimization mechanism is to minimize the value of f(C) and maximize the gain f(G) for evaluating the performance and the efficiency of our system. Firstly, we have:

$$f\left(C\right)=C_1\ast {\raisebox{1ex}{${\mathit{WT}}_c$}\!\left/ \!\raisebox{-1ex}{$\mathit{WT}$}\right.}_m+C_2\ast \raisebox{1ex}{${\mathit{PT}}_c$}\!\left/ \!\raisebox{-1ex}{${\mathit{PT}}_m$}\right.+C_3\ast \raisebox{1ex}{${\mathit{\text{Dist}}}_c$}\!\left/ \!\raisebox{-1ex}{${\mathit{\text{Dist}}}_m$}\right.$$E1

C1, C2, and C3 are the user-defined weighting factors, which indicate the importance of the three comfort factors and resolve the possible equipment conflicts. These factors take values in the range of [0, 1]. The drivers can set their own preferred values in different situations according to its travel. Since the travel period has a profound influence on energy savings, it should be taken into account in the control strategy design. Generally speaking, the parking agent activates the optimizer to tune the set point in order to obtain the acceptable drivers’ comfort and to maximize the revenues [16]. Otherwise, the parking agent turns off all the resource lights and keeps the blind position to save energy if there are no vehicles in the parking. The objective function is defined in Eq. (1), and the optimization goal is to maximize these objective functions. Since the ratio between the measured value and comfort value is determined by drivers’ play via graphic interface, it has an important role in achieving the control goal. Thus, it permits increasing the drivers’ comfort level and optimize the parking places.

The second objective function permits controlling the gain of parking. The objective of this function consists of maximizing the total gain of parking. Thus, we can define this objective function as the following:

$$f\left(G\right)=N\ast \mathrm{Cos}t$$E2

The cost represents the unit cost of parking.

6. Vehicle agent

When the vehicle needs to use parking, vehicle agents change their behavior and try to find a parking. This behavior of vehicle agent is triggered by a lower threshold E₁. The vehicle finds a parking; four parameters have to take into account: the actual position of the vehicle, the destination, the distance between the vehicle and the parking, and availability of place in the parking and the maximum waiting time. The proposed smart model should find the closest distance and minimize the waiting time.

Firstly, each vehicle that needs to find a parking sends a request of parking to all the parking agents. Then, each parking treats this request and sends a response to the vehicle agent. Finally, the vehicle drivers are assumed to park its vehicle in the optimal parking. Figure 6 presents an intelligent parking in the city.

Figure 6.

Intelligent parking in the cities.

7. Negotiation and cooperation

To model an optimal allocation of vehicle into parking, using the multi-agent system and genetic algorithm, we have to propose an efficient mechanism of negotiation, cooperation, and coordination between different agents. A single agent is unable to achieve some complex tasks, as the allocation parking problems because its capability is individually limited or although can complete, but its performance and efficiency are far lower than the performance and the efficiency with the cooperation and the coordination of many agents [17]. In order to solve charging station location conflict, the vehicle agents negotiate, each trying to find an available charging station. Therefore, when conflicts occur between two or many parking agents, it is important to limit their effects. In such case, negotiation techniques enable the involved parking agents to resolve their different conflicts by reaching compromises between the three parameters as the distance between the actual position of the vehicle, the waiting and parking time, and the availability of parking. This negotiation allows the parking agents to solve various conflicts at once and prevents new conflicts to appear. The parking agents negotiate with each other in order to decide whether the optimal plan can be applied to satisfy the need of drivers’ vehicles in parking and in the same time reduce the waiting time of parking. Thus, in our proposed approach, the parking agents negotiate with each other in order to determine the best possible arrangement. This negotiation enables them to solve various conflicts simultaneously and avoid new conflicts from appearing. In Figure 7, we present an example of negotiation between two vehicle agents: vehicle agent 1 and vehicle agent 2. Thus, these two agents negotiate by proposing a plan of actions which can arrange the two agents. In each cycle, one parking agent makes a plan proposal to the other vehicle agents, which they can accept or reject. If they accept, negotiation ends; otherwise, the other parking agent makes a proposal at the next cycle.

Figure 7.

Negotiation between two agents.

Also, the cooperation is defined as the collaboration between vehicle agents or station agents to find the optimal action to solve conflicts in the research station problem. In this paper, we use cooperation in order to solve conflicts which occur between the different vehicles. Each parking agent cooperates with the other parking agents in order to find the optimal solution which permits reducing the waiting time and finds the closed parking. Each vehicle agent sends to the parking agent some data as the position, the remaining energy, and maximum waiting and parking time that permit to the parking agent analysis this data and performs its genetic algorithm. Next, each parking agent checks its list of requests to treat them and try to find the final optimal sequence of values of waiting time and the parking time that permit it to solve the conflict and avoid other conflicts to occur. The vehicle agents can accept or refuse the response of other agents according to their current situations. Thus, the parking agent sends the demand of the solution founded by its neighbors, and it waits to receive the responses of them, analyzes these responses, and determines whether the solution is possible or not. If a solution is feasible, it sends a confirmation to those of its neighbors that accepted this solution. Figure 8 presents a simple configuration of cooperation between three agents.

Figure 8.

Cooperation between agents.

8. Experiments and results

In this section, we present two case studies that illustrate how to design the different agents of our system and show collaboration between them. We use Jade to implement the different agents, vehicle agent, profile agent, and parking agent. Also, we use Java to implement the different steps of genetic algorithm as crossover operator, mutation operator, and the evaluation function.

The vehicle agent uses the sensor to learn the traffic data, waiting time, and parking time, which can be used as input in the genetic algorithms. The drivers can introduce their preferences in the profile agent via a graphic interface. The parking agent runs a genetic algorithm that can find the optimal values of waiting and parking time, which permit an optimal allocation of vehicle and increase drivers’ comfort level.

During each simulation process, the optimizer of the parking agent can run a genetic algorithm. The optimizer computes the corresponding fitness value of each proposed parking according to the remaining energy of vehicle, the distance between vehicle and proposed parking, and waiting and parking time. In this experiment, the total number of parking place that can be served is set to 100.

When the vehicle agent sends a request to all station agents which are its neighbors, each parking agent can execute its genetic agent to define the optimal response, according to the parameters of vehicle agent as the distance, parking time demanded, and the maximum waiting time. This data is sent by the vehicle agent. It had the possible parking configurations distributed in the city. In this work, we use the Euclidean distance to measure the distance between the actual position of the vehicle and the demanded parking. Also, the parking agents can be cooperated and negotiated to define the final solution.

In Figure 9, we present the waiting time of vehicles when we use the approach without MAS-GA. We observe that the waiting time increases, according to the number of vehicles which demand parking.

Figure 9.

The waiting time of vehicle without MAS-GA.

When we use the approach of optimization with MAS-GA, each parking agent can interact with the other parking agents, and also it can perform its genetic algorithm to discover the optimal solution. We observe that the waiting time of vehicle decreases over the generation number. Figure 10 shows the experimental results.

Figure 10.

The waiting time of vehicle with MAS-GA.

What is clear from Figure 10 is that by using multi-agent system and genetic algorithm, the waiting time of vehicles is decreased in a few generations and in significantly less time than the approach without MAS-GA. For the MAS-GA approach, after 600 generations, the maximum expected waiting time achieved by Experiment 02 is less than 87 seconds, whereas the maximum expected waiting time achieved by Experiment 01 was rapidly augmented. Thus, the MAS-GA approach used in Experiment 02 converges to their optimal solution significantly faster than the other solutions presented in Experiment 01.

9. Conclusion

In this paper, we present a hybrid approach to control and manage an intelligent parking. Thus, we should find the available and adaptable parking according to the distance between the position of the vehicle and the proposed parking, the remaining energy of the vehicle, and waiting and the parking time. The experimental results show that our proposed approach can rapidly find the optimal parking compared with the other approaches. Also, when we use the MAS-GA approach, the revenues will be maximized.