Method and system of optimized sequencing and configuring of items for packing in a bounded region

• US 6,876,958 B1
• Filed: 06/30/2000
• Issued: 04/05/2005
• Est. Priority Date: 07/01/1999
• Status: Expired due to Term

• Current Assignee: XPO Logistics Supply Chain Corporate Services, Inc. (XPO, Inc.)
• Original Assignee: New Breed Corporations
• Inventors: Lane, Richard F., Janke, Jennifer, Chowdhury, Ashfaque
• Primary Examiner(s): Broda, Esq., Samuel
• Application Number:
  US09/607,403
• Time in Patent Office: 1,740 Days
• Field of Search: 703/1, 703/2, 703/7, 700213-244, 414881-802, 414/787
• US Class Current: 703/7
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

The present invention includes methods of selecting cases in which to pack items in an item order and selecting the sequence and configuration of placement of items into the selected cases. One such method includes examining an order comprising a list of items to be packed, determining the cases available for packing, determining the minimum number of cases required for packing the items in the list of items to be packed, selecting a case to be packed with one or more of the items in the list of items to be packed, wherein said selecting a case comprises determining a desired average volume per case and selecting the smallest of the cases available to be packed that comprises a volume in excess of the average volume per case, and determining the configuration of placement in the case to be packed of items in the list of items to be packed. Such steps may be repeated until all items in the item list are selected and configured for packing.

Claims

1. A computerized method of optimized placement of items in a bounded region, comprising:

(a) examining an order comprising a list of items to be packed;

(b) determining the cases available for packing;

(c) determining the minimum number of cases required for packing the items in the list of items to be packed;

(d) selecting a case to be packed with one or more of the items in the list of items to be packed, wherein the selecting the case comprises determining a desired average volume per case and selecting the smallest of the cases available to be packed that comprises a volume in excess of the desired average volume per case; and

(e) determining the configuration of placement in the case to be packed of items in the list of items to be packed; and

(f) if the list of items to be packed is not empty, repeating steps (d)-(e).

2. The method of claim 1 wherein the step of determining the cases available for packing comprises examining a list of available case types.

3. The method of claim 2 wherein the list of available case types comprises an indication of the quantity available for each case type.

4. The method of claim 1 wherein the step of determining the minimum number of cases required for packing the items in the list of items to be packed comprises calculating a weight-based minimum case variable.

5. The method of claim 4 wherein the weight-based minimum case variable comprises the total weight of the items in the list of items to be packed divided by a weight constraint value.

6. The method of claim 5 wherein the weight constraint value comprises the largest maximum weight constraint value of the cases on the list of available case types.

7. The method of claim 6 wherein the step of determining the minimum number of cases required for packing the items in the list of items to be packed further comprises calculating an item-based minimum case variable.

8. The method of claim 7 wherein the item-based minimum case variable comprises the total number of items in the list of items to be packed divided by an item constraint value.

9. The method of claim 8 wherein the item constraint value comprises the largest maximum item constraint value of the cases on the list of available case types.

10. The method of claim 9 wherein the step of determining the minimum number of cases required for packing the items in the list of items to be packed further comprises calculating a fill-based minimum case variable.

11. The method of claim 10 wherein the fill-based minimum case variable comprises the total volume of items in the list of items to be packed divided by a fill constraint value.

12. The method of claim 11 wherein the fill constraint value comprises the largest maximum fill constraint value of the cases on the list of available case types.

13. The method of claim 12 wherein the step of determining the minimum number of cases further comprises adding one to the integer value of the largest of the weight-based minimum case variable, item-based minimum case variable, and fill-based minimum case variable.

14. The method of claim 13 wherein the minimum number of cases comprises one plus the integer value of the largest of the weight-based minimum case variable, item-based minimum case variable, and fill-based minimum case variable.

15. The method of claim 1 further comprising the step of determining whether the list of items comprises one or more items making up a pre-packaged case, and, if so, removing the one or more items making up the pre-packaged case from the list of items.

16. The method of claim 1 wherein the desired average volume per case comprises A*B/C, where;

A=the total volume of all items on the list of items to be packed,

B=1+(1−

a maximum fill constraint), and

C=the minimum number of cases required for Racking the items in the list of items to be packed.

17. The method of claim 1 wherein the step of determining the configuration of placement in the case to be packed of items in the list of items to be packed comprises

(g) dividing unused volume in the case to be packed into one or more cubes;

(h) selecting a one cube to be packed from the one or more cubes;

(i) selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate;

(j) remove the item for packing from the list of items to be packed;

(k) designating the volume associated with the one cube to be packed as occupied by the item for packing; and

(I) if volume within the case that may hold an item from the list of items to be packed has not been designated as occupied, and if the list of items to be packed is not empty, repeating steps (g)-(l).

18. The step of claim 17 wherein, if no items for packing have yet been designated for placement in the case to be packed, the step of dividing unused volume in the case to be packed into one or more cubes comprises designating the entire volume of the case to be packed.

19. The method of claim 18 wherein the step of selecting a one cube to be packed from the one or more cubes comprises selecting the smallest of the one or more cubes.

20. The method of claim 19 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate comprises selecting the largest of the items from the list of items to be packed not previously selected in association with the one cube to be packed.

21. The method of claim 20 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate further comprises determining whether the volume of the item for packing is less than the volume of the one cube to be packed.

22. The method of claim 21 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate further comprises determining whether the dimensions of the item for packing are less then the dimensions of the one cube to be packed.

23. The method of claim 22 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate further comprises determining whether addition of the item for packing to the case would result in exceeding the maximum item constraint of the case to be packed.

24. The method of claim 23 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate further comprises determining whether it is preferred that the item not be placed in the layer of the one cube to be packed.

25. The method of claim 24 wherein the step of selecting an item for packing from the list of items to be packed that the one cube to be packed can accommodate further comprises determining whether addition of the item for packing to the case to be packed would result in exceeding the maximum weight constraint of the case to be packed.

26. The method of claim 25 wherein the step of designating the volume associated with the one cube to be packed as occupied by the item for packing comprises recording the coordinates of the volume associated with the one cube in association an identifier for the item for packing.

27. The method of claim 17 wherein the step of determining the configuration of placement in the case to be packed of items in the list of items to be packed comprises recording the configuration in a deliverables data file.

28. The method of claim 27 further comprising printing a pick label.

29. The method of claim 28 wherein printing a pick label comprises printing data in deliverables data file.

30. The method of claim 29 wherein the pick label indicates the type of case for packing and a list of items for packing in the type of case.

31. The method of claim 1 wherein the step of determining the configuration of placement in the case to be packed of items in the list of items to be packed comprises recording the configuration in a deliverables data file.

32. The method of claim 31 further comprising printing a pick label.

33. The method of claim 32 wherein printing a pick label comprises printing data in the deliverables data file.

34. The method of claim 33 wherein the pick label indicates the type of case for packing and a list of items for packing in the type of case.