Determining adjusted trip duration using route features

• US 10,429,200 B1
• Filed: 05/15/2017
• Issued: 10/01/2019
• Est. Priority Date: 05/15/2017
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Parameswaran, Vasudev, Kadous, Mohammed Waleed
• Primary Examiner(s): Badii, Behrang
• Assistant Examiner(s): Testardi, David A
• Application Number:
  US15/595,852
• Time in Patent Office: 869 Days
• 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: G01C 21/3658 Lane guidance
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0137 for specific applications
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

A system adjusts an estimated travel time from an origin to a destination to better predict an actual trip duration. The system receives a route from a specified origin and destination. The system receives an estimated trip duration corresponding to the generated route. A machine learned model improves the estimated trip duration by applying data about past trips facilitated by the system and data about traffic-control features associated with a route. For example, the system may use counts of a number of road signs and a number of traffic signals located along the generated route to predict an actual trip duration. In some cases, the system may additionally use data about synchronized traffic lights to predict actual trip duration.

Claims

1. A computer-implemented method, comprising:

storing information about geofence cells that subdivide a geographical region, each geofence cell being stored with an indication of traffic-control features located within the geofence cell;

receiving a route from an origin to a destination, the route passing through the geographical region;

receiving an estimated trip duration corresponding to the route;

selecting, from the geofence cells that subdivide the geographical region, a set of geofence cells through which the route passes;

determining, using the stored information about geofence cells that subdivide the geographical region, a set of traffic-control features that are located within the selected set of geofence cells through which the route passes;

predicting an adjusted trip duration by applying a machine learned model to the determined set of traffic-control features and the estimated trip duration; and

transmitting the adjusted trip duration to a user device.

2. The computer-implemented method of claim 1, wherein the estimated trip duration is determined by a model that traverses a graph and accumulates weights for road segments corresponding to the route.

3. The computer-implemented method of claim 1, wherein the determined set of traffic-control features includes at least one of:

a count of a number of road signs located within the geofence cells included in the selected set of geofence cells and a count of a number of traffic signals located within the geofence cells included in the selected set of geofence cells.

4. The computer-implemented method of claim 1, wherein determining a set of traffic-control features that are located within the selected set of geofence cells through which the route passes further comprises:

determining values associated with traffic-control features located within one or more geofence cells through which the route passes; and

determining additional values associated with additional traffic-control features located within one or more geofence cells through which the route does not pass, the additional values being affected by weighting coefficients based on a distance of the geofence containing the additional traffic-control features from a geofence through which the route passes.

5. The computer-implemented method of claim 1, wherein determining a set of traffic-control features that are located within the selected set of geofence cells through which the route passes comprises:

determining sequences of synchronized traffic signals along the route, wherein a sequence of synchronized traffic signals includes two or more synchronized traffic signals located at successive intersections on a road along the route; and

for each sequence of synchronized traffic signals;

calculating a weighted sum of the number of traffic signals in the sequence, wherein each subsequent traffic signal in the sequence of synchronized traffic signals has a smaller weighting coefficient than the previous traffic signal in the sequence of synchronized traffic signals.

6. The computer-implemented method of claim 1, wherein an adjusted trip duration is predicted responsive to the route including road segments that are known to have heavy traffic.

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

storing information about geofence cells that subdivide a geographical region, each geofence cell being stored with an indication of traffic-control features located within the geofence cell;

receiving a route from an origin to a destination, the route passing through the geographical region;

receiving an estimated trip duration corresponding to the route;

selecting, from the geofence cells that subdivide the geographical region, a set of geofence cells through which the route passes;

determining, using the stored information about geofence cells that subdivide the geographical region, a set of traffic-control features that are located within the selected set of geofence cells through which the route passes;

predicting an adjusted trip duration by applying a machine learned model to the determined set of traffic-control features and the estimated trip duration; and

transmitting the adjusted trip duration to a user device.

8. The non-transitory computer-readable storage medium of claim 7, wherein the estimated trip duration is determined by a model that traverses a graph and accumulates weights for road segments corresponding to the route.

9. The non-transitory computer-readable storage medium of claim 7, wherein the determined set of traffic-control features includes at least one of:

a count of a number of road signs located within the geofence cells included in the selected set of geofence cells and a count of a number of traffic signals located within the geofence cells included in the selected set of geofence cells.

10. The non-transitory computer-readable storage medium of claim 7, wherein determining a set of traffic-control features that are located within the selected set of geofence cells through which the route passes further comprises:

determining values associated with traffic-control features located within one or more geofence cells through which the route passes; and

determining additional values associated with additional traffic-control features located within one or more geofence cells through which the route does not pass, the additional values being affected by weighting coefficients based on a distance of the geofence containing the additional traffic-control features from a geofence through which the route passes.

11. The non-transitory computer-readable storage medium of claim 7, wherein determining a set of traffic-control features that are located within the selected set of geofence cells through which the route passes comprises:

determining sequences of synchronized traffic signals along the route, wherein a sequence of synchronized traffic signals includes two or more synchronized traffic signals located at successive intersections on a road along the route; and

for each sequence of synchronized traffic signals;

calculating a weighted sum of the number of traffic signals in the sequence, wherein each subsequent traffic signal in the sequence of synchronized traffic signals has a smaller weighting coefficient than the previous traffic signal in the sequence of synchronized traffic signals.

12. The non-transitory computer-readable storage medium of claim 7, wherein an adjusted trip duration is predicted responsive to the route including road segments that are known to have heavy traffic.

13. 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;

storing information about geofence cells that subdivide a geographical region, each geofence cell being stored with an indication of traffic-control features located within the geofence cell;

receiving a route from an origin to a destination, the route passing through the geographical region;

receiving an estimated trip duration corresponding to the route;

selecting, from the geofence cells that subdivide the geographical region, a set of geofence cells through which the route passes;

determining, using the stored information about geofence cells that subdivide the geographical region, a set of traffic-control features that are located within the selected set of geofence cells through which the route passes;

predicting an adjusted trip duration by applying a machine learned model to the determined set of traffic-control features and the estimated trip duration; and

transmitting the adjusted trip duration to a user device.

14. The computer system of claim 13, wherein the estimated trip duration is determined by a model that traverses a graph and accumulates weights for road segments corresponding to the route.

15. The computer system of claim 13, wherein the determined set of traffic-control features includes at least one of:

a count of a number of road signs located within the geofence cells included in the selected set of geofence cells and a count of a number of traffic signals located within the geofence cells included in the selected set of geofence cells.

16. The computer system of claim 13, wherein determining a set of traffic-control features that are located within the selected set of geofence cells through which the route passes further comprises:

determining values associated with traffic-control features located within one or more geofence cells through which the route passes; and

determining additional values associated with additional traffic-control features located within one or more geofence cells through which the route does not pass, the additional values being affected by weighting coefficients based on a distance of the geofence containing the additional traffic-control features from a geofence through which the route passes.

17. The computer system of claim 13, wherein determining a set of traffic-control features that are located within the selected set if geofence cells through which the route passes comprises:

determining sequences of synchronized traffic signals along the route, wherein a sequence of synchronized traffic signals includes two or more synchronized traffic signals located at successive intersections on a road along the route; and

for each sequence of synchronized traffic signals;

calculating a weighted sum of the number of traffic signals in the sequence, wherein each subsequent traffic signal in the sequence of synchronized traffic signals has a smaller weighting coefficient than the previous traffic signal in the sequence of synchronized traffic signals.