Predicting and utilizing variability of travel times in mapping services

• US 10,175,054 B2
• Filed: 04/10/2015
• Issued: 01/08/2019
• Est. Priority Date: 01/11/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Woodard, Dawn, Horvitz, Eric J., Nogin, Galina, Koch, Paul B., Racz, David, Goldszmidt, Moises
• Primary Examiner(s): Cass, Jean Paul
• Application Number:
  US14/684,108
• Publication Number:
  US 20160202074A1
• Time in Patent Office: 1,369 Days
• Field of Search: None
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A system for predicting variability of travel time for a trip at a particular time may utilize a machine learning model including latent variables that are associated with the trip. The machine learning model may be trained from historical trip data that is based on location-based measurements reported from mobile devices. Once trained, the machine learning model may be utilized for predicting variability of travel time. A process may include receiving an origin, a destination, and a start time associated with a trip, obtaining candidate routes that run from the origin to the destination, and predicting, based at least in part on the machine learning model, a probability distribution of travel time for individual ones of the candidate routes. One or more routes may be recommended based on the predicted probability distribution, and a measure of travel time for the recommended route(s) may be provided.

Claims

1. A system for predicting variability of travel time for a trip and utilizing the predicted variability for route planning, the system comprising:

a display;

one or more processors; and

memory storing instructions that when executed by the one or more processors, cause the one or more processors to perform a method comprising;

receiving an origin, a destination, and a start time associated with the trip;

receiving candidate routes that run from the origin to the destination, each candidate route comprising a plurality of individual route segments;

generating, using a machine learning model, a variability in a measure of travel time for each candidate route, wherein the machine learning model;

captures a variability in a travel time of each individual route segment within the candidate route;

captures a variability in a travel time of the candidate route; and

captures interdependencies of travel times on sequential individual route segments within the candidate route, the interdependencies comprising one or more latent variables that capture relationships of the travel times on the individual route segments;

selecting at least one route from the candidate routes based on a criterion that is based at least in part on each variability in the measure of travel time; and

causing, on the display, a presentation of a user interface configured to;

graphically display the selected at least one route; and

graphically display a measure of travel time for the selected at least one route.

2. The system of claim 1, the method further comprising prior to graphically displaying the selected at least one route, ranking the candidate routes according to routes that minimize the criterion.

3. The system of claim 1, wherein the criterion comprises at least one of a percentile of travel time or a probability that arrival at the destination will occur before a specified time.

4. The system of claim 1, wherein the one or more latent variables included in the machine learning model comprise one or more latent variables that capture unobserved quantities capturing for each candidate route a probabilistic dependence of a first travel time of a first segment of the candidate route on a second travel time of a second segment of the candidate route.

5. The system of claim 1, wherein the one or more latent variables include at least one of:

a latent variable that captures trip-level variability of travel time as an extent to which travel speed is faster or slower than usual on all segments that make up a candidate route of the candidate routes for the trip;

a latent variable that captures segment-level variability of travel time as a tendency for travel speeds to be similar for segments of the candidate route that are close to each other in the candidate route;

or

a latent variable capturing a level of congestion on the segments that make up the candidate route.

6. The system of claim 1, wherein the measure of travel time comprises a range of travel times.

7. The system of claim 1, the user interface being further configured to provide an interactive virtual tool for adjusting a level of risk aversion for a user that, upon adjustment of the level of risk, causes adjustment of the criterion.

8. A computer-implemented method comprising:

receiving an origin, a destination, and a start time associated with a trip;

obtaining candidate routes that run from the origin to the destination;

predicting, based at least in part on a machine learning model, a variability in a measure of travel time for each candidate route, wherein the machine learning model;

captures a variability in a travel time of each individual route segment within the candidate route;

captures a variability in a travel time of the candidate route;

captures interdependencies of travel times on sequential individual route segments within the candidate route, the interdependencies comprising one or more latent variables that capture relationships of the travel times on the individual route segments; and

captures an effect of contextual data on a travel time of the candidate route, the contextual data comprising one or more of a time of a day, a day of a week, weather information, or traffic information;

providing a recommendation of one or more routes from the candidate routes based at least in part on the variabilities in the measure of travel times; and

providing a measure of travel time for the recommended one or more routes.

9. The computer-implemented method of claim 8, wherein providing the recommendation of one or more routes from the candidate routes based at least in part on the variabilities in the measure of travel times comprises providing the recommendation of one or more routes from the candidate routes based at least in part on a criterion that is based at least in part on the variabilities in the measure of travel times, the criterion comprising at least one of a percentile of travel time or a probability that arrival at the destination will occur before a specified time.

10. The computer-implemented method of claim 8, wherein the one or more latent variables comprise latent variables that capture unobserved quantities capturing, for each candidate route of the candidate routes, a probabilistic dependence of a first travel time of a first segment of the candidate route on a second travel time of a second segment of the candidate route.

11. The computer-implemented method of claim 8, wherein the one or more latent variables comprise at least one of:

a latent variable that captures trip-level variability of travel time as an extent to which travel speed is faster or slower than usual on all segments that make up a candidate route for the trip;

a latent variable that captures segment-level variability of travel time as a tendency for travel speeds to be similar for segments of the candidate route that are close to each other in the candidate route;

or

a effect latent variable capturing a level of congestion on the segments that make up the candidate route.

12. The computer-implemented method of claim 8, wherein the variability in the measure of travel time comprises a range of travel times having an upper bound travel time and a lower bound travel time.

13. The computer-implemented method of claim 9, further comprising:

providing, via a user interface, an interactive virtual tool for adjusting a level of risk aversion for a user;

receiving an adjustment of the level of risk aversion via the interactive virtual tool; and

adjusting the criterion up or down based on the adjustment.

20. The computer-implemented method of claim 8, wherein the user interface is further configured to provide an interactive virtual tool for adjusting a level of risk aversion for a user that, upon adjustment of the level of risk, causes adjustment of the criterion.

14. A computer-implemented method of training a machine learning model to be used for predicting a probability distribution of travel time for a trip, the method comprising:

receiving historical trip data that is based at least in part on location-based measurements reported from mobile devices, individual ones of the location-based measurements including at least location data and time data; and

training, using the historical trip data, a machine learning model to generate probability distributions of travel times for one or more candidate routes, wherein the training of the machine learning model comprises;

capturing a variability in a travel time of each individual route segment within the candidate route;

capturing a variability in a travel time of the candidate route;

capturing interdependencies of travel times on sequential individual route segments within the candidate route, the interdependencies comprising one or more latent variables that capture relationships of the travel times on the individual route segments; and

capturing an effect of contextual data on a travel time of the candidate route, the contextual data comprising one or more of a time of a day, a day of a week, weather information, or traffic information.

15. The computer-implemented method of claim 14, further comprising testing a performance of the machine learning model in predicting the probability distribution of travel time by applying the machine learning model to a portion of the historical trip data that was not used to train the machine learning model.

16. The computer-implemented method of claim 15, wherein the performance of the machine learning model is measured by at least one of:

a measure of accuracy of a 95% interval prediction of travel time;

or

a measure of accuracy of a point prediction of travel time.

17. The computer-implemented method of claim 14, further comprising periodically retraining the machine learning model with newly received historical trip data since the training.

18. The computer-implemented method of claim 17, wherein the retraining occurs upon receipt of a threshold amount of the newly received historical trip data.

19. The computer-implemented method of claim 14, wherein the one or more latent variables comprise one or more latent variables that capture unobserved quantities capturing, for each candidate route that runs from the origin to the destination, a probabilistic dependence of a first travel time of a first segment of the candidate route on a second travel time of a second segment of the candidate route.