# RoPT: Route-Planning Model with Transformer
## 4 Methodology  
In this paper, a model named Route Planning with Transformer (RoPT) is proposed to improve the accuracy of route planning in road networks. Existing approaches typically concatenate features of destination node with those of traversed node to predict the next node. However, due to the fact that the destination is more important than other nodes in route planning, in this paper, two prediction tasks are executed on destination and the current route composed of nodes that have been passed. The final results are computed on these two intermediate predictions results.  
Firstly, with GCN, representations corresponding to spatial correlations of nodes are obtained, according to their adjacency matrix. Secondly, with Transformer, the representations of current route are captured based on concatenations of above node representations. Finally, based on the similarity between spatial representations of current route and the destination, and the similarity between temporal representations and spatial representations of current route, the next node of the route is recommended. As illustrated in Figure 1,  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Symbol** & **Definition** \\ \hline \(\text{M}_{\text{A}}\) & adjacent matrix \\ \hline \(\text{N}_{\text{Des}}\) & destination node \\ \hline \(\text{M}_{\text{R}}\) & eigenvector of the current route \(R\) \\ \hline LookUp(M, i) & the _LookUp_ operation finds a vector at the index position \(i\) in \(M\) \\ \hline \(\text{Ne}_{i}\) & the neighbor set of the current route \(R\) \\ \hline \(\text{M}_{\text{Nei}}\) & the weight matrix composed of the features of the neighbor \(\textsl{Ne}_{R}\) \\  & of the current route \(R\) \\ \hline \(\text{M}_{\text{Des}}\) & the feature matrix of the destination \\ \hline \(\text{M}_{\text{S}}\) & the road feature matrix extracted with GCN \\ \hline \multirow{3}{*}{\(\text{R}_{\text{mask}}\)} & the mask matrix of the route \(R\), where the value of -inf \\  & represents the filling positions and 0 represents the remaining \\ \cline{1-1}  & positions \\ \cline{1-1}  & \(\text{d}_{\text{Ne}}\) & maximum number of neighbors of a node \\ \hline \(\text{M}_{\text{T}}\) & route hidden state matrix \\ \hline \(\text{M}_{\text{Prob}}\) & transition probability matrix \\ \hline n & total number of nodes (sections) \\ \hline l & the maximum length of the trajectory \\ \hline e & dimension of node (sections) embedding representation \\ \hline \hline \end{tabular}
\end{table}
Table 1: Symbols and interpretations.  
RoPT is composed of three parts. The first part is the spatial feature aggregation module, which captures spatial representations of nodes on a road network with GCN, whose input are an adjacent matrix of a road network (\(M_{A}\)) and a learnable representation matrix of nodes (\(M_{Emb}\)). The second part is the sequence feature aggregation module based on Transformer, which captures temporal representations of nodes on long-term dependencies and sequential correlations in current route. The last part is next node prediction module, which calculates transition probabilities of nodes who are neighbors of current node in the route, according to representations of the destination and those neighboring nodes captured from results of the first part (GCN). In the end, the recommended neighboring node is the one with highest probability.