×

zbMATH — the first resource for mathematics

Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study. (English) Zbl 1061.90094
Summary: We propose two exact algorithms for solving the three-dimensional cutting (3DC) problem. We study the two cases of the unconstrained 3DC problem: (i) only one large pallet is considered, denoted U_ G3DC, and (ii) the general version, denoted U_ G3DC, in which different large pallets are considered. For both cases of the problem, we consider that there is unlimited quantity of each type of pieces to cut, and that all cuts are of guillotine type. We propose a first exact algorithm for the U_ 3DC problem. The algorithm is an adaptation of P. C. Gilmore and R. E. Gomory’s approach Oper. Res. 14, 1045–1074 (1966; Zbl 0173.21502)] initially proposed for solving the unconstrained two-dimensional guillotine cutting problem. We then present a second algorithm for the same problem. This algorithm is mainly based upon a graph search procedure using a depth-first search strategy. This algorithm is a straightforward extension of the two-dimensional guillotine cutting approach proposed in [M. Hifi and V. Zissimopoulos, Eur. J. Oper. Res. 91, No. 3, 553–564 (1996; Zbl 0924.90118)]. We later show how we can extend the dynamic programming based algorithm for exactly solving the U_ G3DC problem. Finally, we undertake an extensive experimental study with a large number of problem instances extracted from the literature and compare the performances of both algorithms.

MSC:
90C27 Combinatorial optimization
Software:
Knapsack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bischoff, E.; Marriott, M., A comparative evaluation of heuristic for container loading, European journal of operational research, 44, 267-276, (1990) · Zbl 0684.90083
[2] Gilmore, P.C.; Gomory, R.E., Multistage cutting problems of two and more dimensions, Operations research, 13, 94-119, (1965) · Zbl 0128.39601
[3] Beasley, J.E., Algorithms for unconstrained two-dimensional guillotine cutting, Journal of the operational research society, 84, 503-505, (1985) · Zbl 0589.90040
[4] Gilmore, P.C.; Gomory, R.E., The theory and computation of knapsack functions, Operations research, 14, 1045-1074, (1966) · Zbl 0173.21502
[5] Herz, J., A recursive computing procedure for two-dimensional stock cutting, IBM journal of research and development, 16, 462-469, (1972) · Zbl 0265.90057
[6] Hifi M. Dynamic programming and hill-climbing techniques for the constrained cutting stock problem. Journal of Combinatorial Optimization 2002; in press. · Zbl 1136.90495
[7] Hifi, M.; Zissimopoulos, V., A recursive exact algorithm for weighted two-dimensional cutting, European journal of operational research, 91, 553-564, (1996) · Zbl 0924.90118
[8] Alvares-ValdĂ©s, R.; Prajon, A.; Tamarit, J.-.M., A tabu search for large-scale (un)constrained two-dimensional cutting problems, Computers and operations research, 29/7, 925-947, (2002) · Zbl 0995.90075
[9] Hifi, M., The DH/KD algorithma hybrid approach for unconstrained two-dimensional cutting problems, European journal of operational research, 97, 41-52, (1997) · Zbl 0929.90073
[10] Morabito, R.; Arenales, M.; Arcaro, V., An and/or graph approach for two-dimensional cutting problems, European journal of operational research, 1, 59-73, (1992) · Zbl 0757.90071
[11] Coffman, E.G.; Gilbert, E.N., Dynamic, first-fit packings in two or more dimensions, Information and control, 61, 1-14, (1984) · Zbl 0591.68074
[12] George, J.; Robinson, D., A heuristic for packing boxes into a container, Computers and operations research, 7, 147-156, (1980)
[13] Haessler, R.; Talbot, F., Load planning for shipments of low density products, European journal of operational research, 44, 289-299, (1990) · Zbl 0684.90085
[14] Hifi M. Approximate algorithms for the container loading problem. International Transactions in Operational Research 2002; in press. · Zbl 1044.90060
[15] Morabito, R.; Arenales, M., An and/or graph approach to the container loading problem, International transactions in operational research, 58, 263-271, (1994)
[16] Movshovich, F.S.; Saksonov, E.L.; Petrov, M.V., Computer aided selection of rational container sizes in automated transport and storage systems, Soviet electrical engineering, USA, 59, 107-110, (1988)
[17] Portmann, M.C., An efficient algorithm for container loading, Methods of operations research, 64, 563-572, (1990)
[18] Prosser P. A hybrid genetic algorithm for pallet loading. In: Proceeding of the Eighth European Conference on Artificial Intelligence. Pitman, London, 1988. p. 159-64.
[19] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations research, 2, 31-44, (1977) · Zbl 0369.90059
[20] Cung, V.-.D.; Hifi, M.; Le Cun, B., Constrained two-dimensional cutting problema best-first branch-and-bound exact algorithm, International transactions in operational research, 7, 185-210, (2000)
[21] Pisinger, D., A minimal algorithm for the 0-1 knapsack problem, Operations research, 45, 758-767, (1997) · Zbl 0902.90126
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.