FMA-ETA: Estimating Travel Time Entirely
Based on FFN With Attention

Estimated time of arrival (ETA) is a challenging problem in the field of intelligent transportation system. There are two representative methods for solving ETA, route-based method and data-driven method. The route-based method focus on formulate the travel time of a given route as the summation of time on each road segment and each intersection. Traditional machine learning methods such as dynamic Bayesian network [7], least-square minimization [26] and pattern matching [3] are typical approaches to capture the spatial-temporal features in the route-based method. However, the idea of dividing the original trajectory results in the accumulation of local errors. The data-driven method has shifted from traditional methods such as TEMP [20] and time-dependent landmark graph [25] to deep-learning based methods [22, 5]. MURAT [14] uses multi-task learning and graph convolutional networks to assist a residual block to predict the travel time from the departure to the destination without a given trajectory. In recent years, researchers have conducted more explorations on applying deep learning methods to solve ETA problems, such as Deeptravel [28], DeepTTE [19], Deepi2t [12] and WDR [22]. These methods apply different approaches on modeling spatial information, but they all use LSTM [6] to extract features from time series. However, the inference speed of the model with LSTM is too slow to be applied in actual scenarios. In this work, we proposed FMA-ETA which can sufficiently handle the above problem.

Attention is a very effective mechanism in natural language processing [1], image caption [23] and other research areas [16]. Attention mechanism has outstanding ability in capturing semantic dependencies. Common attention mechanisms are local attention, global attention [15], self-attention [18], etc. Transformer [18] is a novel sequence to sequence network entirely based on FFN with Multi-head self-attention. It achieves promising results in translation with a faster speed than RNN-based models. Then self-attention becomes a hot topic in neural network attention research. Self-attention is calculated by:

$$\text{ Self-attention }=\operatorname{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d}}\right)\mathbf{V}$$

(1)

where $\mathbf{Q},\mathbf{K},\mathbf{V}$ is query, key and value matrix, $d$ is the dimension of key and query matrix, and key and query matrix are usually the same. Self-attention is proved useful in a wide variety of tasks including sequential recommendation [10], reading comprehension [24], speech recognition [17] and traffic flow predicting [29].

Deep learning-based ETA models are mostly RNN-based models. RNN has problems when deals with long-range dependencies. LSTM are able to deal the problem to some extent, but in practice it still have problems in long-range dependencies. The inference time of LSTM-based model is too long for practical application, so it is vital to introduce attention mechanism to the ETA problem.

The first main step is the sophisticated feature engineering where we follow [22]. Rich features from massive raw data is the key input for deep learning model. Features could be divided into the following two categories.

(1) Global features are sparse and one trajectory corresponds to one global representation, such as driverID, day of week, departure time slice. The method, Embedding [2] is adopted for the dimensionality reduction of sparse features.

(2) Sequential features are related to each link of the trajectory, for instance, length of the link (road segment), speed (road contidion), link time (related to road contidion) and embedding of linkID. These four factors influence ETA from different perspectives.

We then describe the overall framework of FMA-ETA, as shown in Fig. 2.

Two main components of FMA-ETA are Multi-factor Attention and FFN.

(1) Sequential features adopt our Multi-factor Attention which will be discussed in detail in next subsection. This component fully explores the relationship between different links in each track.

(2) Parallelizable FFN is the main reason for simplicity and fast inference that are our greatest advantages compared with RNN. The front FFN is utilized for each sequential factor to mining the spatial-temporal patterns in their single aspect as well as for concatenated factors. The last FFN is for the information aggregation from sequential separate and combined representations as well as embeddings of global features.

The regressor is one linear layer with ReLU [11] as the activation function. The Objective function of the overall deep learning model is the mean absolute percentage error (MAPE) which is an common and relative loss function for ETA. The FMA-ETA’s parameters are trained through:

$$\min_{\theta}\sum_{i}\left|\frac{y_{i}-y_{i}^{\prime}}{y_{i}}\right|,$$

(2)

where $y_{i}^{\prime}$ is $i_{th}$ query’s ETA, $y_{i}$ is the ground truth time and $\theta$ is all the parameters of FMA-ETA.

ETA is a challenging and complex problem due to the fact that various factors affect the accuracy of prediction, such as the link length as well as its road condition. Therefore, unlike for natural language processing where one word can be represented by a single embedding vector, different sequential features ought to be treated and dealt with more specifically for ETA. Our Multi-factor Attention mechanism is proposed to let different sequential factors mine its patterns and the impact on ETA in different subspaces, as shown in the upper left corner of Fig. 2. Self attention is with reference to [18] and we add position encoding, residual connections, layer normalization, and dropout after self attention following [18]. Combined sequential features also capture the spatial-temporal patterns as a whole by FFN with self-attention.

In the Fig. 2, we show the Multi-factor Attention mechanism with three factors. When the number of the factors is arbitrary $n$, the general Multi-factor Attention could be expressed:

	$\displaystyle\text{Multi-factor}(\text{factor}_{1},...,\text{factor}_{n})\left.=\text{Concat}(\text{self}_{1},...,\text{self}_{n},\text{self}_{\text{all}}\right)\mathbf{W}^{O}$		(3)
	$\displaystyle\text{where}\ \text{self}_{i}=\text{Self-attention}\left(\text{factor}_{i}\mathbf{W}_{i}^{Q},\text{factor}_{i}\mathbf{W}_{i}^{K},\text{factor}_{i}\mathbf{W}_{i}^{V}\right),$
	$\displaystyle i=1,...,n$
	$\displaystyle\text{self}_{\text{all}}=\text{Self-attention}\left(\text{factor}_{C}\mathbf{W}_{all}^{Q},\text{factor}_{C}\mathbf{W}_{all}^{K},\text{factor}_{C}\mathbf{W}_{all}^{V}\right),$
	$\displaystyle\text{factor}_{C}=\text{Concat}(\text{factor}_{1},...,\text{factor}_{n}).$

Where $\text{factor}_{i}$ is the i-th factor of ETA problem, ${\mathbf{W}_{i}}^{*}$ is the learned parameters in the FFN layers of the i-th factor, ${\mathbf{W}_{all}}^{*}$ is the learned parameters in the FFN layers of the combined features. For our FMA-ETA, sequential factors contains (1) length of the link, (2) road contidion speed, (3) corresponding link time and (4) embedding of linkID. Hence, we adopt the Multi-factor Attention version of four factors, i.e., $n=4$. Through concatenating the separate and combined sequence representations, our Multi-factor Attention complete the multi level and detailed extraction of the spatial-temporal dependencies of sequence data.

We evaluate our model on a large-scale real-world floating-car trajectory dataset Beijing 2018 collected by a ride hailing platform. It contains the trajectory data of hundreds of millions of Beijing taxi drivers after desensitization for more than 4 months in 2018. This dataset covers different types of roads in Beijing urban areas, including local streets and freeways. We filter out the abnormal data where the driving time is less than 60s or the speed exceeds 120 km/h in Beijing 2018. We divided this data set into atraining set (the first 16 weeks of data), a validation set (the middle2 weeks of data) Test set (data for the last 2 weeks).

We compared the proposed FMA-ETA with the following competitors:

(1) Route-ETA: a representative method for traditional non-deep learning methods. It divides the trajectory into several links and intersections. The travel time $t_{i}$ in the i-th link of this trajectory is calculated by dividing the link’s length by the estimated speed in the i-th link. The delay time $c_{j}$ in the j-th intersection is provided by a real-time traffic monitoring system.The final arrival time is the sum of the estimated time spent in each subsection.

(2) WDR(RNN): a deep learning method achieving the state-of-the-art performance in ETA problem. WDR is a joint model including width module, depth module, and recurrent module. It can effectively use the dense features, high-dimensional sparse features and local features of road sequence in traffic information. Here we use RNN in the recurrent module.

(3) WDR(LSTM): a variants of WDR(RNN). Here we use LSTM in the recurrent module of WDR and we make no changes to other part of WDR.

(4) WD-FFN: a variants of WDR. It uses deep module to replace the recurrent module. Here we use a Multi-Layer Perceptron network for comparision.

(5) WD-Resnet: a variants of WDR. It uses deep module to replace the recurrent module. Here we use a residual structure to extract features.

(6) Multi-head attention: a variants of WDR. We use FFN with multi-head attention mechanism instead of RNN to extract features from the sequential data.

If this work is accepted, we will open source the codes of proposed deep learning-based model, FMA-ETA.

In our experiment, all models are written in PyTorch. They are trained and evaluated on a single NVIDIA Tesla P40 GPU. The number of iterations of the deep learning-based method is 3.5 million. We use the method of Back Propagation (BP) to train the deep learning-based methods, and the loss function is the MAPE loss. We choose Adam as the optimizer due to its good performance. The batch size is 256 and the initial learning rate is 0.0002.

To evaluate and compare the performance of FMA-ETA and other baselines, we use evaluation metrics, Mean Absolute Percentage Error (MAPE), Mean Absolute Error (MAE) and Rooted Mean Square Error (RMSE):

$$\mathrm{MAE}(y,y^{\prime})=\frac{1}{N}\sum_{i=1}^{N}\left|y_{i}-y_{i}^{\prime}\right|$$

(4)

$$\mathrm{RMSE}(y,y^{\prime})=\sqrt{\frac{1}{N}\sum_{i=1}^{N}\left(y_{i}-y_{i}^{\prime}\right)^{2}}$$

(5)

where $y_{i}^{\prime}$ is the predicted travel time, and $y_{i}$ is the ground truth travel time. The calculation process of MAPE is shown in Section 3.

Table 2 shows the general three evaluation metrics for ETA problems. Our FMA-ETA outperforms all competitors in terms of MAE and RMSE metrics. FMA-ETA achieves similar results with the start-of-the-art method WDR(LSTM) in terms of MAPE metric. The detailed analysis of the experimental results are as follows.

(1) The representative non-deep learning method, route-ETA performs worse than other deep learning based methods. It shows that the data-driven method is more effective than route-based method. The deep method is suitable for modeling complex transportation system given massive spatio-temporal data.

(2) Models with recurrent module performs better than models that only use deep modules without attention mechanism. WDR(RNN) and WDR(LSTM) achieves better results than WD-FFN and WD-Resnet. WDR(LSTM) performs best on MAPE metric, because the use of gated units can solve the problem of long-term dependencies to a certain extent. The deep modules with attention achieve better results than WDR on MAE and RMSE metrics, which means attention mechanism can help to extract features and sole the long-range dependencies in long sequence.

(3) Our FMA-ETA performs best on MAE and RMSE metrics, which means our method is very applicable to ETA problems. Our FMA-ETA outperforms LSTM by 1.05% in terms of MAE loss and 1.86% in terms of RMSE loss. Our FMA-ETA perform similar results to WDR(LSTM), and our FMA-ETA only 0.1% worse than WDR(LSTM) in terms of MAPE metric. Considering the three evaluation metrics, our FMA-ETA performs best on ETA problems.

(4) As can be seen in the "Latency" column of Table 2, our FMA-ETA speed up the inference process by $21.8\%$ compared with WDR(LSTM). Route-ETA has the shortest time of 0.179s, but its performance on evaluation metrics is poor. FFN-based methods without attention mechanism is fast, but it brings a great loss on the evaluation metrics. Model with multi-head attention is faster than FMA-ETA. Its performance is worse than FMA-ETA. If the performance of models for ETA problem is not good enough, many tasks of ETA’s downstream in intelligent transportation systems such as route planning, navigation and vehicle dispatching will be affected greatly. Therefore, we should increase the inference speed of the model while ensuring the accuracy. Currently only our FMA-ETA can reach the goal.

Our FMA-ETA has a good performance on the ETA problem, and it greatly prompts the inference speed compared with the state-of-the-art method WDR(LSTM). FMA-ETA achieves clear improvements over WDR(LSTM) regarding to MAE and MAPE metrics. Taking into account both evaluation metrics and speed, our method is the most suitable method for ETA problems.

As we analyzed above, the state-of-the-art method WDR(LSTM) for ETA problem in previous literature takes a long time for inference. This makes WDR(LSTM) hard to be applied in the real-time traffic system. FFN can greatly accelerate the inference speed of the model for ETA problem, such as WD-FFN and WD-Resnet, but it causes a large decrease in accuracy which can be seen in Table 2. The attention mechanism can help FFN to effectively extract sequence features. The existing multi-head attention improves the inference speed, but it still brings a great loss of accuracy. Our goal is to increase the inference speed of the ETA model while ensure that the evaluation metrics do not decrease. We can see from the average inference speed in Tabel 2, only FMA-ETA can achieve the goal. We further explore the inference speed of WDR(LSTM) and FMA-ETA with different sequence length. We randomly sample 50 samples at each sequence length for WDR(LSTM) and FMA-ETA, then plot the scatters in Figure 3. The curve in Figure 3 is obtained by fitting the sampling points through logarithmic fitting.

As illustrated by the figure, our FMA-ETA is obviously faster than WDR(LSTM) when the sequence length is large than 180. LSTM-based model is fast in short sequences, and its consuming time increases rapidly as the sequence becomes longer. In actual car rides data, long-range sequences are common, so FMA-ETA is more applicable for practical problems.