PREDICTING AND UTILIZING VARIABILITY OF TRAVEL TIMES IN MAPPING SERVICES

• US 20160202074A1
• Filed: 04/10/2015
• Published: 07/14/2016
• 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, Nogin, Galina, Koch, Paul B., Racz, David, Horvitz, Eric J., Goldszmidt, Moises
• Granted Patent: US 10,175,054 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

one or more processors; and

memory storing instructions that are executable by the one or more processors, the memory including;

an input component to receive an origin, a destination, and a start time associated with the trip;

a route generator to obtain candidate routes that run from the origin to the destination;

a prediction component to predict, based at least in part on a machine learning model that includes latent variables that are associated with the trip, a probability distribution of travel time for individual ones of the candidate routes; and

an output component to;

recommend 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 probability distribution; and

provide a measure of travel time for individual ones of the recommended one or more routes.

2. The system of claim 1, further comprising a ranker to, prior to the output component recommending the one or more routes, rank 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 latent variables included in the machine learning model comprise unobserved quantities capturing a probabilistic dependence of travel times on different segments of the trip.

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

a latent variable that captures trip-level variability of travel time as an extent to which a particular trip is faster or slower than usual on all segments that make up a 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 a route for the trip that are close to each other in the route;

or

a latent variable capturing a level of congestion on segments

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

7. The system of claim 6, wherein the range of travel times is depicted in a graphical representation on a display of the system.

8. The system of claim 1, further comprising a user interface 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.

9. 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 that includes random effects that are associated with the trip, a probability distribution of travel time for individual ones of the candidate routes;

recommending 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 probability distribution; and

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

10. The computer-implemented method of claim 9, 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.

11. The computer-implemented method of claim 9, wherein the latent variables included in the machine learning model comprise unobserved quantities capturing a probabilistic dependence of travel times on different segments of the trip.

12. The computer-implemented method of claim 9, wherein the latent variables include at least one of:

a latent variable that captures trip-level variability of travel time as an extent to which a particular trip is faster or slower than usual on all segments that make up a 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 a route for the trip that are close to each other in the route;

or

a latent variable capturing a level of congestion on segments.

13. The computer-implemented method of claim 9, wherein the measure of travel time comprises a range of travel times.

14. The computer-implemented method of claim 13, 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 via the interactive virtual tool; and

adjusting the criterion up or down based on the adjustment.

15. 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 a machine learning model using the historical trip data, the machine learning model including latent variables that are associated with the trip from an origin to a destination.

16. The computer-implemented method of claim 15, 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.

17. The computer-implemented method of claim 16, 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.

18. The computer-implemented method of claim 15, periodically re-training the machine learning model with newly received historical trip data since the training.

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

20. The computer-implemented method of claim 15, wherein the latent variables included in the machine learning model comprise unobserved quantities capturing a probabilistic dependence of travel times on different segments of the trip.