Claims:Claims:
I/We claim:
1. A method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines comprises of;
a) hardware-executable components for execution;
b) data acquisition module;
c) Wi-Fi module;
d) spatial correlating means ;
e) real-time prediction processing module;
f) base transceiver station;
g) display module;
h) controller means configured to update using an Extended Kalman filter
2. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said data acquisition module collects data from GPS enabled buses with their position information logged every 5 sec through segmented sections and repeated consequently for a specified number of days and time period.
3. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1) wherein the spatial correlating means is the determining unit between each section and travel times and correlation learning means by performing, for the spatial relation, a correlation analysis based on historical traffic data of the section and its order of determining sections.
4. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the a non-linear filter for receiving signals is acquired in base transceiver station and displayed in the receiving end display module
5. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said Wi-Fi Module communicates and transfers information to the receiving end.
6. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said real-time prediction module sends the exact location of the bus and position to the receiving end.
7. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said display module includes the bus station or stop and the mobile communication device of the passenger.
8. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said controller means configured to update using an Extended Kalman Filter reduces and filters the statistical sequence noises and predicts the correct estimate.
9. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the time prediction method is characterized by collecting real-time location information and sending to the prediction processing module thereby displaying the arrival time based on the received location information through the display module using the Wi-Fi Module.
10. The method and system for bus travel time prediction, capturing non-linear spatial correlations using support vector machines according to claim (1), wherein the said method and system provides high prediction accuracy, utilizing learnt model recasting in a non-linear statespace form and improved Extended Kalman Filter. , Description:DESCRIPTION
BUS TRAVEL TIME PREDICTION CAPTURING NON-LINEAR SPATIAL CORRELATIONS USING SUPPORT VECTOR MACHINES

FIELD OF INVENTION
[001] The present invention generally relates to transportation industry. More specifically, the invention relates to a new method for bus travel time prediction using a data-driven approach.
BACKGROUND OF THE INVENTION
[002] Travel time prediction in bus transportation is very crucial for passengers and it is very difficult to predict the arrival and departure time accurately. Several methods have been identified and proposed for accurate time prediction such as machine learning techniques, time series analysis, and the like.
[003] Forecasting time of departure and arrival of bus to a particular location will enhance public transportation experience for every individual across the globe. Factors like excess vehicles, diverse modes of transport and acute lack of lane discipline which are common in many of the countries adds complexities to the prediction problem.
[004] Several prior-arts in this field have discussed various methods for time prediction such as data driven class of methods, high quality GPS sensing, nonlinear and non-stationary spatial dependencies, non-linear dynamical system (NLDS), Extended Kalman filter (EKF) and the like.
[005] The patent CN101123515A discusses on time prediction method comprising of vehicle information device mounted on a vehicle, and at least one electronic kiosk station information management system.
[006] The invention JP3012570B2 claims display information generator for displaying the arrival time of the bus and current location and movement of the bus through communication hub, mobile transceiver signal recognition unit and the like.
[007] Another invention CN104064028A discusses on transit arrival time prediction based on the multi-information data. This method ensures to intimate the bus arrival time to the passengers and has the advantage of being high in prediction time validity and accuracy.
[008] The scientific literature titled “Dynamic Bus Travel Time Prediction Using an ANN-based Model” by Mansur As et al. discusses on predicting method using 8 time-periods in calculating travel time over the interval at each time-period and also use the travel time condition as well as the historical average travel time at the same time-period during the past several days.
[009] Also there are prior arts that claim on time prediction using spatial correlations/patterns of traffic and temporal variations in travel time using statistical methods.
[010] However, there is no method that can accurately provide time without high variations
[011] Therefore there exists a need to devise a system and process which overcomes the above mentioned problems and provides improved solution for effective bus travel time prediction.
[012] The current invention addresses the problems of the existing technologies in this field regarding the variations and accuracy issues and thereby has developed a method that explicitly learns the spatial correlations/patterns of traffic in a novel nonlinear fashion resulting in less variation and high accuracy in prediction.
SUMMARY OF THE INVENTION
[013] The following summary is provided to facilitate a clear understanding of the new features in the disclosed embodiment and it is not intended to be a full, detailed description. A detailed description of all the aspects of the disclosed invention can be understood by reviewing the full specification, the drawing and the claims and the abstract, as a whole.
[014] The objective of the present invention is to increase and enhance time prediction methods in public transportation field.
[015] The aforementioned aspects along with the objectives and the advantages can be achieved as described herein.
[016] The current invention discloses the methods to address arrival time prediction in real-time under chaotic conditions using the spatial correlations/patterns of traffic in an improved nonlinear fashion.
[017] In one aspect of the invention, it first detects the unknown order of spatial dependence and then learns the non-stationary nonlinear correlations for this detected order using support vector machines.
[018] Further the present invention addresses the bus travel time problem by posing it as an inference problem on a non-linear dynamical system (NLDS) model and uses an Extended Kalman Filter to solve this inference problem in an efficient and optimal manner.
[019] The present invention exploits the correlations in the data, to capture the spatial correlations between section travel times based on an auto-regressive (AR) approach.
[020] The current invention employs State-Space Formulation to solve the prediction problem, wherein the method used is a non-stationary, state-space based LDS model. This model would depend on the real-time position of the current bus and accordingly starts from the specified section.
[021] According to one of the aspect of the present invention, to perform inference or predictions in a statistically optimal sense under NLDS models, there is a need to use approximate methods wherein the invention uses an Extended Kalman filter as an approximate solution which is also very efficient run-time wise. It uses a Taylor series based linearized approximation which is performed dynamically at each step and followed by an application of the linear KF (Kalman Filter).
[022] The current invention thereby has developed an efficient method for travel time prediction wherein the route is segmented into small sections. The data-driven model captures general non-linear, non-stationary spatial correlations.
[023] In one aspect of the invention the support vector regression has been developed to learn the spatial non-linear dependencies of this model. The learnt model is recast in a non-linear state space form which enabled an elegant and improved Extended Kalman filter based prediction.
DETAILED DESCRIPTION
[024] The principles of operation, design configurations and evaluation values in these non-limiting examples can be varied and are merely cited to illustrate at least one embodiment of the invention, without limiting the scope thereof.
[025] The embodiments will be described in detail with corresponding marked references to the drawings, in which the illustrative components of the invention are outlined. The embodiments disclosed herein can be expressed in different forms and should not be considered as limited to the listed embodiments in the disclosed invention. The various embodiments outlined in the subsequent sections are construed such that it provides a complete and a thorough understanding of the disclosed invention, by clearly describing the scope of the invention, for those skilled in the art.
[026] The methodology adopted in present invention is to first collect data (Data Input). The data used in the current invention is collected from a bus route in an Indian city across 34 days. All the plying buses were GPS enabled with their position information logged every 5 sec. The bus route was segmented into sections each of 500 m length and time taken to cover each section was calculated by linear interpolation from the high frequency GPS data. This data across all sections and trips over 34 consecutive days was finally used. In particular, data for the first 27 days was used for training and the remaining 7 days for testing. For learning, the trips from 27 test days were grouped into hourly slots and all trips with start times falling in a given hour slot were assumed to follow a specific NLDS model.
[027] In one embodiment of the present invention. The spatial correlation is captured by exploiting the correlations in the data, between section travel times based on an auto-regressive (AR) approach using a non-linear and non-stationary auto-regressive model to capture these dependencies.
[028] We denote the travel time at section k by Zk and hypothesize that, Zk is some non-linear function of its previous Q section travel times with some additive noise with zero-mean and variance s 2 superscript and w subscript (k). We assume that Q which captures the extent of dependence into the past is same at all sections.
Algorithm 1: Learn Spatial Correlations for all sections.
Input: Historical Data z = (z1; z2; : : : zN), zn - travel time observation vector (d × 1) at the nth section, d -number of trips across all days in a one-hour slot, N-number of sections.
Output: Q- order of dependence on previous section observations, fn, sw2 (n) 8n.
1) Concatenate all rows (d of them) of z into one long sequence or time series S ;
2) Form a differenced series S0 (if seasonal non-stationarity is present) by taking a seasonal difference of S;
3) Compute PACF (Partial Auto Correlation Function) of differenced series S 0;
4) Choose largest lag (Q) in PACF s.t. all PACF values at lags (< Q) are > critical threshold.;
5) Threshold is based on a std. Z-test of testing zero PAC;
6) for n N to 2 do
7) Compute non-linear regression functions fn and the residual error variance s2 w(n) by non-linearly regressing
Zn w.r.t (Zn-1; Zn-2; : : : Zn-Q) using an SVM with appropriate kernels.
8) If n < Q + 1, then regress Zn with all previous section travel times i.e. Zn-1; Zn-2 : : : Z1.
[029] Algorithm 1 explains the method of choosing Q and the associated learning. Lines 1 to 4 describe the method of arriving at Q. It is well known that for stationary time series [Brockwell and Davis, 1986], the order of auto-regression is decided by looking at the decay of the associated Partial Auto-Correlation Function (PACF). To employ this, the first string together all section travel time vectors (in the order of their start time and date) of all trips recorded within a specific time bin (line 1). This construction can induce some seasonal trends with period N, the number of sections.
[030] Based on the Auto-Correlation Function (ACF) of this constructed time series, we perform a seasonal difference to compensate for seasonal non-stationarities (if any) if the ACF values at multiples of Ns display a slow decay (line2). On the differenced data, at the PACF and read off a Q, based on a standard statistical threshold (line 3, 4 & 5) The obtained Q can be viewed as some kind of an average window length into the past, which influences the present (spatially) at each section. Next, non-linear functions fn are computed by performing a SVM based non-linear regression at each section, based on its Q previous section travel times as its inputs and the resulting regression parameters and residual variances (s2w(n)) are stored for each section (line 7). If the section n under consideration is such that n = Q, then, it is regressed using all the previous sections’ travel time data.
[031] In another embodiment of the present invention, in addition to the current bus travel time observations on the traversed sections, we also use current travel time data of the previous bus towards prediction. Specifically, if Z pv superscript k subscript and Z k subscript denote the travel time at the kth section of the previous and current bus respectively, then we hypothesize that Z pv superscript k subscript = (ck superscript 1 subscript *Zk) + c k superscript 0 subscript + ?(k) where ?(k) is additive noise with zero-mean and variance s2v (k). We consider the immediate previous bus’ observations but rather that of the previous to previous bus, which can potentially be a poorer approximation of Zk compared to the previous bus’s observation, while the previous bus’s real-time measurements are utilized for model calibration.
[032] Alg. 2 describes how these temporal dependencies are learnt.
Algorithm 2: Learn Correlations between successive trips for section n. Input: Historical Data zn - travel time observation vector (d1) at the nth section, d - number of trips across all D days in a one-hour slot.
Output: slope (cn) and intercept (cn) term (based on linear fit) and variance (s2(n)) of additive noise at section n.

[033] The model parameters of the present invention are learnt in an unambiguous manner as explained above, the real-time prediction problem that we address is as follows.
[033] Suppose the real-time position of the current bus is at the end of section m. Given the current bus’s (observed) section travel times upto section m and the previous bus’s section travel times beyond section m, there is a need to predict current bus’s travel times beyond section m.
[034] To solve the above prediction problem, we reformulate the learnt model (from the previous section) as a non-stationary, state-space based LDS model. This model would depend on the real-time position of the current bus and accordingly starts from section m. Since at every section, we allowed for a general order of dependence (Q) on the previous sections, we cannot use a one-dimensional state space model.
[035] Algorithm 3: Build State Space Model for Prediction after section m

As described in Alg. 3, we build a non-linear state-space model (eq. 1) of order Q.
Specifically, the state space model is as follows.
X(k) = Fk (X(k - 1)) + w(k)
y(k) = C(k)X(k) + C0(k) + v(k) (1)
Note the dimension of the (unobserved) state vector, X(k), here is Q. X(k) essentially captures the travel times of Q consecutive sections ending at section m + k. The non-linear functions Fk are vector valued functions with both input and output dimension being Q. The first component function (scalar valued) of Fk is fm+k. This is easy to see as Fk maps X(k - 1) to X(k) while fm+k learnt by (Alg. 1) captures the non-linear dependence of Zm+k in terms of its previous Q observed section travel times. The remaining Q - 1 scalar valued functions basically facilitate a 1-step downshift of the first Q - 1 components of X(k - 1). Recollect that we hypothesized that the previous bus’s travel time is some linear function of the previous bus’s travel time plus some additive noise. As a consequence, the first component of C(k) is the slope (c k superscript 1 subscript) while the rest of its components are 0. The intercept of this linear fit is captured by C0(k). The residual error variances are captured by the first component of w(k) and v(k).
[036] In another aspect of the present invention prediction is set to be conducted through use of an Extended Kalman filter which is one approximate solution which is also very efficient run-time wise. It uses a Taylor series based linearized approximation which is performed dynamically at each step and followed by an application of the linear Kalman Filter (KF).
Algorithm 4: K-step travel-time prediction using Kalman Filter.
[037] Alg. 4 describes the present invention wherein the EKF is discussed in detail. Lines 4 to 11 here overall follow a standard EKF procedure. As explained above,
at each step in the filter, a linear approximation of the non-linear map Fk is performed dynamically at the current state estimate. An interesting feature is
given the structure of Fk, only a few partial derivatives need
to be explicitly computed. By the definition of Fk, the first
row of A(k) involves the partial derivatives of fm+k. The
remaining rows will turn out to be binary with a single 1 exactly at an appropriate position. This is mainly because the remaining component functions just pick precisely one of the Q inputs. The final optimal travel time prediction at the kth
section ahead will be the first component of Xb (kjk) (line 11)

Partial derivative closed forms for SVR: The functional form of a support-vector regressor is of the form
y= = wT f(x) + w0 where f is the non-linear function which maps the inputs to a high-dimensional space. However, based on the kernel trick this can be rewritten as where Ns is the number of support vectors. We consider two standard kernels namely (a) Polynomial (b) Gaussian - . By taking partial derivative w.r.t xj,
we get For the polynomial kernel, For the Gaussian kernel, Hence the partial derivatives can be computed efficiently in closed form and hence
the efficient dynamic computation of A(k) and C(k) matrices
is feasible for prediction.
[038] The log transformation of the present invention is implemented by Kalman filter also known as optimal predictors (in the mean square error sense) if associated distributions are Gaussian. The histogram of the travel times which are always positive at any particular section and time
bin were mostly observed to be right-skewed. To account
for this, the present invention applied a log transformation on each of the travel time observations to begin with before applying any of the
algorithms discussed in this section. The idea is to make the
marginal distributions approximately symmetric so that the
predictions of the algorithms are close to statistically optimal. The predictions output by Alg. 4 are exponentiated to
obtain the final predictions.
[039] Thereby the current invention has provided an improved and efficient method of predicting the bus travel time wherein the route is segmented into small sections. The data-driven model captures general non-linear,
non-stationary spatial correlations. The invention used support vector
regression to learn the spatial non-linear dependencies of this model. The learnt model was recast in a non-linear statespace form which enabled an elegant and enhanced Extended Kalman filter based prediction.
[040] What has been described above includes examples of the disclosed architecture. It is, of course, not possible to describe every conceivable combination of components and/or methodologies, but one of ordinary skill in the art may recognize that many further combinations and permutations are possible. Accordingly, the novel architecture is intended to embrace all such alterations, modifications and variations that fall within the spirit and scope of the appended claims.
[041] Without further description, it is believed that one of ordinary skill in the art can, using the preceding description and the illustrative examples, make and utilize the present invention and practice the claimed methods. It should be understood that the foregoing discussion and examples merely present a detailed description of certain preferred embodiments. It will be apparent to those of ordinary skill in the art that various modifications and equivalents can be made without departing from the spirit and scope of the invention.