An Algorithm of Parking Planning for Smart Parking System
Xuejian Zhao Kui Zhao Feng Ha









An Algorithm of Parking Planning for
Smart Parking System
    Xuejian Zhao
Wuhan University

Hubei, China

Email: xuejian_zhao@sina.com
Kui Zhao
Zhejiang University

Zhejiang, China

Email: zhaokui@zju.edu.cn
Feng Hai
Wuhan University

Hubei, China

Telephone: (+86) 027-68753031

    December 30, 2023
==============================================================================================================================================================================================================================




There are so many vehicles in the world and the number of vehicles is increasing 
rapidly. To alleviate the parking problems caused by that, 
the smart parking system has been developed. The parking 
planning is one of the most important parts of it. An effective 
parking planning strategy makes the better use of parking resources possible. 
In this paper, we present a feasible method to do parking planning. 
We transform the parking planning problem into a kind of linear assignment problem. 
We take vehicles as jobs and parking spaces as agents. 
We take distances between vehicles and parking spaces as 
costs for agents doing jobs. Then we design an algorithm for this particular assignment problem
and solve the parking planning problem. The method 
proposed can give timely and efficient guide information to vehicles for 
a real time smart parking system. Finally, we show the 
effectiveness of the method with experiments over some data, 
which can simulate the situation of doing parking planning in the real world.






§ INTRODUCTION

There are so many vehicles in the world, especially in China. 
According to the annual report presented by J. Wang
<cit.>, there are almost one 
billion private cars in China till 2013. In other words,  
there are 20 private cars per 100 families. By contrast, 
the parking resources are too limited. Taking Beijing as an 
example, in 2013, there are 4.075 million private cars, but the number of 
parking spaces is only about 1.622 million
[http://www.gov.cn/gzdt/2013-04/10/content_2374428.htm].
That is to say, on average, each private car has only 0.398 parking spaces. 
If we take other types of vehicles into consideration, the situation will get 
worse with no doubt. The problem can be alleviated via many methods. But in 
this paper we focuse on the smart parking system, primarily on 
the algorithm of parking planning.


 §.§ Related Work

T. Litman<cit.> presents a comprehensive implementation guide 
on parking management, including parking planning practices.
The study of M. Idris<cit.> reviews the evolution of parking space 
occupancy detection. The detection technology makes the status of the parking space 
available for the parking management system. 
S. Zeitman<cit.> invents a communication system for the 
parking management system. They provide a method to establish communication 
between municipality, driver and parking spaces. S. Shaheen<cit.> 
documents the research and feasibility analysis for the 
design and implementation of parking management field test. Their report gives 
a description of the parking field test and its technology in detail. 
R. Lu<cit.> provides a solution for smart parking scheme through taking advantage of communication 
between vehicules. Our method is different since we study the problem of processing 
parking planning on a real time smart parking system, then sending the guide information to vehicles.


 §.§ Contributions

In this paper we present an algorithm to process parking planning for a 
real time smart parking system. First, basing on some limiting conditions in 
the real world, we transform the parking planning problem which is an on-line 
problem into an off-line problem. 
Second, we establish the mathematical model by regarding this off-line problem 
as a kind of linear assignment problem.  
Third, we design an algorithm to solve this particular linear assignment problem. 
Last, we evaluate our algorithm by some simulation experiments. 
The experimental results show that our method is both timely and efficient.

Outline The remainder of this paper is organized as follows. 
In Section 2 we describe the parking planning 
problem with mathematical model. In Section 3 we 
present the details about the method of parking planning. 
In Section 4 we present the experimental 
evaluation of the method. Finally, in Section 5 
we conclude and outline some prospects for future work.



§ ESTABLISHING MATHEMATICAL MODEL

The smart parking system receives parking queries one by one. 
If the smart parking system processes each parking 
query immediately when it arrives, the problem to be solved is an on-line problem. 
We can solve this on-line problem easily through greedy method. For instance, 
we guide the vehicle, which is querying parking space, to the nearest available 
parking space. The experimental results presented in 
Section 5 reveal greedy method is very 
inefficient in some situations and that makes it less feasible. 

In order to make parking planning strategy be efficient in most situations, instead of processing it immediately 
we hold parking queries in a queue for a while and the number of queries we hold is a controllable parameter. By transforming 
the on-line problem into an off-line problem, we get more information and 
then we can get efficient solution in most situations. 
Let P denote the set of all vehicles having parking query in the queue. 
Let S denote the set of all available parking spaces included in the smart parking system. 
Let D denote the set of d_ij, and d_ij is the distance between the 
vehicle p_i(p_i∈P) and the parking space s_j(s_j∈S). 
We can achieve D through many methods, such as GPS<cit.>. 
Let M and N be the size of P and S, respectively. 
So the size of D is M×N. 

We take vehicles as jobs and parking spaces as agents. 
We take distances between vehicles and parking spaces as costs for agents 
doing jobs. We save the solution in X where x_ij∈X. That is, 

    x_ij={[                                0,                                   if p_i will not be guided to s_j;;                                1,                                       if p_i will be guided to s_j. ].


Let C be the total cost for all vehicles in P going to the parking spaces 
assigned to them by the smart parking system. That is, 

    C=∑_i=1^M∑_j=1^Nd_ij×x_ij.


We aim to make C minimum on condition that each vehicle gets exactly one parking 
space and each parking space can be assigned to only one vehicle at most. That is, 

    {[  ∑_i=1^Mx_ij=1;                ; ∑_j=1^Nx_ij≤ 1.                 ].


This optimization problem is a linear assignment problem. 



§ PROCESSING PARKING PLANNING

When M is equal to N, the well-known Hungarian method<cit.>, proposed by 
H. W. Kuhn in 1955, can solve this optimization problem. 
The time complexity of that is O(N^4). 
In 1971, N. Tomizawa<cit.> improved it to achieve 
an O(N^3) running time. We describe the latter one as 
Algorithm <ref> without detailed steps. 

In Algorithm <ref>, D_N×N is the distance square matrix and 
we save the solution in X_N×N.
The space complexity of Algorithm <ref> is O(N^2). 





 §.§ Available Parking Spaces are Enough

In most situations, the available parking spaces are enough to satisfy all parking queries 
in the queue. That is to say, M and N satisfy M≤ N. In fact, 
M and N satisfy M≪N in most situations. 

We can simply extend P to P' by adding N-M virtual vehicles. 
At the same time, we extend the old distance matrix D_M× N 
to a new distance square matrix D'_N×N by 
setting all distances between virtual vehicles and 
parking spaces zero. If we have d'_ij∈ D'_N× N, that is,

    d'_ij={[                      0,                         if p_i'∈ P' and p_i'∉P;;                   d_ij,                                      otherwise. ].


We can solve this new problem by running  
Algorithm <ref> on D'_N× N. 
H. W. Kuhn proved that the solution of this new problem includes the solution 
of the original one<cit.>. However, the value of N is always 
very large. In practice, the value of N is almost certainly in the millions. 
Because its time complexity is O(N^3), the time consumed by Algorithm <ref> 
is too long for a real time smart parking system. 

If we notice that the value of M is always small and its upper bound is 
under our control, we can design an approximation algorithm to solve the original 
problem. First, we select a subset of S, denoted S'. Second, 
we extend P to P' which has the same size with S' by adding virtual vehicles. We construct 
a new distance matrix D' between P' and S'. Finally, we run 
Algorithm <ref> on D' and convert the result into final solution. 



  §.§.§ Construct the Set S'

Let SUB_i be the top M nearest available parking spaces for p_i. We construct the set S' from the union of 
SUB_i (1≤i≤M). That is, 

    S'=⋃_i=1^MSUB_i.

We describe it as Algorithm <ref> in detail. 

In Algorithm <ref>, P represents the set of vehicles that 
have query in the queue and D_M×N is the original distance matrix. 
We save the subset in S' picked from S, denoting the set of all available parking spaces. 
For each vehicle in P, we save the top nearest M available parking spaces 
in S-Set temporarily. To the best of our knowledge, 
we can get the top M nearest available 
parking spaces by using Heap, which is a common and useful data structure. 
The time complexity of it is O(MN+Mlog_2N).
We check whether s_j has been in S' or not by using Hash method. 
The time consumed by that is constant, thus it can be omitted. 
So the the total time cost by Algorithm <ref> 
is O(MN+M^2log_2N). The space complexity is O(N+M^2). 





  §.§.§ Extend P to P' and Construct D'

Let N' be the size of S' and we extend P to P' by adding N'-M virtual 
vehicles. The distances between virtual vehicles and parking spaces in S' 
are all zero. We describe the method of constructing D' in 
Algorithm <ref>. 

In Algorithm <ref>, S' is the subset picked from the set of all available 
parking spaces by algorithm <ref>, D_M×N is the original distance matrix. 
We save the new distance square matrix in D'_N'× N'. We use MAP_P to 
map the row index in D'_N'× N' to the vehicle in P'. 
We use MAP_P to map the column index in D'_N'× N' to the parking space in S'. 
They help us to construct the new distance square matrix D'_N'× N'. 
The time complexity of Algorithm <ref> 
is O(MN') and the space complexity is O(N'^2). 
If we notice O(N')=O(M^2) and substitute it into O(MN') and O(N'^2), 
the time and space complexity are O(M^3) and O(M^4), respectively.

 



  §.§.§ Get the Final Solution

First, we run Algorithm <ref> on D'_N'× N' and save its solution 
in X_N'×N'. It costs O(N'^3) running time 
and O(N'^2) running space. If we notice O(N')=O(M^2) and substitute it 
into O(N'^3) and O(N'^2), the running time and space are O(M^6) and O(M^4), respectively. 
Because N'≥M is obviously always right, the solution X always exists. 
Let X' be the final solution for the original problem. We can construct X' from X 
by the method shown in Algorithm <ref>. 

In Algorithm <ref>, M is the number of vehicles 
in set P, MAP_P and MAP_S are used to map the index in D'_N'× N', 
X_N'×N' is the temporary solution from Algorithm <ref>.
We save the final solution in X'. The time complexity of 
Algorithm <ref> is O(MN') and the space complexity is 
O(M). If we notice O(N')=O(M^2) and substitute it into O(MN'), 
the time complexity is O(M^3). 



The total running time and space to process parking planning in most solutions  
are O(MN+M^2log_2N+M^6) and O(M^4), respectively. 
Because M and N satisfy M≪N in most situations, 
the method proposed by us is much better than the naive Hungarian Method, 
whose running time and space are O(N^3) and O(N^2), respectively. 
In practice, the size of S' denoted by N' is very close to M rather than M^2. 
This implied fact makes the method we proposed more efficient than what it looks like on the level of theory. 
We will show more details about that in Section 4.



 §.§ Available Parking Spaces are Not Enough

In a few situations, the relation between M and N is M>N. In other words, 
the available parking spaces are not enough to satisfy all queries in the queue. 
In order to distribute parking spaces 
fairly, we should follow the principle of first come first served. 
So we select the top N parking queries in the queue and assign the N available parking spaces 
to them using Algorithm <ref>. Because the 
value of M is always small and M and N satisfy M>N, the value of N is also small in this situation. 
So we can get the result from Algorithm <ref> quickly enough in this special situation.
Moreover, we will respond the other M-N parking queries with the information that there are 
no more available parking spaces. 



 §.§ Relation with Greedy Method


We notice that our method covers the greedy method. When we set M=1, 
our method is exactly the greedy method. However, 
the greedy method is very inefficient in some situations.
When we set M a right value, our method is efficient in most situations. 
We will see that our method is controllable and 
that point makes it more feasible than the simple greedy method. 



§ EXPERIMENTAL EVALUATION OF THE ALGORITHM

We simulate different situations of parking planning in the real world by 
constructing different distance matrices D_M× N. Because the running space is 
not a critical problem for any method, we put our attentions on the efficiency and 
running time of the algorithm. 



 §.§ Efficiency of Our Method

The new method proposed by us is an approximation algorithm. So the total cost C 
will be a little higher than the global optimal solution. We run our method on many different 
distance matrices and calculate an average. Fig.1. shows the result we have got. 


It can be seen from Fig.1. that 
the more parking queries we hold the less waste our method has. 
When M and N satisfy M≪N, the waste of our method is less than 11%. 
It is proved that our method is efficient enough for a real time smart parking 
system. 



 §.§ Running Time of Our Method


We run our method on an old personal laptop. The CPU of it is 
Intel(R) Core(TM)2 Duo CPU P8800 @ 2.66GHz and the memory of it 
is Kingston(R) 8.00 GB @ 1066MHz. We set the value of N as 1.6 million 
to simulate the situation of parking planning in Beijing. We run our method on many 
different distance matrices and record the average running time in
TABLE 1 in seconds. 
As we can see, our method is quick enough for a real time smart parking system. 



TABLE 1 and Fig.2. also tell 
us that if we want to get results more quickly we should 
hold as few parking queries as possible.

In the real world, one parking place often has many available parking spaces. 
For instance, the number of parking spaces in each parking place in Beijing is about 3 hundred. 
As we can see from Fig.3., such clustering phenomenon makes N', the size of S', 
very close to M and very far away from M^2. So the time complexity 
of our method is close to O(MN+Mlog_2N+M^3) rather than O(MN+M^2log_2N+M^6). 
This gives us the reason why the running time taken by our method 
in practice is much less than what it looks like in theory.





Above all, our method can give timely and efficient solutions 
for a real time smart parking system on condition that we choose a right value for M. 



 §.§ How to Choose the Best Value for M

Although a small value for M makes it possible for our method to get solutions quickly, 
it may also lead our method to the annoying instability. In other words, 
our method with an extremely small M is very inefficient in some special situations.

To be specific, we construct a special distance matrix D as an example. 
When we set M=1, our method is exactly the greedy method, 
the total cost of it to do parking planning is 50069. When we set M=2, the total 
cost  is 23549. When we set M=3, the total cost is 8525. When we set M=N, 
that is 6, the total cost is 209, which is the minimum cost in theory. 
This example helps us to illustrate that the value of M should not be too small if we 
want the algorithm to be efficient in most situations. 

    D=
    ( 
       1    2    3    4    5    6 
    
       1    4    9    16    25    36 
    
       1    8    27    64    125    216 
    
       1    16    81    256    625    1296 
    
       1    32    243    1024    3125    7776 
    
       1    64    729    4096    15625    46656 
    )


From the above, when we try to choose the best value for M, we should take the waste, running time and 
stability into consideration based on the real situation. 


§ CONCLUSION

We have presented a novel method of parking planning for smart parking system.
We transform parking planning into a kind of linear assignment problem by holding parking queries in a queue for a while. 
We develop a new approximation algorithm to solve this particular linear assignment 
problem. The experimental results on simulation clearly show our method is a feasible 
method which can give timely and efficient solutions for a real time smart parking 
system. 

As future work, we consider to develop methods to get an adaptive number of parking queries holden in the queue, which is denoted by M.  
We also consider to find ways to construct the subset of available parking spaces denoted by S' more effective. For example, we can decide 
the value of M according to the operation of the smart parking system and the 
historical parking data. We can try to find new ways to construct better S' 
to reduce the waste and running time. All of them may also help to improve the stability. 










IEEEtran


