NORMALIZING ADDRESSES TO FACILITATE SORTATION AND ROUTING SOLUTION USING NATURAL LANGUAGE TEXT PROCESSING

• US 20200134014A1
• Filed: 10/29/2018
• Published: 04/30/2020
• Est. Priority Date: 10/29/2018
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: TIWARI, Alok, ARORA, Rajat, VARGHESE, Bonney, SURABHI, Vamshi, TAHERIAN, Homayoun, VERMA, Abhishek
• Granted Patent: US 10,977,441 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/083 Shipping

Abstract

Techniques for routing items addressed to an unstructured address are described. One embodiment includes receiving an order for delivery of a first package, the order specifying a first address that does not comply with a defined address format. The first address is processed using one or more hybrid machine learning algorithms to determine a Normalized Delivery Location (NDL) associated with the first address. A sorting zone that encompasses the NDL is determined. The sorting zones correspond to a predefined geographic region. Embodiments facilitate transport of the first package to a physical shipping location within the predefined geographic region.

Claims

1. A method, comprising:

processing a plurality of electronic address records for a plurality of historical orders, wherein the electronic address records in the plurality of electronic address records include natural language text data specifying a respective address, and wherein at least one of the electronic address records in the plurality of electronic address records contains natural language text data that does not comply with a defined address format;

determining a set of most commonly used keywords within the natural language text data within the plurality of electronic address records;

determining a plurality of Normalized Delivery Locations (NDLs) based on the set of most commonly used keywords, wherein each NDL in the plurality of NDLs corresponds to a respective one or more keywords in the set of most commonly used keywords;

determining a plurality of geolocations corresponding to the plurality of NDLs;

generating a plurality of sorting zones by applying a clustering algorithm to the plurality of geolocations, wherein each of the sorting zones in the plurality of sorting zones corresponds to a cluster of one or more geolocations for one or more NDLs;

receiving first address data for the delivery of a first package, wherein the first address data does not comply with a defined address format;

processing the first address data using one or more hybrid machine learning algorithms to determine at least one NDL associated with the first address data;

identifying a sorting zone that encompasses a first NDL of the at least one NDLs; and

generating a label for affixing to the first package, wherein the generated label specifies at least the identified sorting zone.

2. The method of claim 1, wherein processing the first address data using one or more hybrid machine learning algorithms to determine at least one NDL associated with the first address data further comprises:

dividing the first address data into a first plurality of n-grams; and

performing a comparison between the first plurality of n-grams and a second plurality of n-grams associated with the at least one NDL.

3. The method of claim 2, wherein processing the first address data using one or more hybrid machine learning algorithms to determine at least one NDL associated with the first address data further comprises:

calculating a Levenshtein distance between the first plurality of n-grams and the second plurality of n-grams; and

determining that the first address data corresponds to the at least one NDL, based at least in part on the calculated Levenshtein distance.

4. The method of claim 1, further comprising:

outputting the generated label to a printer device to generate a physical label for the first package;

facilitating the sorting of the first package to a container corresponding to the identified sorting zone, using the physical label.

5. The method of claim 4, wherein the container is adapted to store package to be transported to a physical location within a geographic region corresponding to the identified sorting zone.

6. The method of claim 1, wherein processing the first address data using one or more hybrid machine learning algorithms to determine at least one NDL associated with the first address data further comprises:

determining two or more NDLs of a plurality of NDLs, that correspond to the first address;

determining a two or more weights associated with the two or more NDLs; and

selecting the NDL, from the two or more NDLs, based on the determined two or more weights.

7. The method of claim 6, wherein processing the first address data using one or more hybrid machine learning algorithms to determine at least one NDL associated with the first address data further comprises:

determining two or more confidence values representing strengths of the associations between the two or more NDLs and the first address,

wherein selecting the NDL, from the two or more NDLs, is further based on the determined two or more confidence values, and

wherein determining the two or more weights associated with the two or more NDLs further comprises;

determining, for each NDL of the two or more NDLs, a respective category of a plurality of predefined categories that corresponds to the NDL, wherein each of the plurality of predefined categories represents a geographic region of a defined size; and

retrieving a predefined weight related to the determined category, wherein a magnitude of the predefined weight corresponds to the defined size of the represented geographic region.

8. A system, comprising:

one or more computer processors; and

a memory containing computer program code that, when executed by operation of one or more computer processors, performs an operation comprising;

receiving an order for delivery of a first package, the order specifying a first address that does not comply with a defined address format;

processing the first address using one or more hybrid machine learning algorithms to determine a Normalized Delivery Location (NDL) associated with the first address;

identifying a sorting zone that encompasses the NDL, wherein the sorting zones corresponds to a predefined geographic region; and

facilitating transport of the first package to a physical shipping location within the predefined geographic region.

9. The system of claim 8, wherein processing the first address using one or more hybrid machine learning algorithms to determine the NDL associated with the first address further comprises:

determining two or more NDLs of a plurality of NDLs, that correspond to the first address;

determining a two or more weights associated with the two or more NDLs; and

selecting the NDL, from the two or more NDLs, based on the determined two or more weights.

10. The system of claim 9, wherein processing the first address using one or more hybrid machine learning algorithms to determine the NDL associated with the first address further comprises:

determining two or more confidence values representing strengths of the associations between the two or more NDLs and the first address,

wherein selecting the NDL, from the two or more NDLs, is further based on the determined two or more confidence values.

11. The system of claim 9, determining the two or more weights associated with the two or more NDLs further comprises:

determining, for each NDL of the two or more NDLs, a respective category of a plurality of predefined categories that corresponds to the NDL, wherein each of the plurality of predefined categories represents a geographic region of a defined size; and

retrieving a predefined weight related to the determined category, wherein a magnitude of the predefined weight corresponds to the defined size of the represented geographic region.

12. The system of claim 8, the operation further comprising:

processing a plurality of electronic address records for a plurality of historical orders, wherein the electronic address records in the plurality of electronic address records include natural language text data specifying a respective address, and wherein at least one of the electronic address records in the plurality of electronic address records contains natural language text data that does not comply with a defined address format; and

determining a plurality of Normalized Delivery Locations (NDLs) based on the natural language text data within the plurality of electronic address records, the plurality of NDLs being inclusive of the determined NDL.

13. The system of claim 12, the operation further comprising:

for each of the plurality of NDLs, determining a set of corresponding phrases of one or more words;

determining a plurality of geolocations corresponding to the plurality of NDLs; and

generating a plurality of sorting zones by applying a clustering algorithm to the plurality of geolocations, wherein each of the sorting zones in the plurality of sorting zones corresponds to a cluster of one or more geolocations for one or more NDLs.

14. The system of claim 13, wherein facilitating the transport of the first package to the physical shipping location within the predefined geographic region further comprises:

generating a label for affixing to the first package, wherein the generated label specifies at least the identified sorting zone.

15. A non-transitory computer-readable medium containing computer program code that, when executed by operation of one or more computer processors, performs an operation comprising:

receiving first address data for the delivery of a first package, wherein the first address data does not comply with a defined address format;

determining a region corresponding to the first address data;

identifying a plurality of Normalized Delivery Locations (NDLs) that correspond to the specified zip code;

processing the first address data using one or more hybrid machine learning algorithms to select a first NDL from the plurality of NDLs;

identifying a sorting zone that encompasses the first NDL; and

facilitating the generation of a physical label for affixing to the first package, wherein the generated label specifies at least the identified sorting zone.

16. The non-transitory computer-readable medium of claim 15, wherein the region corresponding to the first address data corresponds to a city, a country, a county, a zip code or a sub-zip code region, and the operation further comprising:

processing a plurality of electronic address records for a plurality of historical orders, wherein the plurality of historical orders correspond to the zip code, wherein the electronic address records in the plurality of electronic address records include natural language text data specifying a respective address, and wherein at least one of the electronic address records in the plurality of electronic address records contains natural language text data that does not comply with a defined address format; and

determining the plurality of NDLs based on the natural language text data within the plurality of electronic address records.

17. The non-transitory computer-readable medium of claim 16, the operation further comprising:

for each of the plurality of NDLs, determining a set of corresponding phrases of one or more words;

determining a plurality of geolocations corresponding to the plurality of NDLs; and

generating a plurality of sorting zones by applying a clustering algorithm to the plurality of geolocations, wherein each of the sorting zones in the plurality of sorting zones corresponds to a cluster of one or more geolocations for one or more NDLs, and wherein the plurality of sorting zones includes the identified sorting zone that encompasses the first NDL.

18. The non-transitory computer-readable medium of claim 17, the operation further comprising:

categorizing each of the plurality of NDLs into one of a plurality of predefined categories, wherein each of the plurality of predefined categories corresponds to a geographic region of a respective size; and

assigning a respective weight to each of the plurality of predefined categories, based on the size of the corresponding geographic region.

19. The non-transitory computer-readable medium of claim 15, the operation further comprising:

determining a plurality of weights associated with the a plurality of NDLs, and

wherein processing the first address data using the one or more hybrid machine learning algorithms to select the first NDL from the plurality of NDLs is further based on the determined plurality of weights.

20. The non-transitory computer-readable medium of claim 19, wherein processing the first address data using the one or more hybrid machine learning algorithms to select the first NDL from the plurality of NDLs further comprises:

determining, for each NDL of the two or more NDLs, a respective category of a plurality of predefined categories that corresponds to the NDL, wherein each of the plurality of predefined categories represents a geographic region of a defined size; and

retrieving a predefined weight related to the determined category, wherein a magnitude of the predefined weight corresponds to the defined size of the represented geographic region.