CN109035761A - Travel time estimation method based on back-up surveillance study - Google Patents

Abstract

The invention belongs to the technical field of intelligent transportation, in particular to a method for estimating travel time based on auxiliary supervised learning. It looks for statistical laws from massive historical trajectory data, and estimates the time of the entire trip through an end-to-end deep learning model; the steps include: feature extraction and representation stages, preprocessing the trajectory data, extracting its time and Spatial features, driving state features, short-term and long-term traffic condition features; in the training and prediction phase, these extracted features are trained and predicted with a unified two-way cyclic neural network; each step of the cyclic neural network outputs through the current small area The time cost of these small areas is the sum of the time cost of the total path. At the same time, a bidirectional interval loss function is also introduced to constrain the intermediate time overhead. This method can efficiently and accurately estimate the vehicle travel time in the city, and has a good effect in the actual environment.

Description

Travel Time Estimation Method Based on Auxiliary Supervised Learning

technical field

The invention belongs to the technical field of intelligent transportation, and in particular relates to a method for estimating travel time based on auxiliary supervised learning.

Background technique

Travel time estimation is an essential and important technology in the field of urban transportation, which can provide assistance for people's travel and commuting, and can also provide support for government planning decisions. But this is not a simple small problem, but will be affected by various dynamic factors, such as traffic dynamics, intersection conditions, changes in driver's driving behavior and historical periodic data evolution, etc. These factors lead to uncertainty and difficulty in estimating travel time. With the development and popularization of GPS-enabled mobile devices, a large amount of trajectory data has been continuously generated and covers every corner of the city. With these massive historical trajectory data, we can mine the inherent laws behind the data, and learn the cycle and trend of travel time changes by building an algorithm model, so as to more accurately infer the time required for the current query trajectory.

At present, most of the existing methods adopt a divide-and-conquer method, mainly by decomposing the path into a series of road sections or sub-paths.

(1) The method based on a single road section:

The method based on a single road segment mainly estimates the average speed of the trajectory of each single road segment, and then calculates the average time cost of passing according to the length of the road segment, and finally accumulates the time of each road segment to obtain the total time. But this method does not consider the intersection time overhead between road segments. Additionally, this estimation relies heavily on high-quality velocity data, which is often not available in trajectory data.

(2) Subpath-based method:

The subpath-based method mainly divides the path into a series of subpaths, so that the time cost of the intersection is also considered. The main idea is to splicing and mining the rich public sub-path information in the historical data. Although this approach can overcome many of the shortcomings of the single-segment approach, it is still based on heuristic design rather than directly taking travel time as the algorithm optimization goal.

All in all, there are two reasons why currently existing methods cannot achieve satisfactory accuracy. One is that they do not treat the path as a whole, but split it into sub-blocks. In this splitting process, a lot of useful information is lost. Moreover, they do not make full use of the unique intermediate supervision labels of trajectory data, that is, the timestamp information of each intermediate GPS sampling point. On the other hand, with the development and prosperity of deep learning technology, more problems can be solved through end-to-end integration, which is more efficient than traditional heuristic models. Moreover, deep learning has a powerful representation ability. Compared with manual models, it can capture more potential features and can deal with various complex dynamics in travel estimation problems.

Contents of the invention

The purpose of the present invention is to address the limitations of the traditional two types of travel time estimation techniques, and propose a travel time estimation method based on historical trajectories of auxiliary supervised learning to overcome the deficiencies of the prior art.

The method of the present invention searches for statistical laws from massive historical trajectory data, and performs an overall estimation of the entire travel time through an end-to-end deep learning model. The basic steps include: the feature extraction and representation stage, preprocessing the trajectory data, and extracting its various features; the training and prediction stage, using a unified two-way cyclic neural network to train and predict these extracted features; cyclic neural network Each step of the network outputs the time cost of passing through the current small area; the sum of the time cost of these small areas is the time cost of the total path; in order to train more effectively, a bidirectional interval loss function is also introduced to constrain the intermediate time cost.

The travel time estimation method based on the historical trajectory of auxiliary supervised learning proposed by the present invention is divided into the following three stages:

(1) Feature extraction and representation stage, preprocessing the historical trajectory data, and extracting its various features (including temporal and spatial features, driving state features, short-term and long-term traffic conditions, etc.). The specific steps are:

In step (1), within the city limits, the grid is fine-grained according to the latitude and longitude coordinates to form adjacent small rectangular areas. Sorting in chronological order, each coordinate point in the trajectory sequence composed of GPS coordinates is mapped to the corresponding small area to form a sequence composed of grid coordinates. For the situation that the adjacent trajectory points are far away and fall in a small discontinuous area, the intermediate path can be obtained by algorithms such as map matching, and the information of this part of the discontinuous area can be supplemented.

Step (2), for each grid, mining its different aspects of features. First, embedding vector technology is used to mine latent semantic information. Embedded vector technology has been widely used in the fields of natural language processing and social networks. It mainly uses low-dimensional real number vectors to represent the semantic information of each word or thing, and measures the relationship between objects through the distance relationship in the vector space. Correspondence. The present invention uses embedded vector technology to represent the semantic information of each small grid area in different spaces and different time periods. These information include the spatial location information of different functional areas of the city (such as residential areas, commercial areas or industrial areas, etc.), as well as time information such as morning peak hours and weekends. Specifically, a low-dimensional vector is used to represent the space vector V _sp of each grid, and a day is divided into multiple time buckets (for example, one bucket per hour), and each trajectory obtains the time vector V according to the specific time bucket it falls into. _tp . Randomly initialize V _sp and V _tp , and then train with the model during model training.

In step (3), when the driver is driving, the driving speed and driving behavior will change in different driving states. For example, when the vehicle is in the middle of the driving path, it will be more inclined to drive on the road or elevated, and the speed will be faster at this time. When just starting or approaching the end, the speed will often slow down due to driving on a small road or in a crowded area. Specifically, the four-dimensional vector V _dri is used to indicate whether the current driving stage is a departure stage, a midway stage, or an end stage, and the proportion of the current driving in each stage. For example, V _dri =(1, 0, 0, 0.2) means that the driver travels at the beginning stage, which accounts for 20% of the total trip.

In step (4), traffic conditions in an area tend to change periodically and regularly over time. For example, if a road segment is congested from 8:00 to 8:30, it may also be congested at 8:35. That is to say, the traffic condition information in a short period of time in the past is very helpful for predicting the current traffic condition. The traffic condition characteristic of this short time is defined as V _short . At the same time, long-term periodic changes in traffic conditions can also help predict the current traffic conditions, such as the regularity of traffic conditions on weekdays and weekends. The traffic condition characteristic of this long time is defined as V _long . Specifically,

definition:

Indicates the traffic status of the current small area g _i in the jth time interval in the past, where v _j represents the historical average speed, n _j represents the number of historical trajectory data, and len _i /v _j represents the roughly estimated passing time. These traffic condition features are input into a sub-cycle neural network according to the order of historical time, and the traffic condition features can be extracted.

In addition, due to the uneven distribution of historical data in different spatial regions, some regions have a small number of trajectories, which may affect the accuracy of estimation. In order to solve this data sparsity problem, the traffic status information of adjacent small areas is also taken into account, that is,

definition:

Represents a set of grids whose distance from g _i does not exceed d, collects their past short-term traffic condition characteristics, and inputs them into the neural network together. Among them, x, y represent the coordinates of the grid, and g _j represents other grids except g _i .

(2) In the training phase, the features extracted from the historical trajectory data are input into a unified bidirectional LSTM, references: Graves A, Schmidhuber J. Framewise phoneme classification with bidirectional LSTM and other neural network architectures[J]. Neural Networks,2005,18(5-6):602-610.) for training, and use the bidirectional interval loss function as the training constraint; the specific steps are:

Step (1), constructing a recurrent neural network. Define the hidden layer of the network as The input data is Then, the input data of step t is x _t , and the calculation result obtained in step t is h _t , then:

h _t ＝φ(x _t ·W _x +h _t-1 ·W _h +b) (3)

in, is the weight matrix of the input data, is the weight matrix of the hidden layer, is the bias parameter (bias). φ represents a nonlinear activation function, which can be a sigmoid function, a ReLU function, a tanh function, and so on.

That is to say, the hidden state can be expressed as a function:

h _t ＝f(h _t-1 ,x _t ) (4)

On this basis, the forget gate is defined as:

f _t ＝σ(W _f ·[h _t-1 ,x _t ]+b _f ) (5)

The input gate is:

i _t =σ(W _i ·[h _t-1 ,x _t ]+b _i ) (6)

The output gate is:

o _t ＝σ(W _o [h _t-1 ,x _t ]+b _o ) (7)

The update of the memory unit is:

The update of the hidden layer is:

h _t ＝O _t ·tanh(C _t ) (10)

Among them, W _f , W _i , W _o , represent the weight matrix of forget gate, input gate, output gate and memory unit respectively, b _f , b _i , b _o , is the corresponding bias parameter. σ() is a non-linear activation function, such as is a sigmoid function, is a hyperbolic tangent function, and f( ) represents an abstract neural network function including parameters of each layer. Define the parameter corresponding to the cyclic neural network as W _N ; initialize each weight parameter in the cyclic neural network from the uniform distribution of [-α,α], where α is a hyperparameter, and the setting range is from 0.01 to 1.

Bidirectional RNNs use both a forward RNN and a reverse RNN for computation. Among them, the forward cyclic neural network sequentially inputs the grid features extracted in the previous steps according to the order of the sequence, while the reverse cyclic neural network inputs the grid features after the sequence is reversed. The advantage of doing this is that the neural network can observe the position distance of the current grid from the starting point and the end point at the same time, so as to have an overall feature. Define its hidden variable as the splicing of forward and reverse networks in Represents the hidden layer of the forward recurrent neural network, Represents the hidden layer of a reverse recurrent neural network.

Step (2), the features extracted from the historical trajectory data, that is, the spatial features time feature driving status characteristics Historical short-term and long-term traffic status characteristics and Concatenate into a unified eigenvector:

Input the bidirectional cyclic neural network into each passing small grid to obtain the passing time of the grid, that is, W ^T h _i +b. total trip time cost for:

definition are the weight matrix and bias parameters for calculating the total time overhead, respectively. W ^T denotes the transpose of the W matrix.

Step (3), define the real time cost vector of the trajectory passing through each grid sequence as T. The sequential real time cost vector is T ^f , and the reverse real time cost vector is T ^b . Then the time cost vector estimated by the neural network is:

The model is assisted with supervised learning using a bidirectional interval loss function, so that it not only learns the time cost of the entire path, but also learns the transit time of each intermediate stage. Define the two-way interval loss function as:

Among them, M indicates whether the trajectory passes through the mask of the small area, and [] indicates the operation between each element of the vector.

Step (4), the training goal is to minimize the loss function L, namely:

Among them, θ represents the training parameters of the model, ε represents the embedding vector in time and space, and S is the size of the training set. Finally, the parameters of the model are updated and optimized using the backpropagation algorithm based on time sequence. Backpropagation Algorithm References: Chauvin Y, Rumelhart D E. Backpropagation: theory, architectures, and applications [M]. Psychology Press, 2013.

(3) In the prediction stage, use the bidirectional recurrent neural network to infer the features extracted from the query path and estimate the travel time; the specific steps are:

Step (1), given a real itinerary without a time stamp as the query path, according to the actual path passed, get its mapped grid sequence. For each passing small grid, use the spatio-temporal features V _sp and V _tp obtained in the feature extraction and representation stages, the driving state features V _dri , and the historical short-term and long-term traffic state features V _short and V _long , V is represented as the total feature of the grid. Among them, the embedding vector of the spatio-temporal feature uses the vector information updated by the parameters of the training process. Short-term and long-term traffic state features are mined using a trained sub-recurrent neural network.

In step (2), in each passing grid, input all aspects of the extracted features into the trained bidirectional cyclic neural network to obtain the current hidden variable h _t , then the estimated time to pass through the current area is W ^T · _ht +b. And the total time cost estimate is:

Among them, n represents the total number of grids passed, Calculate the weight matrix and bias parameters of the total time overhead for training. W ^T denotes the transpose of the W matrix.

In general, the method of the present invention has the following advantages. First, using an end-to-end (end-to-end) deep learning method based on historical data training, directly learn the characteristics of the entire path and estimate the overall transit time. We define a bidirectional interval loss function, which can supervise the overall path time while assisting in supervising the time cost of passing through the intermediate road sections. This method of introducing auxiliary supervision not only enriches the sample information of the path, but also makes the propagation signal more accurate when the backpropagation algorithm updates the parameters. Secondly, a feature extraction structure is proposed, which can effectively estimate the travel time of the route by extracting dynamic features of different dimensions such as spatio-temporal embedding vectors, driving status, and short-term and long-term traffic conditions. Finally, it has been verified by experiments in the actual environment, and has better experimental results than existing methods.

As shown in Table 1, we conduct experiments with real historical trajectory data, including the two cities of Porto and Shanghai. We compare existing methods such as segment average time method, sub-path dynamic programming method, grid fully connected network method, and grid convolution network method. Among them, the road section average time method obtains the result by directly accumulating the average passing time of each road section. Sub-path dynamic programming method[Yilun Wang, Yu Zheng, and Yexiang Xue.Travel timeestimation of a path using sparse trajectory-ries.In Proceedings of the 20thInternational Conference on Knowledge Discovery and Data Mining(SIGKDD),pages25–34,2014.] Using dynamic programming to find the optimal stitching method for subpaths. The grid fully connected network method and the grid convolutional network method take an N×N overall grid as input, and use a fully connected network (Multi-Layer Perceptron) and a convolutional neural network (Convolutional Neural Network) for optimization and estimation, respectively. We use MAE, RMSE, and MAPE three error metrics to measure the quality of the method.

Among them, y represents the real value, Indicates the estimated value, and n indicates the total number of samples. As can be seen from the results in Table 1, the method of the present invention is far better than the existing comparative method in every index. For example, on the Shanghai data set, the method of the present invention estimates that the MAE error is only 126 seconds, and the MAPE error is 13.3%, while the MAE error of the existing best method is 168 seconds, and the MAPE error is 19.1%.

Table 1

Description of drawings

Figure 1 shows a real trajectory sample, including the time stamp information of each intermediate GPS trajectory point, and a total of 720s has passed.

Figure 2 shows the path samples that need to be queried, which only contain specific path information and do not contain any time stamp information.

Detailed ways

The specific implementation process of the present invention will be described below in conjunction with specific examples:

The historical trajectories in Figure 1 are used for training, and the travel time in Figure 2 is estimated.

1. The preprocessing stage, the feature extraction and representation stage, preprocesses the trajectory data and extracts its various features. Taking Figure 1 as an example, the specific steps are:

(1) In the urban area, fine-grained grid division is carried out, and it is divided into adjacent small areas. As shown in Figure 1, the map is divided into 5×6 grids. Each coordinate point in the trajectory sequence is mapped to a corresponding small area to form a grid sequence, that is, g={g ₁ , g ₂ ,...,g ₁₀ }.

(2) For each grid, mine its characteristics in different aspects. For example, for g ₁ , use a random vector and to represent spatiotemporal semantic information. which is:

Second, use the 4D vector To indicate whether the current driving stage is the starting stage, the halfway stage, or the end stage, and the proportion of driving in each stage, namely:

Finally, use past short-term and long-term traffic condition information to predict current traffic condition characteristics and Specifically, define It is the traffic condition of the current area g ₁ in the past 1st to 6th time interval (5min). E.g Indicates that the historical average speed is 10m/s, there are 8 historical trajectories, and the average passing time is estimated to be 20m/s. Will These traffic condition features are input into a sub-cycle neural network according to the order of historical time, and the final output hidden layer vector h ₆ is used as the traffic condition feature.

Second, the training phase, the specific steps are:

(1) Establish a bidirectional cyclic neural network (Bi-directional LSTM) model. Randomly initialize the parameters of the model, including the forget gate, input gate, matrix parameters and bias parameters of the output gate.

(2) The features extracted from the historical trajectory data, namely the spatial feature V _sp , the temporal feature V _sp , the driving state feature V _dri , the historical short-term and long-term traffic state features V _short and V _long , are spliced into a unified eigenvectors of . Take grid g ₁ as an example

(3) Input each passed small grid into the bidirectional cyclic neural network to obtain the passing time of the grid, that is, W ^T ·h _i +b. The total travel time cost is:

For example, define W=(0.1,0.3,..,0.7), and the 10 grid hidden layer variable values are h ₁ =(0.8,0.3,…,0.2),…,h ₁₀ =(0.7,0.4,.. 0.5), bias value b=0.7, then:

(4) Define the real time cost vector of the trajectory passing through each grid sequence as T. The real time cost vector in sequence is T ^f =(70,120,...,720), and the real time cost vector in reverse order is T ^b =(720,640,...,50). Then the time cost vector estimated by the neural network is:

The model is assisted with supervised learning using a bidirectional interval loss function, so that it not only learns the time cost of the entire path, but also learns the transit time of each intermediate stage. Define the two-way interval loss function as:

Among them, M indicates whether the trajectory passes through the mask of the small area, and [] indicates the operation between each element of the vector.

(5) Minimize the loss function L, namely:

Among them, θ represents the training parameters of the model, ε represents the embedding vector in time and space, and S is the size of the training set. Finally, the parameters of the model are updated and optimized using the backpropagation algorithm based on time sequence.

3. Prediction stage, the specific steps are (take Figure 2 as an example):

(1) Given a real itinerary without a time stamp as the query path g={g ₁ ,g ₂ ,…,g ₈ }, according to the actual path passed, obtain its mapped grid sequence. For each passing small grid g ₁ ~ g ₈ , the spatio-temporal features V _sp and V _tp , the driving state features V _dri , and the historical short-term and long-term traffic state features V _short and V _long , representing V as the total feature of the grid. Among them, the embedding vector of the spatio-temporal feature uses the vector information updated by the parameters of the training process. Short-term and long-term traffic state features are mined using a trained sub-recurrent neural network.

(2) In each passing grid, input all aspects of the extracted features into the trained bidirectional cyclic neural network to obtain the current hidden variable h _t , then the estimated time to pass through the current area is W ^T h _t +b. And the total time overhead estimate is;

Among them, W and b are the parameters obtained in the previous training process.

Claims (1)

1. A travel time estimation method based on auxiliary supervised learning, characterized in that, is divided into three stages: (1) Feature extraction and representation stage, preprocessing the historical trajectory data and extracting its various features; (2) In the training phase, the features extracted from the historical trajectory data are input into a unified bidirectional recurrent neural network for training, and the bidirectional interval loss function is used as the training constraint; (3) In the prediction stage, a bidirectional recurrent neural network is used to infer the features extracted in the query path and estimate the travel time; (1) The specific steps in the feature extraction and representation stage are: Step (1), within the city, fine-grained division of the grid according to latitude and longitude coordinates to form adjacent small rectangular areas; each coordinate point in the track sequence composed of historical GPS coordinates sorted in chronological order Mapped to the corresponding small area to form a sequence composed of grid coordinates; Step (2), for each grid, mine its different features; first, use the embedding vector technology to represent the semantic information of each grid small area in different spaces and different time periods; these information include different functions of the city Regional spatial location information also includes time information such as morning peak hours and weekends; specifically, a low-dimensional vector is used to represent the spatial vector V _sp of each grid, and a day is divided into multiple time buckets, and each trajectory falls into time bucket to get the time vector V _tp ; randomly initialize V _sp and V _tp , and then train with the model during model training; Step (3), using the four-dimensional vector V _dri to indicate whether the current driving stage is the departure stage, the halfway stage, or the end stage, and the proportion of the travel in each stage; Step (4), define the short-term traffic condition characteristic as V _short , define the long-term traffic condition characteristic as V _long , specifically, definition: Indicates the traffic status of the current small area g _i in the jth time interval in the past, where v _j represents the historical average speed, n _j represents the number of historical trajectory data, len _i /v _j represents the roughly estimated passing time; these traffic The condition features are input into a sub-cyclic neural network in order of historical time to extract traffic condition features; In addition, consider the traffic condition information of adjacent small areas, namely definition: Indicates the grid set whose distance from g _i does not exceed d, collects their past short-term traffic condition characteristics, and inputs them into the neural network together; where x, y represent the coordinates of the grid, and g _j represents other grids except g _i grid; (2) The specific steps in the training phase are: Step (1), build a recurrent neural network; define the hidden layer of the network as The input data is Then, the input data of step t is x _t , and the calculation result obtained in step t is h _t , then: h _t ＝φ(x _t ·W _x +h _t-1 ·W _h +b) (3) in, is the weight matrix of the input data, is the weight matrix of the hidden layer, is the bias parameter (bias); That is, the hidden state is expressed as a function: h _t ＝f(h _t-1 ,x _t ) (4) On this basis, the forget gate is defined as: f _t ＝σ(W _f ·[h _t-1 ,x _t ]+b _f ) (5) The input gate is: i _t =σ(W _i ·[h _t-1 ,x _t ]+b _i ) (6) The output gate is: o _t ＝σ(W _o [h _t-1 ,x _t ]+b _o ) (7) The update of the memory unit is: The update of the hidden layer is: h _t ＝O _t ·tanh(C _t ) (10) Among them, W _f ,W _i ,W _o , represent the weight matrix of forget gate, input gate, output gate and memory unit respectively, b _f , b _i , b _o , is the corresponding bias parameter; σ() is a nonlinear activation function; f( ) represents an abstract neural network function including parameters of each layer, and defines the corresponding parameter of the recurrent neural network as W _N , from [-α, Initialize each element in the uniform distribution of α], where α is a hyperparameter with a setting range of 0.01 to 1; The two-way cyclic neural network uses both the forward cyclic neural network and the reverse cyclic neural network for calculation; the forward cyclic neural network sequentially inputs the grid features extracted in the previous steps according to the order of the sequence, and the reverse cyclic neural network uses Enter the grid feature after the sequence is reversed; define its hidden variable as the splicing of the forward and reverse networks, namely: In step (2), the features extracted from the historical trajectory data, namely the spatial feature V _sp , the temporal feature V _sp , the driving state feature V _dri , and the historical short-term and long-term traffic state features V _short and V _long , are spliced into A uniform eigenvector: V=(V _sp , V _sp , V _dri , V _short , V _long ) (11) Input each passing small grid to the two-way cyclic neural network to obtain the passing time through the grid, that is, W ^T h _i + b, the total travel time overhead for: To calculate the weight matrix and bias parameters of the total time overhead, W ^T represents the transposition of the W matrix; Step (3), define the real time cost vector of the trajectory passing through each grid sequence as T; the real time cost vector of sequence is T ^f , the real time cost vector of reverse order is T ^b ; then the time cost vector estimated by the neural network is : Use the two-way interval loss function to assist the model in supervised learning, so that it can not only learn the time cost of the entire path, but also learn the transit time of each intermediate stage; define the two-way interval loss function as: Among them, M indicates whether the trajectory passes through the mask of a small area, and [] indicates the operation between each element of the vector; Step (4), the training goal is to minimize the loss function L, namely: Among them, θ represents the training parameters of the model, ε represents the embedding vector in time and space, and S is the size of the training set; finally, the parameters of the model are updated and optimized using the backpropagation algorithm based on time sequence; (3) The specific steps in the prediction stage are as follows: Step (1), given a real itinerary without a time stamp as the query path, according to the actual path passed, the grid sequence mapped to it is obtained; for each passing small grid, the feature extraction and representation stages are used to obtain Spatio-temporal features V _sp and V _tp , driving state features V _dri , and historical short-term and long-term traffic state features V _short and V _long , as the total feature representation V of the grid; among them, the embedding vector of spatio-temporal features Use the vector information updated by the parameters of the training process; the short-term and long-term traffic state features use the trained sub-cycle neural network for feature mining; In step (2), in each passing grid, input all aspects of the extracted features into the trained bidirectional cyclic neural network to obtain the current hidden variable h _t , then the estimated time to pass through the current area is W ^T · h _t +b, and the estimated total time cost is: Among them, n represents the total number of grids passed, is the weight matrix and bias parameters obtained through training to calculate the total time overhead, and W ^T represents the transpose of the W matrix.