Anti-Congestion Route Planning Scheme Based on Dijkstra Algorithm for Automatic Valet Parking System

Featured Application

This anti-congestion route planning scheme will be used in the automatic valet parking area. It will have outstanding performance in the combination technology of V2X environment and driverless technology.

Abstract

Based on the Dijkstra algorithm, with the parking parameters in the static state, the shortest route to each parking space of the parking lot without dynamic influence factors can be calculated. In the new technology background of the combination of the V2X environment and driverless technology, the dynamic influence factors, for example, the lanes occupancy situation caused by parking, can be considered to improve the shortest route with the new scheme in this paper. Then the final route that costs the least time to reach each parking space will be calculated. This is very important for the development of the intelligent transportation system in the parking lot environment.

1. Introduction

Valet parking technology is a service that can help people park their vehicles without any drivers’ operation [1,2]. It was born based on automatic parking [3,4], and combines the advantages of automatic parking technology and driverless technology [5,6,7,8]. The user only needs to drive the vehicle to the designated drop-off area of the parking lot. After getting off the vehicle, the vehicle will go to the designated parking space for parking. People do not need to find the parking space on their own in the complex parking lot environment. The technology also can solve the parking problem for some drivers if they have trouble parking, because the vehicle is controlled by the system. The parking lot does not need to prepare much driving space for drivers with poor driving skills, because the driving and parking processes are all controlled by the system, so more parking spaces can be arranged in the same area.

In the existing intelligent parking lot guidance systems, vehicles are all controlled by human drivers, so the condition of the parking lot cannot be predicted accurately. It is very hard to plan the route line based on real-time conditions. Road congestion is likely to occur when the traffic volume is large.

In our research, we used the Dijkstra algorithm as a basic tool [9,10,11,12]. It is a kind of shortest path algorithm. This algorithm has been used in many areas, such as the pathfinding applications designed by Balado, the distribution network optimization problem solved by Binh, or the fuel economy area studied by Xu [13,14,15]. Shakhovska created a conceptual model of a tourists’ guide system [16]. They took the duration of switching traffic lights into account and did further research on time dimension based on the Dijkstra algorithm. In fact, many researchers have made the similar attempt in the parking lot guidance system, such as a route planning scheme for a parking lot designed by Ge et al. or a parking guidance algorithm proposed by Yuan [17,18].

Their researches saved a lot of time for vehicle costs on the road, but the uncertain factors of human drivers will bring many errors into the system. They will not be suitable for the automatic valet parking system.

In the automatic valet parking system, the parking lot is implemented in the V2X environment [19,20,21]. In the V2X environment, vehicles can exchange information with other vehicles or infrastructures based on vehicle networking. Also, all the vehicles in the parking lot are all controlled by the base station. Real-time road information in the parking lot, such as the vehicle’s driving route, parking time, etc., can be transmitted through the communication network to the base station. The information is used for the parking lot control system to perform the calculation of the parking space allocation and route planning of the subsequent vehicles [22].

The combination of the V2X environment and driverless technology is a big breakthrough in valet parking technology. It has been a great help in making sure of the real-time condition and predicting future conditions in the parking lot. Based on the Dijkstra algorithm and combined with the dynamic influence factors of the valet parking lot, this paper designed a route planning scheme to reach each parking space in the shortest time for an automatic valet parking lot.

The contributions of this paper are described as follows:

1. The combination of the V2X environment and driverless technology has been a great help in making sure of the real-time condition and predicting future conditions in the parking lot. This paper designed a method to transform the dynamic influence factors in the parking lot into data based on the new technology for further calculation.

2. Based on the obtainment of the high-precise data in the new technology environment, this paper designed a route planning scheme to reach each parking space with the shortest time. This scheme is suitable for a driverless parking lot. It has been a great help in reducing the congestion of the automatic valet parking lot.

2. Research Status

In the middle of the nineteenth century, the first mechanized parking system was based on the vertical Ferris wheel, which effectively solved the problem of stacking vehicles in limited space. Since then, the same system has been used extensively in the United States, Asia and Europe [23].

In 2006, Beinhaker et al. designed a routing system. This system can forecast traffic conditions to some extent, but the vehicles are all driven by people, so the accurate driving time for each vehicle cannot be calculated.

In 2011, Liu et al. designed a model of the large parking lots guidance information system. It mainly uses the ant colony optimization to design the paths for parking space guidance. Ant colony optimization is a good way to find the shortest path from the start point to the end. However, the algorithm only considers the distance of the route. There is a great possibility that vehicles will line up in the same short way and wait for a long time [24].

Wang et al. presented a new system for intelligent navigation inside a parking lot in 2015 [25]. After modeling the parking lot with a time-varying graph, the proposed system applies a time-varying shortest path algorithm and dynamically tunes arc transit times based on planned vehicle routes as well as traffic flow sensor data. The proposed system showed an improvement of about 40% in travel time when compared with a system that only applies the conventional Dijkstra algorithm. But the differences in driving skills of human drivers bring a lot of errors to the system. It will not be a good choice for a driverless parking lot.

In early 2015, the high-tech Internet company AIpark began to develop intelligent parking systems [26,27]. Under the intelligent parking lot control system developed by the company, the driver only needs to drive into the parking lot. The parking lot can automatically identify the license plate, guide the car to the empty parking space and plan the route. The technology solves the parking problem to some extent [28,29,30,31]. It is a relatively complete model of the intelligent parking guidance system. However, since the vehicle is driven by the driver, the intelligent parking system cannot control the vehicles’ speed and the actual driving route. It makes the guiding route planning of the following vehicles difficult.

On 14 September 2018, the automatic valet parking technology jointly developed by Daimler and Bosch was exhibited in Beijing [32]. In the underground parking lot of the Mercedes-Benz passenger car China R&D center, two Mercedes-Benz E63s were used for valet parking operation at the same time. The two-lane dual-vehicle synchronous valet parking process was successfully realized. After the vehicle enters the parking lot, vehicle control is handed over to the parking lot [33,34]. As shown in Figure 1, single-line light detection and ranging systems (Lidars) are placed in the parking lot. They are mainly used to sense the accessible areas and obstacles in the parking lot [35], so as to control the vehicle for emergency braking or winding in time.

The appearance of this technology can make the vehicles in the parking lot completely controlled by the base station. It reduces the occurrence of unexpected situations. However, in terms of route planning, the system cannot adjust the route according to the real-time road conditions in the parking lot, and it is prone to occur congestion when facing large traffic.

Therefore, it is meaningful to avoid congested roads in the process of route planning. In the new technology background of the combination of the V2X environment and driverless technology, we did research on how to design the route to reach each parking space with the least time based on the real-time working conditions in the parking lot.

3. Dijkstra Algorithm

The Dijkstra algorithm was proposed by Dutch computer scientists in 1959 [14,15]. It is a kind of shortest path algorithm used to calculate the shortest path from one node to another. The main idea of the algorithm is similar to the breath-first search.

3.1. Algorithm Principle

Divide the vertex set $V$ into two groups:

(1)

$S$: The set of vertices that have been determined (initially only contains the origin point $V_0$)

(2)

$V-S=T$: set of vertices that have not yet been determined

Add the vertices in $T$ to $S$ in ascending order to ensure:

(1)

The length from $V_0$ to the other vertices in the $S$ is not longer than the shortest route length from $V_0$ to any vertices in $T$.

(2)

Each vertex corresponds to a distance value

Vertices in $S$: the length from $V_0$ to the vertex

Vertices in $T$: the shortest route length from $V_0$ to the vertex that only include the vertices in $S$ as the middle vertices

3.2. Algorithm Demonstration

(1) Point A is the starting point, allocated in the set $S$, and the remaining points are allocated in the set $T$.

(2) Initializing, except for the starting point A, the weights of all nodes are set to infinity. As shown in Figure 2a.

(3) Updating the distance of the A’s adjacent point. Since the weight of AB is 2, the value of Distance (B) is updated to 2. Similarly, the value of Distance (D) is updated to 1. As shown in Figure 2b.

(4) Moving the point with the minimum weight to the set $S$. The value of Distance (D) is 1, so move the D point to the set $S$.

(5) Calculating the weights of the adjacent points, starting from point D. The weight is equal to the distance of AD plus the weights of point D to its adjacent point. Distance (C) = 1 + 2 = 3, Distance (E) = 1 + 2 = 3, Distance (F) = 1 + 8 = 9, Distance (G) = 1 + 4 = 5. As shown in Figure 2c.

(6) In all current nodes, node B with the minimum weight (Distance (B) = 2) is moved to set $S$ and the weights of its adjacent points are updated.

(7) And so on, each time the node’s weights are updated, the node with the minimum weight is moved to set $S$, and the node with the minimum weight is used as the starting point to update the weights of its adjacent nodes until all the nodes are moved from set $T$ to set $S$. After that, the current value of each node is the minimum weight from point A to itself, as shown in Figure 2d.

4. Anti-Congestion Route Planning Based on Dijkstra Algorithm for Valet Parking System

In the valet parking scenario, the vehicle can obtain real-time conditions in the parking lot from the base station [36]. Based on the Dijkstra algorithm, this scheme combines the parking lot map information and the dynamic influence factors in the parking lot to plan the route to each parking space which costs the least time.

The specific program steps are as follows:

(1)

Obtaining the parking space, road information map of the parking lot and the prescribed speed of the vehicle in the parking lot.

(2)

According to the signal transmitted by the parking space geomagnetic sensor [37], the free parking space is confirmed. The parking lot entrance, the free parking space and the crossroads inside the parking lot are set to be nodes. Then connect them to their adjacent nodes to construct an undirected graph with weights.

(3)

Based on the undirected graph with weights, the adjacency matrix composed of the weights between nodes is shown in Equation (1). The value of the diagonal of the matrix is 0. The values of adjacent nodes are the distances between them, and the remaining values are endless.

$$\left[\begin{array}{ccccc}0& D_{12}& D_{13}& \dots & D_{1n}\\ D_{21}& 0& D_{23}& \dots & D_{2n}\\ D_{31}& D_{32}& 0& \dots & D_{3n}\\ \dots & \dots & \dots & \dots & \dots \\ D_{n1}& D_{n2}& D_{n3}& \dots & 0\end{array}\right]$$

(1)

(4)

Using this matrix as the data source of the Dijkstra algorithm, and calculating the shortest distance and the shortest route from the entrance to each parking space.

(5)

In the V2X environment of the valet parking lot, real-time dynamic influence factors (remaining parking time of the vehicle, the position of the moving vehicle and its driving route) can be obtained and then take them into consideration.

(6)

After the vehicle owner finishes the selection of the parking space, checking the driving route to the parking space planned in step 4. Making sure that if there is any dynamic influence factor mentioned in the route in step 5.

(7)

Updating the corresponding matrix values between the nodes lie in the two ends of the road which contains the dynamic influencing factors, and then re-calculating with the Dijkstra algorithm.

If there is a car parking in the route, the corresponding matrix value between the two nodes is updated as follows:

(1)

Calculating the time $t_0$ that the current vehicle costs to reach the occupied parking space based on the distance $d_1$ from the starting point to the parking space.

(2)

Comparing the $t_{0 }$ with the parking space’s occupied time $t_1$. If $t_0>t_1$, it means that when the current vehicle arrives at the occupied parking space, the parking vehicle has completed parking, and the corresponding matrix value between the two nodes does not need to change. If $t_0<t_1$, it means that when the current vehicle arrives at the occupied parking space, the parking vehicle does not complete parking, then the corresponding matrix value between the two nodes is calculated according to Equation (2).

$$D=\left(t_1-t_0\right)·v_0+D_0$$

(2)

If there is an allocated parking space in the route and the vehicle pairing with the parking space is driving toward the parking space, the corresponding matrix value between the two nodes is updated as follows:

(1)

Calculating the time $t_0$ that the current vehicle costs to reach the allocated parking space based on the distance $d_1$ from the starting point to the parking space.

(2)

Calculating the time $t_2$ that the vehicle pairing with the parking space costs to reach the parking space based on the distance $d_2$ from the current location of the vehicle to the parking space.

(3)

Comparing $t_0$ with $t_2$. If $t_0<t_2$, it means that when the current vehicle arrives at the allocated parking space, the vehicle pairing with the parking space has not arrived at the allocated parking space, and the corresponding matrix value between the two nodes does not need to change. If $t_0>t_2$, it means that when the current vehicle arrives at the allocated parking space, the vehicle pairing with the parking space has reached the parking space and starts automatic parking, then the corresponding matrix value between the two nodes is calculated according to Equation (3).

$$D=\left[50-\left(t_0-t_2\right)\right]·v_0+D_0$$

(3)

The 50 in the formula means that the most automatic parking systems on the market need to complete the automatic parking in the standard parking space is about 50 s. This is because, when the vehicle in the parking lot does not reach the parking space, the automatic parking system cannot finish the identification of the parking space, the route planning and other processes, so take we 50 s as an estimate of the time required for parking.

(8)

After the matrix value update is completed, the value of the new matrix is brought into the Dijkstra algorithm for calculation, and the new route is obtained from the starting point to reach each parking space.

(9)

Extracting the driving route of the corresponding parking space in the new calculated route result. If the driving route is unchanged or the new dynamic influencing factors do not appear in the new route, the route is selected as the optimal route; if the driving route changes and there is an unconsidered dynamic influencing factor in the new route, the weight of the corresponding road is optimized by the method of step 7 until the driving route is unchanged or there is not any dynamic influencing factor appearing in the new route. Selecting the current route as the optimal route.

The whole process is shown in Figure 3.

5. Simulation

5.1. Simulation Example

(1) The target parking lot which was selected as the simulation prototype is shown in Figure 4. As shown in Figure 5, We have redesigned the parking spaces and roads in the target parking lot according to the Engineering Construction Industry Standard JGJ 100-98.

(2) We have extracted the parking spaces and lanes in Figure 5 as the frame of Figure 6. As shown in Figure 6, we have set a working condition in the parking lot. The solid circles represent the occupied parking spaces and the hollow circles represent the parking lot entrance, free parking spaces, and crossroads.

(3) We have set the hollow circles in Figure 6 as nodes. Then we connected them to their adjacent nodes to construct an undirected graph with weights, as shown in Figure 7.

Based on the undirected graph with weights, the adjacency matrix composed of the weights between the nodes is shown in Equation (4).

$$\left[\begin{array}{ccccccccccccc}0& 13.375& \infty & \infty & \infty & \infty & 11.465& \infty & \infty & \infty & \infty & \infty & \infty \\ 13.375& 0& 1.65& \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & 1.65& 0& 13.19& \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & 13.19& 0& 5.875& \infty & \infty & \infty & \infty & \infty & 11& \infty & \infty \\ \infty & \infty & \infty & 5.875& 0& 5& \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & 5& 0& 5.875& \infty & \infty & \infty & \infty & \infty & \infty \\ 11.465& \infty & \infty & \infty & \infty & 5.875& 0& 11& \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & 11& 0& 3.375& \infty & \infty & \infty & 14.058\\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 3.375& 0& 5& \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 5& 0& 8.375& \infty & \infty \\ \infty & \infty & \infty & 11& \infty & \infty & \infty & \infty & \infty & 8.375& 0& 12.656& \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 12.686& 0& 10.054\\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 14.058& \infty & \infty & \infty & 10.054& 0\end{array}\right]$$

(4)

(4) Using this matrix as the data source of the Dijkstra algorithm, and calculating the shortest distance and the shortest route from the entrance to each parking space. The result is shown in

Table 1. Shortest route and distance from the starting point to each parking space.

Parking Space Number	Route	Distance/m
Parking Space 2	1→2	13.375
Parking Space 3	1→2→3	15.025
Parking Space 5	1→7→6→5	22.340
Parking Space 6	1→7→6	17.340
Parking Space 9	1→7→8→9	25.840
Parking Space 10	1→7→8→9→10	30.840
Parking Space 12	1→7→8→13→12	47.027
Parking Space 13	1→7→8→13	36.523

.

(5) Setting the dynamic influence factors in the parking lot (the remaining parking time of the vehicle during parking, the moving vehicles’ current position, and their driving routes). The test vehicle speed is set to 5 km/h, which not only ensures the safety of driving in the parking lot, but also satisfies the vehicle’s recognition ability for surrounding parking spaces [38].

Figure 8 means that there are two cars going on automatic parking, the remaining time is 45 s and 50 s, and there is a car in the parking lot, driving to follow the red line to the parking space pointed by the red arrow to start automatic parking.

(6) Selecting the No. 6 node as the target parking space, and the driving route of the No. 6 parking space is 1→7→6.

(7) There is a dynamic influence factor in the driving route of No. 6 parking space. It is a parking space being used for automatic parking, and the required time is 50 s. It means that the lane will be occupied for 50 s, and the weight of the corresponding road in the matrix needs to be corrected. As shown in Equation (5).

$$\left[\begin{array}{ccccccccccccc}0& 13.375& \infty & \infty & \infty & \infty & 11.465& \infty & \infty & \infty & \infty & \infty & \infty \\ 13.375& 0& 1.65& \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & 1.65& 0& 13.19& \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & 13.19& 0& 5.875& \infty & \infty & \infty & \infty & \infty & 11& \infty & \infty \\ \infty & \infty & \infty & 5.875& 0& 5& \infty & \infty & \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & 5& 0& 5.875& \infty & \infty & \infty & \infty & \infty & \infty \\ 11.465& \infty & \infty & \infty & \infty & 60.479& 0& 11& \infty & \infty & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & 11& 0& 3.375& \infty & \infty & \infty & 14.058\\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 3.375& 0& 5& \infty & \infty & \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 5& 0& 8.375& \infty & \infty \\ \infty & \infty & \infty & 11& \infty & \infty & \infty & \infty & \infty & 8.375& 0& 12.656& \infty \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & \infty & 12.686& 0& 10.054\\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 14.058& \infty & \infty & \infty & 10.054& 0\end{array}\right]$$

(5)

(8) Bring the optimized adjacency matrix into the Dijkstra algorithm for calculation, and obtain a new driving route 1→2→3→4→5→6. There are not any other influencing factors in the new route, so this new route is the optimal route from the entrance of the parking lot to the parking space.

5.2. Simulation Analysis

In the target parking lot scene, three kinds of parking lot conditions with different dynamic factors are selected to do the simulation. The test vehicle speed is set to 5 km/h.

Scene 1:

As shown in Figure 9, there are two cars going on the automatic parking. The remaining time is 45 s and 20 s. In addition, there are two cars in the parking lot driving to follow the red lines to the parking spaces pointed by the red arrows to start automatic parking.

The initial driving route of each parking space is shown in

Table 2. Initial driving route of each parking space.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→2	3.375	2.430
Parking Space 3	1→2→3	10.875	23.600
Parking Space 4	1→2→3→4	15.025	26.588
Parking Space 6	1→8→7→6	24.840	62.125
Parking Space 7	1→8→7	14.840	10.685
Parking Space 10	1→8→9→10	33.340	71.845
Parking Space 12	1→8→9→13→12	47.027	52.563
Parking Space 13	1→8→9→13	41.775	48.781

.

The driving route of each parking space under the improved algorithm is shown in

Table 3. Driving route of each parking space under the improved algorithm.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→2	3.375	2.430
Parking Space 3	1→2→3	10.875	23.600
Parking Space 4	1→2→3→4	15.025	26.588
Parking Space 6	1→2→3→4→5→6	24.840	62.125
Parking Space 7	1→8→7	14.840	10.685
Parking Space 10	1→2→3→4→5→11→10	33.340	71.845
Parking Space 12	1→8→9→13→12	47.027	52.563
Parking Space 13	1→8→9→13	41.775	48.781

.

Under the improved planning scheme, the corresponding driving route of parking space No. 6 and parking space No. 10 has changed. The time saved is 23.610 s and 15.192 s, respectively, and the saving time accounts for 38.004% and 21.146% of the original time, respectively;

Scene 2:

As shown in Figure 10, there are two cars going on the automatic parking. The remaining time for each parking process is 50 s. There is also a car in the parking lot driving following the red line to the parking space pointed by the red arrow to start automatic parking.

The initial driving route of each parking space is shown in

Table 4. Initial driving route of each parking space.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→2	5.875	51.800
Parking Space 3	1→2→3	10.025	54.788
Parking Space 4	1→2→3→4	17.525	60.188
Parking Space 6	1→8→7→6	22.340	16.085
Parking Space 7	1→8→7	14.840	10.685
Parking Space 10	1→8→9→10	25.840	18.605
Parking Space 11	1→8→9→10→11	33.340	71.845
Parking Space 13	1→8→9→13	41.775	53.781

.

The driving route of each parking space under the improved algorithm is shown in

Table 5. Driving route of each parking space under the improved algorithm.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→8→7→6→5→3→2	50.555	36.400
Parking Space 3	1→8→7→6→5→3	46.405	33.412
Parking Space 4	1→8→7→6→5→4	40.455	29.128
Parking Space 6	1→8→7→6	22.340	16.085
Parking Space 7	1→8→7	14.840	10.685
Parking Space 10	1→8→9→10	25.840	18.605
Parking Space 11	1→8→7→6→5→12→11	45.090	32.465
Parking Space 13	1→8→7→6→5→12→13	57.153	41.150

.

Under the improved planning scheme, the corresponding driving routes of parking spaces No. 2, No. 3, No. 4, No. 11 and No. 13 have changed. The time saved is 15.400 s, 21.376, 31.060 s, 39.380 s and 12.631 s, respectively, and the saving time accounts for 29.730%, 39.016%, 51.605%, 54.812% and 23.486% of the original time, respectively.

Scene 3:

As shown in Figure 11, there are two cars going on the automatic parking. The remaining time is 45 s and 50 s. There is a car in the parking lot driving to follow the red line to the parking space pointed by the red arrow to start automatic parking.

The initial driving route of each parking space is shown in

Table 6. Initial driving route of each parking space.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→2	13.375	9.630
Parking Space 3	1→2→3	15.025	10.818
Parking Space 5	1→7→6→5	22.340	55.400
Parking Space 6	1→7→6	17.340	51.800
Parking Space 9	1→7→8→9	25.840	18.605
Parking Space 10	1→7→8→9→10	30.840	63.590
Parking Space 12	1→7→8→13→12	47.027	50.672
Parking Space 13	1→7→8→13	36.523	26.297

.

The driving route of each parking space under the improved algorithm is shown in

Table 7. Driving route of each parking space under the improved algorithm.

Parking Space Number	Route	Distance/m	Time Consuming/s
Parking Space 2	1→2	13.375	9.630
Parking Space 3	1→2→3	15.025	10.818
Parking Space 5	1→2→3→4→5	34.090	24.545
Parking Space 6	1→2→3→4→5→6	39.090	28.145
Parking Space 9	1→7→8→9	25.840	18.605
Parking Space 10	1→2→3→4→11→10	47.590	34.265
Parking Space 12	1→2→3→4→11→12	51.901	37.369
Parking Space 13	1→7→8→13	36.523	26.297

.

Under the improved planning scheme, the corresponding driving routes of parking spaces No. 5, No. 6, No. 10 and No. 12 have changed. The time saved is 30.855 s, 23.655 s, 29.325 s and 13.303 s, respectively, and the saving time accounts for 55.695%, 45.666%, 46.116% and 26.253% of the original time, respectively.

5.3. Summary

Under the three conditions of the target parking lot, the improved parking space planning scheme is compared with the parking space guiding scheme based on the Dijkstra algorithm. The guiding routes of some parking spaces do not simply select the route with the shortest length. After taking the dynamic influencing factors into account in the parking lot, the route which takes less time to reach the target parking space is selected.

It means that the study arranges a new way for vehicles. It takes less time to reach their parking spaces. Vehicles will not gather in some short routes without considering the waiting time. It has become a great help in reducing the congestion in the parking lot.

6. Conclusions and Future Research

Because of the appearance of the valet parking technology, people do not need to find the parking space on their own in the complex parking lot environment. The technology also can solve the parking problem for some drivers if they have trouble parking because the vehicle is controlled by the system. The parking lot does not need to prepare much driving space for drivers with poor driving skills, because the driving and parking processes are all controlled by the system. The land use of the parking area will be much more rational.

The combination of the V2X environment and driverless technology is a new attempt in the parking assistance area. It has been a great help in making sure of the real-time condition and predicting future conditions in the parking lot. In this new technology environment, the base station can obtain the current working conditions of the parking lot in real-time. The vehicles in the valet parking lot are all driverless vehicles and the parking spaces are all standard. The speed can also be specified by the base station. These provide the data foundation for the planning scheme of this article.

Under the planning scheme of this paper, the driverless vehicle can avoid the congested roads in the valet parking lot and select the fastest route to reach the target parking space. It can reduce the congestion inside the parking lot.

For future research, more dynamic influence factors will be taken into consideration. The methods to deal with various conditions of the obstacle avoidance need to be found. To make the system have a wider applicability, the mixed condition of driverless vehicles and human drive vehicles should be considered. Overall, this study is an important step in the automatic valet parking technology. The following research will also have great help in the development of this technology.