Dynamic vehicle routing for regional clusters

• US 9,569,745 B1
• Filed: 07/27/2015
• Issued: 02/14/2017
• Est. Priority Date: 07/27/2015
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ananthanarayanan, Kalyanakrishnan, Poddar, Rajiv Kumar, Verma, Tej Paul, Das, Sushanta, Yadav, Ankit Kumar, Kan, Eric Yuk-Hon, Michener, Mark Robert
• Primary Examiner(s): Trivedi, Atul
• Application Number:
  US14/810,315
• Time in Patent Office: 568 Days
• Field of Search: 701/533
• US Class Current: 1/1
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/08355 Routing methods
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 30/0635 Processing of requisition or of purchase orders

Abstract

Techniques described herein are directed towards dynamically adding new pickup orders to an existing route structure. In at least some embodiments, a service provider separates a number of vendors into separate clusters based on one or more attributes. For example, the vendors may be separated by geographic region. The service provider may then identify a set of routes that are associated with each of the vendor clusters and run optimization techniques on that set of routes. The set of routes may be filtered based on attributes of the route. In some embodiments, the service provider may make a route alteration that accommodates the new pickup order.

Claims

1. A computer-implemented method, comprising:

receiving order data including information related to an item, an availability date for the item, an identification of a fulfillment center to receive the item, and location information associated with a pickup of the item;

determining, based at least in part on an inventory demand for the item, a deliver-by date for the item;

identifying, based at least in part on the location information, a regional cluster to be associated with the item, wherein the regional cluster is identified using one or more clustering techniques to determine a centroid from a plurality of centroids to which the pickup of the item belongs, wherein the regional cluster surrounds the determined centroid;

identifying a set of delivery routes related to the availability date, the deliver-by date, and the regional cluster, each of the delivery routes in the set of delivery routes being a previously scheduled delivery route that includes delivery to the fulfillment center;

determining, based at least in part on at least one efficiency metric associated with one or more of the set of delivery routes, a delivery route from the set of delivery routes to include the item; and

causing the set of delivery routes to be updated such that the determined delivery route from the set of delivery routes includes a delivery pickup related to the received order data.

2. The computer-implemented method of claim 1, further comprising providing the determined delivery route to a carrier, the carrier being instructed to make the delivery pickup.

3. The computer-implemented method of claim 2, wherein the carrier is a third-party entity.

4. The computer-implemented method of claim 1, wherein the delivery route from the set of delivery routes is determined based at least in part on a weight or a volume of the item.

5. The computer-implemented method of claim 1, wherein locations associated with each of the centroids in the plurality of centroids are recalculated on a periodic basis.

6. The computer-implemented method of claim 1, wherein each of the delivery routes in the set of delivery routes originates somewhere other than the fulfillment center.

7. A system comprising:

a processor; and

a memory including instructions that, when executed with the processor, cause the system to at least;

identify one or more pickup regions, each of the one or more pickup regions associated with a respective plurality of vendors, the pickup regions being identified using one or more clustering techniques to identify a plurality of centroids to which the plurality of vendors belongs, the pickup regions each surrounding an identified centroid;

receive, from a vendor of the plurality of vendors, an indication that an item is available for pickup;

identify, based at least in part on the received indication, a pickup region of the one or more pickup regions associated with the vendor of the plurality of vendors;

identify a set of delivery routes associated with the pickup region;

determine, based at least in part on an efficiency value, a delivery route of the set of delivery routes to include the item available for pickup; and

update the delivery route to include the item available for pickup.

8. The system of claim 7, wherein at least one optimization technique is used to determine the delivery route of the set of delivery routes to include the item available for pickup.

9. The system of claim 8, wherein multiple optimization techniques are used to determine the delivery route of the set of delivery routes to include the item available for pickup, the delivery route of the set of delivery routes determined based at least in part on a result of at least one of the multiple optimization techniques.

10. The system of claim 9, wherein the multiple optimization techniques are performed in parallel.

11. The system of claim 7, wherein the instructions further cause the system to at least:

determine a demand date for the item available for pickup; and

filter the set of delivery routes associated with the pickup region such that the set of delivery routes includes routes that meet the demand date.

12. The system of claim 11, wherein the demand date is determined based at least in part on a depletion rate for the item and a current inventory amount of the item.

13. The system of claim 11, wherein the demand date is determined based at least in part on outstanding orders for the item.

14. The system of claim 7, wherein the set of delivery routes is identified based at least in part on delivery routes of the set of delivery routes being associated with at least one second item available for pickup within the pickup region.

15. The system of claim 7, wherein each of the one or more pickup regions associated with the respective plurality of vendors is defined by one or more geographic boundaries.

16. A non-transitory computer readable medium storing specific computer-executable instructions that, when executed by one or more processors, cause a computer system to perform operations comprising:

identifying, based at least in part on collective pickup data, a plurality of origination regions each associated with a respective plurality of vendor locations, the origination regions being identified using one or more clustering techniques to identify a plurality of centroids to which the plurality of vendor locations belongs, the origination regions each surrounding an identified centroid;

receiving information related to a new item pickup, the information including an indication of an origination region of the plurality of origination regions;

identifying, from a set of pickup routes associated with the origination region of the plurality of origination regions, a pickup route to include the new item pickup, the pickup route being identified based at least in part on a route optimization of the set of pickup routes; and

providing, to a pickup driver associated with the identified pickup route, the information related to the new item pickup.

17. The computer readable medium of claim 16, wherein the collective pickup data includes information related to past pickup locations.

18. The computer readable medium of claim 16, wherein the information related to the new item pickup includes a first time at which the new item pickup becomes available, and wherein the set of pickup routes is identified based at least in part on the first time.

19. The computer readable medium of claim 16, wherein the set of pickup routes associated with the origination region of the plurality of origination regions includes at least one route that passes through the origination region.

20. The computer readable medium of claim 16, wherein the information related to the new item pickup provided to the pickup driver is a route map.

21. The computer readable medium of claim 16, wherein the pickup route is identified from the set of pickup routes associated with the origination region using a first processor of the one or more processors, the first processor being associated with the origination region.

22. The computer readable medium of claim 16, wherein the pickup route is identified based at least in part on a cost associated with the pickup route.