## 4 Expressway PTV Detection Algorithm for Over-the-Horizon
### Data Preprocessing
#### 4.3.2 Vehicle Speed Dataset Construction  
After the preliminary cleaning of the vehicle transaction data collected by the ETC gantry system, construct the driving trajectory for each vehicle according to the chronological order; use the road section collection of the expressway network to conduct a road section search for the driving trajectory of each vehicle, traverse the two adjacent ETC gantries in the driving trajectory one by one, check whether the two adjacent gantries exist in the road section collection of the expressway network, and if they exist, calculate the vehicle travelling time \(\Delta\)t through the two gantries by the difference between the collected transaction times.  
Then, based on the distance between the two neighboring gantries, calculate the speed of the vehicle passing through the road section V\({}_{\text{car}}\); if it does not exist, perform a path search based on these two ETC gantries to fill in the vehicle's travelling track, calculate the average speed of the vehicle through the path based on the results of the search path, and take this average speed as the speed of the vehicle through all the sections between the two ETC gantries, thus obtaining the speed of the sections of the expressway network that each vehicle passes through in the process of travelling. In turn, the interval speed dataset of all vehicles passing through the road section is obtained. The specific construction method is shown in Algorithm 1.  
```
Input: Real-time vehicle trajectory data: Traj; expressway network topology dataset: LW. Output: Vehicle travel speed
1. \(\text{Traj}=[\text{Node}_{1},\ \dots\dots,\ \text{Node}_{n}]\), LW = \([\text{QD}_{1},\ \dots\dots\dots,\ \text{QD}_{n}]\), QD = \([\text{Q},\text{Distance}]\);
2. \(\text{FOR}\ \text{i}=0\ \text{to}\ \text{i}=n-1\)
3. \(\text{Node}_{i}\), Time\({}_{i}\), Node\({}_{i+1}\), Time\({}_{i+1}\)#Extract information from adjacent nodes;
4. \(\Delta\text{t}_{i}=\text{Time}_{i+1}-\text{Time}_{i}\)#Calculate the time difference between adjacent nodes;
5. \(\text{Q}=(\text{Node}_{i}\text{,Time}_{i}\), Node\({}_{i+1}\), Time\({}_{i+1}\))#Save the information of adjacent nodes;
6. \(\Delta\text{t}=(\text{Q},\Delta\text{t}_{i})\)# Save vehicle travel time data;
7. \(\text{IF}\ \text{Node}_{i}\) and Node\({}_{i+1}\) in LW # If adjacent nodes are in the topology data;
8. \(\Delta\text{t}=\Delta\text{t}(\text{Q},\Delta\text{t}_{i})\)#Vehicle travelling time t data remains unchanged;
9. \(\text{ELSE}\ \text{Node}_{i}\) and Node\({}_{i+1}\) not in LW;
10. \(\text{distance}=\{\}\);
11. \(\text{\{Node}_{i},\ \dots\dots\dots\ \text{Node}_{n}}\leftarrow\text{shortest path LW \#Search for the shortest path;
12. \(\text{distance}_{i},\ \dots\dots\dots\ \text{distance}_{n}\}\leftarrow\text{LW \# Extract the shortest distance between gantries;
13. \(\text{v}=\text{Distance}/\text{v}\ \#\text{Calculate the passing speed of the front and rear gantries;
14. \(\text{Node}_{i},\ \dots\dots\dots\ \text{Node}_{n}]\) = v #Add speed attribute to adjacent gantries;
15. \(\Delta\text{t}_{i}=\text{distance}/\text{v}\ \#\text{Calculate the time difference between adjacent nodes;
16. \(\text{Node}_{j},\text{Node}_{j+1}\), Time\({}_{j}\), Time\({}_{j+1}\), \(\Delta\text{t}_{j}\)#Extract information about adjacent nodes in shortest paths;
17. \(\Delta\text{t}=(\text{Q},\Delta\text{t})\)#Replace the original passage time and generate a new passage time;
18. END IF
19. \(\text{V}_{\text{car}}=\text{Speed acquisition(Q},\Delta\text{t})\);#Calculate vehicle passing speed
20. END FOR
21. RETURN V\({}_{\text{car}}\)
```  
**Algorithm 1**Construction of the vehicle speed dataset