Travel time prediction is an important component in intelligent transportation systems, and plays a key role in daily life. Predicting travel time for a trip is quite challenging and has been studied by many researcher. However, most of the studies focus on short term travel time prediction. In this study, LSTM (Long-Short Term Memory) neural network models are constructed to predict travel time for both long term and short term using real world data of New York city. Results of this study show that, LSTM provides satisfying results for long term travel time prediction as well as short term.
Tra c is a common problem of urban life and ITS
(Intelligent Transportation System) [
In recent years, there has been an increasing
interest in travel time prediction. For this reason, many
researchers focus on travel time prediction. In some
Copyright © CIKM 2018 for the individual papers by the papers'
authors. Copyright © CIKM 2018 for the volume as a collection
by its editors. This volume and its papers are published under
the Creative Commons License Attribution 4.0 International (CC
of these studies, time series models such as traditional
ARIMA [
In the forthcoming years, neural networks come in
the use for travel time prediction. There are several
researches which use arti cial neural network models
for this problem [
LSTM is also used for travel time prediction [
Although a research has been carried out on short term travel time prediction using LSTM, no single study exists which uses LSTM for both short term and long term, in details. Another contribution of this paper is that, this is the rst time LSTM is applied for long term travel time prediction problem, to the best of our knowledge. As it can be guessed, long term travel time prediction is quite di cult than short term travel time prediction. In long term travel time prediction, the main objective is predicting travel time value for a speci c day and hour, at least one week ago. In summary, we can say that main objectives of this study are applying LSTM models for long term and short term travel time prediction using real world data of New York.
The paper is organized as follows. Section 2 presents the approach and details of the dataset. Section 3 describes the experiments and the results obtained. Finally, in Section 4 we conclude and discuss some possible future works. 2
In this study, we aim to predict travel time for short term and long term using a real world travel time data. Several di erent tests are done to investigate behavior of LSTM for travel time prediction problem. In this section, we rst describe the data set used and then give the details of the method we applied to solve the problem of travel time prediction. 2.1
The data set used in this study is obtained from New
York City Department Of Transportation (NYC DOT)
which provides real-time tra c information from
major arterials and highways within New York city using
numerous IoT sensors [
Rows of obtained data contain these elds: id, speed, travel time, data as of, link points, borough and link name. De nition of these elds can be seen in Table 1. The data are updated every ve minutes and contain 135 di erent links within the ve boroughs of New York City. The dataset contains real time tra c data of links from April 2015 up to the current date but it is updated regularly by NYC DOT. Data row count of each month is nearly 1,150,000. For each link, there are nearly 275 rows (travel time values) in one day. The time intervals between each travel time values of a link are 5 minutes.
In this study, "DataAsOf" column which represents timestamp of the row and "TravelTime" column which represents the travel time value of the link are used for time series modeling. For each link, travel time values are ordered by "DataAsOf" column which represents date and time of the measurement. 2.2
Our experimental system design consists of four steps. The rst step is Data Preparation step. Afterwards, outlier elimination step helps us to discard the out of ordinary data rows. Then, LSTM model is applied to the dataset in Prediction Model step. At the end of the work ow, the Evaluation step calculates the error rates based on selected evaluation metric. The details of the whole process is given below. The aim of this study is predicting travel time for a selected link (a given street section) using previous travel time data. In order to achieve this aim, a time series is constructed using previous travel time information, for each link. This dataset contains travel time values of each link for every 5 minutes. As can be seen in Fig. 1, for predicting travel time of 5 minutes later using this dataset, the link's previous travel time values measured at 5 minute intervals should be used. On the other hand, for predicting travel time of 15 minutes later using this dataset, previous travel time values measured at 15 minute intervals should be used. In case of long term travel time prediction, for predicting the travel time value of a link at 8 o'clock on Monday, the data set should be generated using travel time values of previous weeks' Monday at 8 o'clock.
Also, data preparation step transforms data rows to a sequential structure. Using sequential output of this step, a time series forecasting model can be applied easily for predicting next step travel time value. Tra c prediction is quite di cult because of the fact that tra c is a ected by numerous di erent factors. Some of these factors can be handled with special solutions but some other factors such as weather conditions, special events, tra c accidents can be only handled using additional information. Because of the fact that we do not use additional dataset, these special situations are eliminated using an outlier detection method.
In this study, outliers are detected using the standard deviation of the last N travel time values. In our case, N is selected as 4. If a travel time value is quite di erent from the previous 4 travel time values, it is considered to be an outlier in our approach. According to this moving average approach, the outliers are eliminated from the dataset. 2.2.3
In the prediction step of the methodology, LSTM
(Long-Short Term Memories) [
The basic job of a cell is remembering the temporal state of the network. The input gate, output gate and forget gate can be thought as a neuron of a neural network. The input gate is responsible for deciding whether a new value ows into the memory, or not. On the other hand, the output gate decides whether the memory cell state is going to have an e ect on other neurons or not. The forget gate allows the cell to remember previous state or forget it.
In a given time t, the input of cell is xt, ht shows the output of the gate and Wi; Wf ; Wc; Wo; Ui; Uf ; Uc; Uo; Vo correspond to weight matrices. bi; bf ; bc; bo are bias vectors in the model equations of LSTM.
First of all, input gate values (it) and possible memory cell state values Cft are calculated using Eq. 1 and Eq. 2.
it = (Wixt + Uiht 1 + bi) ot = (Woxt + Uoht 1 + VoCt + bi)
ht = ot tanh(Ct)
LSTM networks can be applied to several di erent problems which contain prediction on sequential data. In this study, LSTM is applied for travel time prediction which is a time series prediction problem. Chain like structure of LSTM network which is used for this study, can be seen in Fig. 3. Reason of choosing LSTM as travel time prediction model is that LSTM neural network model is a special kind of neural network which considers sequential relation.
Cft = tanh(Wcxt + Ucht 1 + bc)
After that, the forget gate activation can be seen in Eq. 3. (1) (2) (4) (5) (6) ft = (Wf xt + Uf ht 1 + bf ) (3)
Using the Cft (candidate state value), it (input gate value) and ft (forget gate value), Ct which is the memory cell value can be calculated using Eq. 4.
Ct = it
Cft + ft
Ct 1
After state of the memory cell is calculated, the value of output gate ot and output ht can be calculated using Eq. 5 and Eq. 6. The error rates of the models are estimated using Mean Average Percentage Error (MAPE). In Eq. 7 which shows calculation formula of MAPE, At means actual value and Ft means forecasting value.
Comparison of all experiments can be seen in the next section, Experiments and Results.
n M AP E = 100 X jAt n t=1
Ftj jAtj (7) 3
In this section, we describe the details of our experiments and present the results obtained by our experiments for travel time prediction.
In the rst group of experiments, LSTM network is applied to long term travel time prediction problem. In long term travel time prediction, the aim is predicting travel time for a speci c day and speci c time of a week. In long term travel time prediction approach, the datasets are constructed using travel time values on the same day and time of previous weeks on a particular day's previous weeks' travel time values. For instance, if we want to predict travel time value at 2 p.m. on Wednesday, we construct the related time series dataset using travel time values on the same day and time of previous weeks. Afterwards, the outlier values are eliminated from the datasets because of the fact that these outlier values originate from unusual situations such as tra c accident, bad weather conditions, special occasions, etc. These cases cannot be handled without any extra information from other resources; therefore outliers are ignored during time series construction.
The long term travel time series datasets are constructed separately for each link, day and hour. For each link, there are 2016 di erent test instances which corresponds to data of one week. For each test instances, related previous travel time values are selected for training the related model. There 153 di erent links in the dataset.
In our LSTM experiments, there are a visible
input layer, a visible output layer and 3 hidden layers
with 4 LSTM neurons. Adam algorithm is used for
stochastic optimization [
In order to compare performance of the LSTM neural network on long term travel time prediction, we conduct the a prediction model using ARIMA. The results of these experiments can be seen in Table II.
According to our tests, it can be said that LSTM provides satisfying results for long term travel time prediction. Reason of this situation is that, LSTM is quite suitable for prediction on sequential data.
Rest of the experiments are focus on short term travel time prediction. In short term travel time prediction case, we complete 2 di erent test cases: predicting 5 minutes later and predicting 15 minutes later.
For predicting travel time value of 5 minutes later, the train datasets obtained using travel times of every 5th minutes for previous 2 hours. For each link, this experiment is done 12 times. You can see the comparison of LSTM and ARIMA models for predicting travel time of 5 minutes later, in Table III.
As we mentioned before, there is another paper
which applies LSTM for short term travel time
prediction [
It is apparent from Table III that LSTM models provide lower error rates than ARIMA models for both cases. In addition to that, it can be said that predicting 15 minutes later with LSTM network gives higher error rates than predicting 5 minutes later with LSTM network. Reason of this situation is that, previous 5 minutes gives more accurate information about travel time value of 5 minutes later.
Finally, some multi-step ahead predictions are performed using LSTM and obtained results are shown in Table IV.
From the Table IV, it can be seen that the lowest error rates are provided by 1 step ahead predictions. As the number of steps increases, the error rates are increases for both prediction models (model for 5 minutes step interval and model for 15 minutes step interval). What is interesting in Table IV is that 3 step ahead prediction with 5 minutes interval model and 1 step ahead prediction with 15 minutes interval model are both aim to predict 15 minutes later. 1 step ahead prediction with 15 minutes interval model gives lower error rate than the other. Because of the fact that multi-step ahead prediction uses its own prediction results for predicting the next step, errors of each step are cumulates. The main goal of the current study was to investigate the performance of LSTM models for both short term and long term travel time prediction. As far as we know, this is the rst time LSTM is applied for long term travel time prediction and obtained results show that it provides satisfying results for this problem. In addition to that, LSTM network model is applied for short term prediction and it is shown that LSTM model for predicting 5 minutes later overcomes LSTM model for predicting 15 minutes later. Also, multistep ahead prediction performances are measured for short term predictions. Evaluation results show that the 1-step ahead predictions give better results than multi-step ahead prediction. Taken together, these results suggest that LSTM network model is quite suitable for travel time prediction problem. As a fearure work, we are going to improve these results by involving other data resources to predict outlier situations such as bad weather conditions, tra c jam which is originated from social events, etc.