Inserting stops into delivery routes

• US 8,498,947 B1
• Filed: 12/17/2009
• Issued: 07/30/2013
• Est. Priority Date: 12/17/2009
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Haake, Paul N., Lee, Dennis, Rowe, Sarah T., Harman, Steve R.
• Primary Examiner(s): FLYNN, KEVIN H
• Application Number:
  US12/640,516
• Time in Patent Office: 1,321 Days
• Field of Search: 705/338, 705/7.13
• US Class Current: 705/338
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083

Abstract

Various systems and methods are described for insertion of optional stops in delivery routes. To this end, a plurality of delivery routes is provided in a computing device, where each delivery route has a plurality of stops. A determination is made in the computing devices as to whether an optional stop can be inserted between a pair of the stops in at least one of the delivery routes without violating a predefined set of criteria. The optional stop is ultimately inserted between a respective pair of stops in a selected one of the delivery routes.

Claims

1. An apparatus, comprising:

a computing device;

a plurality of delivery routes stored in a memory associated with the computing device, each delivery route having a plurality of stops; and

a stop insertion application executable in the computing device, the stop insertion application being configured to;

determine an area of consideration surrounding an optional stop, the area of consideration falling within a predefined radius from the optional stop;

for each pair of stops for each delivery route included within the area of consideration, determine whether the optional stop can be inserted between the pair of stops in at least one of the delivery routes without violating a predefined set of criteria, wherein the optional stop is to be implemented to pick up an empty tote used to deliver at least one item, wherein the predefined set of criteria further comprises;

whether an insertion of the optional stop between the pair of stops results in a delay for the selected one of the delivery routes that is greater than a predefined threshold;

whether an insertion of the optional stop between the pair of stops causes a delay that breaks a promise to deliver within a predefined window of time associated with one of the stops; and

whether a first one of the pair of stops is within a predefined distance of the optional stop; and

insert the optional stop between a respective pair of stops in a selected one of the delivery routes.

2. The apparatus of claim 1, wherein the selected one of the delivery routes in which to insert the optional stop is the delivery route in which the insertion of the optional stop results in a minimum of disruption for the delivery route.

3. A method, comprising the steps of:

providing a plurality of delivery routes in a computing device, each delivery route having a plurality of stops;

determining in the computing device an area of consideration surrounding an optional stop, the area of consideration falling within a predefined radius from the optional stop;

identifying in the computing device each stop of each delivery route included within the area of consideration;

for each stop of each delivery route included within the area of consideration, determining in the computing device whether the optional stop can be inserted between a corresponding pair of stops in accordance with a predefined set of criteria, wherein determining whether the optional stop can be inserted between the corresponding pair of stops in accordance with the predefined set of criteria comprises determining whether an insertion of the optional stop results in a period of time spent between the corresponding pair of stops that is greater than a predefined threshold of time; and

inserting in the computing device the optional stop in a selected one of the delivery routes.

4. The method of claim 3, wherein the optional stop comprises a stop to pick up an empty tote used to deliver at least one item.

5. The method of claim 3, wherein the optional stop comprises a driver break to be inserted into a delivery route, wherein the driver break comprises a stoppage of performing delivery work.

6. The method of claim 3, wherein the step of determining whether the optional stop can be inserted between the corresponding pair of stops in accordance with the predefined set of criteria further comprises the step of determining whether an insertion of the optional stop between the corresponding pair of stops results in a delay for the selected one of the delivery routes that is greater than a predefined threshold of delay.

7. The method of claim 3, wherein the step of determining whether the optional stop can be inserted between the corresponding pair of stops in accordance with the predefined set of criteria further comprises the step of determining whether an insertion of the optional stop between the corresponding pair of stops causes a delay that breaks a promise to deliver within a predefined window of time associated with one of the stops.

8. The method of claim 3, wherein of the selected one of the delivery routes in which to insert the optional stop is the delivery route in which the insertion of the optional stop results in a lowest relative disruption for the delivery route.

9. The method of claim 3, wherein the step of determining whether the optional stop can be inserted between the corresponding pair of stops in accordance with the predefined set of criteria further comprises the step of determining whether a first one of the corresponding pair of stops is within a predefined driving time of the optional stop.

10. The method of claim 9, wherein the predefined driving time is determined based upon an average driving speed and a predefined time period.

11. The method of claim 3, further comprising the step of generating the delivery routes in the computing device.

22. The method of claim 3, wherein the predefined radius is a distance.

23. The method of claim 3, wherein the predefined radius is expressed in terms of a travel time.

24. The method of claim 23, wherein the predefined radius is expressed in terms of average speed based on a location of the area of consideration.

12. An apparatus, comprising:

a computing device;

a plurality of delivery routes stored in a memory associated with the computing device, each delivery route having a plurality of stops; and

a stop insertion application executable in the computing device, the stop insertion application being configured to;

determine an area of consideration surrounding an optional stop, the area of consideration falling within a predefined radius from the optional stop;

identify each stop of each delivery route included within the area of consideration;

for each stop of each delivery route included within the area of consideration, determine whether the optional stop can be inserted between a corresponding pair of the stops without violating a predefined set of criteria, wherein the predefined set of criteria further comprises whether an insertion of the optional stop between the corresponding pair of stops results in a delay for the selected one of the delivery routes that is greater than a predefined threshold; and

insert the optional stop between a respective pair of stops in a selected one of the delivery routes.

13. The apparatus of claim 12, wherein the optional stop comprises a stop to pick up an empty tote used to deliver at least one item.

14. The apparatus of claim 12, wherein the optional stop comprises a driver break to be inserted into a delivery route, wherein the driver break comprises a stoppage of performing delivery work.

15. The apparatus of claim 12, wherein the predefined set of criteria further comprises whether an insertion of the optional stop between the corresponding pair of stops causes a delay that breaks a promise to deliver within a predefined window of time associated with one of the stops.

16. The apparatus of claim 12, wherein the selected one of the delivery routes in which to insert the optional stop is the delivery route in which the insertion of the optional stop results in a minimum of disruption for the delivery route.

17. The apparatus of claim 12, wherein the predefined set of criteria further comprises whether a first one of the pair of stops is within a predefined distance of the optional stop.

18. The apparatus of claim 17, wherein the predefined distance is determined based upon an average driving speed and a predefined time period.

19. The apparatus of claim 12, further comprising a route generation application executable in the computing device, the route generation application being configured to generate the delivery routes.

20. A non-transitory computer readable medium embodying a program executable in a computing device, comprising:

a plurality of delivery routes, each delivery route having a plurality of stops, where a delivery is to be made at each of the stops;

code that determines an area of consideration surrounding an optional stop, the area of consideration falling within a predefined radius from the optional stop;

code that determines, for each pair of stops for each delivery route included within the area of consideration, whether the optional stop can be inserted between the pair of stops in at least one of the delivery routes without imposing a delay in the at least one of the delivery routes that is greater than a predefined time threshold and without breaking a promise to deliver within a predefined window of time associated with one of the stops; and

code that inserts the optional stop between a respective pair of stops in a selected one of the delivery routes.

21. The non-transitory computer readable medium embodying the program executable in the computing device of claim 20, wherein the optional stop comprises a stop to pick up an empty tote previously used to deliver at least one item at the stop.