Predicting and utilizing variability of travel times in mapping services

Patent metadata

Field	Value
Publication number	US-2016202074-A1
Application number	US-201514684108-A
Country	US
Kind code	A1
Filing date	Apr 10, 2015
Priority date	Jan 11, 2015
Publication date	Jul 14, 2016
Grant date	—

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.

First claim

What is claimed is:

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.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Woodard Dawn
• Horvitz Eric J
• Nogin Galina
• Koch Paul B
• Racz David
• Goldszmidt Moises

Classifications

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G01C21/34 Primary

  Route searching; Route guidance · CPC title