Geohash-related location predictions

• US 10,638,264 B1
• Filed: 11/19/2019
• Issued: 04/28/2020
• Est. Priority Date: 04/04/2017
• Status: Active Grant

• Current Assignee: LYFT Incorporated
• Original Assignee: LYFT Incorporated
• Inventors: Pao, Yuanyuan, Kodesh, Snir, Chopra, Jatin, Fan, Kevin, Lin, Charlie, Shen, Limin, Levi, Dor, Haque, Asif, Baz, Zeynep Erkin
• Primary Examiner(s): Patel, Mahendra R
• Application Number:
  US16/688,859
• Publication Number:
  US 20200112826A1
• Time in Patent Office: 161 Days
• Field of Search: 4554563, 455457, 4554141, 70533813
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/024 Guidance services
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 4/44 for communication between vehicles and infrastructures, e.g. vehicle-to-cloud [V2C] or vehicle-to-home [V2H]

Abstract

Embodiments provide techniques, including systems and methods, for determining an estimated target pickup location for a corresponding transport request at a particular location, such as associated with a particular geohash. A requestor may send a request that is associated with a location that does not reflect the requestor'"'"'s intent regarding where they would like to be met by the provider (i.e., “picked up”). GPS inaccuracies may cause the request location to inaccurately indicate where the requestor will be; for example, the request location may be inside a building while the requestor is waiting on a curb around a far side of the building. The target pickup location allows for a requestor and a provider to meet more efficiently, reducing delay for the provider and improving the efficiency of the system by preventing provider system resources from being taken from other service areas and decreasing provider downtime upon matching.

Claims

1. A method of managing transportation services comprising:

receiving, by a dynamic transportation matching system from a requestor device, a transportation request indicating a request location;

determining distances from the request location for a threshold number of instances of prior transport data within a geographical area corresponding to the request location;

generating, at a radius corresponding to a farthest instance of prior transport data within the threshold number of instances of prior transport data, a boundary for a sub-cluster comprising the threshold number of instances of prior transport data by;

counting, based on the distances from the request location for the threshold number of instances of prior transport data, instances of prior transport data outwardly from the request location until the threshold number of instances is met; and

determining, for the radius, a distance from the request location of the farthest instance of prior transport data within the threshold number of instances;

utilizing the sub-cluster of the prior transport data to identify a suggested location for the transportation request, wherein the suggested location is within the boundary; and

providing the suggested location to the requestor device.

2. The method of claim 1, wherein counting the instances of prior transport data comprises:

counting a closest instance of prior transport data to the request location first; and

counting a next-closest instance of prior transport data to the request location next.

3. The method of claim 1, wherein counting the instances of prior transport data comprises:

counting instances of prior transport data that correspond to prior request locations; and

disregarding instances of prior transport data that correspond to prior drop-off locations.

4. The method of claim 1, further comprising:

determining, beyond the farthest instance of prior transport data within the threshold number of instances, distances from the request location for a second threshold number of instances of prior transport data within the geographical area corresponding to the request location; and

generating, at a radius corresponding to a farthest instance of prior transport data within the second threshold number of instances of prior transport data, a second boundary for a second sub-cluster comprising the second threshold number of instances of prior transport data.

5. The method of claim 1, wherein utilizing the sub-cluster of prior transport data to identify a suggested location for the transportation request comprises:

weighting a first instance type of prior transport data more heavily than a second instance type of prior transport data; and

determining the suggested location based on the weighting of instances of prior transport data.

6. The method of claim 1, wherein utilizing the sub-cluster of prior transport data to identify a suggested location for the transportation request comprises determining an average location of prior pickup instances.

7. The method of claim 1, further comprising:

determining, for the sub-cluster of prior transport data, prior actual pickup locations corresponding to respective prior transportation request locations; and

wherein utilizing the sub-cluster of prior transport data to identify a suggested location for the transportation request comprises;

comparing the prior actual pickup locations with the respective prior transportation request locations; and

determining the suggested location for the transportation request based on the comparison.

8. A non-transitory computer readable medium comprising instructions that, when executed by at least one processor, cause a computing device to:

receive, by a dynamic transportation matching system from a requestor device, a transportation request indicating a request location;

determine distances from the request location for a threshold number of instances of prior transport data within a geographical area corresponding to the request location;

generate, at a radius corresponding to a farthest instance of prior transport data within the threshold number of instances of prior transport data, a boundary for a sub-cluster comprising the threshold number of instances of prior transport data by;

counting, based on the distances from the request location for the threshold number of instances of prior transport data, instances of prior transport data outwardly from the request location until the threshold number of instances is met; and

determining, for the radius, a distance from the request location of the farthest instance of prior transport data within the threshold number of instances;

utilize the sub-cluster of the prior transport data to identify a suggested location for the transportation request, wherein the suggested location is within the boundary; and

provide the suggested location to the requestor device.

9. The non-transitory computer readable medium of claim 8,

wherein counting the instances of prior transport data comprises:

counting a closest instance of prior transport data to the request location first; and

counting a next-closest instance of prior transport data to the request location next.

10. The non-transitory computer readable medium of claim 8, wherein counting the instances of prior transport data comprises:

counting instances of prior transport data that correspond to prior request locations; and

disregarding instances of prior transport data that correspond to prior drop-off locations.

11. The non-transitory computer readable medium of claim 8, further comprising instructions that, when executed by the at least one processor, cause the computing device to:

determine, beyond the farthest instance of prior transport data within the threshold number of instances, distances from the request location for a second threshold number of instances of prior transport data within the geographical area corresponding to the request location; and

generate, at a radius corresponding to a farthest instance of prior transport data within the second threshold number of instances of prior transport data, a second boundary for a second sub-cluster comprising the second threshold number of instances of prior transport data.

12. The non-transitory computer readable medium of claim 8, wherein the instructions cause the computing device to utilize the sub-cluster of prior transport data to identify a suggested location for the transportation request by:

weighting a first instance type of prior transport data more heavily than a second instance type of prior transport data; and

determining the suggested location based on the weighting of instances of prior transport data.

13. The non-transitory computer readable medium of claim 8, wherein the instructions cause the computing device to utilize the sub-cluster of prior transport data to identify a suggested location for the transportation request by determining an average location of prior pickup instances.

14. The non-transitory computer readable medium of claim 8, further comprising instructions that, when executed by the at least one processor, cause the computing device to:

determine, for the sub-cluster of prior transport data, prior actual pickup locations corresponding to respective prior transportation request locations; and

wherein the instructions cause the computing device to utilize the sub-cluster of prior transport data to identify a suggested location for the transportation request by;

comparing the prior actual pickup locations with the respective prior transportation request locations; and

determining the suggested location for the transportation request based on the comparison.

15. A system comprising:

at least one processor; and

a non-transitory computer readable medium comprising instructions that, when executed by the at least one processor, cause the system to;

receive, by a dynamic transportation matching system from a requestor device, a transportation request indicating a request location;

determine distances from the request location for a threshold number of instances of prior transport data within a geographical area corresponding to the request location;

generate, at a radius corresponding to a farthest instance of prior transport data within the threshold number of instances of prior transport data, a boundary for a sub-cluster comprising the threshold number of instances of prior transport data by;

counting, based on the distances from the request location for the threshold number of instances of prior transport data, instances of prior transport data outwardly from the request location until the threshold number of instances is met; and

determining, for the radius, a distance from the request location of the farthest instance of prior transport data within the threshold number of instances;

utilize the sub-cluster of the prior transport data to identify a suggested location for the transportation request, wherein the suggested location is within the boundary; and

provide the suggested location to the requestor device.

16. The system of claim 15, wherein counting the instances of prior transport data comprises:

counting a closest instance of prior transport data to the request location first; and

counting a next-closest instance of prior transport data to the request location next.

17. The system of claim 15, wherein counting the instances of prior transport data comprises:

counting instances of prior transport data that correspond to prior request locations; and

disregarding instances of prior transport data that correspond to prior drop-off locations.

18. The system of claim 15, further comprising instructions that, when executed by the at least one processor, cause the system to:

determine, beyond the farthest instance of prior transport data within the threshold number of instances, distances from the request location for a second threshold number of instances of prior transport data within the geographical area corresponding to the request location; and

generate, at a radius corresponding to a farthest instance of prior transport data within the second threshold number of instances of prior transport data, a second boundary for a second sub-cluster comprising the second threshold number of instances of prior transport data.

19. The system of claim 15, wherein the instructions cause the system to utilize the sub-cluster of prior transport data to identify a suggested location for the transportation request by:

weighting a first instance type of prior transport data more heavily than a second instance type of prior transport data; and

determining the suggested location based on the weighting of instances of prior transport data.

20. The system of claim 15, wherein the instructions cause the system to utilize the sub-cluster of prior transport data to identify a suggested location for the transportation request by determining an average location of prior pickup instances.