FORM 2
THE PATENTS ACT, 1970 (39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION (See section 10, rule 13) 1. Title of the invention: MODEL-BASED TRAVEL TIME PREDICTION
2. Applicant(s)
NAME NATIONALITY ADDRESS
TATA CONSULTANCY SERVICES Indian Nirmal Building, 9th Floor, Nariman Point, Mumbai 400021, India
INDIAN INSTITUTE OF TECHNOLOGY, MADRAS Indian Indian Institute of Technology, Madras IIT P.O., Chennai 600 036, India
3. Preamble to the description
COMPLETE SPECIFICATION
The following specification particularly describes the invention and the manner in which it
is to be performed.

TECHNICAL FIELD
[0001] The present subject matter relates, in general, to prediction of travel time of
vehicles, such as public transport buses, and in particular, to prediction of travel time of vehicles using a prediction model.
BACKGROUND
[0001] Accurate prediction of travel time of vehicles, such as public transport buses,
become difficult due to dynamic traffic conditions. For instance, it may not be possible to accurately predict the time at which a public transport bus will arrive at a location, such as a bus stop on its route, if traffic variation is very high.
BRIEF DESCRIPTION OF DRAWINGS
[0002] The features, aspects, and advantages of the present subject matter will be
better understood with regard to the following description, and accompanying figures. The use of the same reference number in different figures indicates similar or identical features and components.
[0003] Fig. 1 illustrates a system for predicting travel time of a vehicle, in accordance
with an implementation of the present subject matter.
[0004] Fig. 2 illustrates a method for predicting travel time of a vehicle, in accordance
with an implementation of the present subject matter.
[0005] Fig. 3 illustrates a method for predicting travel time of a vehicle, in accordance
with an implementation of the present subject matter.
[0006] Fig. 4 illustrates a method for predicting travel time of a vehicle, in accordance
with an implementation of the present subject matter.
[0007] Fig. 5(a) illustrates performance comparison in terms of Mean Absolute
Percentage Error (MAPE) for the extended Kalman filter technique (EKF) and Particle filter technique (PF) proposed by the present approach for a plurality of trips for a two-step prediction, in accordance with an implementation of the present subject matter.

[0008] Fig. 5(b) illustrates rum time comparison of EKF and PF proposed by the
present approach for a plurality of trips for a two-step prediction, in accordance with an
implementation of the present subject matter.
[0009] Fig. 6(a) illustrate the results of comparison of the performance for a single
step prediction by the present subject matter with four methods for a plurality of days for
the first set of data, in terms of Mean Absolute Percentage Error (MAPE), in accordance
with an implementation of the present subject matter.
[0010] Fig. 6(b) illustrate the results of comparison of the performance for a single
step prediction by the present subject matter with four methods for a plurality of days for
the second set of data for the single step prediction, in terms of Mean Absolute
Percentage Error (MAPE), in accordance with an implementation of the present subject
matter.
[0011] Fig. 7(a) illustrates reduction of MAPE for the single step prediction provided
by the present compared to the HA method for each section, for the first set of data, in
accordance with an implementation of the present subject matter.
[0012] Fig. 7(b) illustrates reduction of MAPE for the single step prediction provided
by the present compared to the SD method for each section for the first set of data, in
accordance with an implementation of the present subject matter.
[0013] Fig. 7(c) illustrates reduction of MAPE for the single step prediction provided
by the present compared to the SVM07 method for each section for the first set of data,
in accordance with an implementation of the present subject matter.
[0014] Fig. 7(d) illustrates reduction of MAPE for the single step prediction provided
by the present compared to the SVM16 method for each section for the first set of data,
in accordance with an implementation of the present subject matter.
[0015] Fig. 8(a) illustrates reduction of MAPE for the single step prediction provided
by the present compared to the HA method for each section for the second set of data in
accordance with an implementation of the present subject matter.
[0016] Fig. 8(b) illustrates reduction of MAPE for the single step prediction provided
by the present approach compared to Space Discretization (SD) method for each section
for the second set of data, in accordance with an implementation of the present subject
matter.

[0017] Fig. 8(c) illustrates reduction of MAPE for the single step prediction provided
by the present approach compared to support vector machine method with spatial and
temporal dependency (SVM07) for each section for the second set of data, in accordance
with an implementation of the present subject matter.
[0018] Fig. 8(d) illustrates reduction of MAPE for the single step prediction provided
by the present approach compared to support vector machine method with temporal
dependency (SVM16) for each section for the second set of data, in the single step
prediction, in accordance with an implementation of the present subject matter.
[0019] Fig. 9(a) illustrates the comparison of MAE values for multi-step prediction of
the arrival time predicted for bus stop A for the first set of data, in accordance with an
implementation of the present subject matter.
[0020] Fig. 9(b) illustrates the comparison of MAE values for multi-step prediction of
arrival time predicted for bus stop B for the second set of data, in accordance with an
implementation of the present subject matter.
DETAILED DESCRIPTION
[0021] Prediction of the travel time of vehicles, such as public transport buses, may
not be accurate, owing to dynamic traffic conditions. That is, prediction of time taken by a public transport bus to travel between two locations, such as two bus stops, may not be accurate. This is because of factors such as excess vehicles on the route, lack of lane discipline, diversity in modes of transportation and so on. In addition, factors, such as dwell time, traffic signals and fluctuating travel demands, may also make prediction of travel time of public transport buses inaccurate.
[0022] The present subject matter relates to predicting travel time of vehicles. With
the implementations of the present subject matter, travel and arrival time of vehicles, such
as public transport buses, can be accurately predicted in real-time.
[0023] In an implementation of the present subject matter, a prediction model is
developed, using which travel times of vehicles at various sections along a route can be accurately predicted. To develop the prediction model, first, an order of dependence is determined based on a dataset. The dataset comprises data of travel times of a vehicle at each of the plurality of sections on the route and entry times at each section. The order of dependence is a first number of sections immediately before a section on the route that

are likely to influence the travel time of the vehicle at the section. For instance, if the first
number of sections is determined to be five, it is likely that the travel time of a vehicle at
a section is influenced by travel time in five sections immediately preceding the section.
[0024] Subsequently, a prediction model is formulated. The prediction model
indicates dependence of travel time of the vehicle at a section in a first trip on travel time in the first trip at the first number of sections immediately before the section and entry time of the vehicle at the section in the first trip. For instance, the prediction model may be developed such that the travel time of the vehicle at the section in the first trip may be represented as a function of travel time in the first trip at the first number of sections and entry time of the vehicle at the section in the first trip.
[0025] In an implementation, the formulation of the prediction model comprises
estimating a non-linear function, using a non-linear regression technique, by non-linearly regressing the travel times of a vehicle at the section at a plurality of trips with travel times of a vehicle at the first number of sections at the plurality of trips and entry times of the vehicle at the section at the plurality of trips. For instance, consider a fifth section from the origin on a route, and the first number of sections is 3. Then, the travel time at the fifth section is regressed with travel times at each of the fourth section from the origin, third section from the origin and second section from the origin and with the entry time at the fifth section. This may be repeated for each of the plurality of sections for a plurality of trips, to estimate the non-linear function.
[0026] Further, in an implementation, the formulated prediction model is fine-tuned
for each section by incorporating travel times and entry times in a second trip, such that
the prediction model indicates the dependence of the travel time at the section in the first
trip on travel time at the section in the second trip, on entry time at the section in the
second trip and on entry time at the section in the second trip. The second trip is a trip on
the route immediately preceding the first trip. For instance, consider a vehicle makes a
trip on the route with a start time at 11.00 AM as the first trip. Also, consider an
immediately preceding trip has been made on the route with a start time at 10.00 AM.
Then the immediately preceding trip may be referred to as the second trip.
[0027] Furthermore, in an implementation, the prediction model incorporates travel
times and entry times in a third trip, such that the prediction model indicates the

dependence of travel time at the section in the first trip on travel time at the section in the third trip, on entry time at the section in the first trip and entry time at the section in the third trip. The third trip is a trip on the route on a same day as the first trip on the preceding week with a start time of the trip closest to the start time of the first trip compared to start times of plurality of trips on the same day as the first trip on the preceding week. For instance, consider a vehicle has made a trip on the route with a start time at 11.00 AM on a Wednesday of a week, referred to as the first trip. Also, consider a trip has been made on the route with a start time at 10.30 AM on a Wednesday of a preceding week from the first trip, and another trip has been made on the route with a start time at 12.00 Noon on the Wednesday of the preceding week from the first trip. Then the trip made on the route with the start time at 10.30 AM may be the third trip. This is because the trip with start time 10.30 AM is closest to the start time of the first trip compared to the trip with start time 12.00 Noon.
[0028] The prediction model may then be used for predicting travel times of the
vehicle. For instance, the travel time at a particular section, i.e., the time taken to cross the particular section, can be predicted using real-time data of travel times of the vehicle in previous sections and in previous trips. In an example, to make the prediction feasible, the prediction model may be rewritten in a state-space form, using which a predictive filtering technique, such as an extended Kalman filter technique (EKF) or a particle filtering (PF) technique, can be applied. The state-space form may also be referred to as a state-space model.
[0029] In an implementation, prediction of travel time of the vehicle at the section in
the first trip may be refined using by estimating a travel time of the vehicle at the section in the second trip by using a first non-linear temporal function. The first non-linear temporal function indicates travel time at the section in the second trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the second trip. Also, the prediction of travel time of the vehicle at the section in the first trip may be refined by estimating a travel time of the vehicle at the section in the first trip by using a second non-linear temporal function. The second non¬linear temporal function indicates travel time at the section in the third trip as a function of travel time at the section in the first trip, entry time at the section in the third trip and

entry time at the section in the first trip. Further, a residual may be computed. The residual indicates a difference in estimated travel time at the section in the second trip and an actual travel time at the section in the second trip and an estimated travel time at the section in the third trip and an actual travel time at the section in the third trip. Further, the residual may be used to refine the predicted travel time of the vehicle at the section in the first trip.
[0030] With the systems and methods of the present subject matter, travel times of
vehicles can be predicted with accuracy. The prediction can be used for public transport
buses, for which the travel time is highly variable. In particular, the present subject matter
can be used for predicting travel time in conditions where lane discipline is not strictly
followed and in dynamic traffic conditions, including non-homogenous traffic, i.e., the
modes of transport can range from bicycles and two-wheelers to buses and trucks. With
the systems and methods of the present subject matter, the time required for prediction
is less. The systems and methods of the present subject matter may be hardware
resource efficient. Further, the systems and methods may be implemented with minimal
hardware resources and without the use of specialized hardware.
[0031] In addition, by predicting the real-time travel time information of the vehicle,
according to the present subject matter, an arrival time of the vehicle at a particular
location, such as a bus stop, may be accurately predicted. For instance, by using the
predicted travel time of vehicle between two locations, such as a bus stop 'A' and a bus
stop 'B', an arrival time of vehicle at the bus stop 'B' may be accurately predicted.
[0032] The above and other features, aspects, and advantages of the subject matter
will be better explained with regard to the following description, and accompanying figures. It should be noted that the description and figures merely illustrate the principles of the present subject matter along with examples described herein and, should not be construed as a limitation to the present subject matter. It is thus understood that various arrangements may be devised that, although not explicitly described or shown herein, embody the principles of the present disclosure. Moreover, all statements herein reciting principles, aspects, and examples thereof, are intended to encompass equivalents thereof. Further, for the sake of simplicity, and without limitation, the same numbers are used throughout the drawings to reference like features and components.

[0033] Fig. 1 illustrates a system 100 for predicting travel time of a vehicle, in accordance with an implementation of the present subject matter. [0034] The system 100 can include a processor 102 to run at least one operating system and other applications and services. The system 100 can also include an interface 104 and a memory 106. Further, the system 100 can include modules 108 and data 112. [0035] The processor 102, amongst other capabilities, may be configured to fetch and execute computer-readable instructions stored in the memory 106. The processor 102 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. The functions of the various elements shown in the figure, including any functional blocks labelled as "processor", may be provided through the use of dedicated hardware as well as hardware capable of executing machine readable instructions. [0036] When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term "processor" should not be construed to refer exclusively to hardware capable of executing machine readable instructions, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing machine readable instructions, random access memory (RAM), non-volatile storage. Other hardware, conventional and/or custom, may also be included. [0037] The interface 104 may include a variety of machine readable instructions-based interfaces and hardware interfaces that allow the system 100 to interact with different entities, such as the processor 102, the modules 108, and the data 112. Further, the interface 104 may enable the components of the system 100 to communicate with computing devices, web servers, and external repositories. The interface 104 may facilitate multiple communications within a wide variety of networks and protocol types, including wireless networks, wireless Local Area Network (WLAN), RAN, satellite-based network, and the like.

[0038] The memory 106 may be coupled to the processor 102 and may, among other
capabilities, provide data and instructions for generating different requests. The memory 106 can include any computer-readable medium known in the art including, for example, volatile memory, such as static random-access memory (SRAM) and dynamic random-access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
[0039] The modules 108 may include routines, programs, objects, components, data
structures, and the like, which perform particular tasks or implement particular abstract data types. The modules 108 may further include modules that supplement applications on the system 100, for example, modules of an operating system. Further, the modules 108 may be implemented in hardware, instructions executed by a processing unit, or by a combination thereof.
[0040] In an implementation, the modules 108 may be machine-readable
instructions which, when executed by the processor 102, perform any of the described functionalities. The machine-readable instructions may be stored on an electronic memory device, hard disk, optical disk or other machine-readable storage medium or non-transitory medium. In one implementation, the machine-readable instructions can also be downloaded to the storage medium via a network connection.
[0041] The modules 108 include one or more modules which may perform different
functionalities. The one or more modules include a prediction module 110. The functions of the prediction module 110 are explained in later paragraphs.
[0042] The data 112 serves, amongst other things, as a repository for storing data
that may be fetched, processed, received, or generated by one or more of the modules
108. In an implementation, the data 112 may contain travel times of at least one vehicle
at a plurality of section at a plurality of trips and entry of at least one vehicle at a plurality
of section at a plurality of trips, which may be explained in detail later.
[0043] In operation, the prediction module 110 develops a prediction model that
indicates dependence of travel time of a vehicle in a first trip at a section on a route of the vehicle on travel times in the first trip at immediately preceding sections on the route. Such a dependence may be referred to as spatial correlations on the route of the vehicle.

In particular, this dependence may be referred to as non-linear spatial correlation, since the travel time of the vehicle in a first trip at the section on a transport route of the vehicle may vary non-linearly with travel times at first number of sections immediately preceding the section on the route. Here, the transport route may be referred to as the route and sections on the route of a vehicle may be referred to as a section, which may be, for example, 500 m in length. Further, the first number of sections is referred to as an order of dependence for the route and is represented by 'Q' The order of dependence may be common for all sections on the route. The determination of the order of dependence will be explained later.
[0044] Further, the spatial correlation may also include correlation between travel time at the section in the first trip and an entry time of the vehicle at the section in the first trip. Accordingly, the prediction model developed by the prediction module 110, further indicates the dependence of travel time at the section in the first trip on an entry time of the vehicle at the section in the first trip.
[0045] So, the prediction model is formulated such that the prediction model indicates the dependence of travel time at the section in the first trip on travel times at the first number of sections in the first trip and on entry time of the vehicle in the first trip. For instance, consider that a route has a total of 56 sections and that the first number of sections is three. Then, to predict travel time in a first trip at the fifth section from the origin on the route, the prediction model indicates dependence of travel time in the first trip at the fifth section from the origin of the route on travel times in the first trip at each of the second section from the origin, third section from the origin, fourth section from the origin and on an entry time at the fifth section in the first trip.
[0046] In an example, the prediction model is formulated such that the travel time at a section in a first trip may be represented as a function of the travel times at a first number of sections immediately before the section on the route and entry time of the vehicle at the section in the first trip. Also, the prediction model formulated may be a non-linear dynamic model.
[0047] In an implementation, a state-space model may be formulated based on the prediction model. A predictive filtering technique may be applied on the state-space model to predict the travel time of a vehicle at a section in a first trip. The methods for developing

the prediction model and predicting travel time of a vehicle may be described in the below methods.
[0048] Fig. 2 illustrates a method 200 for determining an order of dependence Q and a non-linear function fn for predicting travel time of a vehicle, in accordance with an implementation of the present subject matter. The method 200 may be performed by the prediction module 110.
[0049] At block 202, travel times in the dataset are segregated into a plurality of subgroups of travel times, each subgroup corresponding to a time slot of a plurality of time slots. That is, a subgroup comprises travel time vectors for the plurality of trips corresponding to a time slot. Travel time vectors may be the travel times of a vehicle at the plurality of sections. As an example, if the route has 56 sections, then a travel time vector may include travel times of a vehicle at each of the 56 sections. A time slot may be, for example, a one-hour time slot corresponding to running time of the vehicle on a day. For a 9-10 time slot, the subgroup corresponding to the 9-10 time slot may comprise travel times vectors of at least one vehicle at 9-10 time slot for a plurality of trips. [0050] As mentioned earlier, the dataset comprises travel times of at least one vehicle for a plurality of sections for a plurality of trips and entry times of at least one vehicle for a plurality of section for a plurality of trips. To enable segregation of travel time vectors, the travel time across the plurality of sections may be arranged in the order of start time of the trip. [0051 ] The arranged travel times may be represented as follows:
(1) where z may be referred to as travel time vector including travel times at each of the N
sections of the route, is a travel time vector (d x 1) at the ith section and d is the number of trips across all days in a time slot, and N is the number of sections. [0001 ] At block 204, a subgroup order for each subgroup is computed. In this regard, for each subgroup, a plurality of iterations may be performed. Each iteration may comprise the following steps. First, subgroup of travel time vectors may be concatenated. That is, the segregated subgroup of travel time vectors may be concatenated to form a time series S. The concatenation may induce some seasonal trends with a period N, where N refers to the number of sections. Subsequently, to eliminate the seasonal trends,

a seasonal difference is performed. The output of the seasonal difference may be referred to as a time series and is represented as S'.
[0052] Then, a partial auto correlation function (PACF) value for the subgroup may be determined based on the time series S' and a largest lag for which the PACF value is above a cut-off PACF value is identified as a subgroup order. This is because, for a stationary time series, i.e., a time series for which mean, variance and autocorrelation structure do not change over time, an order of auto-regression can be determined based on the decay of associated PACF value with respect to lag. In this case, the lag may be the number of previous sections. The variation of the PACF values with respect to the lag may be plotted in the form of a PACF plot, as will be understood by a person skilled in the art.
[0053] As mentioned earlier, the aforementioned steps may be performed for a plurality of iterations, each iteration corresponding to a subgroup. For instance, first iteration may be performed on the subgroup of travel time vectors corresponding to a 6AM- 7 AM time slot, a second iteration may be performed on the subgroup of travel time vectors corresponding to a 7AM- 8 AM time slot, and so forth.
[0054] Upon performing the plurality of iterations, a subgroup order identified for each of the subgroup. For instance, a subgroup order corresponding to a travel time vectors in a 6AM- 7 AM time slot, a subgroup order corresponding to travel time vectors in a 7 AM- 8 AM time slot, and so forth. Subsequently, a highest subgroup order from the plurality of iterations as the order of dependence for the section. For instance, consider there are 3 subgroups corresponding to three time slots- 6 AM-7 AM time slot, 7 AM- 8 AM time slot and 8 AM-9 AM time slot. Further consider, a subgroup order for a 6 AM- 7 AM time slot is 2, a subgroup order 7 AM- 8 AM time slot is 3, a subgroup order for a 8 AM- 9 AM time slot is 4. Then, order of dependence may be 4, since it is the highest subgroup order among the considered subgroups.
[0055] Next, at block 206, a non-linear function fn may be determined. For this, a non-linear regression technique may be utilized. The non-linear function fn may be determined by non-linearly regressing travel times at the section in a plurality of trips with travel times at the first number of sections in the plurality of trips and entry times at the section at the plurality of trips. This may be computed based on the order of dependence

computed from the step mentioned at block 204. That is, Zn is non-linearly regressed with respect to , here Zn represents the travel time at the nth
section, represent travel times at first number of sections immediately
before the nth section on the route and T«(n) represents entry time of the vehicle at the nth section. For example, consider a vehicle traversing a seventh section on the route in a trip and the first number of sections (i.e., order of dependence) is 3. The travel time at the seventh section in the trip may be non-linearly regressed with the travel time at the sixth section in the trip, travel time at the fifth section in the trip and the travel time at the fourth section in the first trip, and entry time of the vehicle at the seventh section in the trip. This process of non-linear regression may be continued for each of the plurality of sections on the route and further, for each of the plurality of trips made on the route, to estimate the non-linear function fn.
[0056] In an implementation, if n< Q+1, then Zn is non-linearly regressed with respect to all the sections
[0057] For the determination of non-linear function fn, the travel times at the section for the plurality of trips, the travel times at each of the first number of sections, and entry times at the section for the plurality of trips may be retrieved from the dataset. [0058] In an implementation, to determine the non-linear function fn, a non-linear regression technique may be utilized. The non-linear regression technique may be a Support vector regression technique (SVR) with a Gaussian Kernel and an artificial neural network technique (ANN). Further, the resulting residual error variances are stored for the section. The residual error variance may be represented as [0059] In an example, to fine tune prediction of travel time at the section in the first trip, a first non-linear temporal function , may be estimated. The first non-linear temporal function , indicates travel time at the section in a second trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the second trip. . The second trip is a trip immediately preceding the first trip on the route. The second trip may have been undertaken by a previous vehicle, i.e., a vehicle that traversed the sections at an earlier instant of time, or the same vehicle. The method of fine tuning the prediction of travel time using a second non-linear temporal function will be described later.

[0060] For instance, consider that a first public transport bus travelling on a route has crossed 40 sections on the route. Also, consider that a second public transport bus has just started from the origin on the route. So, the trip made by the first public transport bus is referred to as the second trip and the trip being made by the second public transport bus is referred to as the first trip. This is because the trip made by the first public transport bus is the immediately preceding trip made on the route with respect to the trip made by the second public transport bus. In such a case, to refine predicted travel time for the second public transport bus at a third section from the origin, a travel time for the first public transport bus at the third section from the origin, an entry time of the first public transport bus at the third section from the origin and an entry time of the second public transport bus at the third section may be used.
[0061 ] The inclusion of the first non-linear temporal function in the prediction
model will be mathematically represented below:
[0062] If and denote the travel time at the nth section in the second trip and in the first trip, respectively, then may be a non-linear noisy version of , where n(k) is additive noise with a variance . This may be referred to as a temporal dependency.
This temporal dependency may further include dependence of travel time of the vehicle at the section in the second trip on entry time at the section in the first trip and on entry time at the section in the second trip. Below equations describe how the temporal dependencies of the first trip with respect to the second trip are learnt:

where is the number of trips on kth day, zn is the travel time vector (d X 1) at the nth section, and d is the number of trips across all D days in a time slot, such as one-hour slot.

where
[0063] In this regard, a first non-linear temporal function is computed by non-linearly regressing the travel times and the entry times in the dataset. In particular, the first non-linear temporal function may be estimated by non-linearly regressing the training set from the above equation, using the non-linear regression technique. For

instance, in the above training set, , may be non-linearly regressed with respect to
, to estimate the first non-linear temporal function . In an implementation, the non-linear regression technique may be a support vector regression (SVR) technique with a Gaussian Kernel may be used. In another implementation, the non-linear regression technique may be a feed forward artificial neural network technique may be used.
[0064] For instance, to learn the first non-linear temporal function , consider, for a section, a dataset for a first day fornumber of
trips on the first day, for a second day fornumber
of trips on the second day, and so on. A first dataset may be formed as first trip of the first day to last but one trip of the first day, first trip of the second day to last but one trip of the second day, and so on. Similarly, a second dataset may be formed as 2nd trip of the first day to last trip of the first day, 2nd trip of the second day to last trip of the second day, and so on. Accordingly, the first dataset may be regressed with the second dataset for each section, such that the travel time at the section in an immediately preceding trip to a trip is regressed with the travel times at the section at the the trip, with entry times at the section in the first dataset, with entry times at the section in the second dataset, such that the first non-linear temporal function is estimated. subsequently, covariance at the section may be computed.
[0065] In an example, to refine prediction of travel time at the section in the first trip, a second non-linear temporal function may be estimated. The second non-linear temporal function indicates travel time at the section in a third trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the third trip. As mentioned earlier, the third trip is a trip on the route on a same day as the first trip on the preceding week with a start time of the trip closest to the start time of the first trip compared to start times of plurality of trip on the same day as the first trip on the preceding week. The third trip may have been undertaken by a different vehicle travelling on the route or the same vehicle. The method of fine tuning the prediction of travel time using a second non-linear temporal function will be described later.

[0066] For instance, consider a first public transport bus has just started from the origin on the route with a start time at 10.00 AM on a Wednesday of the first week. Also, consider that a second public transport bus made a trip on a Wednesday of the preceding week from the first week, with a start time at 10.05 AM and a third public transport bus made a trip on the Wednesday of the preceding week from the first week, with a start time at 11.05 AM. In this case, as mentioned earlier, the trip made by the second public transport bus with a start time at 10.05 AM may be referred as the third trip, since it has the closest start time relative to the first public transport bus compared to the trip made by third public transport bus. To refine tune the travel time for the second public transport bus at a third section, an entry time for the second public transport bus at the third section and the entry time for the first public transport bus at the third section, the travel time for the first public transport bus at the third section may be used.
[0067] If: and zn denote the travel time at the nth section in the second trip and in the first trip, respectively, then may be a non-linear noisy version of zn, where n(k) is additive noise with a variance . This may be referred to as a temporal dependency.
This temporal dependency may further include dependence on entry time at the section in the first trip and on entry time at the section in the third trip. Below equations describe how the temporal dependencies of the first trip with respect to the third trip are learnt:

Here w =2,...,W, d indexes of a week; is a trip with the closest starting time as
the first trip on day d of the previous week w-1 compared to starting times of all other trips made on day d of the previous week w-1.
[0068] In this regard, a second non-linear temporal function is computed by non-linearly regressing the travel times and the entry times in the dataset, using the non-linear regression technique. In particular, the second non-linear temporal function may be estimated by non-linearly regressing the training set from the above equation. For instance, second non-linear temporal function is estimated by non-linearly regressing rwith respect to . In an implementation, the non-linear

regression technique may be, for example, a support vector regression technique with a Gaussian Kernel. In another implementation, the non-linear regression technique may be, for example, a feed forward artificial neural network technique may be used. [0069] For instance, to learn the second non-linear temporal function , Consider, for a section, a series may be formed for a first
day of a first week for number of trips on the first day of the first week,
for a second day for number of trips on the second day, and
so on for multiple trips on multiple days for multiple weeks. A third dataset may be formed as first trip of the first day of the second week to last trip of the last day of the second week till the last trip of the last day of the last week of data. Similarly, a fourth dataset may be formed as first trip of the first day of the first week to last trip of the last day of the last but one week of data. Accordingly, the third dataset may be regressed with the fourth dataset for each section, such that travel times at the section at the third trip is regressed with travel times at the section in the first trip, with entry times at the section in the first trip and with the entry times at the section in the third trip. In this regard, the second non¬linear temporal function is estimated and subsequently, covariance at the section may be computed.
[0070] Now, the utilization of the prediction model to predict the section travel times will be explained. In an implementation, the prediction model may be utilized by a predictive filtering technique for performing the prediction. An example of a predictive filter is an extended Kalman-Filter (EKF). Accordingly, the predictive filtering technique may be referred to as extended Kalman-Filter technique (EKF). To enable utilization by the predictive filter, the prediction module 110 may formulate a state-space based non-linear dynamical system (NLDS) model based on the prediction model. The state-space-based NLDS model may be referred to as a state-space model.
[0071] The state space model may comprise a state equation and an observation equation. A state equation of the state-space model may need to capture travel times at the first number of sections ('Q' sections), exit time from a section of current position of the vehicle and also capture data from the second trip (i.e., travel times at the section from the second trip and entry time at the second trip), in order to set up the observation
39

equation of the state space model. So, if (Q+1) dimension is used, then the state equation only has information of the exit time from the section of current position and the observations from the second trip may not be included in the state equation. So, a (Q+2) dimensional state space model may be used, such that the observation equation may be set up. In this regard, in the state equation of the state space model an entry time of the vehicle in a section of the current position of the vehicle is included. [0072] Accordingly, the state-space model may be built using the vehicle's (observed) section travel times up to section m and the previous vehicle's section travel times beyond section m and entry times of both the vehicles into the section m. The state-space model, usable by the EKF, is represented in the below equations:

Equation (6) represents the state equation and equation (7) represents the observation equation. In the above equation, X(k) is a state variable, also referred to as state vector, that is describing the system behavior and y(k) is a observation variable. X(k) is taken as the travel time in a current section, X(k-1) represents travel times in previous many sections and Fk is a state transition map, which is non-linear. Further, w(k) represents process noise, i.e., noise in the state equation and v(k) represents observation noise, noise in the observation equation. To develop the state-space model, the following computations are performed by the prediction module 110: General State Vector



Here are state and observation noise covariances respectively.
[0073] In the above equations, the observation equation Gk , which is non-linear, has two components component due to the previous trip (i.e., second trip) and ,
component due to travel time at the previous week trip (i.e., third trip). Accordingly, the observation equation is built to capture the non-linear temporal relationship between travel time at the section in the first trip on travel time at the section in the second trip, travel time at the section in the third trip, entry time at the section in the first trip, entry time at the section in the second trip and entry time at the section in the third trip. [0074] The components have three inputs out of which the inputs
(travel time at the section m+k), (entry time at the section m+k in the first
trip) may be obtained from the vehicle's state or the information from the dataset. The third input (entry time at the section in the second trip) and (entry
time at the section in the third trip) are modelled via and respectively, as can
be seen from the above equations.
[0075] The above computations are part of the EKF technique. For the equations (8)
are obtained as inputs by non-linear regression technique in spatial correlation and temporal correlations.
[0076] The state-space model, as explained above, may be utilized to perform travel time prediction for a vehicle at a section based on the travel time of the vehicle at the second number of sections immediately preceding the section on the route. For the prediction, the extended Kalman Filter (EKF) may be used. In the EKF, a taylor series

based linearized approximation is performed at each step, followed by an application of
linear Kalman filter.
[0077] The prediction of travel time and refining of predicted travel time performed is
explained with the help of below equations:
Initial State Vector

[0078] The equations (21) -(31) correspond to the steps in EKF. Equations (18) -
(26b) are referred to as time update equations and use the model and system inputs to

predict a priori state estimate. Equations (27) - (31) are referred to as observation update equations, which use the output observations to obtain a posteriori estimate. [0079] As explained in the above equations (26 a) & (27), at each step in the EKF, a linear approximation of the functions Fk and Gk may be performed. This includes computation of jacobians of these functions as matrices A(k) and c(k) respectively. By the definition of Fk from equation (14), the first row of A(k) involves partial derivatives of . The last element is 0 because, fm+k is independent of the entry time into section m+k-1. The next Q-1 components of Fk are downshift operations of the first Q-1 components of the input X(k-1), thereby the next Q-1 rows of A(k) are binary with a single 1 at the appropriate column. The (Q+1)th row differs from the first row at the (Q+1)th position as this component function via the definition of Fk is . The
last component function is just and thereby, at position (Q+1) at the last row
has '1'. For c(k), in both rows except for the first row and the last values, all partial derivatives are zero from the definition of Gk, from equation (17). In an implementation, closed form derivative of A(k) and C(k) may be computed using one of: a support vector machining technique (SVM) and an artificial neural network technique(ANN). This may reduce the computational time required for computing the EKF and hence reducing computational time for the prediction of travel time. Further, the travel time prediction at the kth section ahead will be the first component of. (k|k). [0080] Overall, the above equations (25) - (31) may be run as a recursively, so that new observations can be processed when they are obtained. The running of the above equations recursively may be referred to as recursive use of the EKF. To run the above equations, only the current instant state estimate, current input, and output observation are utilized to calculate the next instant's state estimate. As will be understood, the current input may include the real-time data of section travel times in the first number of sections, entry and exit times at section m, the section travel times in the second trip after section m along the route, entry times at section beyond section m in the second trip, the section travel times in the third trip after section m along the route and the entry ties at section beyond section m in the third trip.
[0081] In the above equations, represent current travel time data of
current vehicle at its first m sections, represent travel time data of the at

the second trip beyond the mth section, represent travel time data of the at the
third trip beyond the mth section, represent entry and exit times at the
section m in the first trip, represent the entry time at the (m+k)th
section in the second trip and the third trip respectively. Further, represents the
travel time prediction for the kth section ahead of mth section. Here, k may be any positive integer. Thus, using the present subject matter section travel times can be predicted not only for immediately next section (m+1th section) that a vehicle is to arrive at, but also for other sections after the immediately next section, such as m+2nd section, m+3rd section, and the like. Accordingly, the present subject matter can be used for accurate prediction of section travel times at several sections that a vehicle is yet to cross. [0082] As mentioned earlier, predicted travel time at the section in the first trip may be refined to get a better accuracy. In this regard, the travel time at the section in the first trip may be predicted using the state-space model based on the prediction model. This is done using the EKF technique, which is represented by the mathematical equation (25). As explained earlier, this is computed using the function In an example, the non-
linear function. is , when n is represented as m+k. [0083] Upon prediction of travel time, the predicted travel time may be refined by using a first non-linear temporal function and a second non-linear temporal function
. The first non-linear temporal function , may be used to estimate travel time at the section in the second trip. In particular, using predicted travel time at the section in the first trip, entry time at the first trip, the entry time at the second trip and the first non¬linear temporal function the travel time at the section in the second trip may be estimated. The second non-linear temporal function may be used to estimate travel time at the section in the third trip. In particular, using predicted travel time at the section in the first trip, entry time at the third trip, the entry time at the third trip and the second non-linear temporal function the travel time at the section in the third trip may be estimated. In an example, the non-linear function when n is represented as m+k. For instance, this may be performed by the equation (27) mentioned above.
[0084] Using estimated travel time at the section in the second trip and estimated travel time at the section in the third trip, the travel time at the section in the first trip may

be refined. For instance, estimated travel time at the section in the second trip may be compared with an actual travel time at the section in the second trip, estimated travel time at the section in the third trip may be compared with an actual travel time at the section in the third trip. Further, a residual is computed. The residual indicates a difference of estimated travel time at the section in the second trip and actual travel time at the section in the second trip and a difference of estimated travel time at the section in the third trip and the actual travel time at the section in the third trip. The residual, may be, for example, a matrix comprising the aforementioned differences. For instance, in the above equation
represents the residual which, may be a matrix.
[0085] Further, using the residual, predicted travel time at the section in the first trip
may be refined. For instance, the predicted travel time may be updated using the residual and a Kalman Gain, which is represented using equation (29). The Kalman Gain is computed by using the equation (28). Refined prediction of travel time at the section in the first trip is shown at equation (31).
[0086] In another implementation, the prediction model may be utilized by a
predictive filtering technique, such as a particle-Filter (PF). To enable utilization by the predictive filter, the prediction module 110 may formulate a state-space based non-linear dynamical system (NLDS) model based on the prediction model, as represented by equations (6) and (7). The state-space-based NLDS model may be referred to as a state-space model. In this regard, the PF is initialized with a prefixed number of particles, all of them at state X(0). Each of the particles makes a markovian state transition per the state equation (6) from state X(k-1) into state X(k) with noise w(k). The following mathematical equation represent the above mentioned statement. Initial Np particles with initial Stave Vector


Subsequently, weight of each particle is calculated based on current state X(k) and observation Y(k).

Then, the weight vector is normalized to form a distribution and the particles are resampled with a replacement to obtain new set of particles Np. The travel time prediction is obtained by taking mean of the first component of all the particles i.e., first component of

[0087] Using the models of the present subject matter, the prediction of the travel
time is optimal if the associated distributions are gaussian. However, in some cases, the distribution of the travel times (which are always positive) in the dataset at any particular section and time slot may be right-skewed, i.e., may be a lognormal distribution. In such cases, a log transformation may be applied on each travel time observation in the dataset before applying the method 200 and before performing the computations of equations (2) - (21) and (21)- (31) or (2) - (21) and (32)- (37). The log transformation may be performed on the collected travel times while collating travel times as part of the dataset. This enables making the marginal distributions approximately gaussian, so that the predictions made are close to optimal. Subsequently, the predictions output from equation (31) or the equation (37), i.e., the predicted section travel times, are exponentiated to obtain final predictions. It may be noted that the entry times and the exit times at the section are retained in the original form (i.e., without log transformation).
[0088] (Q+1)th component of Fk may be modified from to
in equation (14) and thereby, A(k) may be modified from
in equation (25).

[0089] Fig. 3 illustrates a method 300 for developing a prediction model usable in
prediction of travel time of vehicles at sections along a route that has a plurality of sections, in accordance with an implementation of the present subject matter. The travel time at a section may refer to the time taken to cross the section.

[0090] The order in which the method 300 is described is not intended to be
construed as a limitation, and any number of the described method blocks may be combined in any order to implement the method 300, or an alternative method. Furthermore, the method 300 may be implemented by processor(s) or computing device(s) through any suitable hardware, non-transitory machine-readable instructions, or a combination thereof.
[0091] It may be understood that steps of the method 300 may be performed by
programmed computing devices and may be executed based on instructions stored in a non-transitory computer readable medium. The non-transitory computer readable medium may include, for example, digital memories, magnetic storage media, such as one or more magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. Further, although the method 300 may be implemented in a variety of systems, the method 300 is described in relation to the aforementioned system 100, for ease of explanation. The steps of the method 300 may be performed by the prediction module 110.
[0092] At block 302, an order of dependence for a section is determined based on a
dataset. The dataset comprises data of travel times of at least one vehicle at each of the plurality of sections for a plurality of trips on the route and entry times of the vehicle at each of the plurality of sections for the plurality of trips. In an example, for developing the dataset, the method 300 includes partitioning the route into the plurality of sections, collecting the travel time in the plurality of sections for a plurality of trips on the route for at least one vehicle and entry times at the plurality of section for the plurality of trips, and collating the travel times and entry times as the dataset.
[0093] The order of dependence is a first number of sections immediately before a
section on the route that influence the travel time of the vehicle at the section. The order
of dependence may be, for example, Q, as explained with reference to Fig. 2. The order
of dependence may be a common value for all sections on the route.
[0094] At block 304, a prediction model is formulated. The prediction model indicates
dependence travel time of the vehicle at the section in a first trip on travel time at the first number of sections in the first trip and on an entry time of the vehicle at the section in the first trip. In this regard, formulating the prediction model comprises estimating a non-linear

function fn, using a non-linear regression technique, by non-linearly regressing travel
times of the vehicle at the section in the plurality of trips with travel time at the first number
of sections in the plurality of trips and the entry time of the vehicle at the section in the
plurality of trips and the prediction model is usable to predict travel time at the section.
For instance, the non-linear regression technique is one of a support vector regression
(SVR) technique and an artificial neural network (ANN) technique.
[0095] In an exemplary implementation, the method 300 includes formulating a
prediction model indicates dependence of travel time at the section in the first trip on travel time at the section in a second trip on the route and on an entry time at the section in the second trip, the second trip being a trip immediately preceding the first trip on the route. Further, the method 300 includes formulating a prediction model. The prediction model indicates dependence of travel time at the section in the first trip on travel time at the section in a third trip, and on an entry time at the section in the third trip, the third trip being a trip on a same day as the first trip on a preceding week with a start time of the third trip being closest to a start time of the first trip compared to start times of a plurality of trips on the same day as the first trip on the preceding week.
[0096] In an exemplary implementation, the method 300 further includes, formulating
a state-space model based on the prediction model, predicting travel time of a vehicle at
a section based on travel times of the vehicle at the first number of sections immediately
before the section on the route and on an entry time of the vehicle at the section, using
the state-space model. For instance, the prediction may be performed as mentioned in
the equation (6) and (7). Further, in an implementation, a predictive filtering technique
may be utilised by the state space model to predict the travel time by using equations
(21)- (31). In another implementation, a predictive filtering technique may be utilised by
the state space model to predict the travel time by using equations (32) -(38).
[0097] Fig. 4 illustrates a method 400 for predicting travel time of vehicles at sections
along a route that has a plurality of sections, in accordance with an implementation of the
present subject matter. The route may have an origin and a destination.
[0098] The order in which the method 400 is described is not intended to be
construed as a limitation, and any number of the described method blocks may be combined in any order to implement the method 400, or an alternative method.

Furthermore, the method 400 may be implemented by processor(s) or computing device(s) through any suitable hardware, non-transitory machine-readable instructions, or a combination thereof.
[0099] It may be understood that steps of the method 400 may be performed by
programmed computing devices and may be executed based on instructions stored in a non-transitory computer readable medium. The non-transitory computer readable medium may include, for example, digital memories, magnetic storage media, such as one or more magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. Further, although the method 400 may be implemented in a variety of systems, the method 400 is described in relation to the aforementioned system 100, for ease of explanation. The steps of the method 400 may be performed by the prediction module 110.
[00100] At block 402, receiving real time data of travel time of a vehicle. The real-time travel time data comprises the following data:
(a) travel times of the vehicle at each section of a first plurality of sections travelled by the vehicle in a first trip. The first plurality of sections are sections on the route before a first section. The first plurality of sections is a subset of the plurality of sections. For instance, consider the route has 56 sections and the vehicle has travelled 15 sections in the first trip, then first plurality of sections is 15 sections and travel time data of the vehicle at each of the 15 sections may be received.
(b) travel time at the first section in a second trip on the route and an entry time at the first section in the second trip. The second trip is a trip immediately preceding the first trip on the route. For instance, the second trip could be made in the route by the same vehicle as the first trip or by a different vehicle on the route.
(c) travel time at the first section in a third trip and an entry time of the vehicle at the first section in the third trip. The third trip is a trip on a same day as the first trip on a preceding week with a start time of the third trip closest to a start time of the first trip compared to start times of a plurality of trips on the same day as the first trip on the preceding week. For instance, the third trip may be a trip made by the same vehicle as the first trip or by a different vehicle.

(d) an entry time of the vehicle in the first trip at a section immediately preceding the first section and an exit time of the vehicle in the first trip at the section immediately preceding the first section. For instance, consider the first section is seventh section on the route, the real-time travel time data may comprise entry time of the vehicle at the sixth section in the first trip and the exit time of the vehicle at the sixth section in the first trip. [00101] At block 404, a state-space model is received. The state-space model is generated from a prediction model.
[00102] The prediction model indicates dependence of travel time of a vehicle at a first section in a first trip on a travel time of the vehicle in the first trip at a first number of sections before the first section on the route and on entry time of the vehicle at the first section in the first trip. The prediction model may be the prediction model generated from the method 300. The state-space model may be, for example, the model explained with reference to equations (6) and (7).
[00103] At block 406, travel time of the vehicle for the first section to be traversed in the first trip is predicted using the prediction model and the real-time data. The prediction of the travel time may involve recursive use of Kalman filtering technique (EKF) or a particle filtering technique (PF), as explained earlier. For instance, as explained in equation (31) or (38), section travel time at any kth section ahead of the current section traversed by the section can be predicted using the state-space model [00104] In an example, the method 400 comprises estimating travel time of the vehicle at the section in the second trip by using a first non-linear temporal function. The first non¬linear temporal function indicates the travel time at the section in the second trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the second trip. The method 400 also includes estimating travel time of the vehicle at the section in the third trip using a second non-linear temporal function. The second non-linear temporal function may indicate travel time of the vehicle at the section in the third trip as a function of travel time of the vehicle at the section in the first trip, entry time at the section in the first trip and entry time at the section in the third trip. The method 400, further comprises, computing a residual. The residual indicates a difference in estimated travel time at the section in the second trip and an actual travel time at the section in the second trip and a difference in estimated travel time at the

section in the third trip and an actual travel time at the section in the third trip. The actual travel time at the section in the second trip and actual travel time at the section in the third trip may be available in the dataset in data 112. Further, the method 400 may comprise refining predicted travel time at the section in the first trip using the residual. This increases the accuracy of the predicted travel time at the section in the first trip. The aforementioned steps of the method 400, may be for example, performed by EKF, which are shown in the equations (21)- (31). In another implementation, PF may be used to perform the aforementioned method 400 steps, as shown in equation (32)- (38). As an example, the real-time data further comprises a travel time at a second section in the second trip, a travel time at the second section in the third trip, an entry time at the second section in the second trip, an entry time at the second section in the second trip, an entry time at the second section in the third trip. The prediction model indicates dependence of travel time of the vehicle at the second section in the first trip on travel times in the first trip at a second number of sections immediately before the second section and on entry time of the vehicle at the second section in the first trip. The prediction model may be the prediction model generated from the method 300. The state-space model may be, for example, the model explained with reference to equations (6) and (7). As explained with reference to method 200, the predicted travel time may be refined using the first non¬linear temporal function and second non-linear temporal function. Further, as mentioned earlier, predicting travel time of the vehicle at the second section to be traversed in the first trip using the prediction model and the real-time data.
[00105] The accuracy of the travel times predicted by the present subject matter is illustrated with the help of a few examples below.
EXAMPLES [00106] The proposed methodology was implemented in a bus route in a city in India. Data was collected across two non-overlapping sets of weeks, a set containing data for 12 consecutive weeks and another set containing data for 5 consecutive weeks. In each week, data was collected from Monday to Saturday, since travel time on Sundays being different from rest of the days of the week. The selected bus route was of length 28 km. The bus route was segmented into sections each of 400 m length.

[00107] For testing and training, data across all sections and trips for 11 consecutive weeks in the first set and data across all sections and trips from four consecutive weeks in the second set were used. Prediction were carried out on data of last week of the first set i.e., 12th week in the first set and on data of last week of the second set i.e., 5th week in the second set.
[00108] The results of the prediction from the present approach is compared between two filtering techniques used in the present approach viz., extended Kalman filter (EKF) and particle filter technique (PF). Fig. 5(a) illustrates performance comparison in terms of Mean Absolute Percentage Error (MAPE) for the extended Kalman filter technique (EKF) and Particle filter technique proposed by the present approach for a plurality of trips for a two-step prediction. Fig. 5(b) illustrates rum time comparison of EKF and PF proposed by the present approach for a plurality of trips for a two-step prediction. Tow step prediction refers to prediction of travel time when the vehicle is two sections behind a location for which travel time is predicted. Referring to Fig. 5(a) and Fig. 5(b), prediction accuracies are nearly identical for EKF and PF, while the run time of EKF is substantially lower compared to that of PF. In this regard, further comparisons were made using the EKF technique alone.
[00109] Next, the results of the present subject matter were compared with five conventional methods: (a) historical average (HA) of the training data which will serve as a baseline comparison, (b) Space discretization (SD) (a conventional method which uses a data-based model and employs model calibration), and (c) Support Vector Machine method (SVM07), which captures spatial and temporal dependency in a simple way, (d) support vector machine method (SVM16), which exploits temporal dependencies alone from multiple trips and (e) an artificial neural network method (NN04), which doesn't exploit temporal correlation. As mentioned earlier, the prediction was carried out for a test period of one week in the selected route for the first set of data and one week for the second set of data. The prediction accuracy was calculated in terms of Mean Absolute Percentage Error (MAPE) and Mean Absolute Error (MAE). Percentage error is the Absolute Error divided by the true prediction expressed in percentage. The prediction accuracy of a technique may also be referred to as the performance of the technique.

[00110] For single-step prediction (when the vehicle is one section behind a location for which travel time is predicted) was compared with methods (a), (b), (c) and (d). Since, the method (e) yielded MAPE more than 100%, which could be due to high variability in data arising from heterogenous traffic conditions. Fig. 6(a) illustrate the results of comparison of the performance of the present subject matter with the aforesaid four methods for a single step prediction for a plurality of days for the first set of data, in accordance with an implementation of the present subject matter. Fig. 6(b) illustrate the results of comparison of the performance of the present subject matter with the aforesaid four methods for a single step prediction for a plurality of days for the second set of data, in accordance with an implementation of the present subject matter. It can be observed that the proposed method consistently outperforms the existing methods by reducing MAPE up to 15%, 10%, 3.5% and 3.5% as compared to historical average, space discretization, SVM07 and SVM16 approaches, respectively.
[00111] Next, comparisons at were performed at a finer level, i.e., at a section level. [00112] Fig. 7(a) illustrates reduction of MAPE provided by the present compared to the HA method for each section for the single step prediction, for the first set of data, in accordance with an implementation of the present subject matter. Fig. 7(b) illustrates reduction of MAPE provided by the present compared to the SD method for each section for the single step prediction for the first set of data, in accordance with an implementation of the present subject matter. Fig. 7(c) illustrates reduction of MAPE provided by the present compared to the SVM07 method for each section for the single step prediction for the first set of data, in accordance with an implementation of the present subject matter. Fig. 7(d) illustrates reduction of MAPE provided by the present compared to the SVM16 method for each section for the single step prediction for the first set of data, in accordance with an implementation of the present subject matter. [00113] From Figs. 7(a) and 7(b), it can be observed that the present subject matter outperforms HA and SD methods across all sections with a worst-case improvement of up to 29% and 22%, respectively, in terms of MAPE. Further, from Fig. 7(c) and fig. 7(d), it is clear that the present subject matter provides a worst-case improvement of up to 10% and 17% in terms of MAPE compared to the SVM07, SVM16 methods respectively.

[00114] Fig. 8(a) illustrates reduction of MAPE provided by the present compared to the HA method for each section, for the single step prediction for the second set of data, in accordance with an implementation of the present subject matter. Fig. 8(b) illustrates reduction of MAPE provided by the present compared to the SD method for each section for the single step prediction for the second set of data, in accordance with an implementation of the present subject matter. Fig. 8(c) illustrates reduction of MAPE provided by the present compared to the SVM07 method for each section for the single step prediction for the second set of data, in accordance with an implementation of the present subject matter. Fig. 8(d) illustrates reduction of MAPE provided by the present compared to the SVM16 method for each section for the single step prediction for the second set of data, in accordance with an implementation of the present subject matter. [00115] From Figs. 8(a), 8(b), 8(c) and 8(d), it can be seen that the trend in second set of data was similar to trend in first set of data represented by the Fig. 7(a), 7(b), 7(c) and 7(d). The MAPE reductions are maximum in comparison to HA while among the existing methods, the present method outperforms SD method in all sections, while the present method does better than SVM07 and SVM16 in majority of the sections. [00116] As explained earlier, an application of the present subject matter is to provide the arrival information of public transport vehicle, such as bus, to passengers at the bus stops at which the public transport vehicle is yet to arrive, prior to its arrival. Therefore, the performance of the present subject matter was evaluated and compared by checking the deviation of the predicted travel time from the measured travel time for each bus stop in the route. Further, the errors were expressed in user-understandable clock time difference. For this multi-step prediction (i.e., when the vehicle is more than one section behind a location for which travel time is predicted), the proposed method was compared with methods (a), (b), (c) and (e)
[00117] Fig. 9(a) illustrates the comparison of MAE values for multi-step prediction of the arrival time predicted for bus stop A for the first set of data, in accordance with an implementation of the present subject matter. Fig. 9(b) illustrates the comparison of MAE values for multi-step prediction of arrival time predicted for bus stop B for the second set of data, in accordance with an implementation of the present subject matter. In this regard, the results from artificial neural network method (NN04) method were also compared, as

its multi-step prediction errors were comparable with historical averaging (HA) method. In particular, in fig. 9(a) and fig. 9(b), the arrival time is predicted for the bus stops A and B when a bus is 1, 5, 10, 15, and 25 sections away from the bus stops A and B, respectively. As mentioned earlier, the arrival times may be predicted using travel time at each section. From Figs. 9(a) and 9(b), it can be seen that the present subject matter outperforms HA, NN04 and SD methods, while it outperforms SVM07 method.
[00118] The present subject matter provides an effective travel time prediction method even under mixed traffic conditions and when there is a lack of lane discipline. The present subject matter provided an improvement in terms of error in the predicted travel time with the existing methods. The present subject matter provides a superior performance both under a (i) single-step setting (when the vehicle is one section behind a location for which travel time is predicted) and (ii) multi-step setting (when the vehicle is more than one section behind a location for which travel time is predicted). [00119] The present subject matter provides a data-based statistical model which fully exploits the inherent spatial dependencies and temporal dependencies. Accordingly, the historical data are utilized to learn non-linear (a)spatial dependencies between travel times of adjacent sections and (b)temporal dependency between successive trips and (c) temporal dependency between trips made on a same day of two consecutive weeks with comparable start times. Further, the learnt model is reformulated as a non-linear dynamical system (NLDS) in a state space form which enables application of Kalman Filtering (EKF) for prediction. Furthermore, travel times predicted according to the present subject matter is accurate. The time required for prediction of travel times is less. The systems and methods of the present subject matter may be hardware resource efficient. Further, the systems and methods may be implemented with minimal hardware resources and without the use of specialized hardware.
[00120] Although the present subject matter has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as alternate embodiments of the subject matter, will become apparent to persons skilled in the art upon reference to the description of the subject matter.

I/We Claim:
1. A method for predicting travel time of a vehicle at a section in a trip in a route
comprising a plurality of sections, the method comprising:
determining an order of dependence for the section based on a dataset, wherein the dataset comprises data of travel times of at least one vehicle at each of the plurality of sections for a plurality of trips on the route and entry times of the vehicle at each of the plurality of sections for the plurality of trips and wherein the order of dependence is a first number of sections immediately before the section on the route that are likely to influence travel time of the vehicle at the section; and
formulating a prediction model indicating dependence of travel time of the vehicle at the section in a first trip on travel time at the first number of sections in the first trip and on an entry time of the vehicle at the section in the first trip, wherein the formulating the prediction model comprises:
estimating a non-linear function, using a non-linear regression technique, by non-linearly regressing travel times of the vehicle at the section in the plurality of trips with travel time at the first number of sections in the plurality of trips and entry times of the vehicle at the section in the plurality of trips, wherein the prediction model is usable to predict travel time at the section.
2. The method as claimed in claim 1, wherein determining the order of dependence
for the section comprises:
segregating travel times of the vehicle in the dataset into a plurality of subgroups of travel times, a subgroup corresponding to a time slot of a plurality of time slots;
performing, for each subgroup, a plurality of iterations, wherein each iteration comprises:
concatenating the subgroup to form a time series; and determining a partial auto correlation function (PACF) value for the subgroup based on the time series; and

identifying a largest lag for which the PACF value is above a cut-off PACF value as a subgroup order; and
selecting a highest subgroup order from the plurality of iterations as the order of dependence for the section.
3. The method as claimed in claim 1, wherein the non-linear regression technique is one of: a support vector regression (SVR) technique and artificial neural network (ANN) technique.
4. The method as claimed in claim 1, wherein the prediction model indicates dependence of travel time at the section in the first trip on travel time at the section in a second trip on the route and on an entry time at the section in the second trip, the second trip being a trip immediately preceding the first trip on the route.
5. The method as claimed in claim 1, wherein the prediction model indicates dependence of travel time at the section in the first trip on travel time at the section in a third trip, and on an entry time at the section in the third trip, the third trip being a trip on a same day as the first trip on a preceding week with a start time of the third trip being closest to a start time of the first trip compared to start times of a plurality of trips on the same day as the first trip on the preceding week.
6. The method as claimed in claim 1, comprising:
formulating a state-space model based on the prediction model; and predicting travel time of the vehicle at the section in the first trip based on travel times of the vehicle in the first trip at the first number of sections immediately before the section on the route, entry time of the vehicle at the section in the first trip using the state-space model.
7. The method as claimed in claim 1, comprising:
partitioning the route into the plurality of sections;
collecting the travel times in the plurality of sections for the plurality of trips on the route and entry times at the plurality of sections in the plurality of trips; and collating the travel times and entry times as the dataset.

8. The method as claimed in claim 7, wherein distribution of travel time in the dataset is lognormal, and collating the travel times as the dataset comprises performing a log transformation on the collected travel times.
9. A method for predicting travel time of a vehicle in real time at a section in a trip on a route comprising a plurality of sections, the method comprising:
receiving real-time data pertaining to travel of a vehicle on the route, wherein the real-time data comprises:
travel times of the vehicle at each section of a first plurality of sections travelled by the vehicle in a first trip, the first plurality of sections being sections on the route before a first section, the first plurality of sections being a subset of the plurality of sections;
travel time at the first section in a second trip on the route, the second trip being a trip immediately preceding the first trip on the route;
travel time at the first section in a third trip, the third trip being a trip on a same day as the first trip on a preceding week with a start time of the third trip closest to a start time of the first trip compared to start times of other trips on the same day as the first trip on the preceding week;
an entry time of the vehicle in the first trip at a section immediately preceding the first section;
an exit time of the vehicle in the first trip at the section immediately preceding the first section;
an entry time at the first section in the second trip;
an entry time at the first section in the third trip; receiving a state-space model generated from a prediction model, wherein the prediction model indicates:
dependence of travel time of the vehicle at the first section in the first trip on travel time at a first number of sections immediately before the first section on the route in the first trip and on entry time of the vehicle at the first section in the first trip; and
predicting travel time of the vehicle for the first section to be traversed in the first trip using the prediction model and the real-time data.

10. The method as claimed in claim 9, comprising:
estimating travel time of the vehicle at the section in the second trip by using a first non-linear temporal function, the first non-linear temporal function indicates travel time at the section in the second trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the second trip;
estimating travel time of the vehicle at the section in the third trip by using a second non-linear temporal function, the second non-linear temporal indicates travel time at the section in the third trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the third trip;
computing a residual, wherein the residual indicates a difference in estimated travel time at the section in the second trip and an actual travel time at the section in the second trip and a difference in estimated travel time at the section in the third trip and an actual travel time at the section in the third trip; and
refining predicted travel time at the section in the first trip using the residual.
11. The method as claimed in claim 9, wherein the real-time data further comprises:
a travel time at a second section in the second trip, the second section being a section immediately after the first section in the route;
a travel time at the second section in the third trip;
an entry time at the second section in the second trip;
an entry time at the second section in the third trip, and wherein the prediction model further indicates:
dependence of travel time of the vehicle at the second section in
the first trip on travel times in the first trip at a second number of sections
immediately before the second section and on entry time of the vehicle
at the second section in the first trip; and

predicting travel time of the vehicle at the second section to be traversed in the first trip using the prediction model and the real-time data.
12. The method as claimed in claim 9, wherein predicting travel time of the vehicle comprises one of: an extended Kalman filtering technique (EKF) and a particle filtering (PF) technique.
13. The method as claimed in claim 12, wherein the extended Kalman filtering technique further comprises one of: a support vector machining technique or Artificial Neural Network technique.
14. A system for predicting travel time of a vehicle at a section in a trip in a route comprising a plurality of sections, the system comprising:
a processor; and
a prediction module coupled to the processor, wherein the prediction module is executable by the processor to:
determine an order of dependence for the section based on a dataset, wherein the dataset comprises data of travel times of at least one vehicle at each of the plurality of sections for a plurality of trips on the route and entry times of a vehicle at each of the plurality of sections for the plurality of trips and wherein the order of dependence is a first number of sections immediately after the section on the route that are likely to influence travel time of the vehicle at the section; and
formulate a prediction model indicating dependence of travel time of the vehicle at the section in a first trip on travel time at the first number of sections in the first trip and on an entry time of the vehicle at the section in the first trip, wherein the prediction module is executable to:
estimate a non-linear function, using a non-linear regression technique, by non-linearly regressing travel times of the vehicle at the section in the plurality of trips with travel time at the first number of sections in the plurality of trips and the entry time of the vehicle at the section in the plurality of trips,

wherein the prediction model is usable to predict travel time at the section.
15. The system as claimed in claim 14, wherein the prediction module is executable
to:
formulate a state-space model based on the prediction model; and predict travel time of the vehicle at the section in the first trip based on travel time of the vehicle in the first trip at the first number of sections immediately before the section on the route and on the entry time of the vehicle at the section, using the state-space model.
16. The system as claimed in claim 14, wherein the
prediction module is executable to:
estimate travel time of the vehicle at the section in the second trip by using a first non-linear temporal function, the first non-linear temporal function indicates travel time at the section in the second trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the second trip;
estimate travel time of the vehicle at the section in the third trip by using a second non-linear temporal function, the second non-linear temporal indicates travel time at the section in the third trip as a function of travel time at the section in the first trip, entry time at the section in the first trip and entry time at the section in the third trip;
compute a residual, wherein the residual indicates a difference in estimated travel time at the section in the second trip and an actual travel time at the section in the second trip and a difference in estimated travel time at the section in the third trip and an actual travel time at the section in the third trip; and
refine predicted travel time at the section in the first trip using the residual.

17. The system as claimed in claim 14, wherein the non-linear regression technique is one of: a Support vector regression technique (SVR) and an artificial neural network technique (ANN).