## 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. Figure 2: Dijkstra algorithm. 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}{cccc}0&D_{12}&D_{13}&\ldots&D_{1n}\\ D_{21}&0&D_{23}&\ldots&D_{2n}\\ D_{31}&D_{32}&0&\ldots&D_{3n}\\ \ldots&\ldots&\ldots&\ldots&\ldots\\ D_{n1}&D_{n2}&D_{n3}&\ldots&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=(t_{1}-t_{0})\cdot 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.