Adaptive regionalization for transit characteristic prediction
First Claim
1. A method, comprising:
- performing by one or more computers;
determining respective values of transit characteristics from a source location to a plurality of destination locations, wherein the plurality of destination locations define a macro region;
dividing the macro region into a first plurality of regions;
performing splitting of one or more regions of the first plurality of regions to create additional regions and expanding at least one of the first plurality of regions to form a new region, wherein said splitting and expanding is performed a plurality of times to generate a plurality of possible sets of regions, wherein each set of the plurality of possible sets comprises a different plurality of divisions of regions of the macro region;
evaluating each set of possible regions using a fitness function, wherein said evaluating comprises applying the fitness function to each region of the set of possible regions to produce a fitness score, wherein the fitness function takes the respective values of transit characteristics for each region as input;
selecting a set of regions for the macro area based on said evaluating, wherein the selected set of regions has a best fitness score based on the evaluation of the sets of possible regions; and
determining a regional value of a transit characteristic for at least one region of the selected set of regions, wherein the regional value provides a common transit characteristic value for each of multiple destinations within the respective region.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and system for transit characteristic prediction. In one embodiment, a method may include determining respective transit latencies from a source location to a number of destination locations, and grouping the destination locations according to a fitness function into a number of subsets corresponding to respective geographical regions. The grouping may involve a series of divisions and combinations of potential regions to form a plurality of sets of potential regions. Each set of potential regions may be evaluated using the fitness function, and the set with the better fitness score may be selected. The method may also include dynamically updating the respective transit characteristic, regrouping the regions, and reselecting a set of potential regions based on empirical transit data.
-
Citations
37 Claims
-
1. A method, comprising:
performing by one or more computers; determining respective values of transit characteristics from a source location to a plurality of destination locations, wherein the plurality of destination locations define a macro region; dividing the macro region into a first plurality of regions; performing splitting of one or more regions of the first plurality of regions to create additional regions and expanding at least one of the first plurality of regions to form a new region, wherein said splitting and expanding is performed a plurality of times to generate a plurality of possible sets of regions, wherein each set of the plurality of possible sets comprises a different plurality of divisions of regions of the macro region; evaluating each set of possible regions using a fitness function, wherein said evaluating comprises applying the fitness function to each region of the set of possible regions to produce a fitness score, wherein the fitness function takes the respective values of transit characteristics for each region as input; selecting a set of regions for the macro area based on said evaluating, wherein the selected set of regions has a best fitness score based on the evaluation of the sets of possible regions; and determining a regional value of a transit characteristic for at least one region of the selected set of regions, wherein the regional value provides a common transit characteristic value for each of multiple destinations within the respective region. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
14. A non-transitory computer-accessible memory medium comprising program instructions, wherein the program instructions are executable to:
-
determine respective values of transit characteristics from a source location to a plurality of destination locations, wherein the plurality of destination locations define a macro region; divide the macro region into a first plurality of regions; perform splitting of one or more regions of the first plurality of regions to create additional regions and expanding at least one of the first plurality of regions to form a new region, wherein said splitting and expanding is performed a plurality of times to generate a plurality of possible sets of regions, wherein each set of the plurality of possible sets comprises a different plurality of divisions of regions of the macro region; evaluate each set of possible regions using a fitness function, wherein said evaluating comprises applying the fitness function to each region of the set of possible regions to produce a fitness score, wherein the fitness function takes the respective values of transit characteristics for each region as input; select a set of regions for the macro area based on said evaluating, wherein the selected set of regions has a best fitness score based on the evaluation of the sets of possible regions; and determine a regional value of a transit characteristic for at least one region of the selected set of regions, wherein the regional value provides a common transit characteristic value for each of multiple destinations within the respective region. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. A system, comprising:
-
one or more processors; and one or more memory mediums coupled to the one or more processors, wherein the one or more memory mediums comprise program instructions, wherein the program instructions are executable by the one or more processors to; determine respective values of transit characteristics from a source location to a plurality of destination locations, wherein the plurality of destination locations define a macro region; divide the macro region into a first plurality of regions; perform splitting of one or more regions of the first plurality of regions to create additional regions and expanding at least one of the first plurality of regions to form a new region, wherein said splitting and expanding is performed a plurality of times to generate a plurality of possible sets of regions, wherein each set of the plurality of possible sets comprises a different plurality of divisions of regions of the macro region; evaluate each set of possible regions using a fitness function, wherein said evaluating comprises applying the fitness function to each region of the set of possible regions to produce a fitness score, wherein the fitness function takes the respective values of transit characteristics for each region as input; select a set of regions for the macro area based on said evaluating, wherein the selected set of regions has a best fitness score based on the evaluation of the sets of possible regions; and determine a regional value of a transit characteristic for at least one region of the selected set of regions, wherein the regional value provides a common transit characteristic value for each of multiple destinations within the respective region. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37)
-
Specification