GEOSPATIAL CLUSTERING FOR SERVICE COORDINATION SYSTEMS

• US 20180232397A1
• Filed: 02/16/2017
• Published: 08/16/2018
• Est. Priority Date: 02/15/2017
• Status: Abandoned Application

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Uber Technologies, Inc.
• Inventors: Liu, Yifang, Liu, Shaosu
• Application Number:
  US15/434,929
• Publication Number:
  US 20180232397A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06F 7/08 Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry by merging two or more sets of carriers in ordered sequence G06F7/16
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

A service coordination system divides a geographic region into clusters by performing an iterative clustering process that joins locations with similar characteristics. An operational parameter is generated for each cluster, and this parameter is used throughout the cluster. This process results in the generation of clusters that cover areas that have relatively uniform characteristics. As a result, when the same operational parameter is used throughout a cluster, the parameter is appropriate for every location covered by the cluster.

Claims

1. (canceled)

5-8. -8. (canceled)

11-14. -14. (canceled)

17-18. -18. (canceled)

19. A method for identifying incentive values for areas of a service coordination system, the method comprising:

identifying a plurality of cells in a geographic region, each of the cells covering a two-dimensional geographic area within the geographic region;

identifying a plurality of service coordination metrics for each of the cells, the service coordination metrics for a cell comprising a provider sensitivity metric representing a likelihood that a service provider will provide a transportation service in the cell in return for a given incentive payment amount, the provider sensitivity metric generated based on trip data collected from a plurality of trips associated with the cell;

dividing the geographic region into a plurality of clusters, each cluster covering a two-dimensional geographic area comprising one or more cells, wherein dividing the geographic region into the plurality of clusters causes cells having similar service coordination metrics to be combined into the same cluster; and

generating an incentive value for each of the clusters, the incentive value for each cluster representing a payment offered to a service provider for providing a service in the cluster, wherein the incentive value for a cluster is generated based at least in part on a provider sensitivity metric for the cluster.

2. The method of claim 19, wherein each cell covers a geographic area of the same size.

3. The method of claim 19, wherein identifying the plurality of service coordination metrics comprises generating the plurality of service coordination metrics based on location-based data previously received at the service coordination system.

4. The method of claim 19, wherein dividing the geographic region into the plurality of clusters comprises generating a plurality of service coordination metrics for each cluster.

9. The method of claim 19, wherein dividing the geographic region into a plurality of clusters comprises:

identifying a plurality of clusters, each cluster having at least one cell and each cell of the plurality of cells belonging to one cluster;

for at least two pairs of clusters in the plurality of clusters, generating a similarity score between the pair of clusters by combining a plurality of similarity components, the plurality of similarity components comprising a provider sensitivity component representing a degree of similarity between the provider sensitivity metric of a first cluster in the pair of clusters and the provider sensitivity metric of a second cluster in the pair of clusters;

until a stop condition is satisfied, performing an iterative clustering process, each iteration of the iterative clustering process causing a pair of clusters having a similarity score representing the highest degree of similarity among the generated similarity scores to be combined to create a new cluster.

10. The method of claim 9, wherein an iteration of the iterative clustering process comprises:

selecting a pair of clusters, the selected pair of clusters having a similarity score representing the highest degree of similarity among the generated similarity scores;

combining the selected pair of clusters to create a new cluster;

generating one or more service coordination metrics for the new cluster based on the one or more service coordination metrics for the selected pair of clusters; and

generating one or more new similarity scores, each new similarity score generated between the new cluster and one other cluster, and each new similarity score generated based on the one or more service coordination metrics for the new cluster and the one or more service coordination metrics for the other cluster.

15. The method of claim 19, the service coordination metrics further comprising a provider-to-rider match probability metric representing a likelihood that a provider in the cell who provides a transportation service will be matched with a rider.

16. The method of claim 15, wherein the incentive value for a cluster is generated based at least in part on a provider-to-rider match probability metric for the cluster.

20. The method of claim 19, wherein the incentive value for a cluster is used in a process for providing a service in the cluster.