Dynamic vehicle routing for regional clusters

• US 10,152,685 B1
• Filed: 01/03/2017
• Issued: 12/11/2018
• 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:
  US15/397,617
• Time in Patent Office: 707 Days
• Field of Search: 701533
• 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 for an item, the order data comprising an availability date for the item, a need-by date, an indication of a destination location, and an indication of a pickup location;

identifying, based at least in part on the pickup location, a region that includes the pickup location to be associated with the item, the region comprising a number of geographic boundaries;

identifying, based on the availability date for the item, a set of delivery routes that traverse the region, each of the delivery routes in the set of delivery routes being a previously scheduled delivery route that includes delivery to the destination location, wherein at least a portion of each delivery route in the set of delivery routes passes within the geographic boundaries of the region, each of the delivery routes being associated with a pickup time window and a delivery time for the scheduled delivery route within that pickup time window;

identifying, from the set of delivery routes, a subset of delivery routes having a pickup time window that includes the availability date and the need-by date;

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

updating the delivery time for the delivery route to be prior to the need-by date upon determining that the delivery time for the delivery route is subsequent to the need-by date; 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, wherein the region is identified based on regional boundaries comprising man-made boundaries and geographic boundaries.

3. 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.

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

5. 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.

6. A system comprising:

a processor; and

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

receive, from a vendor, an indication that an item is available for pickup, the indication including at least a need-by date;

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

identify a set of delivery routes scheduled to traverse the pickup region, wherein at least a portion of each delivery route in the set of delivery routes passes within geographic boundaries of the pickup region, each of the delivery routes being associated with a pickup time window and a delivery time within that pickup time window;

identify, from the set of delivery routes, a subset of delivery routes having a pickup time window that includes the need-by date;

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;

update the delivery time for the delivery route to be prior to the need-by date upon determining that the delivery time is subsequent to the need-by date; and

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

7. The system of claim 6, 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.

8. The system of claim 7, 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.

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

10. The system of claim 6, 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 scheduled to traverse the pickup region before the demand date.

11. The system of claim 10, 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.

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

13. The system of claim 6, 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.

14. The system of claim 6, wherein the pickup region is defined by one or more geographic boundaries or man-made boundaries.

15. 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 a plurality of origination regions each associated with a respective plurality of vendor locations;

receiving information related to a new item pickup, the information including an indication of an origination region of the plurality of origination regions, a need-by date, and a destination location;

identifying, from a set of pickup routes traversing the origination region of the plurality of origination regions and including the destination location, 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, wherein at least a portion of the pickup route passes within geographic boundaries of the origination region, the pickup route being associated with a pickup time window and a delivery time within that pickup time window, the pickup route being identified based at least in part on having a pickup time window that includes the need-by date;

updating the delivery time for the pickup route to be prior to the need-by date upon determining that the delivery time is subsequent to the need-by date; and

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

16. The non-transitory computer readable medium of claim 15, 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 traversing the origination region the first time.

17. The non-transitory computer readable medium of claim 15, wherein the information related to the new item pickup provided to the pickup driver is a route map.

18. The non-transitory computer readable medium of claim 15, 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.

19. The non-transitory computer readable medium of claim 15, wherein the pickup route is identified based at least in part on a cost associated with the pickup route.

20. The non-transitory computer readable medium of claim 15, wherein each of the pickup routes in the set of pickup routes originates somewhere other than the destination location.