Predicting arrival times of vehicles based upon observed schedule adherence

• US 9,159,032 B1
• Filed: 03/19/2014
• Issued: 10/13/2015
• Est. Priority Date: 03/19/2014
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Tripathi, Abhishek, Rajan, Vaibhav, Edakunni, Narayanan Unny
• Primary Examiner(s): El Chanti, Hussein A.
• Application Number:
  US14/219,487
• Publication Number:
  US 20150269491A1
• Time in Patent Office: 573 Days
• Field of Search: 701/465
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0141 for traffic information dissemination
• CPC Class Codes: G08G 1/127 to a central station ; Indicators in a central station

Abstract

A method and system for determining real-time delay information in a transportation system. Historical operational information about the transportation system, including data related to a plurality of arrival events corresponding to one or more stops within the transportation system is received and a dependency graph is built based upon the historic information. The dependency graph defines relationships that exist in the transportation system between the plurality of arrival events, each of the relationships defining a specific dependent relationship between at least two of the arrival events. Delay dependency values are fitted into the dependency graph, each of the delay dependency values being associated with one of the plurality of relationships and defining a specific dependency value associated with that relationship. Predictive delay information is determined based upon the fitted dependency graph for one or more of the arrival events based upon current operating information.

Claims

1. A method for determining real-time delay information in a transportation system, the method comprising:

receiving, by a processing device, historical operational information about the transportation system, wherein the historical operational information comprises data related to a plurality of arrival events corresponding to one or more stops within the transportation system;

building, by the processing device, a dependency graph based upon the historic information, wherein the dependency graph defines a plurality of relationships that exist in the transportation system between the plurality of arrival events, and wherein each of the plurality of relationships defines a specific dependent relationship between at least two of the plurality of arrival events;

fitting, by the processing device, a plurality of delay dependency values into the dependency graph, wherein each of the plurality of delay dependency values is associated with one of the plurality of relationships and defines a specific dependency value associated with that relationship;

determining, by a processing device, predictive delay information as determined based upon the fitted dependency graph for one or more of the plurality of arrival events based upon current operating information related to the transportation system;

outputting, by a processing device, an indication of the predictive delay information;

receiving at least one real-time observed delay for the at least one of the plurality of arrival events associated with the parent node;

propagating the delay through the fitted dependency graph; and

returning real-time predictive delay information based upon the propagation.

2. The method of claim 1, wherein the dependency graph comprises at least one parent node representing at least one of the plurality of arrival events that is not dependent upon any other of the plurality of arrival events.

3. The method of claim 1, wherein each arrival event comprises an associated geographic location and an associated time of day that the arrival event is predicted to occur.

4. The method of claim 1, wherein building the dependency graph further comprises modeling the historical operational information using a linear relation model to determine the relationships between the plurality of arrival events.

5. The method of claim 4, wherein modeling the historical operational information using a linear regression model further comprises including external variables including at least one of weather information, demographic information, and timing information.

6. The method of claim 1, wherein fitting the dependency graph further comprises:

determining, for each relationship in the dependency graph, a coefficient of regression for each of the plurality of arrival events associated with the relationship; and

modeling each relationship using a linear regression model to determine the delay dependency value for that relationship.

7. The method of claim 6, wherein the linear regression model comprises a lasso regression model.

8. The method of claim 1, wherein outputting an indication of predictive delay information comprises at least one of:

producing a report outlining the predictive delay information;

updating dynamic display information at one or more stops in the transportation system indicating at least a portion of the predictive delay information;

providing at least a portion of the predictive delay information to one or more vehicle operators in the transportation system; and

providing at least a portion of the predictive delay information to a dispatcher in the transportation system.

9. A system for determining real-time delay information in a transportation system, the system comprising:

a processing device; and

a non-transitory computer readable medium in communication with the processing device, the computer readable medium comprising one or more programming instructions for causing the processing device to;

receive historical operational information about the transportation system, wherein the historical operational information comprises data related to a plurality of arrival events corresponding to one or more stops within the transportation system,

build a dependency graph based upon the historic information, wherein the dependency graph defines a plurality of relationships that exist in the transportation system between the plurality of arrival events, and wherein each of the plurality of relationships defines a specific dependent relationship between at least two of the plurality of arrival events,

fit a plurality of delay dependency values into the dependency graph, wherein each of the plurality of delay dependency values is associated with one of the plurality of relationships and defines a specific dependency value associated with that relationship,

determine predictive delay information as determined based upon the fitted dependency graph for one or more of the plurality of arrival events based upon current operating information related to the transportation system,

output an indication of the predictive delay information;

receive at least one real-time observed delay for the at least one of the plurality of arrival events associated with the parent node;

propagate the delay through the fitted dependency graph; and

return real-time predictive delay information based upon the propagation.

10. The system of claim 9, wherein the dependency graph comprises at least one parent node representing at least one of the plurality of arrival events that is not dependent upon any other of the plurality of arrival events.

11. The system of claim 9, wherein each arrival event comprises an associated geographic location and an associated time of day that the arrival event is predicted to occur.

12. The system of claim 9, wherein the one or more instructions for causing the processing device to build the dependency graph further comprise one or more instructions for causing the processing device to model the historical operational information using a linear relation model to determine the relationships between the plurality of arrival events.

13. The system of claim 12, wherein the one or more instructions for causing the processing device to model the historical operational information using a linear regression model further comprise one or more instructions for causing the processing device to include external variables including at least one of weather information, demographic information, and timing information.

14. The system of claim 9, wherein the one or more instructions for causing the processing device to fit the dependency graph further comprise one or more instructions for causing the processing device to:

determine, for each relationship in the dependency graph, a coefficient of regression for each of the plurality of arrival events associated with the relationship; and

model each relationship using a linear regression model to determine the delay dependency value for that relationship.

15. The system of claim 14, wherein the linear regression model comprises a lasso regression model.

16. The system of claim 9, wherein the one or more instructions for causing the processing device to output an indication of predictive delay information comprise one or more instructions for causing the processing device to perform at least one of:

produce a report outlining the predictive delay information;

update dynamic display information at one or more stops in the transportation system indicating at least a portion of the predictive delay information;

provide at least a portion of the predictive delay information to one or more vehicle operators in the transportation system; and

provide at least a portion of the predictive delay information to a dispatcher in the transportation system.