Method and system for transit characteristic prediction

• US 9,959,519 B2
• Filed: 03/30/2005
• Issued: 05/01/2018
• Est. Priority Date: 03/30/2005
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lakshman, Girish S., Bezanson, Llewellyn W., Desai, Pradeep
• Primary Examiner(s): GILKEY, CARRIE STRODER
• Application Number:
  US11/094,505
• Publication Number:
  US 20060224398A1
• Time in Patent Office: 4,780 Days
• Field of Search: 705 1, 705 11, 705330-341
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/0833 Tracking
• CPC Class Codes: G06Q 10/08345 Pricing

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 similarity criterion into a number of subsets corresponding to respective geographical regions, where transit characteristics of locations grouped into a geographical region may each satisfy the similarity criterion. The method may further include determining a respective distribution associated with each of the geographical regions, where a given respective distribution correlates a given transit characteristic from the source location to a given geographical region with a respective surety factor, where the respective surety factor includes a cumulative probability that the given transit characteristic will be achieved. The method may also include dynamically updating the respective transit characteristic, the grouping of destination locations into geographical regions and the respective distributions dependent upon collecting empirical transit data.

Claims

1. A computer-implemented method, comprising:

performing by one or more computers, each comprising at least a processor and a memory;

collecting empirical transit data for a plurality of previously-shipped shipments of material;

from said empirical transit data, determining respective transit characteristics from a source location to a plurality of destination locations, wherein each of said respective transit characteristics indicates an empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations;

grouping said plurality of destination locations according to a similarity criterion into a plurality of subsets corresponding to respective geographical regions, wherein respective transit characteristics of destination locations grouped into a given respective geographical region each satisfy said similarity criterion, and wherein each of the geographical regions is geographically defined by a respective set of dimensions, such that said grouping of destination locations into subsets occurs dependent upon the empirical transit data;

storing, in a tree data structure to improve runtime performance of the one or more computers, representations of the subsets corresponding to geographical regions as mappings of the plurality of destination locations;

determining a respective distribution associated with each of said geographical regions, wherein a given respective distribution correlates a given transit characteristic from said source location to a given geographical region with a respective surety factor, wherein said respective surety factor includes a cumulative probability that said given transit characteristic will be achieved; and

dynamically updating said respective transit characteristics, said grouping of destination locations into geographical regions and said respective distributions dependent upon collecting empirical transit data;

wherein dynamically updating said respective transit characteristics comprises collecting additional empirical transit data for one or more previously-shipped shipments of material subsequent to said determining said respective transit characteristics, and, based on said additional empirical transit data, updating one or more of said respective transit characteristics to indicate an additional empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations; and

wherein for at least a given one of the geographical regions, dynamically updating a grouping of destination locations into said given geographical region comprises, in response to updating said respective transit characteristics to reflect additional empirical transit data that is different from previous empirical transit data, regrouping at least some of said destination locations dependent upon said additional empirical transit data and, based on said additional empirical transit data, changing the respective set of dimensions that geographically define the given geographical region; and

in response to receiving, via a network, a request for a predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region,

providing, via the network, the predicted transit characteristic, wherein the predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region is different from a predicted transit characteristic that is determined at least in part on the dimensions of the region prior to the dynamic update.

2. The method as recited in claim 1, wherein said respective transit characteristics include respective transit latencies from said source location to said plurality of destination locations, and wherein said respective distributions associated with said geographical regions include respective transit latency probability distributions, wherein a given one of said transit latency probability distributions comprises a plurality of data points, wherein each of said plurality of data points is indicative of a given respective value of a transit latency and a corresponding probability that the given respective value of the transit latency will occur.

3. The method as recited in claim 2, further comprising estimating a particular transit latency from said source location to a particular destination location, wherein said estimating includes:

specifying a desired surety factor for said particular transit latency;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired surety factor to determine said particular transit latency.

4. The method as recited in claim 2, further comprising estimating a particular surety factor from said source location to a particular destination location, wherein said estimating includes:

specifying a desired transit latency for said particular surety factor;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired transit latency to determine said particular surety factor.

5. The method as recited in claim 1, wherein said respective transit characteristics include respective transit latency probability distributions from said source location to one or more of said plurality of destination locations.

6. The method as recited in claim 5, wherein grouping said plurality of destinations according to said similarity criterion includes determining whether a difference between two or more respective transit latency probability distributions is less than a threshold value.

7. The method as recited in claim 6, wherein determining whether said difference between said two or more respective transit latency probability distributions is less than said threshold value includes determining an absolute difference in area underneath graphical representations of said two or more respective transit latency probability distributions and determining whether said absolute difference in area is less than said threshold value.

8. The method as recited in claim 1, wherein said respective transit characteristics include respective transit costs from said source location to said plurality of destination locations.

9. The method as recited in claim 1, wherein respective transit characteristics associated with destination locations grouped into a given geographical region correspond to a single shipping method.

10. The method as recited in claim 1, further comprising predicting a transit characteristic from said source location to a particular destination location not included within said plurality of destination locations.

11. The method as recited in claim 10, further comprising requesting said predicting of said transit characteristic via a web services interface.

12. The method as recited in claim 10, wherein predicting said transit characteristic includes:

determining that said particular destination location falls within a particular one of said geographical regions; and

evaluating said respective distribution associated with said particular geographical region to determine said predicted transit characteristic.

13. The method as recited in claim 10, wherein predicting said transit latency includes:

determining that said particular destination location does not fall within any of said geographical regions;

identifying a particular geographical region that is closest to said particular destination location; and

evaluating said respective distribution associated with said particular geographical region to determine said predicted transit characteristic.

14. The method as recited in claim 13, wherein identifying said particular geographical region as closest to said particular destination location includes determining the centers of said geographical regions and determining that the center of said particular region is closest to said particular destination location.

15. The method as recited in claim 1, wherein grouping said plurality of destination locations into said plurality of subsets corresponding to respective geographical regions includes defining boundary coordinates of each of said respective geographical regions.

16. The method as recited in claim 15, wherein said boundary coordinates of each of said respective geographical regions include latitude and longitude coordinates.

17. A non-transitory computer-accessible medium that stores program instructions, wherein the program instructions are executable to:

collect empirical transit data for a plurality of previously-shipped shipments of material;

from said empirical transit data, determine respective transit characteristics from a source location to a plurality of destination locations, wherein each of said respective transit characteristics indicates an empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations;

group said plurality of destination locations according to a similarity criterion into a plurality of subsets corresponding to respective geographical regions, wherein respective transit characteristics of destination locations grouped into a given respective geographical region each satisfy said similarity criterion, and wherein each of the geographical regions is geographically defined by a respective set of dimensions, such that the program instructions are executable to group said destination locations into subsets dependent upon the empirical transit data;

store, in a tree data structure to improve runtime performance of one or more computers, representations of the subsets corresponding to geographical regions as mappings of the plurality of destination locations;

determine a respective distribution associated with each of said geographical regions, wherein a given respective distribution correlates a given transit characteristic from said source location to a given geographical region with a respective surety factor, wherein said respective surety factor includes a cumulative probability that said given transit characteristic will be achieved;

dynamically update said respective transit characteristics, said grouping of destination locations into geographical regions and said respective distributions dependent upon collecting empirical transit data;

wherein to dynamically update said respective transit characteristics, the instructions are further executable to collect additional empirical transit data for one or more previously-shipped shipments of material subsequent to determining said respective transit characteristics, and, based on said additional empirical transit data, to update one or more of said respective transit characteristics to indicate an additional empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations;

wherein for at least a given one of the geographical regions, to dynamically update a grouping of destination locations into said given geographical region, the instructions are further executable to, in response to updating said respective transit characteristics to reflect additional empirical transit data that is different from previous empirical transit data, regroup at least some of said destination locations dependent upon said additional empirical transit data and, based on said additional empirical transit data, change the respective set of dimensions that geographically define the given geographical region; and

in response to receipt of a request for a predicted transit characteristic that is determined based at least in part on the dynamically updated dimensions of the region,

provide via a network, the predicted transit characteristic, wherein the predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region is different from a predicted transit characteristic that is determined at least in part on the dimensions of the region prior to the dynamic update.

18. The computer-accessible medium as recited in claim 17, wherein said respective transit characteristics include respective transit latencies from said source location to said plurality of destination locations, and wherein said respective distributions associated with said geographical regions include respective transit latency probability distributions, wherein a given one of said transit latency probability distributions comprises a plurality of data points, wherein each of said plurality of data points is indicative of a given respective value of a transit latency and a corresponding probability that the given respective value of the transit latency will occur.

19. The computer-accessible medium as recited in claim 18, wherein the program instructions are further executable to estimate a particular transit latency from said source location to a particular destination location, wherein said estimating includes:

specifying a desired surety factor for said particular transit latency;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired surety factor to determine said particular transit latency.

20. The computer-accessible medium as recited in claim 18, wherein the program instructions are further executable to estimate a particular surety factor from said source location to a particular destination location, wherein said estimating includes:

specifying a desired transit latency for said particular surety factor;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired transit latency to determine said particular surety factor.

21. The computer-accessible medium as recited in claim 17, wherein said respective transit characteristics include respective transit latency probability distributions from said source location to one or more of said plurality of destination locations.

22. The computer-accessible medium as recited in claim 21, wherein grouping said plurality of destinations according to said similarity criterion includes determining whether a difference between two or more respective transit latency probability distributions is less than a threshold value.

23. The computer-accessible medium as recited in claim 22, wherein determining whether said difference between said two or more respective transit latency probability distributions is less than said threshold value includes determining an absolute difference in area underneath graphical representations of said two or more respective transit latency probability distributions and determining whether said absolute difference in area is less than said threshold value.

24. The computer-accessible medium as recited in claim 17, wherein said respective transit characteristics include respective transit costs from said source location to said plurality of destination locations.

25. The computer-accessible medium as recited in claim 17, wherein respective transit characteristics associated with destination locations grouped into a given geographical region correspond to a single shipping method.

26. The computer-accessible medium as recited in claim 17, wherein the program instructions are further executable to predict a transit characteristic from said source location to a particular destination location not included within said plurality of destination locations.

27. The computer-accessible medium as recited in claim 26, wherein the program instructions are further executable to implement a web services interface through which a prediction of said transit characteristic is requested.

28. The computer-accessible medium as recited in claim 26, wherein predicting said transit characteristic includes:

determining that said particular destination location falls within a particular one of said geographical regions; and

evaluating said respective distribution associated with said particular geographical region to determine said predicted transit characteristic.

29. The computer-accessible medium as recited in claim 26, wherein predicting said transit characteristic includes:

determining that said particular destination location does not fall within any of said geographical regions;

identifying a particular geographical region that is closest to said particular destination location; and

evaluating said respective distribution associated with said particular geographical region to determine said predicted transit characteristic.

30. The computer-accessible medium as recited in claim 29, wherein identifying said particular geographical region as closest to said particular destination location includes determining the centers of said geographical regions and determining that the center of said particular region is closest to said particular destination location.

31. The computer-accessible medium as recited in claim 17, wherein grouping said plurality of destination locations into said plurality of subsets corresponding to respective geographical regions includes defining boundary coordinates of each of said respective geographical regions.

32. The computer-accessible medium as recited in claim 31, wherein said boundary coordinates of each of said respective geographical regions include latitude and longitude coordinates.

33. A system, comprising:

one or more computer systems each including at least a memory and a processor configured to execute instructions, wherein the instructions are executable by the one or more computer systems to implement;

an application program;

a web services interface; and

a transit characteristic model;

wherein said application program is configured to request from said transit characteristic model via said web services interface a prediction of a transit characteristic from a source location to a given destination location;

wherein said transit characteristic model is configured to;

collect empirical transit data for a plurality of previously-shipped shipments of material;

from said empirical transit data, determine respective transit characteristics from said source location to a plurality of destination locations, wherein each of said respective transit characteristics indicates an empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations;

group said plurality of destination locations according to a similarity criterion into a plurality of subsets corresponding to respective geographical regions, wherein respective transit characteristics of destination locations grouped into a given respective geographical region each satisfy said similarity criterion, and wherein each of the geographical regions is geographically defined by a respective set of dimensions, such that the transit characteristic model is configured to group said destination locations into subsets dependent upon the empirical transit data;

store, in a tree data structure to improve runtime performance of the one or more computer systems, representations of the subsets corresponding to geographical regions as mappings of the plurality of destination locations;

determine a respective distribution associated with each of said geographical regions, wherein a given respective distribution correlates a given transit characteristic from said source location to a given geographical region with a respective surety factor, wherein said respective surety factor includes a cumulative probability that said given transit characteristic will be achieved;

predict said transit characteristic to said given destination location, wherein said predicting includes determining that said particular destination location falls within a particular one of said geographical regions, evaluating said respective distribution associated with said particular geographical region to determine said predicted transit characteristic, and returning said predicted transit characteristic to said application; and

dynamically update said respective transit characteristics and said grouping of destination locations into geographical regions dependent upon collecting empirical transit data;

wherein to dynamically update said respective transit characteristics, the transit characteristic model is further configured to collect additional empirical transit data for one or more previously-shipped shipments of material subsequent to determining said respective transit characteristics, and, based on said additional empirical transit data, to update one or more of said respective transit characteristics to indicate an additional empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations;

wherein for at least a given one of the geographical regions, to dynamically update a grouping of destination locations into said given geographical region, the transit characteristic model is further configured to, in response to updating said respective transit characteristics to reflect additional empirical transit data that is different from previous empirical transit data, regroup at least some of said destination locations dependent upon said additional empirical transit data and, based on said additional empirical transit data, change the respective set of dimensions that geographically define the given geographical region; and

wherein in response to receipt of a request from said application via said web services interface for a predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region,

the transit characteristic model is further configured to provide, via said web services interface, the predicted transit characteristic to said application, wherein the predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region is different from a predicted transit characteristic that is determined at least in part on the dimensions of the region prior to the dynamic update.

34. The system as recited in claim 33, wherein said transit characteristic model is further configured to dynamically update said respective transit characteristics, said grouping of destination locations into geographical regions and said respective distributions dependent upon collecting empirical transit data.

35. The system as recited in claim 33, wherein said respective transit characteristics include respective transit latencies from said source location to said plurality of destination locations, and wherein said respective distributions associated with said geographical regions include respective transit latency probability distributions, wherein a given one of said transit latency probability distributions comprises a plurality of data points, wherein each of said plurality of data points is indicative of a given respective value of a transit latency and a corresponding probability that the given respective value of the transit latency will occur.

36. The system as recited in claim 35, wherein said transit characteristic model is further configured to estimate a particular transit latency from said source location to a particular destination location, wherein said estimating includes:

specifying a desired surety factor for said particular transit latency;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired surety factor to determine said particular transit latency.

37. The system as recited in claim 35, wherein said transit characteristic model is further configured to estimate a particular surety factor from said source location to a particular destination location, wherein said estimating includes:

specifying a desired transit latency for said particular surety factor;

determining a particular geographical region to which said particular destination location corresponds; and

evaluating said respective transit latency probability distribution corresponding to said particular geographical region dependent upon said desired transit latency to determine said particular surety factor.

38. The system as recited in claim 33, wherein said respective transit characteristics include respective transit latency probability distributions from said source location to one or more of said plurality of destination locations.

39. The system as recited in claim 38, wherein grouping said plurality of destinations according to said similarity criterion includes determining whether a difference between two or more respective transit latency probability distributions is less than a threshold value.

40. The system as recited in claim 39, wherein determining whether said difference between said two or more respective transit latency probability distributions is less than said threshold value includes determining an absolute difference in area underneath graphical representations of said two or more respective transit latency probability distributions and determining whether said absolute difference in area is less than said threshold value.

41. The system as recited in claim 33, wherein said respective transit characteristics include respective transit costs from said source location to said plurality of destination locations.

42. The system as recited in claim 33, wherein respective transit characteristics associated with destination locations grouped into a given geographical region correspond to a single shipping method.

43. The system as recited in claim 33, wherein grouping said plurality of destination locations into said plurality of subsets corresponding to respective geographical regions includes defining boundary coordinates of each of said respective geographical regions.

44. The system as recited in claim 43, wherein said boundary coordinates of each of said respective geographical regions include latitude and longitude coordinates.

45. The system as recited in claim 33, wherein said transit characteristic model determining respective transit characteristics from said source location to said plurality of destination locations includes said transit characteristic model requesting shipment tracking data for shipments in transit between said source location and said plurality of destination locations.

46. A system, comprising:

one or more computer systems each including at least a memory and a processor configured to execute instructions, wherein the instructions are executable by the one or more computer systems to implement;

a transit characteristic model determined dependent upon collected empirical data for a plurality of previously-shipped shipments of material, wherein the transit characteristic model includes representations of geographical regions as mappings of a plurality of destination locations, the representations stored in a tree data structure to improve runtime performance of the one or more computer systems, and wherein the transit characteristic model is configured to;

predict respective transit characteristics from a given source location to each a plurality of geographical regions, wherein each of said plurality of geographical regions is represented within said transit characteristic model by one or more coordinates, and wherein respective transit characteristics from said given source location to a plurality of destination locations within a given geographical region satisfy a similarity criterion;

determine a respective distribution associated with each of said geographical regions, wherein a given respective distribution correlates a given transit characteristic from said source location to a given geographical region with a respective surety factor, wherein said respective surety factor includes a cumulative probability that said given transit characteristic will be achieved;

dynamically update said respective transit characteristics dependent upon empirical observations of said respective transit characteristics, wherein to dynamically update said respective transit characteristics, the transit characteristic model is further configured to collect additional empirical transit data for one or more previously-shipped shipments of material and, based on said additional empirical transit data, to update one or more of said respective transit characteristics to indicate an additional empirically-observed aspect of a transit of material between said source location and a corresponding one of said destination locations; and

for at least a given one of the geographical regions, in response to dynamically updating said respective transit characteristics to reflect additional empirical transit data that is different from previous empirical transit data, regroup at least some of said destination locations dependent upon said additional empirical data and, based on said additional empirical transit data, change one or more of the coordinates representing said given geographical region; and

in response to receipt of a request for a predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region,

provide, via a network, the predicted transit characteristic, wherein the predicted transit characteristic that is determined at least in part on the dynamically updated dimensions of the region is different from a predicted transit characteristic that is determined at least in part on the dimensions of the region prior to the dynamic update.

47. The system as recited in claim 46, wherein said respective transit characteristics include respective transit latencies from said given source location to said plurality of destination locations.

48. The system as recited in claim 46, wherein the instructions are further executable to implement a web services interface through which an application is configured to request said transit characteristic prediction.

49. The system as recited in claim 46, wherein said transit characteristic model is further configured to predict a transit characteristic to a particular geographical region of a package that is shipped to said particular geographical region without completely specifying a delivery address of said package at time of shipment.

50. The system as recited in claim 46, wherein for each of said geographical regions, transit characteristics associated with destination locations included within a particular one of said geographical regions correspond to a same shipping method from said given source location.

51. The system as recited in claim 50, wherein said transit characteristic model is further configured to select a particular shipping method in response to said application specifying said given source location, a desired destination location, a desired transit characteristic, and a desired surety factor.

52. The system as recited in claim 50, wherein said transit characteristic model is further configured to predict a particular transit characteristic in response to an application specifying said given source location, a desired destination location, a desired shipping method, and a desired surety factor.