Claims:I/We CLAIM
1. A seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel, said method comprising:
using a data-driven statistical model to capture travel times experienced by a bus in its previous sections and the travel times experienced by previous buses in a section of interest simultaneously for every hour of the day;
stacking the trips (associated travel time vectors) that begin at a particular hour of the day together in the order of their occurrence as a matrix (z) wherein the matrix data can be re-arranged into single long sequence of travel-times wherein the trip travel-time vectors are stringed together in the order of their occurrence into a single long sequence of travel time.
2. The method of claim 1 further comprising using an Auto Correlation Function (ACF) analysis to heck for correlations in the matrix data.
3. The method of claim 1 further comprising rearranging the matrix data by stringing together the previous bus travel time vectors of length Nsc in order to cover the correlations from the immediately preceding sections and correlations at lags of the order of Nsc for the number of sections wherein the correlations stem from the previous bus travel times at the same and preceding sections.
4. The method of claim 1 further comprising a 1-D seasonal time series model is built based on the single long concocted sequence to potentially capture spatio- temporal correlations in the data thereby a seasonal model is built on this sequence for capturing spatio-temporal correlations for dynamic bus travel quality predictions.
5. The method of claim 1 further comprising considering both the predictions based on the current bus and the previous two buses’ observations and the travel times from a suitable historical trip as additional for factor for dynamic bus travel quality predictions.
6. The method of claim 1 further comprising applying Kalman filters in principal for real-time predictions for dynamic bus travel quality predictions. , Description:A SEASONAL MODELLING BASED METHOD FOR CAPTURING SPATIO-TEMPORAL CORRELATIONS FOR DYNAMIC BUS TRAVEL TIME PREDICTION
TECHNICAL FIELD
[0001] Embodiments are generally related to transportation industry. Embodiments are further related to techniques for calculating and accurate prediction of bus arrival time in transportation industry. Embodiments are also related to methods for capturing spatio-thermal dependencies in bus travel time. Embodiments are particularly related to a seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel.
BACKGROUND OF THE INVENTION
[0002] Public transportation provides a basic mobility service to commuters for various types of activities including employment, recreation, medical care, and education. One of the visible and most important applications to improve the public transportation service is providing the arrival time information of buses to commuters waiting at bus stops. Such a solution is widely deployed in major cities of the western world and is being considered as a sustainable method to deliver a competitive and reliable public transportation service. For example, in the city of Boston, USA, passengers revealed that provision of real time arrival information of buses and trains was one of their main reason to choose public transport over private modes. Another study also revealed that upon providing the real time bus arrival information to passengers, bus ridership in Chicago has increased by nearly 18%.
[0003] It is highly important to have a robust prediction method for handling heterogeneous traffic conditions (such as traffic condition in India) that can tackle the complex nature of the heterogeneous and lane in-disciplined traffic, where simple heuristic approaches are not sufficient to capture the variations in the system.
[0004] Majority of prior art approaches for predicting and capturing the travel time of a vehicle in such heterogeneous conditions use temporal dependencies or spatial dependencies for modelling solutions for predicting bus travel time. However, it is known fact that the travel time is a variable that varies over space and time. Hence, an efficient modelling process should consider the spatio-temporal dependencies in travel time together.
[0005] Majority of prior art approaches are developed based on the concepts of traffic flow theory and requires data from multiple data sources to build speed-density relationships along with GPS data from buses. However, it may not be practically feasible to collect traffic data and build such speed-density relationships for entire bus route/network.
[0006] Furthermore, the prior art approaches did not exploit the historical data enough for model calibration of bus time arrival. Also, the prior arts did not capture the spatio-temporal correlations in travel time that might exist between successive sections and within a section. Additionally, prior art approaches did not utilize the real time information obtained from the current bus sufficiently.
[0007] Based on the foregoing a need therefore exists for an improved method for capturing spatio-temporal variations in travel time using GPS data based on time series analysis and linear dynamical systems approach. Also, a need exists for an improved seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel, as discussed in greater detail herein.
SUMMARY OF THE INVENTION
[0008] The following summary is provided to facilitate an understanding of some of the innovative features unique to the disclosed embodiment and is not intended to be a full description. A full appreciation of the various aspects of the embodiments disclosed herein can be gained by taking the entire specification, claims, drawings, and abstract as a whole.
[0009] One aspect of the disclosed embodiments is to provide an improved method for capturing and predicting bus arrival time for passengers waiting in a bus stop.
[0010] Another aspect of the disclosed embodiments is to provide an improved method for capturing spatio-temporal variations in travel time using GPS data based on time series analysis and linear dynamical systems approach.
[0011] Further aspect of the disclosed embodiments is to provide an improved seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel.
[0012] The aforementioned aspects and other objectives and advantages can now be achieved as described herein. An improved seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel, is disclosed herein. A data-driven statistical model to capture travel times experienced by a bus in its previous sections and the travel times experienced by previous buses in a section of interest simultaneously for every hour of the day. The trips (associated travel time vectors) that begin at a particular hour of the day are all stacked together in the order of their occurrence as a matrix (z). The matrix data can be re-arranged into single long sequence of travel-times wherein the trip travel-time vectors are stringed together in the order of their occurrence into a single long sequence of travel time. a check for correlations in the data was checked using an Auto Correlation Function (ACF) analysis.
[0013] The matrix data is rearranged by stringing together the previous bus travel time vectors of length Nsc in order to cover the correlations from the immediately preceding sections and correlations at lags of the order of Nsc for the number of sections. These correlations stem from the previous bus travel times at the same and preceding sections. The influence at the same section from the previous bus is purely temporal while the influences from the previous sections and previous bus travel-times is spatio-temporal. Based on this factor, a 1-D seasonal time series model is built based on the single long concocted sequence to potentially capture spatio- temporal correlations in the data. Hence, the seasonal model is built on this sequence for capturing spatio-temporal correlations for dynamic bus travel quality predictions. To enhance further, the predictions based on the current bus and the previous two buses’ observations as described earlier, the travel times from a suitable historical trip is also considered as additional for factor for dynamic bus travel quality predictions.
BRIEF DESCRIPTION OF DRAWINGS
[0014] The accompanying figures, in which like reference numerals refer to identical or functionally-similar elements throughout the separate views and which are incorporated in and form a part of the specification, further illustrate the present invention and, together with the detailed description of the invention, serve to explain the principles of the present invention.
[0015] FIG. 1 illustrates an exemplary graphical representation of Auto Correlation Function (ACF) analysis for a selected time interval, in accordance with the disclosed embodiments; and
[0016] FIG. 2 illustrates an exemplary graphical representation of Partial Auto Correlation Function (PACF) analysis for a selected time interval, in accordance with the disclosed embodiments.
DETAILED DESCRIPTION
[0017] The particular values and configurations discussed in these non-limiting examples can be varied and are cited merely to illustrate at least one embodiment and are not intended to limit the scope thereof.
[0018] The embodiments now will be described more fully hereinafter with reference to the accompanying drawings, in which illustrative embodiments of the invention are shown. The embodiments disclosed herein can be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. Like numbers refer to like elements throughout. As used herein, the term "and/or" includes any and all combinations of one or more of the associated listed items.
[0019] The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms "a", "an" and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms "comprises" and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.
[0020] Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.
[0021] An improved seasonal modelling-based method for capturing spatio-temporal correlations for dynamic bus travel, is disclosed herein. A data-driven statistical model to capture travel times experienced by a bus in its previous sections and the travel times experienced by previous buses in a section of interest simultaneously for every hour of the day. The trips (associated travel time vectors) that begin at a particular hour of the day are all stacked together in the order of their occurrence as a matrix (z). The matrix data can be re-arranged into single long sequence of travel-times wherein the trip travel-time vectors are stringed together in the order of their occurrence into a single long sequence of travel time. a check for correlations in the data was checked using an Auto Correlation Function (ACF) analysis.
[0022] FIG. 1 illustrates an exemplary graphical representation of Auto Correlation Function (ACF) analysis 100 for a selected time interval, in accordance with the disclosed embodiments. There is no evidence for trends either visually in the raw data or via an abnormally slow decay of the ACF. The Dickey-Fuller test is used to ascertain the absence of any standard integrating-type non-stationarity (stochastic) in the data. Further, at every hour, the ACF values at the first seasonal lag being significantly less than 1 which is clear evidence for absence of (a) any periodicity in the data and (b) seasonal unit roots (integrating effects).
[0023] Once the absence of non- stationarities is ascertained as above, a Partial Auto Correlation Function model is fit which is appropriate candidate for an AR model fit wherein the AR modelling also makes prediction implementation efficient and simple. Both additive and multiplicative seasonal AR models for potential fits and a maximum likelihood estimation is used to learn either of these models. A stochastic process y(t) is said to follow a multiplicative seasonal AR model if it satisfies the following:
(1 - ?1L - • • • - ?pLp)(1 - ?1LS - • • • - ?k LPS )y(t) = e(t), (1)
[0024] where e(t) is a zero mean, white noise process with unknown variance, s 2. Lp is the one-step delay operator applied p times i.e. Lpy(t) = y(t p).
[0025] In a multiplicative SAR model (1), the AR term is a multiplication of two lag polynomials: first capturing the standard lags of order up to p, second capturing the influence of the seasonal lags at multiples of the period S and order up to P. For example, in the PACF shown in Fig. 2, the choice of order parameters would be p = 2, P = 2, and S = 56 = Nsc. FIG. 2 illustrates an exemplary graphical representation 200 of Partial Auto Correlation Function (PACF) analysis for a selected time interval, in accordance with the disclosed embodiments.
[0026] An additive seasonal AR model on the other hand is a conventional AR model with co-efficient corresponding to the insignificant values in the PACF constrained to be zero. The PACF usually pick up some significant magnitude at lags which are integral multiples of S , decays down quickly and remains insignificant (for a large number of lags) till it hits the next integral lag of S and so on. In particular, the trend can be expressed in the PACF by considering the non-zero co-efficient alone as follows:

[0027] Note that in the above equations p, Qs and Q2s are all significantly less than S. Note the bands into which we can group the non-zero co-efficients. The first band involves co- efficients ai coming from the neighboring standard lags. The next band involves co-efficients bs, i = 0, . . . , Qs that capture the influence from seasonal lags which are about one period (S lags) behind. The subsequent band involve co-efficients b2s, i = 0, . . . , Q2s which capture the influence from seasonal lags which are about two periods (2S lags) behind. In Eq. (2), the seasonal lags up to two periods can be considered.
[0028] As explained before, these two bands of seasonal correlations come from the previous two buses. We stick to the influence from the previous two buses. We can also cast the multiplicative SAR model in the form of Eq. (2) by expanding the product of two associated polynomials in Eq. (1). On expansion, it turns out that Qs = Q2s = p for the multiplicative model. This leads to .

[0029] Algorithm 1 describes the method to group the data into one hour bins, string all trip travel time vectors in order into one long sequence and then apply a seasonal fit to the data. It returns the learnt co-efficients as 3 sets of vectors a, bs and b2s as explained in Eq. (2).
[0030] The matrix data is rearranged by stringing together the previous bus travel time vectors of length Nsc in order to cover the correlations from the immediately preceding sections and correlations at lags of the order of Nsc for the number of sections. These correlations stem from the previous bus travel times at the same and preceding sections. The influence at the same section from the previous bus is purely temporal while the influences from the previous sections and previous bus travel-times is spatio-temporal. Based on this factor, a 1-D seasonal time series model is built based on the single long concocted sequence to potentially capture spatio- temporal correlations in the data. Hence, the seasonal model is built on this sequence for capturing spatio-temporal correlations for dynamic bus travel quality predictions. To enhance further, the predictions based on the current bus and the previous two buses’ observations as described earlier, the travel times from a suitable historical trip is also considered as additional for factor for dynamic bus travel quality predictions.
[0031] If the bus is currently at the end of section m, then we note the vector of the previous 3 section travel times i.e. . Amongst all the historical trips that began in the same hour as the current bus (ZH ) whose vector of travel times sequent travel-time observations of this trip from section m + 1 onwards can be pretty close to the current bus’s subsequent travel times and can be an additional useful source of information to perform accurate predictions. It is hypothesized that

[0032] where ? is zero mean, unit variance noise and Zcu refers to the current bus’s travel times. To incorporate these additional observations into the real-time prediction scheme, the data-driven model is casted for prediction in a state-space form as shown in Eq. (4). Note that the state-space model is also a function of the current position of the bus (say at the end of section m).


[0033] Here, the dimension of the state X (k) is p, which is the dimension of the a vector returned from Alg. 1. Alg. 2 describes the dynamic data-driven model, where the state- variables are hidden and optimally estimating the unseen state-variables and gives us the travel time predictions of the current bus (trip) in the subsequent sections. Overall, it can be noted that the state equation in Eq. (4) is a vectorized rewrite of Eq. (2) to enable memory of order 1.
[0034] In particular, the state X (k) is the vector of p consecutive travel times from the current bus (line 1). The first row of matrix A (line 3) essentially performs the autoregressive operation of Eq. (2) involving the standard lags of length p. The remaining rows perform one downshift operation of the previous state-vector. The remaining two autoregressive operations of Eq. (2) come from the previous two buses respectively whose travel time observations are known (or already observed) for a sufficient number of sections before section m.
[0035] That is the reason the previous two bus observations are not part of the state and their observed effect is lumped in u(k) (line 4), which is like an external known input to the Linear Dynamical System (LDS) model. It is easy to see that the additive zero mean state noise w(k) is non-zero only in the first component whose variance matches the residual noise variance of e(t) in Eq.(2).

[0036] Given the above LDS dynamic model for real-time prediction, one can apply Kalman filters in principle for optimal prediction. The particle filtering is used for its ease of implementation to predict the unseen state X(k) for every k and in turn the travel times at the sections ahead. Particle filtering is a sampling-oriented technique for inference (of hidden states) in sequential models. PF estimates the empirical conditional distribution of the hidden states given the observations in a recursive fashion.
[0037] A prefixed number of particles (all of them at state X(0)) is used for initialization (line 1 of Alg. 3). Each of these samples make a state transition as per the state equation of 4 (line 4). A weight is calculated for each particle based on its current state and observation (line 5 to 7). This weight vector is normalized to a distribution and the particles are resampled with replacement from this distribution to obtain a set of R particles. The travel-time estimate is obtained by taking mean of the first component of all these particles. (line 10).
[0038] It will be appreciated that variations of the above-disclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also, that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the field.