Selecting a route to a destination based on zones

• US 9,778,057 B2
• Filed: 02/08/2016
• Issued: 10/03/2017
• Est. Priority Date: 02/08/2016
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: O'Mahony, Eoin, Nickels, John Mark, Goldman, Brent, Holden, Jeff
• Primary Examiner(s): Kan, Yuri
• Application Number:
  US15/018,042
• Publication Number:
  US 20170227371A1
• Time in Patent Office: 603 Days
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/09685 where the complete route is computed only once and not updated
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

Abstract

A travel coordination system provides suggestions to providers for where they should go to reduce the wait time between trips. A geographic region is broken down into zones and a score is generated for each zone. A zone score can be generated by determining the estimated wait time for the zone and generating a model for the wait time. A zone score can also be generated using a model for the wait time using factors that likely contribute to the wait time. The zone score for each zone is displayed to the provider on a road map of the geographic region along with the boundaries of each of the zones and the provider'"'"'s position within the region. The travel coordination system also suggests driving routes. The travel coordination system selects a target zone and generates candidate routes to the zone. A route is selected based on route scores.

Claims

1. A method comprising:

receiving, at a travel coordination system from a provider device, a current location of a provider that is available to transport a rider, the provider operating the provider device in communication with the travel coordination system;

identifying, by the travel coordination system, a destination for the provider;

determining, by the travel coordination system, a set of candidate routes from the current location of the provider to the destination;

generating, by the travel coordination system for each candidate route in the set of candidate routes, a route score, wherein generating a route score for a candidate route comprises;

identifying a set of zones through which the candidate route passes,

determining an estimated wait time at an arrival time at each zone in the set of zones for the provider by traveling along the candidate route, an estimated wait time for a zone being an estimated amount of time the provider is expected to wait in the zone before receiving an assignment request to transport a rider in the zone, and

generating a route score for the candidate route based on the estimated wait times for the set of zones;

selecting, by the travel coordination system, a route from the set of candidate routes based on a route score corresponding to the selected route; and

transmitting, by the travel coordination system, data of the selected route to the provider device.

2. The method of claim 1, wherein the destination is selected by the travel coordination system as a suggested destination to reduce a wait time of the provider for an assignment request.

3. The method of claim 1, wherein the destination is selected by the provider.

4. The method of claim 1, wherein a route score for a candidate route is based on an arrival time to the destination by traveling along the candidate route.

5. The method of claim 1, wherein generating a route score for a candidate route further comprises:

determining, by the travel coordination system, a first arrival time for the provider at the destination by traveling along the candidate route;

determining, by the travel coordination system, a second arrival time for the provider at the destination by traveling along a second candidate route in the set of candidate routes;

estimating, by the travel coordination system, for a destination zone containing the destination, a wait time for the provider in the destination zone at the first arrival time; and

generating, by the travel coordination system, a route score the candidate route based on (1) a difference between the first arrival time and the second arrival time, and (2) the estimated wait time.

6. The method of claim 1, wherein the estimated wait time for a zone is determined based on a provider supply model and a provider demand model for the zone, the provider supply model estimating a quantity of providers in the zone that are available to transport a rider, and the provider demand model estimating a quantity of riders in the zone.

7. The method of claim 1, wherein the route score is generated based on amounts of time the provider would spend in the zones through which the candidate route passes by traveling along the candidate route.

8. The method of claim 7, wherein a weighted average of zone scores of the zones through which the candidate route passes is used to generate the route score.

9. The method of claim 7, wherein an integral of zone scores of the zones through which the candidate route passes is used to generate the route score.

10. The method of claim 1, further comprising:

causing, by the travel coordination system, the provider device to display a user interface of the selected route as a suggestion to reduce a wait time to receiving an assignment request.

11. The method of claim 1, wherein the provider is an autonomous vehicle, and further comprises:

transmitting instructions to the provider device instructing the provider to travel along the selected route.

12. A non-transitory computer-readable storage medium storing computer program instructions to perform steps comprising:

receiving, at a travel coordination system from a provider device, a current location of a provider that is available to transport a rider, the provider operating the provider device in communication with the travel coordination system;

identifying, by the travel coordination system, a destination for the provider;

determining, by the travel coordination system, a set of candidate routes from the current location of the provider to the destination;

generating, by the travel coordination system for each candidate route in the set of candidate routes, a route score, wherein generating a route score for a candidate route comprises;

identifying a set of zones through which the candidate route passes,

determining an estimated wait time at an arrival time at each zone in the set of zones for the provider by traveling along the candidate route, an estimated wait time for a zone being an estimated amount of time the provider is expected to wait in the zone before receiving an assignment request to transport a rider in the zone, and

generating a route score for the candidate route based on the estimated wait times for the set of zones;

selecting, by the travel coordination system, a route from the set of candidate routes based on a route score corresponding to the selected route; and

transmitting, by the travel coordination system, data of the selected route to the provider device.

13. The computer-readable storage medium of claim 12, wherein the destination is selected by the travel coordination system as a suggested destination to reduce a wait time of the provider for an assignment request.

14. The computer-readable storage medium of claim 12, wherein the destination is selected by the provider.

15. The computer-readable storage medium of claim 12, wherein a route score for a candidate route is based on an arrival time to the destination by traveling along the candidate route.

16. The computer-readable storage medium of claim 12, wherein

generating, by the travel coordination system, a route score for a candidate route further comprises:

determining, by the travel coordination system, a first arrival time for the provider at the destination by traveling along the candidate route;

determining, by the travel coordination system, a second arrival time for the provider at the destination by traveling along a second candidate route in the set of candidate routes;

estimating, by the travel coordination system for a zone containing the destination, a wait time for the provider in the zone containing the destination at first arrival time;

generating, by the travel coordination system, a route score the candidate route based on (1) a difference between the first arrival time and the second arrival time, and (2) the estimated wait time.

17. The computer-readable storage medium of claim 12, wherein the estimated wait time for a zone is determined based on a provider supply model and a provider demand model for the zone, the provider supply model estimating a quantity of providers in the zone that are available to transport a rider, and the provider demand model estimating a quantity of riders in the zone.

18. The computer-readable storage medium of claim 12, wherein the route score is generated based on amounts of time the provider would spend in the zones through which the candidate route passes by traveling along the candidate route.

19. The computer-readable storage medium of claim 12, wherein further comprising:

causing, by the travel coordination system, the provider device to display a user interface of the selected route as a suggestion to reduce a wait time to receiving an assignment request.

20. The computer-readable storage medium of claim 12, the provider is an autonomous vehicle, and further comprises:

instructing the provider to travel along the selected route.