Map Matching Based on Seq2Seq with Topology Information

Abstract

Most existing road network matching algorithms are designed based on previous rules and do not fully utilize the potential of big data and historical tracks. To solve this problem, we introduce a new road network matching algorithm based on deep learning and using the topology information of the road network. Taking inspiration from the sequence-to-sequence (seq2seq) model popular in natural language processing, our algorithm builds multiple grid-dependent dictionaries based on the topology of road networks. Then the Byte Pair Encoding (BPE) algorithm is used to compress the grid dictionary, which effectively restricts the output range. A Bidirectional gated loop unit (Bi-GRU) with attention mechanisms is used as a recurrent neural network to capture information from a sequence of trajectory points. The model output feedback obtained by training the road network on Yibin City and the empirical evidence of the comparison in this experiment prove the effectiveness of the algorithm. When juxtaposed with similar algorithms, it shows superior accuracy and faster training speeds in road networks matching different scenarios.

1. Introduction

Road network matching refers to the precise positioning of discrete GPS (Global Positioning System) trajectory points onto an actual traffic road network [1], enabling the accurate depiction of vehicle locations. This process finds extensive applications in areas such as trajectory visualization, navigation implementation, intelligent transportation systems, and path planning.

Numerous scholars both domestically and internationally have put forth a plethora of algorithms for road network matching. For instance, in geometric-based matching algorithms, Bernstein [2] initially proposed the computation of distances between GPS points and each node within the road network, subsequently associating the GPS points with their nearest corresponding nodes. This algorithm is straightforward to implement and computationally efficient. However, its practicality is significantly influenced by the node density in the road network. In light of this limitation, Quddus [3] proposed a weighted topological matching algorithm that incorporates the topological relationship of the road network. This approach assigns weights to trajectory direction, geometric distance, and road relevance to determine the overall weight of each road segment. Subsequently, it selects the road segment with the highest weight as the matching counterpart. Wang Xiaohan [4] and colleagues introduced a method that combines a linear regression model for more accurate identification of changes in road shape at intersections. By referring to the matching situation of multiple subsequent points, the map matching at complex road sections reduced matching errors. Abbour [5] and Nadine [6] proposed the confidence interval matching method, which selected multiple road segments within the confidence region and added them to the candidate road segment. Then, a score operation was performed on each candidate road segment, and the road segment with the highest score was selected as the matching road segment. In the algorithm based on Kalman filtering [7,8,9,10], the road network matching was carried out by considering the characteristics of GPS system errors and analyzing whether the error characteristics of the Kalman filtering model meet the Gaussian white noise distribution. The algorithm based on the HMM (Hidden Markov Model) [11,12,13] model has become a widely used benchmark method due to its applicability in sequence modeling and road network connectivity. Among them, the IVVM [12] algorithm fully considers the topological structure of the road network and the mutual influence between GPS trajectory points. By weighted processing the relationship between these points, the matching accuracy is improved. Yan Shenglong [14] and others improved IVVM and proposed the interactive voting algorithm IIVVM, which fully considers the distance characteristics, topological structure of roads, and a series of road attributes. By filtering noisy road segments through constraint conditions, the matching efficiency is improved.

In recent years, the advancement of artificial intelligence and computer processing capabilities has prompted various fields to explore the potential of big data. In the domain of road network matching, Zhao et al. [15] introduced the DeepMM algorithm, which reevaluates road network matching from a data-centric perspective. This algorithm leverages all trajectory data for joint training and knowledge sharing. It employs a sequence learning model that incorporates embedding techniques and attention mechanisms to conduct road network matching in latent spaces while ensuring stability in noisy environments. Lu Jia-Pin [16] proposed a map matching approach based on ranking learning, wherein the scoring function of candidate roads is learned from known matching outcomes. This method selects the optimal matched road segment by assigning scores to candidate road segments.

Inspired by seq2seq models in the field of natural language processing, this paper proposes a novel approach to represent road network data. It leverages multiple dictionaries that capture topological relationships based on road network topology and subdivision into fine-grained grids. To compress these dictionaries, the BPE algorithm is employed. The scope of our results is focused on the road network using fine-grained grids exclusively. In order to provide robust data support for deep learning, we generate a substantial number of simulation standard paths through Gaussian noise path generation within the Frechet distance framework, combined with efficient path search algorithms. Bi-GRU (Bi-directional GRU) is employed as a bidirectional recurrent network to reduce parameters and assimilate information from both trajectory history and future sequences during model training and prediction. Additionally, an attention mechanism is incorporated to augment the model’s proficiency in extracting hidden value information from sequences. Experimental findings demonstrate the commendable performance of our algorithm in road network matching tasks, showcasing improved accuracy compared to similar algorithms while significantly reducing training time.

2. Related Work

Our work comprises three main components: the creation of a dataset featuring a topological network structure, the development of a deep learning model based on the seq2seq approach, and the training and experimental validation of this model through comparisons with other existing models.

2.1. Basic Concepts and Problem Description

A road network is composed of a series of GPS trajectory points. These points are connected based on the topology of the road network, forming a directed graph G(V,E), where V represents the set of GPS points on the roads in the graph, and each point is represented as P = [lng, lat]. E represents the set of road edges formed by these GPS points, and each road edge is represented as l = [P1, P2, P3, … PN]. Based on this concept, this article defines a series of related dictionaries to express the concepts in map matching problems.

2.1.1. Road Network Dictionary

A road network comprises a sequence of GPS trajectory points, which are interconnected based on the topological structure of the road network, thereby forming a directed graph denoted as G(V,E). Here, V represents the set of GPS points located on the roads within the graph, with each point being represented as P = [lng, lat]. E denotes the set of road edges formed by these GPS points and is represented as l = [P1, P2, P3, … PN]. Building upon this concept, this article establishes a series of associated dictionaries to effectively express concepts pertaining to map matching problems.

2.1.2. Trajectory Dictionary

The trajectory dictionary generates a series of standard trajectories that satisfy the road network topology rules based on the network topology of the road, using the road network and road segment dictionaries as the basis. The generated standard trajectories are added to the dictionary, where each standard trajectory is represented as a set of points ST = [P1, P2, P3, …]. The dictionary is in the form of [ST1, ST2, ST3, … STN].

2.1.3. Grid Dictionary

The grid dictionary partitions the map into an N by N grid, serving as the word vector dictionary for the model. Increasing N enhances division accuracy, albeit at the expense of augmenting model parameters. The grid is arranged in ascending order from the bottom left to the top right. The dictionary takes on a sequential form of [1, 2, …, N × N].

2.1.4. Network Grid Dictionary

The road network grid dictionary replaces all GPS trajectory points in the road network dictionary with their corresponding position ID in the grid dictionary, resulting in a dictionary comprising grid IDs. This dictionary is represented as [CELL1, CELL2, … CELLN], where its length matches the number of GPS points present in the road network.

2.1.5. Road Segment Grid Dictionary

The road segment grid dictionary converts all GPS points within the road segments in the road segment dictionary into their corresponding grid points within the grid dictionary. The index of the dictionary represents the unique identifier for each road segment, while its corresponding value denotes the set of grid-based edges associated with that particular road segment. The structure of this dictionary is represented as [L1, L2, L3, … LN], where L = [CELL1, CELL2, CELL3, … CELLN].

2.1.6. Trajectory Grid Dictionary

The trajectory grid dictionary corresponds to the grid representation of the trajectory dictionary by replacing GPS trajectory points with grid IDs. The resulting sequence also adheres to road network topology rules. Each trajectory is represented as CELL_ST = [CELL1, CELL2, CELL3, … CELLN]. The dictionary is structured as [CELL_ST1, CELL_ST2, CELL_ST3, … CELL_STN].

The final grid ID sequence, along with its topology relationship, is utilized during the model training process, while the remaining dictionaries serve as encoding and decoding references. The formats of the corresponding dependent dictionaries are illustrated in

Table 1. Related Dependency Dictionary Form Examples.

Dictionary	Data Structure Example
Road network dictionary	{P0:[104.61686, 28.74756]…}
Trajectory dictionary	[{L0:[P1, P21, P33, P41, P49]}…]
Grid dictionary	[{L0:[P11, P221, P333, P411, P491]}…]
Network grid dictionary	[{Ln:[P131, P2133, P3143, P4415, P4391]}…]
Road segment grid dictionary	[{P0:442367},{P1:442345}…]
Trajectory grid dictionary	[{L0:[432367, 425370,…439404]…}

, whereas Figure 1 depicts the specific mapping logic from points to grids.

The task of road network matching involves inferring the accurate grid sequence from the GPS points’ sequence of a given mobile object, utilizing the algorithm model presented in this paper. Subsequently, the true road network trajectory sequence is decoded based on the inferred grid sequence, thereby completing the road network matching process. For instance, as depicted in Figure 2a, the line represents the GPS point trajectory, while in Figure 2b, it represents the corresponding authentic trajectory. The objective of road network matching is to employ the algorithm for inferring the genuine trajectory shown in Figure 2b from the GPS point trajectory illustrated in Figure 2a.

Described in the form of a grid diagram as shown in the following figure, the lines connected by green points in Figure 3a are the true tracks, the red points are the original measured latitude and longitude points, and the line segment connected by the red points is the wrong track. The purpose of map matching is to infer the wrong trajectory formed by the red dots to the true trajectory formed by the green dots. First, the two trajectory points need to be mapped on the grid, as shown in Figure 3b. The green grid represents the grid sequence of the true trajectory mapping, the red grid represents the grid sequence of the wrong trajectory mapping, and the yellow grid represents the overlap of red and green. The red grid sequence in Figure 3b is input into the trained model, and the model can output the red grid sequence in Figure 3c through calculation, and finally decode the grid sequence into the real geographical longitude and latitude point sequence connected by the green points in Figure 3c.

2.2. Dataset Preparation

The original data for this article was obtained from the OpenStreetMap download of the road network in Yibin City, which was used as the data source. Using QGIS software, special road sections were removed from the network, leaving only the main roads in Yibin City, as shown in the diagram below. The dataset includes 6429 GPS road points and 619 roads. The coordinates of the bottom left corner node are left_bottom = [104.5783146, 28.7090704], and the coordinates of the top right corner node are right_top = [104.6833462, 28.7962751]. The total area is 99,507,385 m².

Based on this information, a directed graph G(V,E) was generated using the NetworkX data processing package for complex graphic network analysis in Python, and all nodes and edges were calculated, totaling 5810.

For ease of description, this article divides the map into a grid of 1000 × 1000, with a precision of 9.95 m × 9.95 m, and assigns a grid code from 1 to 100,000. In actual environments, the grid precision can be adjusted according to demand.

2.2.1. Simulated Real Trajectory Generation

Obtaining large datasets to support deep learning work is a challenging task. Therefore, simulating real and noisy path generation is a crucial part of the work. In this study, we used the NetWorkX library’s simple path function to simulate real paths. All simulated standard trajectories will be used as the target sequence for the model. The format of some short path sequences is shown in

Table 2. Some Shorter Path Sequences.

Starting Point and Endpoint	Path
0==>103	[0, 2970, 377, 592, 2510, 2220, 103]
1==>3923	[1, 5352, 1538, 4355, 2715, 3822, 3923]

. All paths follow the topological rules of the road network.

2.2.2. Noise Trajectory Generation

In real life, GPS systems often have some degree of deviation from the actual location, which is typically within a certain range known as the Fresnel distance as shown in Equation (1), where A and B are two continuous curves, α and β are two reparameterization functions of the unit interval, and d is a metric function. This formula represents the minimum of the maximum distances between A(α(t)) and B(β(t)) under all possible α and β values. This is the optimal case of the worst-case distance under all possible path pairings. This definition captures the similarity between two paths, taking into account both the shape and length of the paths, or there may be an overall error in a series of GPS points. Therefore, following this rule, Gaussian spatial noise is added to all standard simulated paths to generate a series of noisy trajectories as a corpus for the model’s input sequence, as described in Equation (2).

$$F\left(A,B\right)=\underset{\alpha ,\beta }{\mathrm{i}\mathrm{n}\mathrm{f}} \underset{\mathit{tϵ}\left[\mathrm{0,1}\right]}{\max }\left\{d\left(A\left(\alpha \left(t\right)\right),B\left(\beta \left(t\right)\right)\right)\right\}.$$

(1)

$$f\left(x|\mu ,{\sigma }^2\right)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{\frac{-{\left(x-\mu \right)}^2}{2{\sigma }^2}}.$$

(2)

The expected value of the μ distribution and σ is the standard deviation, both of which can be set from the actual accuracy requirements. Examples of noise tracks generated based on nodes 0 to 103 in Table 2 are shown in

Table 3. Noise Pathway Example.

Starting Point and Endpoint	Cell Path
0==>103	[757497, 759494, 764486, 768484, 776483, 811426]
1==>3923	[758500, 759499, 763494, 768488, 773487, 813422]

.

The generated noise trajectory points of the entire road network are shown in Figure 4. The yellow dots are noise points generated by the algorithm, representing inaccurate latitude and longitude points, which are used as materials for model training. The red lines are the road network of Yibin City.

2.2.3. Data Compression

During the dataset preparation stage, a grid of 1000 × 1000 was partitioned, resulting in a grid dictionary with a length of 1 million. However, such an extensive dictionary would significantly impact both the training time and accuracy of the model. Hence, it becomes imperative to compress the grid dictionary.

The BPE algorithm [17] segments all words in the training corpus into character sequences, calculates the frequency of consecutive byte occurrences, selects the most frequent byte pairs, and combines them to form new subwords. This process is iteratively performed to update the vocabulary. As this paper’s data is stored in dictionary mode, employing the BPE algorithm for customized compression becomes effortless. The initial dictionary length was 1,000,000; however, through utilizing the BPE algorithm, it was compressed to one-tenth of its original size. The relationship between the new and original dictionaries has been preserved as a decoding basis for model output.

3. Model Design

In Feng J’s work [15], a unidirectional LSTM (Long short-term memory) was used as the recurrent neural network for state transfer in seq2seq. Although LSTM has slightly higher accuracy in processing large-scale data, it is extremely time consuming. Related experiments have shown that in situations where the data volume is moderately large, the effect of GRU is comparable to that of LSTM, and it has the advantage of faster processing time. The structure of GRU is shown in Figure 5.

The GRU uses a reset gate to control the amount of data in the current and memory information. It uses an update gate to calculate the output of the current hidden state, generating new memory information to continue forward propagation. The relevant mathematical formulas are shown in Equations (3)–(6).

$$z_t=\sigma \left(W_z{x}_t+U_z{h}_{t-1}\right).$$

(3)

$$r_t=\sigma \left(W_z{x}_t+U_z{h}_{t-1}+b_z\right).$$

(4)

$$\tilde{h}=\mathrm{t}\mathrm{a}\mathrm{n}h(W{X}_t+r_{t}U{h}_{t-1}+b_h).$$

(5)

$$h_t=\left(1-z_t\right)h_t+z_T{h}_{t-1},$$

(6)

where $h_{t-1}$ is the hidden layer of the previous time, $x_t$ is the current input, and the output is the hidden layer information $h_t$ of the current time. $r_t$ is the reset gate, used to calculate the candidate hidden layer $\tilde{h}$, in order to retain how much $h_{t-1}$ information. $z_t$ is the update gate, which is used to control how much $\tilde{h}$ information is added to get the output $h_t$.

In this paper, Bi-GRU is used to transfer the state of model coding phase. Its main feature is that it can absorb historical and future information, so as to capture information of a complete trajectory sequence. The structure of Bi-GRU is shown in Figure 6. In the Figure 6, FD represents the last GRU unit of forward propagation, and BD represents the last GRU unit of backward propagation.

In addition, in order to enhance the ability of the model to capture the dependency between noisy trajectories and real road network trajectories, this article applies the Bahdanau [18] attention mechanism, as shown in Figure 7.

First, a weight coefficient α_tj is generated for each hidden state h_j. The weight coefficients are then subjected to a Softmax operation to obtain the attention weights α_tj for each hidden state. The attention vector context is obtained by calculating the weighted sum of the attention weights and each hidden state. Finally, the attention vector is integrated with a fully connected layer to form the output value. The calculation process is shown in Equations (7)–(9).

$$e_{t,j}=a\left(s_{t-1},h_j\right).$$

(7)

$${\alpha }_{t,j}=softmax\left(e_{t,j}\right)=\frac{\exp \left(e_{t,j}\right)}{{\sum }_{k=1}^n\exp \left(e_{tk}\right)}.$$

(8)

$$context={{\displaystyle \sum }}_{t=1}^T({\alpha }_{t,j}{s}_t).$$

(9)

The final output value will be calculated using a Softmax function to obtain a probability matrix for the grid. The highest probability value for each grid will be outputted to form a grid sequence. By converting it to the real coordinates using the dictionary of the road network, the actual trajectory output can be obtained. The overall structure of the algorithmic model is shown in Figure 8.

4. Experiment

4.1. Experimental Environment

The models involved in the experiment were built using the TensorFlow-gpu (2.3.0) framework and trained on a NVIDIA Quadro RTX 6000 graphics card with a 24 GB memory. The model parameters are shown in

Table 4. Model Parameters.

Params	Value
Iteration count.	20
BatchSize	128
Number of nodes on the longest/shortest path.	22/5
Optimizer	Adam
Loss function.	crossentropy
Dictionary compression ratio.	0.2
Shuffer	True
Data set partition ratio.	1/10
Data expansion factor.	50

. The dictionary compression refers to the proportion of the original mesh dictionary compressed using the BPE algorithm, and the data augmentation multiplier is the number of noise paths generated based on a single path.

4.2. Experimental Data

The training data used for the model consisted of the road network of Yibin City downloaded from OpenStreetMap, where standard trajectory data were generated through simple path search in NetWork X, and simulated noisy trajectory data. A total of 260,389 standard paths and 13,019,450 simulated noisy paths were used.

4.3. Evaluation Index

Since the problem of road network matching is the matching of noise track sequence to road segment sequence, the absolute accuracy of the model cannot be simply used as the evaluation criterion. In this paper, the accuracy evaluation method of road section mentioned in article [15] is followed, as shown in Equation (10).

$$acc=\frac{len\left(tru{e}_{tra}\cap pr{e}_{tra}\right)}{\max \left(len\left(tru{e}_{tra}\right),len\left(pr{e}_{tre}\right)\right)} .$$

(10)

$len\left(tru{e}_{tra}\right)$ is the total length of the standard trajectory of the section, $len\left(pr{e}_{tre}\right)$ is the total length of the matched trajectory, and $len\left(tru{e}_{tra}\cap pr{e}_{tra}\right)$ is the total length of the intersection between the correct trajectory and the matched trajectory. In this article, the Haversine formula is used to calculate the distance between latitude and longitude points, as shown in Equation (11).

$$d=2r {\sin }^{-1}\left(\sqrt{{\sin }^2\left(\frac{{\theta }_2-{\theta }_1}{2}\right)+\cos \left({\alpha }_1\right)\cos \left({\alpha }_2\right){\sin }^2\left(\frac{{\alpha }_2-{\alpha }_1}{2}\right)}\right) ,$$

(11)

where $r$ is the radius of the Earth (6371 km), ${\theta }_1$ and ${\theta }_2$ are the latitude between two points, and ${\alpha }_1$ and ${\alpha }_2$ are the longitude between two points.

4.4. Experimental Result

4.4.1. Visualization of Matching Effect

Two simulated noise tracks were selected to match the road network through the model, and the results were visualized as shown in Figure 9.

It can be seen that the results obtained by the model match the topology characteristics of the road network and are consistent with the real trajectory. Vehicle track data is strictly restricted to the road network, so the noise track is confined to the road network with a certain distribution law of data. The simulation trajectory generated by the data expansion method in this paper can almost look like the actual driving trajectory. However, in order to ensure the rigor of the experiment, it is still necessary to use the real driving track for actual verification. Therefore, this paper collected a section of Yibin City driving routes for test verification. The software that collects track information is the Android App (GPS racking Route Map). The track is approximately 31.31 km long and contains 1467 GPS track points.

The overall trajectory is shown in Figure 10 below. The green area represents the recorded track points, and the red is the route formed by the points.

The overall trajectory was decomposed and piecewise put into the model for matching. The total length of matching was 31.31 km. The correct trajectory length calculated by Equation (10) was 28.89 km, and the matching accuracy was 92.27%. The matching results of some conventional sections are shown in Figure 11. In the figure, the red path is the matching path, and the green path is the path formed by the direct connection of the collected original track points.

The matching results of conventional sections are shown in Figure 11.

According to Figure 12 depicting matching results, it can be seen that the matching effect is very good whether it is in the conventional road section or the complex intersection road section. There is no wrong lane matching, large deviation matching, or other types of wrong matching. Some mismatched sections are shown in Figure 13 below.

The left side of Figure 13 shows the turntable area, and the matching results produced an error loop. Our estimation is that there was a traffic jam when the trajectory was collected, which resulted in excessive positioning in a short time, resulting in a deviation of the model prediction. The right side of Figure 13 shows the intersecting multi-road section, and the correct route should be the route in the yellow area.

4.4.2. Model Performance Comparison

The overall model training accuracy rate and loss curve in this paper are shown in Figure 14.

The absolute accuracy of the model on the training set is 89.93%, and the absolute accuracy of the model on the verification set is 89.88%. Through Equation (10), the accuracy of the verification set is re-converted, and the accuracy of the converted model is 95.45%. It shows that the road network matching method proposed in this paper is effective.

Through the comparison of LSTM, Bi-LSTM, Bi-LSTM-ATTN, and other model structures under the experimental conditions of the same parameters in Table 4, the parameters are shown in

Table 5. Model Comparison Experiment.

	LSTM	BI-LSTM	BI-LSTM-Attn	Textual Model
Training set accuracy	83.51%	85.32%	86.71%	89.93%
Test set accuracy	80.23%	82.34%	84.74%	89.88%
Training set loss	0.4131	0.3691	0.3271	0.2311
Test set loss	0.5221	0.4561	0.3711	0.2298

, and all accuracy rates are absolute accuracy rates in the verification set. It can be seen that after 20 iterations, the accuracy of the model trained by the bidirectional LSTM is 1.81 points higher than that of the unidirectional LSTM, and the accuracy of the model with the addition of attention mechanisms on this basis is 86.71 points, and the accuracy of the model in this paper is 89.93 points. It shows that the accuracy of the model can be improved to some extent by using bidirectional recurrent neural network and attention mechanisms.

4.4.3. Optimized Controlled Experiment

In order to verify the validity of the data expansion method and the effect of the compressed dictionary on the training time and training accuracy, based on different data expansion conditions, the compression degree of dictionary compression is shown in Figure 15. Several groups of control experiments were set, and other experimental parameters remained unchanged as shown in Table 4. Accuracy is the absolute accuracy of the verification set.

From the data expansion control test in Figure 15, it can be seen that when the expansion multiple is between 10 and 50 times, the absolute accuracy of the model will be greatly improved, and when the expansion multiple is above 50 times, the accuracy tends to be stable and oscillates between 89.57% and 89.93%.

The experimental results show that the data expansion method is effective to improve the absolute accuracy of the model.

It can be seen from the controlled experiments in Figure 16 that when the compressed data range is between 1/5 and 1/10, the accuracy rate of the model is maintained between 88.11 points and 89.04 points, and the training speed is increased from 276 ms/Step to 27 ms/Step. When the compression degree was increased to 1/15, the absolute accuracy of the model began to decline significantly to 62.37 points, and when the compression was continued to 1/20, the absolute accuracy of the model dropped to 43.37 points.

The experimental results show that the data compression method is effective for improving the training speed, and has limited influence on the accuracy of the model within a certain compression range. Beyond a certain compression range, the absolute accuracy of the model will be seriously affected.

5. Conclusions

To solve the matching problem between GPS tracking and real road networks, this paper proposes a method based on seq2seq combined with topological information, modeling road network matching into seq2seq sequence model, creating multiple dependency dictionaries according to the topological relationship of a road network, fine grid division, and limiting the matching results to road network. Using the BPE algorithm to compress the grid dictionary, the length of the word vector is reduced and the training time is optimized. Standard trajectory data sets are established through simple path search through NetWork X, and a large number of noise trajectories are generated based on Gaussian noise within a certain Frechet distance to support large data volume in deep learning. Bi-GRU is used as a bidirectional recurrent neural network to extract the information of both historical trajectory sequence and future trajectory sequence. We added attention mechanisms to enhance the ability of extracting sequence hidden value information. The experimental results show that this road network matching method is effective and has higher matching accuracy and less model training time than other methods.