Generating container plans for multi-item orders

• US 8,326,679 B1
• Filed: 04/22/2010
• Issued: 12/04/2012
• Est. Priority Date: 04/22/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vuillemot, Ward W., Lee, Dennis, Rowe, Sarah T., Haake, Paul N.
• Primary Examiner(s): Singh, Gurkanwaljit
• Application Number:
  US12/765,163
• Time in Patent Office: 957 Days
• Field of Search: None
• US Class Current: 705/7.38
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

Technologies are described herein for generating container plans for multi-item orders. The items of the order are divided into zones, where the zones may determine the picking zone and/or packaging requirements for the item. Zone-based container plans are generated for the items in the order associated with each individual zone. The container plan includes an assignment of each item to one or more logical shipping containers. A mixed container plan is also generated for all the items in the order regardless of the associated zone. If the number of logical shipping containers in the mixed container plan is less than the total number of logical shipping containers in the zone-based container plans, then a final container plan for the order is generated from the mixed container plan. Otherwise, the final container plan is generated by combining the zone-based plans for each zone associated with items in the order.

Claims

1. A computer-readable non-transitory storage medium having computer-executable instructions stored thereon that, when executed by a computer, cause the computer to:

divide a plurality of items in an order for delivery by zone, wherein the zone associated with an item is based on one or more of a picking zone and packaging requirements for the item;

generate a zone-based container plan for each zone, wherein the zone-based container plan comprises an assignment of each item associated with the zone to one of one or more shipping containers allocated to the zone-based container plan based upon one or more of a weight and volume of each item assigned to the shipping container and a weight constraint and volume constraint associated with the shipping container;

generate a mixed container plan for the order, wherein the mixed container plan comprises an assignment of each item in the order regardless of zone to one of one or more shipping containers allocated to the mixed container plan based upon one or more of a weight and volume of each item assigned to the shipping container and a weight constraint and volume constraint associated with the shipping container;

determine if a number of shipping containers allocated to the mixed container plan is less than a combined number of shipping containers allocated to the zone-based container plans for all zones;

upon determining that the number of shipping containers allocated to the mixed container plan is greater than or equal to the combined number of shipping containers allocated to the zone-based container plans for all zones, generate a final container plan by combining the zone-based container plans for all zones; and

upon determining that the number of shipping containers allocated to the mixed container plan is less than the combined number of shipping containers allocated to the zone-based container plans for all zones, generate the final container plan based on the mixed container plan.

2. The computer-readable storage medium of claim 1, wherein items having a heaviest weight or largest volume are assigned to one of the one or more shipping containers before items having a lighter weight or smaller volume in generating the zone-based container plans or the mixed container plan.

3. The computer-readable storage medium of claim 1, wherein the one or more shipping containers allocated to the zone-based container plans and the mixed container plan are all substantially the same size and are all associated with the same weight constraint and volume constraint.

4. The computer-readable storage medium of claim 1, wherein generating the final container plan comprises determining packing supplies for each of the one or more shipping containers allocated to the container plan based on one or more of the zones associated with the items assigned to the shipping container and delivery preferences of the order.

5. The computer-readable storage medium of claim 1, wherein generating the final container plan based on the mixed container plan comprises executing computer-executable instructions that cause the computer to:

calculate a watermark constraint for the shipping containers based on the items in the order and the number of shipping containers in the mixed container plan;

initially create the final container plan from the zone-based container plan generated for a first zone; and

for each item in the order not assigned to a shipping container in the zone-based container plan, assign the item to one of the one or more shipping containers allocated to the final container plan based in part upon the watermark constraint calculated for the shipping containers.

6. The computer-readable storage medium of claim 5, wherein the watermark constraint is calculated by dividing a total weight of the items in the order by the number of shipping containers allocated to the mixed container plan.

7. The computer-readable storage medium of claim 1, wherein the items in the order are grocery items.

8. A computer-implemented method of generating a container plan for a multi-item order in a merchant system, the method comprising:

dividing, by one or more computers in the merchant system, items in the order by zone, wherein the zone associated with an item is based on one or more of a picking zone and packaging requirements for the item;

generating, by the one or more computers, a zone-based container plan for each zone, wherein the zone-based container plan comprises an assignment of each item associated with the zone to one of one or more shipping containers allocated to the zone-based container plan;

generating, by the one or more computers, a mixed container plan for the order, wherein the mixed container plan comprises an assignment of each item in the order regardless of zone to one of one or more shipping containers allocated to the mixed container plan;

selecting, by the one or more computers, between the mixed container plan and the zone-based container plans based at least in-part on a comparison between a number of shipping containers allocated to the mixed container plan and a combined number of shipping containers allocated to the zone-based container plans for all zones;

upon selecting the zone-based container plans, generating, by the one or more computers, a final container plan by combining the zone-based container plans for all zones; and

upon selecting the mixed container plan, generating, by the one or more computers, the final container plan from the mixed container plan.

9. The computer-implemented method of claim 8, wherein generating a container plan comprises assigning each item to one of the one or more shipping containers allocated to the container plan based upon one or more of a weight and volume of each item assigned to the shipping container and a weight constraint or volume constraint associated with the shipping container.

10. The computer-implemented method of claim 9, wherein the items having a heaviest weight or largest volume are assigned to one of the one or more shipping containers before the items having a lighter weight or smaller volume.

11. The computer-implemented method of claim 9, wherein the one or more shipping containers are all substantially the same size and are all associated with the same weight constraint and/or volume constraint.

12. The computer-implemented method of claim 9, wherein generating the mixed container plan for the order comprises first sorting the items in the order according to a pick location of each item along a pick path, then by the weight of each item, and then by the volume of each item.

13. The computer-implemented method of claim 9, wherein generating the mixed container plan for the order comprises first sorting the items by the zone associated with each item, then by the weight of each item, and then by the volume of each item.

14. The computer-implemented method of claim 8, wherein generating the final container plan comprises determining packing supplies for each of the one or more shipping containers allocated to the container plan based on one or more of the zones associated with the items assigned to the shipping container and delivery preferences of the order.

15. The computer-implemented method of claim 8, wherein generating the final container plan from the mixed container plan comprises rebalancing the mixed container plan by:

calculating, by the one or more computers, a watermark constraint for the shipping containers based on the items in the order and the number of shipping containers in the mixed container plan;

initially creating, by the one or more computers, the final container plan from the zone-based container plan generated for a first zone; and

for each item in the order not assigned to a shipping container in the zone-based container plan, assigning, by the one or more computers, the item to one of the one or more shipping containers allocated to the final container plan based in part upon the watermark constraint calculated for the shipping containers.

16. The computer-implemented method of claim 15, wherein the watermark constraint is calculated by dividing a total weight of the items in the order by the number of shipping containers allocated to the mixed container plan.

17. A system for generating a container plan for a multi-item order, the system comprising:

a server computer comprising a memory and one or more processing units; and

a cartonization module residing in the memory and configured to cause the one or more processing units to;

generate a plurality of zone-based container plans for a number of zones associated with items in an order, wherein each zone-based container plan comprises an assignment of each item associated with the zone to one of one or more logical shipping containers allocated to the zone-based container plan,

generate a mixed container plan for the order, wherein the mixed container plan comprises an assignment of each of the items item in the order to one of one or more logical shipping containers allocated to the mixed container plan,

select between the mixed container plan and the zone-based container plans based at least in-part on a comparison between a number of logical shipping containers allocated to the mixed container plan and a combined number of logical shipping containers allocated to the zone-based container plans for all zones,

upon selecting the zone-based container plans, generate a final container plan by combining the zone-based container plans for all zones,

upon selecting the mixed container plan, generate the final container from the mixed container plan, and

determining packing supplies for each of the one or more logical shipping containers allocated to the final container plan based on one or more of the zones associated with the items assigned to the logical shipping container and delivery preferences of the order, wherein the logical shipping containers represent shipping containers of a particular size and associated with particular weight constraint and volume constraint.

18. The system of claim 17, wherein generating a container plan comprises assigning each item to one of the one or more logical shipping containers allocated to the container plan based upon one or more of a weight and volume of each item assigned to the logical shipping container and the weight constraint or volume constraint associated with the logical shipping container.

19. The system of claim 17, wherein items having a heaviest weight or largest volume are assigned to one of the one or more logical shipping containers before items having a lighter weight or smaller volume in generating the plurality of zone-based container plans or the mixed container plan.

20. The system of claim 17, wherein generating the final container plan from the mixed container plan comprises rebalancing the mixed container plan by executing computer-executable instructions that cause the one or more processing units to:

calculate a watermark constraint for the logical shipping containers based on the items in the order and the number of logical shipping containers in the mixed container plan;

initially create the final container plan from the zone-based container plan generated for a first zone; and

for each item in the order not assigned to a logical shipping container in the zone-based container plan, assign the item to one of the one or more logical shipping containers allocated to the final container plan based in part upon the watermark constraint calculated for the shipping containers.

21. The system of claim 20, wherein the watermark constraint is calculated by dividing a total weight of the items in the order by the number of shipping containers allocated to the mixed container plan.