# Deep Learning-Based Destination Prediction Scheme by Trajectory Prediction Framework

Authors: Jingkang Yang; Jianyu Cao; Yining Liu
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Destination prediction is an important task in vehicular ad hoc networks (VANETs), which benefits to resolve traffic congestion. The traditional destination prediction methods are mainly based on statistical learning, which is difficult to fit the movement pattern of vehicles and predict destination of a new query trajectory. In recent years, deep learning attracted more and more attentions since it has a better ability to adaptively extract features from data and fit complex models. The exiting deep learning-based destination prediction methods mainly extract features from past trajectory and fail to exploit future trajectory because the future locations are unknown, which results in a large prediction error. In this paper, we propose a novel deep learning-based destination prediction model that can predict the future trajectory and make full use of the information about it. Firstly, we exploit a trajectory prediction method to predict future locations, which makes the process of destination prediction continuous. Secondly, we design a branch network to determine which future location is the destination of the trajectory. We also evaluate our model with a real-world dataset. Experimental results show that our model can predict the coordinates of destination with a low prediction error.


---

## Body

## 1. Introduction

The advent of 5G networks has greatly improved the efficiency of data transmission, which greatly promotes the development of vehicular ad hoc networks (VANETs). Connecting vehicles with network provides instant access to information about each vehicle, improving traffic conditions and driving experience. Destination prediction is an important task in VANETs [1], which benefits to resolve traffic congestion. By predicting the destination of each vehicle, it can be known in advance where the traffic flow will increase, and dredging measures can be taken in advance to prevent traffic congestion.Historical trajectories are essential in destination prediction task. However, it is impossible in reality to obtain a historical trajectory set that covers all possible search locations. The existing trajectory dataset is usually a small part of that, and sometimes there is no historical trajectory in the database matching the query trajectory, so that the destination cannot be predicted. This phenomenon is called “data sparsity problem” [2].Different from the traditional statistics-based method, deep learning model can adaptively learn the vehicle movement pattern from the historical trajectory and makes prediction of the future locations according to the learned behavior pattern when encountering a new trajectory. This method can completely solve the problem of data sparsity because it no longer relies on the specific historical trajectory data.Some methods based on deep learning have been applied to destination prediction. Exiting methods mainly follow a common approach, which directly predict the destination using only past trajectory [3–5]. As shown in Figure 1, a vehicle successively reaches L1, L2, L3, L4, and LD at time t1, t2, t3, t4, and t5. It is assumed that the vehicle is currently at L2 and the past trajectory of the vehicle consists of L1 and L2. If the vehicle continues to move, it will successively reach L3, L4 and destination LD. However, the information of L3 and L4 is not available at t2 since the locations of the vehicle at t3 and t4 cannot be determined. The above approaches only extract features of L1 and L2 to predict the destination. In this way, the information of L3 and L4 is not be utilized, resulting in a large prediction error.Figure 1
The process of directly predict the destination using only past trajectory. In this case, only the information ofL1 and L2 is used to predict the destination, while L3 and L4 are ignored.Due to the great success of deep learning in the field of trajectory prediction [6–8], using trajectory prediction method can make this process continuous as Figure 2 shows. Firstly, L3 can be predicted according to the past trajectory consisting of L1 and L2. Then L4 can be predicted according to the new trajectory consisting of L1, L2, and L3. The rest of the locations can be done in the same manner. However, naively using the trajectory prediction method cannot determine which location is the destination; that is, it cannot tell when to stop predicting. For example, when location LD is predicted, the trajectory prediction model cannot judge whether LD is the destination or not. Then the model continues to predict the next location (this location will not be reached in reality), thus missing the ground-truth destination.Figure 2
Schematic of naively using trajectory prediction method. The future locations are predicted one by one, but it is difficult to tell which location is the destination.In this paper, a novel destination prediction method based on deep learning is proposed. As shown in Figure3, the main body of our model is a trajectory prediction model, which can address the problem of discontinuity. In order to make the proposed model determine when to stop predicting, we design a branch network to judge whether the current location is destination. When a future location is predicted, the branch network is used to judge whether the current trajectory is a complete trajectory. If the current trajectory is a complete trajectory, it means that the current predicted location is the destination. If not, the next location will be predicted.Figure 3
Destination prediction process with branch network. Whenever a future location is predicted, the branch network is used to determine whether it is the destination.The contributions of our work are summarized as follows:(1)
We propose a novel deep learning model for destination prediction based on trajectory prediction framework. This model can not only extract the features of past trajectory, but also extract the features of future trajectory.(2)
We use an encoder-decoder structure with attention mechanism to predict future trajectory. The encoder can adaptively extract the features of past trajectory and learn the movement pattern of the vehicle, and then the decoder uses the learned knowledge to predict the future location one by one. We also design a branch network to determine whether the destination is reached or not.(3)
We evaluate the proposed framework on a real word dataset called T-drive. We first clean T-drive dataset by removing the exceptional data and then compare our scheme with three baseline schemes on the cleaned T-drive dataset. The experimental results demonstrate that the proposed scheme can predict the destination with low prediction error.The structure of this paper is organized as follows. Section2 reviews existing destination prediction methods and trajectory prediction methods. Section 3 formulates the problem to be addressed in this paper and elaborates the proposed method. In Section 4, we introduce the real-world dataset we used and present our experimental results. Finally, we conclude the proposed method in Section 5.


## 2. Related Work

Traditional destination prediction schemes mainly follow three streams. The first is using external information to assist predicting the destination. Horvitz and Krumm [9] increased the accuracy of their destination prediction method by referring to information about the areas where the vehicle already visited. Krumm and Horvitz [10] exploited the previously visited destination and ground cover prior as the source of information about the probability of destination. Ziebart et al. [11] proposed a scheme for predicting destination from observed context-aware behavior. These methods need to provide external information that is difficult to record, which is not beneficial to train the model.The second is using each vehicle’s own historical trajectories to predict its destination. Marmasse and Schmandt [12] proposed a model based on user experience. They used pattern recognition models to analyze the user’s patterns of movement and predict the destination. Abul et al. [13] proposed a model to learn the user’s driving habits from everyday driving and thus infer the destination. These methods need to collect the user’s historical trajectories. If the user’s historical trajectories are insufficient, the data sparsity problem will be encountered.The third is based on Bayesian inference framework. These methods divide the city intoN×N grids [2, 10, 14]. Then the probability of a location Lj being the destination of the query trajectory T is computed as(1)PD∈Lj|T=PT|D∈LjPD∈Lj∑i=1N2PT|D∈LiPD∈Li.The key of Bayesian methods is to compute the probabilityPT|D∈Lj. This probability may be zero when the amount of historical trajectories is insufficient, which is called data sparsity problem. To address this problem, Xue et al. [2] proposed a subtrajectory synthesis method to expand the feature space of historical trajectories. However, data sparsity problems still occur when fine-granularity predictions are required.Some deep learning-based methods have been proposed to predict destination recently. Zhao et al. [3] proposed Trajectory based Attentional Long Short-Term Memory Network (LSTM) Learning (TALL) model. They used a bidirectional LSTM model to extract features from past trajectory and applied attention mechanism to emphasize on the features that have strong correlations to destination. Then a dense layer is used to predict the probability distribution of the destination. Xu et al. [4] proposed Location-aware Attentional Trajectory-LSTM (LATL) model. They designed a Location-Aware Attention mechanism instead of the standard attention mechanism to capture distinct features of locations. Tang et al. [5] used diverse networks to extract features from different information (i.e., LSTM for locations and dense layer for time stamps) and then fused these features into a vector as the input of the Multilayer Perception (MLP) for predicting the destination. The above methods follow a common framework; that is, LSTMs are used to extract features of the past trajectory and then an MLP is used to predict the destination. This framework only exploits information about past trajectories and loses information about future locations.In recent years, deep learning has been widely used in trajectory prediction tasks. Many researchers proposed methods based on Recurrent Neural Networks (RNNs) to generate social acceptable trajectories [7, 8, 15]. Ballan et al. [6] use a Dynamic Bayesian Network to predict trajectory from scene-specific knowledge. Alahi et al. [7] used LSTMs to capture the mobility pattern of users. Gupta et al. [8] proposed a GAN-based model to generate the future trajectory. In our scheme, we exploit a trajectory prediction structure to predict future locations. In this way, features of future locations can be extracted for predicting the destination.


## 3. Method

In this section, we first describe the problem formulation and the framework of proposed method, followed by the details of trajectory prediction approach and branch network. Finally, we describe the loss function adopted in our model and the details of training process.


### 3.1. Problem Formulation

Our goal is to predict final destination according the past trajectory of the agent. Suppose that the past trajectory of an agent at a momenttn is denoted as X=X1,X2,…,Xn and the future trajectory is denoted as Y=Y1,Y2,…,Yd (ground truth) with the final destination Yd, in which the i-th location of the past trajectory is defined as Xi=xi,yi and the j-th location of the future trajectory is defined as Yj=xj,yj. We need to predict the final destination Yd at the moment tn receiving the past trajectory X as input.It is hard to predictYd directly because the locations between Xn and Yd are unknown at tn. We tackle this problem in two steps: predict future trajectory step by step and decide when to stop. Specifically, at tn, we firstly predict the next location Y^1 and then judge whether Y^1 is the destination. If Y^1 is not the destination, we predict Y^2 and then judge whether Y^2 is the destination and so on, until the destination is predicted. This is a continuous process, and we can use a common trajectory prediction approach to predict future locations and a branch classification network to judge which is the destination. The framework of proposed method is illustrated in Figure 4.Figure 4
The framework of proposed model. The proposed model consists of encoder-decoder architecture with attentional mechanism and a branch network.


### 3.2. Trajectory Prediction Approach

Trajectory prediction is a generative problem. Generative models can extract the feature of past trajectory and simulate possible future. In our scheme, we propose a time-series processing model basing encoder-decoder architecture to predict future trajectory.


#### 3.2.1. Encoder-Decoder Architecture

Our trajectory prediction model consists of two key components: encoder (E) and decoder (D), as shown in Figure4. E receives the past trajectory as input and then extracts the features and encodes them to a feature vector hd. D receives hd as input and generates future locations step by step. In our scheme, we build E and D based on LSTM.


#### 3.2.2. Encoder

The location of each time stamp in past trajectory is embedded to a fixed length vectoreei by a MLP:(2)eei=ϕxpi,ypi;We,where ϕ⋅ denotes the embedding function with ReLU activation, We is the embedding weight, and xpi,ypi is the i-th location of the past trajectory.These embedded vectors then input to the LSTM of the encoder step by step. This process is the recurrence as follows:(3)hei=LSTMhei−1,eei;Wen,where hei is the i-th hidden state of LSTM, the initial hidden state he0 is a zero vector, and the final hidden state het is used as the output of the encoder, which is representing the feature vector of the past trajectory. Wen denotes the weights of the LSTM, which are shared between all the time stamps.


#### 3.2.3. Decoder

In our scheme, the decoder is a one-to-many LSTM model [16]. The decoder receives the final hidden state of encoder het as the input and predicts k future locations (suppose the k-th future location is the destination). Traditional encoder-decoder model captures the impact of past trajectory on the future via the hidden state, which is an implicit way. This method loses a lot of information and thus damages the prediction accuracy. In order to address this problem, we adopt attentional mechanism to our prediction model. We explicitly model the impact of each location in past trajectory on the k future locations using the attention vector cj (j from 1 to k) and add it to the hidden state of the decoder. Before prediction, the hidden state of the decoder is initialized as(4)hd0=σhet;Wh,h˜d0=c0,hd0,where σ⋅ denotes the MLP with ReLU activation, Wh is the weight of the MLP, and h˜d0 is used as the initial hidden state of the decoder. The future locations are predicted by the decoder as the following recurrence:(5)edj−1=φx^fj−1,y^fj−1;Wd,hdj=LSTMh˜dj−1,edj−1;Wde,h˜dj=cj,hdj,x^fj,y^fj=γh˜dj;Wm,where φ⋅ denotes the embedding function with ReLU activation, Wd is the embedding weight, xfj,yfj is the j-th predicted location of the future trajectory, Wen denotes the weights of the LSTM, and γ⋅ denotes an MLP with ReLU activation with Wm as the weights.


#### 3.2.4. Attentional Mechanism

In order to explicitly model the impact of the past trajectory on the future, we use attentional mechanism in the decoder [17–19]. The key of the attention mechanism is to obtain the attention vector cj (j from 1 to k). When predicting the j-th future location, the weight aj−1 of each encoder hidden state hei to the j−1−th decoder hidden state hdj is calculated as(6)aj−1=expscorehdj,hei∑i=1nexpscorehdj,hei,where score⋅ is a function denoting the correlation. In our scheme, score⋅ is calculated as(7)scorehdj,he=hdj×Wa×hei,where Wa is a trainable weight matrix. Then the attention vector cj is obtained as(8)cj=aj−1×hei.


### 3.3. Branch Network

In order to judge which future location is destination, we design a branch classification network. This network receives the hidden state as input at each time stamp and then judges whether the currently predicted location is the destination. We use an MLP to achieve this mission:(9)Sd=MLPh˜dj;Wf,where Wf is the weight of the MLP and Sd is the score of whether the current location is the destination, ranging from 0 to 1. The smaller Sd is, the closer it is to the destination. If Sd is between 0 and 0.1, the current location is judged to be the destination.It is found that the branch network is difficult to converge by using binary label in training. To address this issue, we use normalized labels instead of binary labels. Specifically, we calculate the distance between each location and the destination in the real trajectory and normalized it to range (0, 1). The normalized distance is used as the label of this location.


### 3.4. Loss Function

The loss function of our model consisting of three terms is defined as follows:(10)L=Lp+αLj+βLd,where α and β are the trade-off parameters for Lj and Ld. We introduce how to determine their values in Section 4.2.There are two optimization objectives of our model. The first is to make the coordinates of the predicted locations as accurate as possible. The second is to judge how far the current location is from the destination. We use trajectory prediction lossLp to optimize the first objective and use destination judgment loss Lj to optimize the second objective. These two losses are defined as(11)Lp=∑inP^i−Pi,Lj=∑ind^i−di,where P^i denotes the coordinate of the i-th predicted location and d^i denotes the normalized distance between the i-th predicted location and the destination. Pi and di, respectively, denote their ground truth.In addition, our ultimate goal is to predict the coordinate of the destination. Therefore, we add a distance lossLd to facilitate this:(12)Ld=D^−D,where D^ denotes the coordinate of the predicted destination and D denotes the coordinate of ground-truth destination.


### 3.5. Implementation Details

There are three LSTMs in the proposed model. Each of them is assigned 128 cell units. In the training stage, we use Adam optimizer to update the parameters of the proposed model. The initial learning rate is 0.0003. We train the model for 200 epochs with a batch size of 64.


## 3.1. Problem Formulation

Our goal is to predict final destination according the past trajectory of the agent. Suppose that the past trajectory of an agent at a momenttn is denoted as X=X1,X2,…,Xn and the future trajectory is denoted as Y=Y1,Y2,…,Yd (ground truth) with the final destination Yd, in which the i-th location of the past trajectory is defined as Xi=xi,yi and the j-th location of the future trajectory is defined as Yj=xj,yj. We need to predict the final destination Yd at the moment tn receiving the past trajectory X as input.It is hard to predictYd directly because the locations between Xn and Yd are unknown at tn. We tackle this problem in two steps: predict future trajectory step by step and decide when to stop. Specifically, at tn, we firstly predict the next location Y^1 and then judge whether Y^1 is the destination. If Y^1 is not the destination, we predict Y^2 and then judge whether Y^2 is the destination and so on, until the destination is predicted. This is a continuous process, and we can use a common trajectory prediction approach to predict future locations and a branch classification network to judge which is the destination. The framework of proposed method is illustrated in Figure 4.Figure 4
The framework of proposed model. The proposed model consists of encoder-decoder architecture with attentional mechanism and a branch network.


## 3.2. Trajectory Prediction Approach

Trajectory prediction is a generative problem. Generative models can extract the feature of past trajectory and simulate possible future. In our scheme, we propose a time-series processing model basing encoder-decoder architecture to predict future trajectory.


### 3.2.1. Encoder-Decoder Architecture

Our trajectory prediction model consists of two key components: encoder (E) and decoder (D), as shown in Figure4. E receives the past trajectory as input and then extracts the features and encodes them to a feature vector hd. D receives hd as input and generates future locations step by step. In our scheme, we build E and D based on LSTM.


### 3.2.2. Encoder

The location of each time stamp in past trajectory is embedded to a fixed length vectoreei by a MLP:(2)eei=ϕxpi,ypi;We,where ϕ⋅ denotes the embedding function with ReLU activation, We is the embedding weight, and xpi,ypi is the i-th location of the past trajectory.These embedded vectors then input to the LSTM of the encoder step by step. This process is the recurrence as follows:(3)hei=LSTMhei−1,eei;Wen,where hei is the i-th hidden state of LSTM, the initial hidden state he0 is a zero vector, and the final hidden state het is used as the output of the encoder, which is representing the feature vector of the past trajectory. Wen denotes the weights of the LSTM, which are shared between all the time stamps.


### 3.2.3. Decoder

In our scheme, the decoder is a one-to-many LSTM model [16]. The decoder receives the final hidden state of encoder het as the input and predicts k future locations (suppose the k-th future location is the destination). Traditional encoder-decoder model captures the impact of past trajectory on the future via the hidden state, which is an implicit way. This method loses a lot of information and thus damages the prediction accuracy. In order to address this problem, we adopt attentional mechanism to our prediction model. We explicitly model the impact of each location in past trajectory on the k future locations using the attention vector cj (j from 1 to k) and add it to the hidden state of the decoder. Before prediction, the hidden state of the decoder is initialized as(4)hd0=σhet;Wh,h˜d0=c0,hd0,where σ⋅ denotes the MLP with ReLU activation, Wh is the weight of the MLP, and h˜d0 is used as the initial hidden state of the decoder. The future locations are predicted by the decoder as the following recurrence:(5)edj−1=φx^fj−1,y^fj−1;Wd,hdj=LSTMh˜dj−1,edj−1;Wde,h˜dj=cj,hdj,x^fj,y^fj=γh˜dj;Wm,where φ⋅ denotes the embedding function with ReLU activation, Wd is the embedding weight, xfj,yfj is the j-th predicted location of the future trajectory, Wen denotes the weights of the LSTM, and γ⋅ denotes an MLP with ReLU activation with Wm as the weights.


### 3.2.4. Attentional Mechanism

In order to explicitly model the impact of the past trajectory on the future, we use attentional mechanism in the decoder [17–19]. The key of the attention mechanism is to obtain the attention vector cj (j from 1 to k). When predicting the j-th future location, the weight aj−1 of each encoder hidden state hei to the j−1−th decoder hidden state hdj is calculated as(6)aj−1=expscorehdj,hei∑i=1nexpscorehdj,hei,where score⋅ is a function denoting the correlation. In our scheme, score⋅ is calculated as(7)scorehdj,he=hdj×Wa×hei,where Wa is a trainable weight matrix. Then the attention vector cj is obtained as(8)cj=aj−1×hei.


## 3.2.1. Encoder-Decoder Architecture

Our trajectory prediction model consists of two key components: encoder (E) and decoder (D), as shown in Figure4. E receives the past trajectory as input and then extracts the features and encodes them to a feature vector hd. D receives hd as input and generates future locations step by step. In our scheme, we build E and D based on LSTM.


## 3.2.2. Encoder

The location of each time stamp in past trajectory is embedded to a fixed length vectoreei by a MLP:(2)eei=ϕxpi,ypi;We,where ϕ⋅ denotes the embedding function with ReLU activation, We is the embedding weight, and xpi,ypi is the i-th location of the past trajectory.These embedded vectors then input to the LSTM of the encoder step by step. This process is the recurrence as follows:(3)hei=LSTMhei−1,eei;Wen,where hei is the i-th hidden state of LSTM, the initial hidden state he0 is a zero vector, and the final hidden state het is used as the output of the encoder, which is representing the feature vector of the past trajectory. Wen denotes the weights of the LSTM, which are shared between all the time stamps.


## 3.2.3. Decoder

In our scheme, the decoder is a one-to-many LSTM model [16]. The decoder receives the final hidden state of encoder het as the input and predicts k future locations (suppose the k-th future location is the destination). Traditional encoder-decoder model captures the impact of past trajectory on the future via the hidden state, which is an implicit way. This method loses a lot of information and thus damages the prediction accuracy. In order to address this problem, we adopt attentional mechanism to our prediction model. We explicitly model the impact of each location in past trajectory on the k future locations using the attention vector cj (j from 1 to k) and add it to the hidden state of the decoder. Before prediction, the hidden state of the decoder is initialized as(4)hd0=σhet;Wh,h˜d0=c0,hd0,where σ⋅ denotes the MLP with ReLU activation, Wh is the weight of the MLP, and h˜d0 is used as the initial hidden state of the decoder. The future locations are predicted by the decoder as the following recurrence:(5)edj−1=φx^fj−1,y^fj−1;Wd,hdj=LSTMh˜dj−1,edj−1;Wde,h˜dj=cj,hdj,x^fj,y^fj=γh˜dj;Wm,where φ⋅ denotes the embedding function with ReLU activation, Wd is the embedding weight, xfj,yfj is the j-th predicted location of the future trajectory, Wen denotes the weights of the LSTM, and γ⋅ denotes an MLP with ReLU activation with Wm as the weights.


## 3.2.4. Attentional Mechanism

In order to explicitly model the impact of the past trajectory on the future, we use attentional mechanism in the decoder [17–19]. The key of the attention mechanism is to obtain the attention vector cj (j from 1 to k). When predicting the j-th future location, the weight aj−1 of each encoder hidden state hei to the j−1−th decoder hidden state hdj is calculated as(6)aj−1=expscorehdj,hei∑i=1nexpscorehdj,hei,where score⋅ is a function denoting the correlation. In our scheme, score⋅ is calculated as(7)scorehdj,he=hdj×Wa×hei,where Wa is a trainable weight matrix. Then the attention vector cj is obtained as(8)cj=aj−1×hei.


## 3.3. Branch Network

In order to judge which future location is destination, we design a branch classification network. This network receives the hidden state as input at each time stamp and then judges whether the currently predicted location is the destination. We use an MLP to achieve this mission:(9)Sd=MLPh˜dj;Wf,where Wf is the weight of the MLP and Sd is the score of whether the current location is the destination, ranging from 0 to 1. The smaller Sd is, the closer it is to the destination. If Sd is between 0 and 0.1, the current location is judged to be the destination.It is found that the branch network is difficult to converge by using binary label in training. To address this issue, we use normalized labels instead of binary labels. Specifically, we calculate the distance between each location and the destination in the real trajectory and normalized it to range (0, 1). The normalized distance is used as the label of this location.


## 3.4. Loss Function

The loss function of our model consisting of three terms is defined as follows:(10)L=Lp+αLj+βLd,where α and β are the trade-off parameters for Lj and Ld. We introduce how to determine their values in Section 4.2.There are two optimization objectives of our model. The first is to make the coordinates of the predicted locations as accurate as possible. The second is to judge how far the current location is from the destination. We use trajectory prediction lossLp to optimize the first objective and use destination judgment loss Lj to optimize the second objective. These two losses are defined as(11)Lp=∑inP^i−Pi,Lj=∑ind^i−di,where P^i denotes the coordinate of the i-th predicted location and d^i denotes the normalized distance between the i-th predicted location and the destination. Pi and di, respectively, denote their ground truth.In addition, our ultimate goal is to predict the coordinate of the destination. Therefore, we add a distance lossLd to facilitate this:(12)Ld=D^−D,where D^ denotes the coordinate of the predicted destination and D denotes the coordinate of ground-truth destination.


## 3.5. Implementation Details

There are three LSTMs in the proposed model. Each of them is assigned 128 cell units. In the training stage, we use Adam optimizer to update the parameters of the proposed model. The initial learning rate is 0.0003. We train the model for 200 epochs with a batch size of 64.


## 4. Evaluation

In this section, we evaluate the proposed destination prediction method on a real world dataset. We introduce the dataset in Section4.1 and evaluate our method on the test set in Section 4.2. Finally, we perform a grid search on the validation set in Section 4.3.


### 4.1. Dataset

We use T-drive trajectory dataset [20] in our experiment, which is collected in T-drive project. This dataset contains trajectories generated by over 33,000 taxis in Beijing. There are about 15 million GPS data points recorded in this dataset and the total distance reaches 9 million kilometers. This dataset is widely used in destination prediction researches (Table 1).Table 1
Partial trajectory data sample in T-drive dataset.
User IDTime stampLongitudeLatitude10002008-02-02 13:34:52116.4836139.9449110002008-02-02 13:39:08116.4834739.9186910002008-02-02 13:49:11116.5138439.8919010002008-02-02 13:49:57116.5135939.8919710002008-02-02 13:54:13116.5244839.87212


#### 4.1.1. Data Cleaning

We find that the original trajectory dataset is partially noisy. Table2 shows two types of exceptional data in the original dataset. The first is the absence of latitude and longitude coordinates of a location. As shown in Table 2 (a), the latitude and longitude coordinates of the third location are zero, which is obviously the default value due to the failure to record this location. The second is that an obvious error of the longitude and the latitude of a location. As shown in Table 2 (b), the third location is over 1000 kilometers away from the area where the other locations are located. It is impossible for a vehicle to go there and back in 5 minutes, thus inferring that the third location is exceptional data. We design an algorithm to remove these exceptional locations from the trajectory to clean the dataset. For the first type, we remove the locations where longitude or latitude is zero value. For the second type, we set a threshold to filter out locations that are too far from the previous locations. In our algorithm, we set the threshold at 100 kilometers. The pseudocode is shown in Algorithm 1.Table 2
Two types of exceptional location data in original dataset.
User IDTime stampLongitudeLatitude(a) Missing location coordinates10162008-02-03 11:53:24116.4562339.9051210162008-02-03 11:54:43116.4573939.9054810162008-02-03 12:05:090.00.010162008-02-03 12:07:52116.4875739.9153610162008-02-03 12:12:56116.4987839.91566(b) Incorrectly recorded location coordinates18642008-02-02 17:22:03116.3001239.982618642008-02-02 17:25:14116.3003539.9718818642008-02-02 17:27:05108.4925431.9529518642008-02-02 17:30:15116.3014939.9638918642008-02-02 17:32:07116.3015839.96374


### 4.2. Evaluation

In this paper, we take three exiting methods as baseline schemes. The first is proposed by Ziebart et al. [11]. They calculated the probability PT|D∈Lj in (1) as follows:(13)PT|D∈Lj=Td∈Lj|T⊂Td∈LjTd∈Lj,where Td∈Lj denotes the trajectories that terminate at location Lj.Algorithm 1: Data cleaning algorithm.
Input: Original trajectory data in dataset including n locationsOutput: the cleaned trajectory(1)
Procedure(2)
fori = 1 to ndo:(3)
if latitude(i) = = 0 or longitude(i) = = 0:(4)
do remove the i-th location(5)
end if(6)
ifdistance((i − 1)-th location, i-th location) > Threshold:(7)
do remove the i-th location(8)
end if(9)
end forThe second is proposed by Xue et al. [2]. They decomposed historical trajectories into subtrajectories and then recombined these subtrajectories into synthesised trajectories to increase the number of historical trajectories.The third is proposed by Tang et al. [5]. They used a LSTM to extract the features of past trajectory and dense layers to extract the features of other information (including time stamps, vehicle ID, and Points of Interest). They fused these features into a vector, which they then fed into an MLP to predict the destination. Because external information is not used in other baseline schemes, we use the version without external information (only extract features from locations and time stamps) in our experiments.We evaluate our method with baselines varying the percentage of trip completed. The accuracy of destination prediction is different for trajectories with different percentages of trip completed. Generally, the prediction accuracy of the query trajectory with higher trip completed percentage is higher. The prediction error is shown in Figure5. Due to the high accuracy of deep learning in trajectory prediction, the prediction error of our method is smaller than that of baseline schemes. Tang et al.’s scheme has high prediction error when the percentage of travel completed is low, even higher than the statistical learning-based methods. This is because deep learning needs more data to extract features. Previous framework can only exploit past locations which are very limited when the percentage of travel completed is low. Our scheme addresses this problem by predicting future locations so that features of the whole trajectory are available when predict the destination.Figure 5
The prediction error varying the percentage of trip completed.


### 4.3. Trade-Off Parameters

In Section3.4, two trade-off parameters α and β are set to balance the loss function in (10). We perform a grid search on the validation set to determine the value of α and β. Specifically, we select α and β from {0.3, 0.5, 0.8, 1.0}. Then the selected α and β are paired together to train the proposed model. We test models using these pairs of trade-off parameter at 30 percentages and 70 percentages of trip completed. The prediction error is shown in Figure 6. When α=0.8 and β=1.0, the prediction error is minimized. Therefore, we adopt this group of trade-off parameters.Figure 6
The visual results of the grid search. (a) The prediction errors at the 70% of trip completed. (b) The prediction errors at the 30% of trip completed. In both cases, the prediction errors are minimal whenα=0.8 and β=1.0.
(a)(b)


## 4.1. Dataset

We use T-drive trajectory dataset [20] in our experiment, which is collected in T-drive project. This dataset contains trajectories generated by over 33,000 taxis in Beijing. There are about 15 million GPS data points recorded in this dataset and the total distance reaches 9 million kilometers. This dataset is widely used in destination prediction researches (Table 1).Table 1
Partial trajectory data sample in T-drive dataset.
User IDTime stampLongitudeLatitude10002008-02-02 13:34:52116.4836139.9449110002008-02-02 13:39:08116.4834739.9186910002008-02-02 13:49:11116.5138439.8919010002008-02-02 13:49:57116.5135939.8919710002008-02-02 13:54:13116.5244839.87212


### 4.1.1. Data Cleaning

We find that the original trajectory dataset is partially noisy. Table2 shows two types of exceptional data in the original dataset. The first is the absence of latitude and longitude coordinates of a location. As shown in Table 2 (a), the latitude and longitude coordinates of the third location are zero, which is obviously the default value due to the failure to record this location. The second is that an obvious error of the longitude and the latitude of a location. As shown in Table 2 (b), the third location is over 1000 kilometers away from the area where the other locations are located. It is impossible for a vehicle to go there and back in 5 minutes, thus inferring that the third location is exceptional data. We design an algorithm to remove these exceptional locations from the trajectory to clean the dataset. For the first type, we remove the locations where longitude or latitude is zero value. For the second type, we set a threshold to filter out locations that are too far from the previous locations. In our algorithm, we set the threshold at 100 kilometers. The pseudocode is shown in Algorithm 1.Table 2
Two types of exceptional location data in original dataset.
User IDTime stampLongitudeLatitude(a) Missing location coordinates10162008-02-03 11:53:24116.4562339.9051210162008-02-03 11:54:43116.4573939.9054810162008-02-03 12:05:090.00.010162008-02-03 12:07:52116.4875739.9153610162008-02-03 12:12:56116.4987839.91566(b) Incorrectly recorded location coordinates18642008-02-02 17:22:03116.3001239.982618642008-02-02 17:25:14116.3003539.9718818642008-02-02 17:27:05108.4925431.9529518642008-02-02 17:30:15116.3014939.9638918642008-02-02 17:32:07116.3015839.96374


## 4.1.1. Data Cleaning

We find that the original trajectory dataset is partially noisy. Table2 shows two types of exceptional data in the original dataset. The first is the absence of latitude and longitude coordinates of a location. As shown in Table 2 (a), the latitude and longitude coordinates of the third location are zero, which is obviously the default value due to the failure to record this location. The second is that an obvious error of the longitude and the latitude of a location. As shown in Table 2 (b), the third location is over 1000 kilometers away from the area where the other locations are located. It is impossible for a vehicle to go there and back in 5 minutes, thus inferring that the third location is exceptional data. We design an algorithm to remove these exceptional locations from the trajectory to clean the dataset. For the first type, we remove the locations where longitude or latitude is zero value. For the second type, we set a threshold to filter out locations that are too far from the previous locations. In our algorithm, we set the threshold at 100 kilometers. The pseudocode is shown in Algorithm 1.Table 2
Two types of exceptional location data in original dataset.
User IDTime stampLongitudeLatitude(a) Missing location coordinates10162008-02-03 11:53:24116.4562339.9051210162008-02-03 11:54:43116.4573939.9054810162008-02-03 12:05:090.00.010162008-02-03 12:07:52116.4875739.9153610162008-02-03 12:12:56116.4987839.91566(b) Incorrectly recorded location coordinates18642008-02-02 17:22:03116.3001239.982618642008-02-02 17:25:14116.3003539.9718818642008-02-02 17:27:05108.4925431.9529518642008-02-02 17:30:15116.3014939.9638918642008-02-02 17:32:07116.3015839.96374


## 4.2. Evaluation

In this paper, we take three exiting methods as baseline schemes. The first is proposed by Ziebart et al. [11]. They calculated the probability PT|D∈Lj in (1) as follows:(13)PT|D∈Lj=Td∈Lj|T⊂Td∈LjTd∈Lj,where Td∈Lj denotes the trajectories that terminate at location Lj.Algorithm 1: Data cleaning algorithm.
Input: Original trajectory data in dataset including n locationsOutput: the cleaned trajectory(1)
Procedure(2)
fori = 1 to ndo:(3)
if latitude(i) = = 0 or longitude(i) = = 0:(4)
do remove the i-th location(5)
end if(6)
ifdistance((i − 1)-th location, i-th location) > Threshold:(7)
do remove the i-th location(8)
end if(9)
end forThe second is proposed by Xue et al. [2]. They decomposed historical trajectories into subtrajectories and then recombined these subtrajectories into synthesised trajectories to increase the number of historical trajectories.The third is proposed by Tang et al. [5]. They used a LSTM to extract the features of past trajectory and dense layers to extract the features of other information (including time stamps, vehicle ID, and Points of Interest). They fused these features into a vector, which they then fed into an MLP to predict the destination. Because external information is not used in other baseline schemes, we use the version without external information (only extract features from locations and time stamps) in our experiments.We evaluate our method with baselines varying the percentage of trip completed. The accuracy of destination prediction is different for trajectories with different percentages of trip completed. Generally, the prediction accuracy of the query trajectory with higher trip completed percentage is higher. The prediction error is shown in Figure5. Due to the high accuracy of deep learning in trajectory prediction, the prediction error of our method is smaller than that of baseline schemes. Tang et al.’s scheme has high prediction error when the percentage of travel completed is low, even higher than the statistical learning-based methods. This is because deep learning needs more data to extract features. Previous framework can only exploit past locations which are very limited when the percentage of travel completed is low. Our scheme addresses this problem by predicting future locations so that features of the whole trajectory are available when predict the destination.Figure 5
The prediction error varying the percentage of trip completed.


## 4.3. Trade-Off Parameters

In Section3.4, two trade-off parameters α and β are set to balance the loss function in (10). We perform a grid search on the validation set to determine the value of α and β. Specifically, we select α and β from {0.3, 0.5, 0.8, 1.0}. Then the selected α and β are paired together to train the proposed model. We test models using these pairs of trade-off parameter at 30 percentages and 70 percentages of trip completed. The prediction error is shown in Figure 6. When α=0.8 and β=1.0, the prediction error is minimized. Therefore, we adopt this group of trade-off parameters.Figure 6
The visual results of the grid search. (a) The prediction errors at the 70% of trip completed. (b) The prediction errors at the 30% of trip completed. In both cases, the prediction errors are minimal whenα=0.8 and β=1.0.
(a)(b)


## 5. Conclusions

In this paper, we propose a destination prediction method based on deep learning. In order to address the discontinuity problem in destination prediction task, the proposed method continuously predicts the future locations using a trajectory prediction model and determines which future location is the destination via a branch network. In addition, we exploit attention mechanism in our model to make the prediction more accurate. Experimental results show that our scheme has a smaller prediction error than the baseline schemes.In the future, we plan to extend this research in the following directions. First, we plan to incorporate external information to the proposed model, such as driving habits and ground cover prior. Second, we plan to extract the semantic information of the trajectory to improve the accuracy of prediction.



---

*Source: 8385854-2022-03-21.xml*