Adaptive regionalization for transit characteristic prediction

• US 8,504,485 B1
• Filed: 03/04/2010
• Issued: 08/06/2013
• Est. Priority Date: 03/04/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Wenneman, M. Christopher, Pew, Benjamin Elliott, Bezanson, Llewellyn W., Lakshman, Girish S., Baji, Saurabh D.
• Primary Examiner(s): Hayes, John
• Assistant Examiner(s): Jung, Allen J
• Application Number:
  US12/717,791
• Time in Patent Office: 1,251 Days
• Field of Search: 705/338
• US Class Current: 705/338
• CPC Class Codes: G06Q 10/083 Shipping

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.

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.

2. The method of claim 1, wherein said splitting and said expanding is performed in a recursive manner for each of the first plurality of regions, the corresponding additional regions, and the corresponding new regions, and wherein said evaluating is performed for each set of possible regions for the region.

3. The method of claim 1, further comprising:

dynamically performing said determining, said performing splitting and expanding, said evaluating, and said selecting dependent upon collecting empirical transit data.

4. The method of claim 1, wherein said expanding is performed upon determining that the new region has a better fitness score than at least one of the plurality of regions.

5. The method of claim 1, wherein said splitting is performed upon determining that each of the additional regions includes a minimum threshold of values of transit characteristics.

6. The method of claim 1, wherein the one or more transit characteristics comprise transit time from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit times from the source location to the plurality of destination locations.

7. The method of claim 1, wherein the one or more transit characteristics comprise transit variability from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit variabilities from the source location to the plurality of destination locations.

8. The method of claim 1, wherein said determining, said dividing, said performing, and said evaluating are performed a plurality of times for respective different shipping methods from the source location.

9. The method of claim 1, further comprising:

providing the selected set of regions and regional values of the transit characteristic of the selected set of regions for display.

10. The method of claim 9, further comprising:

receiving input selecting a region from the selected set of regions;

providing the respective values of transit characteristics for the selected region;

receiving input modifying a first value of the respective values of transit characteristics for the selected region; and

modifying the first value based on the received input.

11. The method of claim 1, wherein the plurality of regions comprise polygons greater than 4 sides.

12. The method of claim 11, wherein the polygons are based on postal codes.

13. The method of claim 1, wherein weights are associated with transit characteristics, wherein said evaluating each set of possible regions using the fitness function utilizes the weights associated with the transit characteristics.

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.

15. The non-transitory memory medium of claim 14, wherein said splitting and said expanding is performed in a recursive manner for each of the first plurality of regions, the corresponding additional regions, and the corresponding new regions, and wherein said evaluating is performed for each set of possible regions for the region.

16. The non-transitory memory medium of claim 14, wherein the program instructions are further executable to:

dynamically perform said determining, said performing splitting and expanding, said evaluating, and said selecting dependent upon collecting empirical transit data.

17. The non-transitory memory medium of claim 14, wherein said expanding is performed upon determining that the new region has a better fitness score than at least one of the plurality of regions.

18. The non-transitory memory medium of claim 14, wherein said splitting is performed upon determining that each of the additional regions includes a minimum threshold of values of transit characteristics.

19. The non-transitory memory medium of claim 14, wherein the one or more transit characteristics comprise transit time from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit times from the source location to the plurality of destination locations.

20. The non-transitory memory medium of claim 14, wherein the one or more transit characteristics comprise transit variability from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit variabilities from the source location to the plurality of destination locations.

21. The non-transitory memory medium of claim 14, wherein said determining, said dividing, said performing, and said evaluating are performed a plurality of times for respective different shipping methods from the source location.

22. The non-transitory memory medium of claim 14, wherein the program instructions are further executable to:

provide the selected set of regions and regional values of the transit characteristic of the selected set of regions for display.

23. The non-transitory memory medium of claim 22, wherein the program instructions are further executable to:

receive input selecting a region from the selected set of regions;

provide the respective values of transit characteristics for the selected region;

receive input modifying a first value of the respective values of transit characteristics for the selected region; and

modify the first value based on the received input.

24. The non-transitory memory medium of claim 14, wherein the plurality of regions comprise polygons greater than 4 sides.

25. The non-transitory memory medium of claim 14, wherein weights are associated with transit characteristics, wherein said evaluating each set of possible regions using the fitness function utilizes the weights associated with the transit characteristics.

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.

27. The system of claim 26, wherein said splitting and said expanding is performed in a recursive manner for each of the first plurality of regions, the corresponding additional regions, and the corresponding new regions, and wherein said evaluating is performed for each set of possible regions for the region.

28. The system of claim 26, wherein the program instructions are further executable to:

dynamically perform said determining, said performing splitting and expanding, said evaluating, and said selecting dependent upon collecting empirical transit data.

29. The system of claim 26, wherein said expanding is performed upon determining that the new region has a better fitness score than at least one of the plurality of regions.

30. The system of claim 26, wherein said splitting is performed upon determining that each of the additional regions includes a minimum threshold of values of transit characteristics.

31. The system of claim 26, wherein the one or more transit characteristics comprise transit time from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit times from the source location to the plurality of destination locations.

32. The system of claim 26, wherein the one or more transit characteristics comprise transit variability from the source location to the plurality of destination locations, and wherein the respective values of transit characteristics comprise transit variabilities from the source location to the plurality of destination locations.

33. The system of claim 26, wherein said determining, said dividing, said performing, and said evaluating are performed a plurality of times for respective different shipping methods from the source location.

34. The system of claim 26, wherein the program instructions are further executable to:

provide the selected set of regions and regional values of the transit characteristic of the selected set of regions for display.

35. The system of claim 34, wherein the program instructions are further executable to:

receive input selecting a region from the selected set of regions;

provide the respective values of transit characteristics for the selected region;

receive input modifying a first value of the respective values of transit characteristics for the selected region; and

modify the first value based on the received input.

36. The system of claim 26, wherein the plurality of regions comprise polygons greater than 4 sides.

37. The system of claim 26, wherein weights are associated with transit characteristics, wherein said evaluating each set of possible regions using the fitness function utilizes the weights associated with the transit characteristics.