## 3 SD-QGrid Routing Platform and Algorithms
### SD-QGrid Offline Q-Learning Training Process
#### 3.3.1 RSU Analysis Unit  
HELLO messages periodically issued from all vehicles on a road segment to the corresponding RSUs include their GPS data, speed, moving direction, vehicle IDs, neighbor vehicle IDs, etc. With the following operations, the average number of vehicles in each road segment is counted and the historical trajectory of each vehicle in this road segment is determined by the RSU. This information is cached on the trajectory cache of the RSU. Each day is divided into eight time periods, as shown in Table 2[22]. Historical trajectories of vehicles are listed in Table 3, which records the vehicle ID, time stamp and the longitude and latitude values of each trajectory point. The RSU counts the average number of vehicle nodes in its connected road segments in a certain time period within the experimental date range. The calculation method is shown in Equation (3). Based on the vehicle ID and its GPS data, i.e., the current position of the vehicle, in the HELLO message, Table 4 counts the number of vehicles that appear in the connected road segment during this time period every day in the date range, before dividing it by the total number of days in the date range and recording it in the table. An example of a table is Table 4, e.g.,  
Figure 5: SD-QGrid experimental map. 2021-10-13-10-12; the average number of nodes appearing in road segment \(i\) of Grid (0,2) over a period of 10:00-12:00 is 314. \[\overline{N_{i}^{t}}=\frac{\sum_{d\in D}N_{i,\;d}^{t}}{|D|} \tag{3}\]  
where \(D\) is the date range, \(|D|\) is the total number of days in \(D\), \(N_{i,\;d}^{t}\) is the number of nodes of road segment \(i\) in period \(t\) on day \(d\), and \(\overline{N_{i}^{t}}\) is the average number of nodes of road segment \(i\) in period \(t\). Please note that each road segment is identified by the (x, y) coordinates of both its intersections, which are called the _start_ and _end_ ones here. Further, multiple HELLO messages issued by the same vehicle only increase this RSU's counter, i.e., \(N_{i,\;d}^{t}\), by one, if this vehicle stays in the same road segment in period \(t\). If the road segment crosses from a grid into one of the up, down, left, right, upper right, lower left, upper left, or lower right neighbor grids, its RSU located in this grid records the number of outgoing nodes, which moves from this grid to the neighbor one. The average number of outgoing nodes in a certain time period within the experimental date range is calculated by an equation such as Equation (3) and stored in a table, as shown in Table 5. The outgoing direction of this road segment is from the current grid toward the neighbor one. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Grid Index** & \begin{tabular}{c} **The Start Intersection** \\ **Coordinate (x, y) of** \\ **Road Segment \(i\)** \\ \end{tabular} & \
\begin{tabular}{c} **The End Intersection** \\ **Coordinate (x, y) of** \\ **Road Segment \(i\)** \\ \end{tabular} &
\begin{tabular}{c} **Average Number of Nodes \(\overline{N_{i}^{t}}\)** \\ **Time Period \(t\)** \\ **Road Segment \(i\)** \\ \end{tabular} \\ \hline \hline (0, 2) & (\(x_{s},y_{s}\)) & (\(x_{e},y_{e}\)) & 314 & 2021-10-13-10-12 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average number of nodes of road segment \(i\) in period \(t\). \begin{table}
\begin{tabular}{c c} \hline \hline
**Time Period** & **Congestion Level** \\ \hline
23:00–07:00 & normal \\
07:00–09:00 & congested \\
09:00–12:00 & normal \\
12:00–13:00 & congested \\
13:00–17:00 & normal \\
17:00–19:00 & congested \\
19:00–22:00 & normal \\
22:00–23:00 & congested \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Time period state interval.