Method of packing rectangular objects in a rectangular area or space by determination of free subareas or subspaces

• US 5,430,831 A
• Filed: 03/19/1993
• Issued: 07/04/1995
• Est. Priority Date: 03/19/1991
• Status: Expired due to Fees

• Current Assignee: Koninklijke KPN NV
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Snellen, Theodorus C. C. M.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/033,959
• Time in Patent Office: 837 Days
• Field of Search: 395/123, 395/124, 395/127, 395/128, 395/133, 395/134, 395/135, 395/141, 395/145, 395/148, 395/155, 395/161, 395/500, 395/919, 395/920, 395/921, 364/148, 364/DIG. 1, 364/DIG. 2
• US Class Current: 700/217
• CPC Class Codes: G05B 2219/35162 Determine workpiece placement, nesting in blank, optimize, minimize loss material
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood
• CPC Class Codes: Y10S 706/919 Designing, planning, programming, CAD, CASE

Abstract

A method of optimally packing, either intermittently or continuously, a storage or transportation area or space with rectangular parallelepiped objects, e.g. parcels, comprises two main steps of complex calculations. A first main step implies the locating of one or more free subareas or free subspaces on the area or in the space available for packing by means of a matrix reduction procedure for a 2- or 3-dimensional matrix representing free and occupied parts of rectangular or rectangular parallelepiped form. In a second main step a score is established for each different combination of a free subarea or subspace and an object to be packed and a possible orientation of the object for fitting in the subarea or subspace. The score is established by assigning a score value to each combination by passing through a hierarchy of determinations, whereby a score is the more favorable if the score value is assigned at a higher level in the hierarchy. Thereafter a combination of free area (or free space) and object and orientation having a most favorable score among the established scores is selected and the object of that combination is placed on the free area (or in the free space) and in the orientation for which the most favorable score was established. After placing the object with the most favorable score the first and second main steps are repeated for the possibly remaining free area or free space and objects to be packed.

Claims

1. A method for optimally placing rectangular objects on an area having dimensions X and Y and already partially covered with at least one rectangular object, comprising the steps of:

depicting said area in the form of a two-dimensional matrix (x, y) having x rows and y columns, each element of the matrix representing a rectangle on the area and it being established for each element whether the corresponding rectangle in the area is free or occupied;

assigning to the respective elements of the matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subarea on the area if a first equation group (I) is satisfied, which states (x_l, y_l)=B and (x_l-1, y_l)=A and (x_l, y_l-1)=A and (x_l+1, Y_l)=A (x_l, y_l+1)=A for the corresponding element in the matrix;

carrying out a matrix reduction after determining the elements x_l, y_l which satisfy (I), by always reducing by one the number of rows or the number of columns in the matrix in a predetermined sequence in consecutive steps until a (1,

     1) matrix is left, the possible free subareas always being determined after a reduction step with the aid of (I);

the number of rows being reduced by determining a second equation group (II) which states for each element (x_l, y_l) of each row, whether (x_l,y_l)=B and (x_l+1, y_l)=B, in which case the element (x_l,y_l)'"'"';

=B in the reduced matrix (x,y)'"'"' and if said equation group (II) is not satisfied, the element (x_l,y_l)'"'"';

=A;

the number of columns being reduced by determining, for each element (x,y) of each column, whether a third equation group (III) is satisfied which states (x_l,y_l)=B and (x_l,y_l +1)=B, in which case the element (x_l,y_l)'"'"';

=B in the reduced matrix (x,y)'"'"', and if said third equation group (III) is not satisfied, the element (x_l,y_l)'"'"';

=A;

the dimensions of the free subareas determined using said first equation group (I) being determined by updating a dimension table both for the rows and for the columns of the matrix, and by adjusting the dimension table for the rows or for the columns in a corresponding step during the matrix reduction,

locating free subareas by matrix reduction to a null matrix in each dimension, and placing objects fitting into said free subareas.

2. A method for optimally placing objects in the shape of a rectangular parallelepiped in a space partially filled with objects in said form, comprising the steps of:

measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;

depicting a space essentially having the form of a right parallelepiped and having dimensions X, Y and Z in the form of three-dimensional matrix (x,y,z) having x rows, y columns and z layers, each element of the matrix representing a right parallelepiped in the space and establishing for each element whether the corresponding right parallelepiped in the space is free or occupied,

assigning the corresponding element of the associated matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subspace in the space if a first equation group (I) is satisfied which states (x_l,y_l,z_l)=B and (x_l-1,y_l,z_l)=A and (x_l,y_l-1,z₁)=A and (x_l+1,y_l,z_l)=A and (x_l,y_l+1,z_l)=A and (x_l,y_l,z_l-1)=A and (x_l,y_l,z_l+1)=A for the corresponding element in the matrix;

carrying out a matrix reduction after determining the elements (x_l,y_l,z_l) which satisfy said first equation group (I), by reducing by one the number of rows or the number of columns or the number of layers of the matrix in a predetermined sequence in consecutive steps until a (1,1,1) matrix or a null matrix is left, the possible free subspaces, if any, always being determined after a reduction step with the aid of said first equation group (I);

the number of rows being reduced by determining, for each element (x_l,y_l,z_l) of the matrix, whether a second equation group (II) is satisfied which states (x_l,y_l,z_l)=B and (x_l+1,y_l,z_l)=B, in which case the element (x_l,y_l,z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said second equation group (II) is not satisfied, the element (x_l, y_l, z_l)'"'"'=A;

the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x_l, y_l, z_l)=B and (x_l, y_l+1, z_l)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said third equation group (III) is not satisfied, then the element (x_l, y_l, z_l)'"'"'=A;

the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x_l, y_l, z_l) =B and (x_l, y_l, z_l+1)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said fourth equation group (IV) is not satisfied, then the element (x.sub. l, y_l, z_l)'"'"'=A;

finding the dimensions of the free subspaces determined using said first equation group (I) by updating a dimension table for the rows and for the columns and for the layers of the matrix, and by adjusting the dimension table for the rows or the columns or the layers in a corresponding step during the matrix reduction, and

placing in said free subspaces said objects fitting into said free subspaces.

3. A method for optimally placing rectangular objects on an area being possibly, but not necessarily, already partially covered with rectangular objects, comprising the steps of:

measuring the dimensions of the rectangle sides (Xp and Yp) of a plurality of said objects;

locating on said area a plurality of free rectangular portions of said area having rectangle sides (Xs and Ys);

establishing a score for each one of said free rectangular portions of said area, for each of said objects, and for each of two possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said area, by assigning score values, in respective substeps, corresponding to the following determinations;

(1) whether said object in a said orientation is too large for fitting in said portion of said area;

(2) whether all dimensions of said object (Xp, Yp) are smaller than the corresponding dimensions of said portion (Xs, Ys) of said area;

(3) whether one dimension of said portion (Xs, or Ys) of said area corresponds to one dimension of said object (Xp or Yp), and

(4) whether two dimensions of said portion (Xs, and Ys) of said area correspond to two dimensions of the object (Xp and Yp),

said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3 or

     4) of said substeps which produces an affirmative answer, and

thereafter selecting and placing an object in a free area portion and in an orientation for which a most favorable score was established among respective scores for said plurality of portions and said plurality of objects and said orientations.

4. The method of claim 3, wherein the most favorable score corresponds with the lowest score value among the respective assigned score values as scores for said plurality of portions, said plurality of objects and said possible orientations, and in substep (2) corresponding to the determination whether all dimensions of said object (Xp, Yp) are smaller than the corresponding dimensions of said portion (Xs, Ys) of said area the assigned score value is:

score value=[(Xs-Xp)/Xs]^k * [(Ys-Yp)/Ys]^l wherein k and 1≧

1.

5. The method of claim 3, wherein the step of locating on said area a plurality of free rectangular portions of said area having rectangle side (Xs and Ys) comprising the following substeps of:

depicting said area in the form of a two-dimensional matrix (x, y) having x rows and y columns, each element of the matrix representing a rectangle on the area and it being established for each element whether the corresponding rectangle in the area is free or occupied;

assigning to the respective elements of the matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subarea on the area if a first equation group (I) is satisfied, which states (x_l, y_l)=B and (x_l-1, y_l)=A and (x_l, y_l-1)=A and (x_l+1, y_l)=A (x_l, y_l+1)=A for the corresponding element in the matrix;

carrying out a matrix reduction after determining the elements x_l, y₁ which satisfy (I), by always reducing by one the number of rows or the number of columns in the matrix in a predetermined sequence in consecutive steps until a (1,

     1) matrix is left, the possible free subareas always being determined after a reduction step with the aid of (I);

the number of rows being reduced by determining a second equation group (II) which states for each element (x_l, y_l) of each row, whether (x_l,y_l)=B and (x_l+1, y_l)=B, in which case the element (x_l,y_l)'"'"';

=B in the reduced matrix (x y)'"'"', and if said equation group (II) is not satisfied, the element (x_l,y_l)'"'"';

=A;

the number of columns being reduced by determining, for each element (x,y) of each column, whether a third equation group (III) is satisfied which states (x_l,y_l)=B and (x_l,y_l+1)=B, in which case the element (x_l,y_l)'"'"';

=B in the reduced matrix (x,y)'"'"', and if said third equation group (III) is not satisfied, the element (x_l,y_l)'"'"';

=A;

the dimensions of the free subareas determined using said first equation group (I) being determined by updating a dimension table both for the rows and for the columns of the matrix, and by adjusting the dimension table for the rows or for the columns in a corresponding step during the matrix reduction, each determined free subarea defining a free rectangular portion of said plurality of portions of said area.

6. A method for optimally placing objects in the shape of a rectangular parallelepiped in a space being possibly, but not necessarily, already partially filled with objects in said form, comprising the steps of:

measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;

locating in said space a plurality of portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs); and

establishing a score for each of said portions of free space, for each of said objects, for each of six possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said free space, by assigning score values, in respective substeps, corresponding to the following determinations;

(1) whether an object (Xp, Yp, Zp) in a said orientation is too large for fitting in said portion (Xs, Ys, Zs) of said space;

(2) whether all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Zs) of said free space;

(3) whether one dimension of said portion (Xs, Ys or Zs) of said free space corresponds to one dimension of said object (Xp, Yp or Zp);

(4) whether two dimensions of said portion (Xs, Ys, Zs) of said free space correspond to two dimensions of said object, and

(5) whether three dimensions of said portion (Xs, Ys, Zs) of said free space correspond to three dimensions of said object,

said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3,4 or

     5) of said substeps which produces an affirmative answer, and

thereafter selecting and placing an object in a portion of free space and in an orientation for which a most favorable score was established among respective scores for said plurality of portions and said plurality of objects and said orientations.

7. The method of claim 6, wherein the most favorable score corresponds with the lowest score value among the respective assigned score values as scores for said plurality of portions, said plurality of objects and said possible orientations, and in the event of an affimative determination in substep (2) signifying that all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Ys) of said area, the assigned score value is:

score value=[(Xs-Xp)/Xs]^k * [(Ys-Yp)/Ys]^l * [(Zs-Zp)/Zs]^m

wherein k, l and m>

1.

8. The method according to claim 7, wherein, prior to or concurrently with the step of establishing a score, a determination is made whether said object would be sufficiently supported in said portion (Xs, Ys, Zs) of said free space, and wherein in the event said support determination is answered in the negative, said object thereby found insufficiently supported is rejected for placement.

9. The method according to claim 8, wherein four areas are defined for said object on its bottom face, which areas do not overlap each other and each of which comprise a corner point of said object, and wherein if each of said areas upon placement is supported at at least one point, said object is found sufficiently supported and said support determination is answered in the affirmative.

10. The method according to claim 9, wherein prior to the method step of defining said four areas on the bottom face of said object, there are performed a method step of locating a center of gravity on the bottom face of said object and thereafter a method step of defining an area around the located center of gravity, which defined area is to be barred from inclusion in said four areas when they are defined.

11. The method according to claim 10, wherein prior to the method step of determining whether a said object would be sufficiently supported, a method step is performed of determining whether in placing said object in said free space said object would come to rest with a lateral face against an adjacent object, and in the event of an affirmative dtermination in the method step just mentioned, the subsequent step of determining sufficient support is carried out on the basis that any of said four areas which is adjacent to said lateral face adjacent to another object does not need to be supported for an affirmation of sufficient support.

12. The method according to claim 8, wherein, prior to or concurrently with the step of establishing a score, a determination is made whether said object would be sufficiently supported in said portion (Xs, Ys, Zs) of said free space, and wherein in the event said support determination is answered in the negative, said object thereby found insufficiently supported is rejected for placement.

13. The method according to claim 12, wherein four areas are defined for said object on its bottom face, which areas do not overlap each other and each of which comprise a corner point of said object, and wherein if each of said areas upon placement is supported at at least one point, said object is found sufficiently supported and said support determination is answered in the affirmative.

14. The method according to claim 13, wherein prior to the method step of defining said four areas on the bottom face of said object, there are performed a method step of locating a center of gravity on the bottom face of said object and thereafter a method step of defining an area around the located center of gravity, which defined area is to be barred from inclusion in said four areas when they are defined.

15. The method according to claim 14, wherein prior to the method step of determining whether a said object would be sufficiently supported, a method step is performed of determining whether in placing said object in said free space said object would come to rest with a lateral face against an adjacent object, and in the event of an affirmative dtermination in the method step just mentioned, the subsequent step of determining sufficient support is carried out on the basis that any of said four areas which is adjacent to said lateral face adjacent to another object does not need to be supported for an affirmation of sufficient support.

16. The method of claim 6, wherein the step of locating in said space a plurality of free portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs) comprises the following substeps of:

depicting a space essentially having the form of a right parallelepiped and having dimensions X, Y and Z in the form of three-dimensional matrix (x,y,z) having x rows, y columns and z layers, each element of the matrix representing a right parallelepiped in the space and establishing for each element whether the corresponding right parallelepiped in the space is free or occupied,

assigning the corresponding element of the associated matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subspace in the space if a first equation group (I) is satisfied which states (x_l,y_l,z_l)=B and (x_l-1,y_l,z_l)=A and (x_l,y_l-1,z_l)=A and (x_l+1,y_l,z_l)=A and (x_l,y_l+1,z_l)=A and (x_l,y_l,z_l-1)=A and (x_l,y_l,z_l+1)=A for the corresponding element in the matrix;

carrying out a matrix reduction after determining the elements (x_l,y_l,z_l) which satisfy said first equation group (I), by reducing by one the number of rows or the number of columns or the number of layers of the matrix in a predetermined sequence in consecutive steps until a (1,1,1) matrix or a null matrix is left, the possible free subspaces, if any, always being determined after a reduction step with the aid of said first equation group (I);

the number of rows being reduced by determining, for each element (x_l,y_l,z_l) of the matrix, whether a second equation group (II) is satisfied which states (x_l,y_l,z_l)=B and (x_l+1,y_l,z_l)=B, in which case the element (x_l,y_l,z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said second equation group (II) is not satisfied, the element (x_l, y_l, z_l)'"'"'=A;

the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x_l, y_l, z_l)=B and (x_l, y_l+1, z_l)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said third equation group (III) is not satisfied, then the element (x_l, y_l, z_l)'"'"'=A;

the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x_l, y_l, z_l)=B and (x_l, y_l, z_l+1)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said fourth equation group (IV) is not satisfied, then the element (x_l, y_l, z_l)'"'"'=A;

finding the dimensions of the free subspaces determined using said first equation group (I) by updating a dimension table for the rows and for the columns and for the layers of the matrix, and by adjusting the dimension table for the rows or the columns or the layers in a corresponding step during the matrix reduction, each determined free subspace defining a free rectangular parallelepiped portion of said plurality of portions of free space in said space.

17. A method for optimally placing objects in the shape of a rectangular parallelepiped in a space available for storage or transportation of said objects and being possibly, but not necessarily, already partially occupied with objects of said shape, comprising the steps of:

(a) measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of a plurality of said objects;

(b) locating in said space a plurality of portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs);

(c) establishing a score for each of said portions, for each of said objects, for each of six possible orientations in which rectangle sides of said objects are parallel to or aligned with rectangle sides of said rectangular portion of said space, by assigning score values, in respective substeps, corresponding to the following determinations;

(1) whether an object (Xp, Yp, Zp) in a said orientation is too large for fitting in said portion (Xs, Ys, Zs) of said space;

(2) whether all dimensions of said object (Xp, Yp, Zp) are smaller than the corresponding dimensions of said portion (Xs, Ys, Zs) of said free space;

(3) whether one dimension of said portion (Xs, Ys or Zs) of said free space corresponds to one dimension of said object (Xp, Yp or Zp);

(4) whether two dimensions of said portion (Xs, Ys, Zs) of said free space correspond to two dimensions of said object, and

(5) whether three dimensions of said portion (Xs, Ys, Zs) of said free space correspond to three dimensions of said object,

said score being the more favorable as the score value is assigned corresponding to a determination in a substep with a higher number of the above-designated numbers (1,2,3,4 or

     5) of said substeps which produces an affirmative answer;

(d) selecting and placing an object in a free portion of free space and in an orientation for which a most favorable score was established among respective scores for said plurality of said portions and said plurality of objects and said possible orientations, thereby leaving unoccupied a free space portion of the originally available space;

(e) adding to said plurality of said objects a next object, if any, and measuring the dimensions of the rectangle sides (Xp, Yp and Zp) of said next object;

(f) repeating method steps (b) through (e) with the plurality of space portions defined in step (b) henceforth being a plurality of portions of free space remaining after an immediately previous performance of method steps (b) through (e), until either all objects of said plurality are placed in previously free space or else no more objects of said plurality can fit in space left free by the most recent performance of method steps (b) through (e).

18. The method of claim 17, wherein the step (b) of locating in said space a plurality of free portions of free space in the shape of a rectangular parallelepiped having rectangle sides (Xs, Ys and Zs) comprises the following substeps of:

depicting a space essentially having the form of a right parallelepiped and having dimensions X, Y and Z in the form of three-dimensional matrix (x,y,z) having x rows, y columns and z layers, each element of the matrix representing a right parallelepiped in the space and establishing for each element whether the corresponding right parallelepiped in the space is free or occupied,

assigning the corresponding element of the associated matrix a first logic value (A) in the first mentioned case and a second logic value (B) in the case mentioned second, there being a free subspace in the space if a first equation group (I) is satisfied which states (x_l,y_l,z_l)=B and (x_l-1,y_l,z_l)=A and (x_l,y_l-1,z₁)=A and (x_l+1,y_l,z_l)=A and (x_l,y_l+1,z_l)=A and (x_l,y_l,z_l-1)=A and (x_l,y_l,z_l+1)=A for the corresponding element in the matrix;

carrying out a matrix reduction after determining the elements (x_l,y_l,z_l) which satisfy said first equation group (I), by reducing by one the number of rows or the number of columns or the number of layers of the matrix in a predetermined sequence in consecutive steps until a (1,1,1) matrix or a null matrix is left, the possible free subspaces, if any, always being determined after a reduction step with the aid of said first equation group (I);

the number of rows being reduced by determining, for each element (x_l,y_l,z_l) of the matrix, whether a second equation group (II) is satisfied which states (x_l,y_l,z_l)=B and (x_l+1,y_l,z_l)=B, in which case the element (x_l,y_l,z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said second equation group (II) is not satisfied, the element (x_l, y_l, z_l)'"'"'=A;

the number of columns being reduced by determining whether a third equation group (III) is satisfied which states (x.sub. l, y_l, z_l)=B and (x_l, y_l+1, z<sub>;

l</sub>)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said third equation group (III) is not satisfied, then the element (x_l, y_l, z_l)'"'"'=A;

the number of layers being reduced by determining whether a fourth equation group (IV) is satisfied which states (x_l, y_l, z_l)=B and (x_l, y_l, z_l+1)=B, in which case the element (x_l, y_l, z_l)'"'"';

=B in the reduced matrix (x, y, z)'"'"', and if said fourth equation group (IV) is not satisfied, then the element (x_l, y_l, z_l)'"'"'=A;

finding the dimensions of the free subspaces determined using said first equation group (I) by updating a dimension table for the rows and for the columns and for the layers of the matrix, and by adjusting the dimension table for the rows or the columns or the layers in a corresponding step during the matrix reduction, each determined free subspace defining a free rectangular parallelepiped portion of said plurality of portions of free space in said space.