×

An \(n\)-tet graph approach for non-guillotine packings of \(n\)-dimensional boxes into an \(n\)-container. (English) Zbl 1081.90592

Summary: We propose a simple recursive uniform algorithm for the problem of packing \(n\)-dimensional boxes into an \(n\)-container. We are particularly concerned about the special case \(n=3\) where the boxes can be packed in a given subset of their six possible positionings. Our method studies symmetries in the packings by the use of an ordered set of three directed graphs with the same edges (a 3-tet or triad) and induced smaller structures of the same kind named minors. With this method, degeneracy and symmetry issues, which curtail the implicit enumeration to practically acceptable running times, become transparent. In order to illustrate the performance of the algorithm, computational results from solving randomly generated 3-D examples are presented and compared with the ones of a layers and knapsack approach. The present study has real world applications for the problems of pallet and container loading.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI

References:

[1] Abdou, G.; Yang, M., A systematic approach for the three-dimensional palletization problem, International Journal of Production Research, 32, 10, 2381-2394 (1994) · Zbl 0902.90053
[2] Arenales, M.; Morabito, R., An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems, European Journal of Operational Research, 84, 599-617 (1995) · Zbl 0928.90074
[3] Arenales, M.; Morabito, R.; Yanasse, H., Special issue: Cutting and packing problems, Pesquisa Operacional, 19, 2, 109-284 (1999)
[4] Balasubramanian, R., The pallet loading problem: A survey, International Journal of Production Economics, 28, 217-225 (1992)
[5] Beasley, J., An exact two-dimensional non-guillotine tree search procedure, Operations Research, 33, 49-64 (1985) · Zbl 0569.90038
[6] Bischoff, E.; Marriott, M., A comparative evaluation of heuristics for container loading, European Journal of Operational Research, 44, 2, 267-276 (1990) · Zbl 0684.90083
[7] Bischoff, E.; Ratcliff, M., Loading multiple pallets, Journal of the Operational Research Society, 46, 1322-1336 (1995) · Zbl 0858.90106
[8] Bischoff, E.; Waescher, G., Special issue on cutting and packing, European Journal of Operational Research, 84, 3, 503-712 (1995) · Zbl 0904.00026
[9] Bhattacharya, S.; Roy, R.; Bhattacharya, S., An exact depth-first algorithm for the pallet loading problem, European Journal of Operational Research, 110, 610-625 (1998) · Zbl 0946.90057
[10] Bortfeldt, A.; Gehring, H., A tabu search algorithm for weakly heterogeneous container loading problems, OR Spektrum, 20, 4, 237-250 (1998) · Zbl 0917.90116
[11] Chen, C.; Lee, S.; Shen, Q., An analytical model for the container loading problem, European Journal of Operational Research, 80, 1, 68-76 (1995) · Zbl 0927.90087
[12] Chien, C.; Wu, W., A recursive computational procedure for container loading, Computers and Industrial Engineering, 35, 319-322 (1998)
[13] Dowsland, K., An exact algorithm for the pallet loading problem, European Journal of Operational Research, 31, 78-84 (1987) · Zbl 0614.90084
[14] Dowsland, K., Some experiments with simulated annealing techniques for packing problems, European Journal of Operational Research, 68, 389-399 (1993) · Zbl 0800.90729
[15] Dowsland, K.; Dowsland, W., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355
[16] Dowsland, W., Improving palletization efficiency - The theoretical basis and practical applications, International Journal of Production Research, 33, 8, 213-222 (1995)
[17] Dyckhoff, H.; Finke, U., Cutting and Packing in Production and Distribution: Typology and Bibliography (1992), Springer: Springer Heidelberg
[18] Dyckhoff, H.; Scheithauer, G.; Terno, J., Cutting and packing, (Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimisation (1997), Wiley: Wiley New York), 393-414 · Zbl 1068.90509
[19] George, J., A method for solving container packing for a single size of box, Journal of the Operational Research Society, 43, 307-312 (1992) · Zbl 0825.90719
[20] Haessler, R.; Talbot, F., Load planning for shipments of low density products, European Journal of Operational Research, 44, 289-299 (1990) · Zbl 0684.90085
[21] Herbert, A.; Dowsland, K., A family of genetic algorithms for the pallet loading problem, Annals of Operations Research, 63, 415-436 (1996) · Zbl 0851.90096
[22] Herz, J., Recursive computational procedure for two dimensional stock cutting, IBM Journal of Research Development, 16, 462-469 (1972) · Zbl 0265.90057
[23] Lins, L.; Lins, S.; Morabito, R., A 9-fold partition heuristic for packing boxes into a container, Investigacion Operativa, 7, 3, 69-82 (1999)
[24] L. Lins, S. Lins, R. Morabito, An \(nnn\); L. Lins, S. Lins, R. Morabito, An \(nnn\) · Zbl 1081.90592
[25] Liu, T.; Hsiao, C., A three-dimensional pallet loading method for single-size boxes, Journal of the Operational Research Society, 48, 7, 726-735 (1997) · Zbl 0881.90105
[26] Martello, S., Special issue: Knapsack, packing and cutting, Part I: One dimensional knapsack problems, INFOR, 32, 3 (1994)
[27] Martello, S., Special issue: Knapsack, packing and cutting, Part II: Multidimensional knapsack and cutting stock problems, INFOR, 32, 4 (1994) · Zbl 0806.00019
[28] Miyazawa, F. K.; Wakabayashi, Y., An algorithm for the three-dimensional packing problem with asymptotic performance analysis, Algorithmica, 18, 1, 122-144 (1997) · Zbl 0876.68051
[29] Morabito, R.; Arenales, M., An AND/OR-graph approach to the container loading problem, International Transactions in Operations Research, 1, 1, 59-73 (1994) · Zbl 0854.90121
[30] Morabito, R.; Morales, S., A simple and effective recursive procedure for the manufacturer’s pallet loading problem, Journal of the Operational Research Society, 49, 819-828 (1998) · Zbl 1140.90517
[31] Morabito, R.; Morales, S.; Widmer, J., Loading optimization of palletized products on trucks, Transportation Research, Part E, 36, 285-296 (2000)
[32] Nelissen, J., How to use structural constraints to compute an upper bound for the pallet loading problem, European Journal of Operational Research, 84, 662-680 (1995) · Zbl 0928.90079
[33] Scheithauer, G.; Sommerweiss, G., 4-block heuristic for the rectangle packing problem, European Journal of Operational Research, 108, 3, 509-526 (1998) · Zbl 0970.90082
[34] Scheithauer, G.; Terno, J., The G4-heuristic for the pallet loading problem, Journal of the Operational Research Society, 47, 511-522 (1996) · Zbl 0864.90108
[35] SICUP, Special Interest Group on Cutting and Packing. Available from http://www.prodlog.wiwi.uni-halle.de/sicup/; SICUP, Special Interest Group on Cutting and Packing. Available from http://www.prodlog.wiwi.uni-halle.de/sicup/
[36] Sweeney, P.; Paternoster, E., Cutting and packing problems: A categorized, application-oriented research bibliography, Journal of the Operational Research Society, 43, 691-706 (1992) · Zbl 0757.90055
[37] Tsai, R.; Malstrom, E.; Kuo, W., Three dimensional palletization of mixed box sizes, IEE Transactions, 25, 4, 64-75 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.