Generation of trip estimates using real-time data and historical data

• US 10,078,337 B1
• Filed: 08/16/2017
• Issued: 09/18/2018
• Est. Priority Date: 07/14/2017
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Yao, Shijing, Cai, Xiao
• Primary Examiner(s): Nguyen, Tan Q
• Application Number:
  US15/678,258
• Time in Patent Office: 398 Days
• Field of Search: 701524
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0276 using signals provided by a source external to the vehicle involving a plurality of vehicles G05D1/0287; automatically controlling vehicle speed responsive to externally generated signals B60K31/0058
• CPC Class Codes: G05D 1/0278 using satellite positioning signals, e.g. GPS
• CPC Class Codes: G05D 1/0287 involving a plurality of land vehicles, e.g. fleet or convoy travelling traffic control systems for road vehicles G08G1/00, particularly anticollision systems G08G1/16

Abstract

A system uses machine models to estimate trip durations or distance. The system trains a historical model to estimate trip duration using characteristics of past trips. The system trains a real-time model to estimate trip duration using characteristics of recently completed trips. The historical and real-time models may use different time windows of training data to predict estimates, and may be trained to predict an adjustment to an initial trip estimate. A selector model is trained to predict whether the historical model, the real-time model, or a combination of the historical and real-time models will more accurately estimate a trip duration, given features associated with a trip duration request, and the system accordingly uses the models to estimate a trip duration. In some embodiments, the real-time model and the selector may be trained using batch machine learning techniques which allow the models to incorporate new trip data as trips complete.

Claims

1. A computer-implemented method comprising:

calculating a first set of confidence intervals representing estimated trip durations using a real-time model;

calculating a second set of confidence intervals representing estimated trip durations using a historical model; and

determining a final confidence interval by applying a selector model which determines whether the real-time model or the historical model is likely to more accurately predict trip durations.

2. The method of claim 1, further comprising:

predicting an initial set of trip durations for the trip based on a network-based estimation algorithm;

wherein the real-time model and the historical model use the predicted set of initial trip durations to generate the first set of confidence intervals and the second set of confidence intervals.

3. The method of claim 2, wherein the network-based estimation algorithm bases trip duration predictions on a graph that models a path between an origin location of the trip and a destination location of the trip as a series of weighted nodes and edges.

4. The method of claim 1, wherein upper and lower bounds of a confidence interval correspond to a quartile values.

5. The method of claim 4, wherein the quartile values are assigned weighting values according to their accuracy and used to train a model to determine the final confidence interval.

6. The method of claim 1, wherein the final confidence interval is determined based on a trained model that uses the first set of confidence intervals and the second set of confidence intervals as inputs when making a determination.

7. The method of claim 1, wherein the real-time model is trained using features of trips that completed within a first time period, and the historical model is trained using features of trips that completed within a second time period.

8. A non-transitory computer-readable storage medium storing computer program instructions executable by one or more processors of a system to perform steps comprising:

calculating a first set of confidence intervals representing estimated trip durations using a real-time model;

calculating a second set of confidence intervals representing estimated trip durations using a historical model; and

determining a final confidence interval representing estimated trip durations from the first and second sets of confidence intervals based on characteristics of the trip and based on whether the first and second confidence intervals include actual trip durations.

9. The non-transitory computer-readable storage medium of claim 8, further comprising:

predicting an initial set of trip durations for the trip based on a network-based estimation algorithm;

wherein the real-time model and the historical model use the predicted set of initial trip durations to generate the first set of confidence intervals and the second set of confidence intervals.

10. The non-transitory computer-readable storage medium of claim 9, wherein the network-based estimation algorithm bases trip duration predictions on a graph that models a path between an origin location of the trip and a destination location of the trip as a series of weighted nodes and edges.

11. The non-transitory computer-readable storage medium of claim 8, wherein upper and lower bounds of a confidence interval correspond to a quartile values.

12. The non-transitory computer-readable storage medium of claim 11, wherein the quartile values are assigned weighting values according to their accuracy and used to train a model to determine the final confidence interval.

13. The non-transitory computer-readable storage medium of claim 8, wherein the final confidence interval is determined based on a trained model that uses the first set of confidence intervals and the second set of confidence intervals as inputs when making a determination.

14. The non-transitory computer-readable storage medium of claim 8, wherein the real-time model is trained using features of trips that completed within a first time period, and the historical model is trained using features of trips that completed within a second time period.

15. A computer system comprising:

one or more computer processors for executing computer program instructions; and

a non-transitory computer-readable storage medium storing instructions executable by the one or more computer processors to perform steps comprising;

calculating a first set of confidence intervals representing estimated trip durations using a real-time model;

calculating a second set of confidence intervals representing estimated trip durations using a historical model; and

determining a final confidence interval representing estimated trip durations from the first and second sets of confidence intervals based on characteristics of the trip and based on whether the first and second confidence intervals include actual trip durations.

16. The system of claim 15, further comprising:

predicting an initial set of trip durations for the trip based on a network-based estimation algorithm;

wherein the real-time model and the historical model use the predicted set of initial trip durations to generate the first set of confidence intervals and the second set of confidence intervals.

17. The system of claim 16, wherein the network-based estimation algorithm bases trip duration predictions on a graph that models a path between an origin location of the trip and a destination location of the trip as a series of weighted nodes and edges.

18. The system of claim 15, wherein upper and lower bounds of a confidence interval correspond to a quartile values.

19. The system of claim 18, wherein the quartile values are assigned weighting values according to their accuracy and used to train a model to determine the final confidence interval.

20. The system of claim 15, wherein the final confidence interval is determined based on a trained model that uses the first set of confidence intervals and the second set of confidence intervals as inputs when making a determination.