Smart Parking Management and Planning Based on Chinese Postman Problem

Longbin Sun^*, Yifei Wei, Mingzhe Li, Changyuan Chen, Miaomiao Yang

School of Mathematics and Statistics, Qilu University of Technology (Shandong Academy of Sciences), Jinan, China.

DOI: 10.4236/jss.2022.1013021                

Abstract

This paper discusses the practicability of the charging for the video collection vehicle in the city of Jinan in China. Firstly, according to the collection vehicle and the charge standard, we have constructed a price loss function for the single parking space and used the method of Chinese postman problem to analyse the parking spaces in the whole area, then obtained the best route by Fleury algorithm which is compared with manual charging at last.

Keywords

Smart Parking, Chinese Postman Problem, Fleury Algorithm

1. Introduction

With the rapid development of China’s economy and society, urban static traffic construction, as a major livelihood project, has become a pain point and difficulty restricting China’s urban development to solve the parking problem. As of December 2019, the total number of motor vehicles in Jinan is 2.8553 million. At present, there are only 1.14 million public parking spaces in the city, and the gap of parking spaces in the core area of Jinan has reached more than 1 million (Chen, 2021). In order to solve the problem of insufficient parking spaces, in addition to parking lots, some road sections are also used for roadside parking time charging. The research on on-road intelligent parking in China (Zhen, 2022) is relatively late in development. In most areas, parking spaces are divided by experience method and charging standards are formulated, and manual hourly charging is adopted. In some areas, many schemes such as parking meter charge (Chen et al., 2014), high and medium video pile charge, geomagnetic charge (Hai, 2022), parking lock charge (Zhang, 2017), intelligent parking charge based on “Internet Plus” (Zhang et al., 2017) are adopted. However, there are few literatures on the scheme of using video capture vehicle. This method can effectively improve the turnover rate of parking space and alleviate the problems of “difficult parking” and “disorderly parking” to some extent (Ning, 2022). Based on the situation of Jinan City, the relevant mathematical model is established from the theoretical level, and the feasibility of this method is discussed by comparing with the traditional manual time charge method.

Billing of mobile video capture vehicle: The capture vehicle drives from the left side of the parking space, uses the camera placed on the roof to collect and identify the license plate information of the parked vehicle, and records the time tag. The principle of timing is accurate timing and less timing. The time is counted from the time when the license plate is first collected to the time when the license plate is last collected. The collection vehicle will collect for many times, calculate the total parking time, charge the vehicle and notify the owner.

Manual time charge: In the manual billing area, the manager will take photos when parking, and when the vehicle is about to leave, the manager will take photos again, and the parking time will be calculated and charged.

2. Problem Analysis

At present, the bottom technology of intelligent parking, including positioning, identification, flow distribution and so on, is not the focus of this paper. Since the current specialized parking lots cannot meet the market demand, a large number of open environments have become an important supplement to urban parking. As there is no effective automatic charging method, the operation cost is high or the charging cannot be carried out, resulting in the income waste of urban resources. Based on the road traffic conditions and charging conditions of Jinan City (Table 1) and other factors, this paper will give the loss function of mobile capture vehicle in different tour cycles compared with manual time charge for a single parking space, and then obtain the average loss of vehicles.

For one region, we can take this problem as the Chinese postman problem. The best route can be obtained by Fleury algorithm and compared with manual

Table 1. Jinan roadside charging standard.

time charge. And then we can get the optimal strategy.

3. Amount Loss Function Modeling of Single Parking Space

This paper analyzes the Class I area which charges by the minute. It is possible to assume that the video capture vehicle takes one round as a fixed time T and the actual parking time is t. According to Table 1, the actual charging standard of the first type of area can be expressed as follows $q_1\left(t\right)$.

$q_1\left(t\right)=\{\begin{array}{l}2\lceil \frac{t}{30}\rceil ,0\le t\le 60;\\ 4+3\lceil \frac{t}{30}\rceil ,60<t\le 720.\end{array}$ (1)

Now we will connect the tour time of the video capture vehicle and the actual parking time. If the parking time is equal to or greater than the tour time of the video capture vehicle, it can be detected at least once. Based on this principle, a billing duration $k\left(t\right)$ can be obtained by multiplying the detected times by the tour time of the video capture vehicle, which represents the parking time recorded by the video capture vehicle

$k\left(t\right)=\left[\frac{t}{T}\right]T.$ (2)

When the video capture vehicle arrives at the parking space again for taking photos, if the vehicle captured this time is not the same as the one last time, it can be considered that the parking time of the last vehicle is $k\left(t\right)$. Then we can calculate the actual charge $q_2\left(t\right)$ by Table 1.

$q_2\left(t\right)=\{\begin{array}{l}2\lceil \frac{k}{30}\rceil ,0\le k\left(t\right)\le 60\\ 4+3\lceil \frac{k}{30}\rceil ,60<k\left(t\right)\le 720\end{array}$ (3)

Because of the less timing principle, the charging duration obtained is also the minimum duration, which should be less than or equal to the actual parking duration. Soone can get the amount loss $Q\left(t\right)$ :

$Q\left(t\right)=q_1\left(t\right)-q_2\left(t\right).$ (4)

Taking T as 10, 30 and 60 minutes respectively, we can find the comparison between the video capture vehicle and the manual billing loss under different tour cycles is obtained (Figure 1). And we also can find that the shorter the tour time of the video capture vehicle is, the closer its charge is to the real charge, and the less the loss amount is. This is in line with the actual situation, because when the tour time of the video capture vehicle gets shorter, the probability of the vehicle being photographed will increase. When the tour time is close to 0, it is equivalent to manual charging. Of course, if the road traffic congestion is taken into account, the actual tour time T is not very small. And it can be found that the loss amount is cyclical from the first hour.

Figure 1. Comparison of video capture vehicle billing and manual billing losses under different tour cycles.

4. Amount Loss Comparison of Regional Charges

4.1. Application of Chinese Postman Problem

Taking the Class I area as an example, the video capture vehicle is considered to conduct tour collection in this area, which can cover all the parking streets and minimize the loss. This problem can be understood as the problem of Chinese postmen (Guan, 1984). A video capture vehicle collecting roadside parking data walks through all the streets, which starts from the starting point and returns to the starting point after completing the task. The key point we have to deal with is what route should be followed to make the shortest distance taken. Assuming that the speed of the video capture vehicle is fixed, it can be seen from the conclusion in the first section that the shorter the tour time is, the smaller the loss is. Then the problem is to find the shortest traversal distance.

Because the two-way roads are considered, we can take roads as edges of a directed graph. Also, since many lanes are narrow and U-turns are forbidden, vehicles have to turn around at intersections, the road intersections can be regarded as intersections of digraphs. It will be shown in Figure 2.

4.2. Fleury Algorithm

For the Chinese postman problem, it is necessary to determine whether it is an Euler chart. If it is not, the odd even diagram operation method (Guan, 1960) can be used to change it into the Euler diagram. The graph in this paper is clearly

Figure 2. Directed graph of a class of regions.

a Euler chart, so the Fleury algorithm can be directly used to find the best itinerary path.

Define 1 Fleury algorithm (Lu, 1980).

Set up $G=\left(V,E\right)$ is one Euler chart. The following is the algorithm flow of Fleury algorithm:

STEP 1 For arbitrary $v_0\in V$, let $C_0=v_0$ ;

STEP 2 Assume that the current vertex $C_i=v_0{e}_1{v}_1{e}_2\cdots e_i{v}_i$ has been reached along the trace $v_i$, we can choose $e_{i+1}$ from the edge $E-\left\{e_1,e_2,\cdots ,e_i\right\}$ set as follows:

1) $e_{i+1}$ associates with $v_i$ ;

2) $e_{i+1}$ is not the cut edge of the graph $G_i=G-\left\{e_1,e_2,\cdots ,e_i\right\}$, unless there are no other optional edges.

STEP 3 Stop the algorithm when STEP2 cannot continue.

If we select v₁ as the starting point, and the label of the optimal itinerant path point is

4.3. Comparative Analysis

Since most of the current areas in Jinan are mainly manual time charge, other methods are less used, so this article mainly compares with manual time charge.

According to our survey, the Class I area includes a large number of restaurants, shopping malls and pedestrian streets. The roadside parking time is about

Table 2. Comparison between video capture vehicle billing and manual time billing.

270 min. So the loss of a carQ (270) can be calculated by the amount loss function in the first section. And there are about 1000 roadside parking spaces on the main roads in this type of area. For workers who charge by hand, one person can manage 10 parking spaces at the same time, and the wages of one worker are about 110 yuan per day. The distance of the tour is 18,160 meters, and the fuel cost is about 0.8 yuan per kilometer. According to these data, the video capture car billing and labor billing costs can be obtained under different tour cycles (Table 2).

5. Conclusion

In this paper, a monetary loss function of video capture vehicle is constructed to obtain the relationship between parking duration and tour duration, and we can find that the shorter the tour duration, the smaller the loss. The problem of different regional charges regions can be taken as the problem of Chinese postmen, and the losses are related to many aspects. Taking the first category of regions in Jinan as an example, this paper analyzes that the losses caused by different tour cycles are also different. Generally speaking, the tour cycle is small and the loss is small, but it is not a simple linear relationship. These are the conclusions drawn under ideal conditions. However, in practice, more uncertain factors will be involved. For example, traffic congestion may make the tour cycle longer, leading to an increase in the amount of loss. Of course, if the appropriate tour cycle is selected, this scheme is also feasible.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Chen, Z. J., Yu, D. J., Zhang, H. Z., & Wu, H. J. (2014). Parking Meter Design Based on Sustainable Design Idea. Packaging Engineering, 35, 34-37, 49. (In Chinese) https://doi.org/10.19554/j.cnki.1001-3563.2014.16.009
[2]	Chen, Z. W. (2021). Study on Parking Management Strategy of Jinan Static Transportation Company. Master’s Thesis, Shihezi University. (In Chinese) https://doi.org/10.27332/d.cnki.gshzu.2021.000411
[3]	Guan, M. G. (1960). Operation Method on Odd Even Point Map. Acta Mathematica Sinica, No. 3, 263-266. (In Chinese)
[4]	Guan, M. G. (1984). A Survey on the Chinese Postman Problems. Journal of Mathematical Research and Exposition, No. 1, 113-119. (In Chinese)
[5]	Hai, T., Li, L., & Li, Y. (2022). Design and Application of the Field Verification Instrument of the Geomagnetic Electronic Parking Time Charging Platform. China Metrology, No. 3, 122-123. (In Chinese) https://doi.org/10.16569/j.cnki.cn11-3720/t.2022.03.011
[6]	Lu, K. C. (1980). Graph Theory and Its Application. Beijing Tsinghua University Press. (In Chinese)
[7]	Ning, J. (2022). Information Acquisition Technology of Urban Road Parking Intelligent Management System. TranspoWorld, No. Z1, 17-19. (In Chinese) https://doi.org/10.16248/j.cnki.11-3723/u.2020.z1.006
[8]	Zhang, C. J., Li, G. D., Gao, F., Shi, C., & Zhu, S. N. (2017). The Study of a City Smart Parking Mode Based on “Internet Plus”. Bulletin of Surveying and Mapping, No. 11, 58-63. (In Chinese) https://doi.org/10.13474/j.cnki.11-2246.2017.0348
[9]	Zhang, R. Z. (2017). Research and Design of Shared Parking Management. System Based on the Intelligent Parking Lock. Master’s Thesis, Shandong University. (In Chinese) https://kns.cnki.net/KCMS/detail/detail.aspx?dbname=CMFD201702&filename=1017081395.nh
[10]	Zhen, W. Q. (2022). Overall Thinking of Urban Smart Parking Project Construction. China Security & Protection, No. 7, 61-66. (In Chinese)